## Work with Mark: Bottom-up Approach

2006-09-18 12:57

After some time Mark d'Inverno and I shifted focus and decided to simplify our ideas. We agreed to work more from a bottom-up approach - letting the agents live within a grid world and visualise their behaviours. Other people have been doing quite some work in this area before, but not particularly many of them have been incorporating sound and music. So we had literature and examples to study and people to ask. It was of great help and I learned a lot about designing multi-agent systems from analysing, for example, Jon McCormack's nice Eden.

So starting out writing our own system, I did a set of classes for handling agents running around in a grid world of 1-3 dimensions. All agents were very simple-minded. They were visually represented with just dots and oh, they could bleep too.

Setting up simple scenarios for these classes helped to pinpoint different system models. It also showed my biggest problems coding this usually boiled down to in which order to do things. The model I tried in turn to 'model' was suggested by Rob Saunders in an article called 'Smash, bam and cell', in were all agents first sense their surroundings and then act. But I constantly had to restructure the code and design. This was harder than I had thought and I think I never came up with an all-around solution.

One example scenario we came up with was the runaway test. It is very simple but can help trying out different designs. It works something like this... Imagine a grid world of say 2 dimensions (we also coded this in 1 and 3D). Agents move about at random speed and direction. If an agent encounters another one blocking its next step, it turns around 180 degrees and flees i.e. moving away in the opposite direction. So far the sense/act cycle is simple: for every update (world tick) it first sense, then acts. But what happens if there's another agent blocking the escape route? So the agents really need to first sense, then if something is ahead, act and turn around 180, sense again and decide if it is possible to flee. Here it'll sense within the act method and that clutters the design. The better solution would probably be to let the agent just turn 180 and wait to flee until the next tick. But perhaps it could also sense behind itself in the first sense round and pause if both escape routes are blocked. There are many possible solutions and creating these small test scenarios helped me to generalise my classes. We also tried the classes by coding the test scenarios as discrete and continuous i.e. if the world was a rigid grid in which the agents only were allowed to move stepwise, or if the world allowed them to move about more smoothly in non-integer directions and speeds.

The SuperCollider code for version 4, including test scenarios and small examples is attached at the bottom of this post and below is some text trying to describe the classes in more detail.

Also, see these QuickTime movies of some test scenarios...

• one-dimensional continuous world
• two-dimensional continuous world
• one-dimensional discrete world
• one-dimensional discrete world
• one-dimensional discrete world
• one-dimensional discrete world
• two-dimensional discrete world

## A4 description

There are 3 basic classes. `ALocation`, `AWorld` and `AnItem`. I first describe them and their immediate subclasses. Then `AnAgent`, `AProxyAgent` and some subclasses of `AWorld`. Then I explain a few of the classes used in the test/example programs. Last I write a little about the main loop.

May look at the files A4.sc and A4subs.sc for completion.

### `ALocation`

#### BASICS:

A place within a world.

`.new` takes 2 arguments: world and list

Instance variable `world` is any (sub)class of `AWorld`. Can be `get` (i.e. accessed from outside).

Instance variable `list` is a list of coordinates. Can be `get` and `set`. Example: `[10]` for x=10 in an 1 dimensional world. `[10, 20, 30]` for x, y, z in a 3D world. The length of the list must correspond to the number of dimensions in the world.

Locations can be compared with the `==` method. It takes another location as an argument. A location is equal to another if they exist in the same world and have the same list of coordinates.

The `!=` method is the negation of `==`.

Distance between 2 locations can be found with the `distance` method. It'll return the shortest distance between locations in any dimension.

With the `at` method, one can query single dimensions. E.g. in a 2D world, `location.at(0)` will return which column and `location.at(1)` will return row. The argument is really just index in list above.

The `surroundingLocations` method. With the arguments exclude(boolean) and area(int) this returns a list of new location objects. This is used for collecting locations to be searched for neighbours. If exclude argument flag is false, this (i.e. the current) location will be counted and included in the list. The locations returned are all positioned next to this location in a cube-like way, covering an area of size: area steps away. To put it in another way: with an area of 1, only directly adjacent locations are returned. An area of 2 gives adjacent and their adjacent locations (as a set of `ALocation` objects) and so on.

So in a 1D world a location at (0) sent the message `.surroundingLocations(false, 1)` will give us `[loc[-1], loc[0], loc[1]]`. And likewise in a 2D world a location at (4, 5) sent the message `.surroundingLocations(false, 1)` will return `[loc[3, 4], loc[3, 5], loc[3, 6], loc[4, 4], loc[4, 5], loc[4, 6], loc[5, 4], loc[5, 5], loc[5, 6]]`. Here's the code that resembles this: `ALocation(AWorld(2, 10), [4, 5]).surroundingLocations(false, 1)`. Last example: a location within a 3D world asked to return its surroundings with an area of 3 like this: `ALocation(AWorld(3, 100), [40, 50]).surroundingLocations(false, 3).size` will return a list of 343 unique locations.

#### DETAILS:

When a location object is created it check its world's size and wrap around borders (by doing modulo(size) on the coordinates in the list).

The location class expects the world to be of uniform size in all dimensions.

• 050712 - `distance` might need to go in a subclass if we do networked worlds - Rob's comment. How to calculate the distance between worlds?
• 050712 - At Rob's suggestion: I'll try to rewrite this and the world classes using hashtable lookup. The matrix/location duality causes trouble keeping the same thing at two places.
• 050712 - Naming needs to be improved. Specially `AQLocation` - what to call it?
• 050726 - Removed the `maxDimension` and `surroundMaxArea` limitations and its class variable
• 050726 - Now hashtable lookup + C primitives. Quite a lot faster overall and easier to keep things at the same place.

#### SUBCLASSES:

• `AQLocation` - a quantified location. The coordinates for this class can be floting point but when it places itself in the matrix it rounds of to nearest integer.

### `AWorld`

#### BASICS:

A placeholder for items. Superclass for `APattern`, `AGrid`, `ACube`, `BugWorld` etc.

.new takes 3 arguments: dimensions, size and location

Instance variable `dimensions` is an integer specifying the number of dimensions for this world. Can be `get`.

Instance variable `size` will decide the size of 1 dimension. The world is then created with a uniform size in all dimensions. Can be `get`.

Instance variable `location` if defined, will place the world at a location. If left out - no parent. Can be `get`.

The `clear` method takes a location object as an argument and puts `nil` there.

With the `remove` method - argument: an item - you remove an item from this world.

With `put` you place an item in this world. Argument: item

The `get` method returns whatever item(s) is in a location. Argument: location

Method `items` returns a list of all items in this world.

`neighbours` - arguments: item, exclude and area. Returns a list of any items within an item's area (1=adjcent locations) including or excluding the item's own location. If no items nearby then empty list.

`neighboursSparse` is similar to `neighbours` above (same arguments and function) but uses a different algorithm for finding nearby items. Where `neighbours` calculates locations around the item in question and then check these locations for any items, this method might be quicker in a sparse world. It looks through all items in the world and checks if they're nearby.

Running the `update` method goes through all items in this world, copies them to their own locations. This is to make sure all item's locations and the hashtable stays in sync.

`save` will write this world, its current settings and all its items and their settings to disk. This allows for backup of longrunning tasks or 'presets' to be loaded.

#### SUBCLASSES:

• `AWorld2` - `remove` and `put` methods are modified to allow for multiple items at the same location. `AWorld` can only do one item in once location. Hopefully, I can merge the two classes later.
• `ASmartWorld` - is a world that can resolve location conflicts. There's a `resolve` method to be called after the `sense` cycle but before `act`. This goes through all items and if more than one intends to move to the same location, only let one move - others stay put and their request is ignored. (Comment: need to find a better name than `ASmartWorld`)
• And many other subclasses. E.g. `BugWorld`, `APattern`, `AGrid`, `ACube`. Almost every test program has its own specialised class inheriting from these two subclasses.

### `AnItem`

#### BASICS:

The lowest level thing that exists in a world. Abstract superclass class for `ARock`, `AMoss`, `AnAgent`

`.new` takes 1 argument: location

The method `remove` will remove this item from its world.

#### DETAILS:

The abstract `init` method is used by some subclasses for initialisation.

• 050726 - is `remove` needed? Will the agent remove itself or will the world handle that eg if energy=0.

#### SUBCLASSES:

• `ARock` - does nothing different. Just exists at a location
• `AMoss` - has an energy that can be `get`/`set`.
• `AnAgent` - is an abstract class. See below

### `AnAgent`

Subclass of `AnItem` but is also an abstract class.

Makes sure the `sense` and `act` methods are there for all agents to follow.

#### SUBCLASSES:

• Many. E.g. `ACell`, `ARunaway`, `ABounce`, `Bug`. Every test program has its own specialised class inheriting from this one. They all do `sense` and `act` in their own way.

### `AProxyAgent`

Subclass of `AnAgent`. It allows replacing the `sense` and `act` methods while running.

#### DETAILS:

When asked to sense and act, sense and act in this class will instead evaluate functions stored in the 2 class variables `senseFunc` and `actFunc`. These can be replaced and coded on the fly! So while the system is running, we can try out, completely rewrite or just slightly modify, behaviour for all agents. Their state is kept (individually) but behaviour changes.

• This is unique to other frameworks I've seen so far. I'd like to explore more and hopefully, we can use it in practice too - not just as a convenience for developing. With this feature, it's easy to replace the rules on the fly.
• Perhaps I redesign the whole framework to use proxies. So the `AnItem` class is really a placeholder (proxy) for anything. Then one can code whole agents with state and behaviour while running I think. And maybe proxy worlds too but I can't find a reason for that now.

### `APattern`

#### BASICS:

A subclass of `AWorld` with 1 dimension.

### `AGrid`

#### BASICS:

A subclass of `AWorld` that has 2 dimensions.

### `ACube`

#### BASICS:

A subclass of `AWorld` that has 3 dimensions.

### `ACell`

used in A4_test1_cellautomata.scd

#### BASICS:

Subclass of `AnAgent`. It doesn't move and is used for cellular automata and game-of-life.

Instance variable `value` can be 0 or 1. Can be `get`/`set`.

There's also a `rules` class variable that contains a dictionary for rule lookup.

The `sense` method here collects and stores values from nearby neighbours (by asking the world for neighbours) including the cell's own value.

The `act` method set the cell's own value to what is returned from the rules dictionary.

### `ALifeCell`

used in A4_test2_gameoflife.scd

#### BASICS:

Subclass of `ACell`. Just implements different `sense` and `act` methods.

The `sense` method here is the same as `ACell.sense` but excludes the cell's own value.

`act` will first calculate the total sum of all neighbour's values and then do a lookup in the rules dictionary. The cell's own values is set to 0 or 1 depending on what the dictionary returns.

### `ARunaway`

used in A4_test3_runaway1D.scd, A4_test4_runaway2D.scd and A4_test8_runaway3D.scd

#### BASICS:

A subclass of `AnAgent` that sense if something at next location and if so, bleep, turn around 90 and flee.

Instance variable `direction` is a list of directions in any dimension. In a 2D world: `[0, 0]` stand still, `[-1, 0]` go west, `[1, 1]` go northeast and so on. Can be `get`/`set`.

Instance variable `freq` decides which bleep frequency to play.

The `sense` method updates the 2 private `nextLocation` and `nextPos` instance variables to figure out where to go and if that location is taken.

Helper method `clearAhead` returns true if there's nothing in `nextPos`

`getNextLocation` returns a new location object at here + directionlist.

`getNewDirection` method turns directionlist around 90 degrees.

The `move` method sets this location to `nextLocation`

The `play` method will beep at a frequency. And pan the sound left/right depending on location.

### `ABounce`

1D - used in A4_test6_bounce1D.scd

#### BASICS:

Subclass of `ARunaway`. Implements `getNextLocation` and `getNewDirection` differently so that the agents bounce of each other rather than turn 90 degrees.

`direction` is here a vector of angle and degree.

#### SUBCLASSES:

• `ABounce2D` and `ABounce3D` for vector math in other dimensions.

The main loop of the program is usually very simple. For the CellularAutomaton and GameOfLife examples it just draws a rectangle if the cell's value is 1, then call `.sense` on all agents and last call `.act` for all agents.

``````while {true}, {
agents.do{|a| if(a.value==1, {a.paintRect})}
agents.do{|a| a.sense};
agents.do{|a| a.act};
}
``````

Agents that move around (i.e. all other examples) need to resolve conflicts and update the world. Also they always draw themselves.

``````while {true}, {
agents.do{|a| a.paintRect}
agents.do{|a| a.sense};
world.resolve;
agents.do{|a| a.act};
world.update;
}
``````