Pack Attack

So I was browsing the Rhinocommon SDK help file one day at work and I stumbled on to the RTree class. I'm not sure how I hadn't noticed it before since it's intuitively nestled next to a handful of other classes I use on a regular basis.

Like other spatial tree data structures, this not-so-hidden gem is used to optimize spatial queries by quickly ruling out large portions of the search space. More importantly, the Rhinocommon implementation is flexible and super straightforward to use. Simply insert objects into the tree, search the tree with a callback method of your choice, and go spend the several hundred milliseconds you just saved with your loved ones. Here's an example in Grasshopper where it's used to speed up the removal of duplicate points. If you turn on the profiler widget you'll see how it stacks up against a brute force approach.

Anyways, this discovery led to several adaptive packing experiments shown below. Here the RTree class is being used to manage collisions among a dynamic population of spheres which are attracted to an input surface (nurbs in the first video implicit in the second two). A new sphere is added to the population if the average pressure felt by the existing spheres falls below a given threshold. Similarly if the average pressure exceeds a second higher threshold a sphere is removed. The RTree callback method used deals with both the calculation/application of repulsion forces and the recording of pressures across the system.

Surface Packing from Davideo Reeves on Vimeo.

Implicit Packing from Davideo Reeves on Vimeo.

Medial Packing from Davideo Reeves on Vimeo.

In each case, the result is a near uniform distribution of spheres across the given surface. While you could run the same process without the use of a spatial tree, things could get out of hand pretty quickly since the algorithm is essentially modifying its own input size each iteration. The RTree just ensures that the execution time scales more reasonably in proportion to this input size - preventing the whole thing from going up in smoke.


Platforms: Rhino, Grasshopper, C#

Stigmergic Particles

I've been getting a few questions on some recent work with indirect particle interaction so I figured I'd try to address them all in one fell swoop via blog post. Here goes.

Typically interactions among a population of particles occur directly. Particles refer to each other's properties (position, velocity, acceleration etc.) in order to build the forces which define their behaviour.

In both examples below, particles aren't particularly concerned with each other. Rather they look to a shared environment in deciding how to act. This environment takes the form of a 2d scalar field where values represent concentration of a diffusing communication medium or "pheromone". Particles build forces by locally sampling this field relative to their own positions. Depending on how they go about reading their environment, different collective patterns emerge over time. In fact this is the only significant difference between the following two systems.

Stigmergic Particles from Davideo Reeves on Vimeo.

In the first example, each particle samples the scalar field at regularly spaced points on a circle centered at its position. A force vector is calculated by summing the gradient vectors found at each sample point before being applied to the particle determining it's future position. The radius of the sample circle is being changed throughout the video causing the system to shift between a range of patterns.

chemorepulsion from Davideo Reeves on Vimeo.

The particles in the second example are less thorough in how they read the field. They only cast two sample points in front of themselves - one to the left and one to the right. The forward biasing of these points results in a completely different family of patterns than seen in the first example. More information on the inner workings of this system can be found here.

Particles can't successfully interact through a read-only environment however. Not much can happen if everyone is listening and no one is talking. In order to close the communicative feedback loop, particles must also write to their shared environment. This occurs through pheromone deposition whereby particles modify local values of the scalar field by either pulling them towards a target value or adding/removing a constant. Diffusion then helps these modifications propagate through the environment so others can take notice.

With both read and write mechanisms in place, particles are able to detect and react to each other's signals producing a variety of emergent patterns. Here the goal is simply the production of visual complexity. As mentioned in previous posts, however, I've been busy applying similar principles of indirect interaction among a population of autonomous entities to solving architectural design problems - specifically those relating to programmatic organization.

Platforms: Java, Processing

Smart Geometry

Just a quick (and tardy) post showing some output from the Volatile Territories cluster at Smart Geometry 2013. Below is a look at the multi-agent space adjacency software sorting out a (much simplified) brief for a mixed-use high rise. Agents were restricted to a predefined building envelope with the core, front lobby, and roof garden being fixed from the get go.

Volatile Territories 02 from Davideo Reeves on Vimeo.

In cases where the brief becomes sufficiently complex like the one above real-time user interaction starts to play a key role in getting the system to settle properly. By temporarily reducing the floor area that each programmatic element is trying to occupy, agents contract providing the necessary wiggle room for less satisfied members of the population to explore other neighborhoods. Hopefully I'll be able to integrate this conditional contraction into the agent behavior itself with a bit more tinkering.

Also I'm happy to say we were able to 3d print with all the colours of the wind. Hats off to the Bartlett. Have a look below.

Volatile Territories

Over the past couple months I've been gearing up for Smart Geometry 2013 which is taking place at the Bartlett/UCL in a little over a week. I'll be running a cluster this year alongside Bruce Davison and Elizabeth Tweedale entitled Volatile Territories. Here's a brief description straight from the cluster page:

"Volatile Territories will explore speculative urban design solutions through the self-organization of spatial boundaries within a set of hypothetical, yet measurable, political, economic and technological constructs."

Most of the preparatory work has revolved around establishing a line of communication between a few different software platforms that we'll be providing. Those who've been following along with the last few posts may have already guessed that one of those platforms is an expansion of my recent thesis work on multi-agent space planning. Here's a look at the tool in its current state.

Volatile Territories 01 from Davideo Reeves on Vimeo.

Below are some screen grabs of an output test in Rhino which we'll be using as a handy middle man of sorts. Importing is handled through Grasshopper which spits out the floor space belonging to each agent and an isosurface defining their respective territories. The latter proved to a be a but of a tricky endeavor since the marching cubes algorithm had to be generalized to handle any number of spatial regions rather than just inside or outside a single threshold. Hopefully it won't have been in vain and we'll be able to do some colour 3d prints during the workshop.

Platforms: Java, Processing, C#, Grasshopper, Rhino

Pheromone Targets

In the previous post I went over some recent work on a multi-agent approach to space planning. I mentioned "pheromone targets" as the basis for agent decision-making without going into much detail on what a pheromone actually is so I figured I'd follow up with a bit of necessary unpacking.

In the context of this model, pheromone concentration refers to a three dimensional rgb value held by each node in the network. This value is under constant modification as nodes participate in ongoing pheromone diffusion by pulling their own concentration towards that of their immediate neighbors. Through diffusion, pheromones propagate through space acting as a communication medium amongst a population of agents.

Similarly, a pheromone target is a three dimensional rgb value held by each agent that informs which node an agent decides to occupy or release at each step. If an agent hasn't reached its spatial quota, it evaluates all unoccupied nodes that lie adjacent to its current territory by comparing their pheromone concentration to its own pheromone target. The node with smallest deviation is then chosen. If an agent already has enough nodes, it evaluates each node it has accumulated in the same way before releasing the one with the largest pheromone deviation.

Pheromone targets also determine how an agent goes about modifying its local environment. Each agent pulls the pheromone concentration of all owned nodes towards its pheromone target, essentially "painting" its portion of the node network with its preferred colour. Through diffusion, other agents within the system are able to sense these changes - encouraging compatible ones (those with similar targets) to occupy space next door and the incompatible ones to settle elsewhere. To give a better sense of compatibility within an agent population, their pheromone targets can be plotted in rgb space as seen above.

Below is a look at two distinct families of agents in action. One family has pheromone targets in the cyan range while the other prefers concentrations in the magenta range. Adjacencies form within each family but the two remain distinctly separate, occupying opposite corners of the bounding volume.

pheromone_space_02 from Davideo Reeves on Vimeo.

The next video introduces pheromone sources as a means of templating external influences. Nodes along opposite faces of the bounding volume pull their own pheromone concentration towards white and black respectively. The gradient produced could represent the transition from public to private as imposed by a hypothetical context for example.

pheromone_space_03 from Davideo Reeves on Vimeo.

The final video below elaborates further on this idea of templating external influences by removing certain nodes from the network through volumetric masking. Agents are thus constrained to a subset of the total volume as they develop their territories.

pheromone_space_04 from Davideo Reeves on Vimeo.

Platforms: Eclipse, Processing

Thecal Matter

The last few months I've been more than a bit preoccupied with thesis work so the blog has suffered from some serious neglect. I'm sorry blog. Having defended last week though, I'm ready to get back in the swing of things and what better way to start than posting some of the fruits of my labour. Ripeness not guaranteed.

In short, my work centered on the development of bottom-up space planning software - borrowing mechanisms of self-organization from ants, termites, slime moulds and other social organisms to solve spatial adjacencies amongst elements of a given programmatic brief. The model treats each programmatic element as an autonomous agent whose goal is to territorialize some portion of a shared three dimensional node network. Agents communicate indirectly through the modification of this mutual environment via virtual "pheromones". Each agent both pursues and emits a specific pheromone concentration or "target" in its occupation of space. As such, agents with similar targets congregate while those with disparate targets avoid each other as they expand and refine their respective territories.

pheromone_space_01 from Davideo Reeves on Vimeo.

In due time, adjacencies between compatible programs self-organize producing an informed schematic design solution. The trick lies in defining compatibility ie. determining the appropriate pheromone target of each element in the programmatic brief. For now I've left this up to manual input - targets can be changed in real time if space is settling in undesirable ways. Moving forward however, I'd be interested in giving the agents the ability to refine their own targets if they find themselves in uncomfortable configurations.

In any case, spatial organization becomes the emergent product of a competitive ecology - agents negotiate with one another, carving out their own niches within a finite volume. The task of space planning, one that is typically carried out by a singular high-level decision-maker (aka the architect), is handed off to the distributed decision-making of low-level collective intelligence - a common approach to solving problems that exceed a certain level of complexity. Much like the slime mould mentioned a few posts back, the individuals of this collective brain are quite stupid - following only the simplest of rules - yet the result of their collective efforts can be remarkably clever.

Platforms: Eclipse, Processing