[erlang-questions] write the ant simulation in Erlang?
Brian Zhou
In the talk, lot of time was spent on walking thru the ant simulation code.
Like many of you here, I was not convinced by the STM approach.
Especially seeing the "Santa Claus" solution in Haskell and Erlang
side-by-side.
But I'm having some difficulty thinking about how to use Erlang for
this ant simulation problem.
It was suggested to me in IRC to have a manager process for the world
state, with interface like world:is_food(loc). But how to make sure
certain calls are in a a transaction? e.g. world:is_food(loc) and
world:take_food(loc)? Maybe move what needs to be in a transaction
into world:single_function() ?
Thanks in advance for any idea,
-Brian
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://www.erlang.org/mailman/listinfo/erlang-questions
Brian Zhou
You can see the simulation in action at 131:00 - 132:00.
-Brian
Brian Zhou
* On a world of 80x80 cells, there are 49 ants, and 35 scattered cells
with food.
* Initially the ants are in their home, a square from (20, 20) to (26,
26), facing random directions.
* An ant can move ahead, turn 45 degree left, or 45 degree right, every 40ms.
* Ant should not move ahead if there is another ant in the ahead cell.
* Whenever ant make a move, it leaves a pheromone trail by increment
pheromone amount by 1.0 in the previous cell.
* For an ant without food,
** If ahead is not home, and there is food ahead, move ahead, take
food and turn around;
** Among cells that are ahead, ahead-left (45 degree), ahead-right (45
degree), turn/move to the one with the most (if (contain-food?) 1 0) +
pheromone score, if all equal, turn/move randomly;
* For an ant with food,
** If ahead is home, move ahead, drop food and turn around;
** Among cells that are ahead, ahead-left (45 degree), ahead-right (45
degree), turn/move to the one with the most (if (at-home?) 1 0) +
pheromone score, if all equal, turn/move randomly;
* Every 1 second, the pheromone in all cells evaporate to 99% of the
previous amount;
* If a graphical animation is provided, the animation is refreshed every 100ms.
* Hard-coded numbers are used above to make description easier. They
are actually adjustable.
;dimensions of square world
(def dim 80)
;number of ants = nants-sqrt^2
(def nants-sqrt 7)
;number of places with food
(def food-places 35)
;range of amount of food at a place
(def food-range 100)
;evaporation rate
(def evap-rate 0.99)
(def animation-sleep-ms 100)
(def ant-sleep-ms 40)
(def evap-sleep-ms 1000)
Anyone feel free to correct me if my understanding is not right.
-Brian
On Wed, Oct 8, 2008 at 7:46 PM, Richard O'Keefe <o...@cs.otago.ac.nz> wrote:
> Bearing in mind that it really isn't practical
> for someone in NZ to watch videos over the international net,
> can you tell me what the ant simulation problem is?
Robert Virding
Do you know if it "turn based" or do the all the ants just move after their own clocks in a parallel way?
A first approximation would be to have one process per ant and one for the world. The only problem would be handling atomic look-at-the-immediate-world-around-me-and-make-a-move.
The really difficult bit is displaying it. :-)
Robert
Richard O'Keefe
On 10 Oct 2008, at 10:47 am, Robert Virding wrote:
> A first approximation would be to have one process per ant and one
> for the world. The only problem would be handling atomic look-at-the-
> immediate-world-around-me-and-make-a-move.
Thinking idly about this last night, I wondered whether
the look at the world bit *should* be atomic. Real ants
don't lock the real world, and while an ant is looking at
one square, something _could_ move into a square it can't
see.
I was wondering about dividing the world into patches.
jm
Richard O'Keefe wrote:
> I was wondering about dividing the world into patches.
>
>
create a process for each square and then use a naming convention for
the processes, eg world_x_y where x, y are the co-ordinates of the
square. For an 80 x 80 world this would be 6400 processes just for the
world plus 49 ant processes which I thought might be a bit of an over
kill. I was also concerned that the process name look up may be a bottle
neck.
The API for the square processes might be something along the lines of
* look return the status of the square. Presents of ant, food, etc.
* take move to this tile. Returns success or failure.
The ant would look at the square to see if it was empty and if there was
any food. If the square was chosen as the next location the ant would
attempt to move there by attempting to take the square which could fail
if another ant had taken the square in the interim. In which case it
would look for a new square, otherwise it would up date its own status
to reflect the new location.
Jeff.
Robert Virding
Thinking idly about this last night, I wondered whether
On 10 Oct 2008, at 10:47 am, Robert Virding wrote:
A first approximation would be to have one process per ant and one for the world. The only problem would be handling atomic look-at-the-immediate-world-around-me-and-make-a-move.
the look at the world bit *should* be atomic. Real ants
don't lock the real world, and while an ant is looking at
one square, something _could_ move into a square it can't
see.
This was to get around the problem of checking if a cell was free before moving into and then finding the cell has been taken. The immediate world is one cell left, center, right, so it is very immediate. The "spec" stated only one ant per cell.
Robert
jm
Richard O'Keefe wrote:
>
> On 10 Oct 2008, at 1:51 pm, jm wrote:
>> This was my first reaction when seeing a description of the problem.
sketching out an idea between doing some work. There are obviously some
problems with the approach taken, but I think using a process per square
(cell) or a subset of squares (patch) is a more natural approach for
erlang. As this approach mantains the atomic nature of the squares and
scales more easily as the cores/processes grow.
> First, I was originally talking about dividing the world
> up into *patches*, not *cells*. In an 80x80 world,
> patches might be 10x10, which is only 64 patches.
>
> Second, why on earth would you *name* the patch processes?
Just a simple way to find the correct process in a first cut and easier
to see what is going on. You could also prime each ant with knowledge of
which processes represent each square(s) or each patch/cell could
contain this knowledge which is what I think your thinking.
>
> startup() ->
> create an 80 x 80 array of processes
> all running cell/0 using spawn_link
> set up all the neighbour links
> send each cell a !go message
>
> Moving is a little tricky because we need to change the
> state of two cells (if doing cells) or possibly two
> patches (if doing patches).
Can you live with an ant occupying two squares at once? Then enter the
new location first before leaving the old location.
Richard O'Keefe
On 10 Oct 2008, at 1:57 pm, Robert Virding wrote:
> This was to get around the problem of checking if a cell was free
> before moving into and then finding the cell has been taken.
That was understood.
> The immediate world is one cell left, center, right, so it is very
> immediate. The "spec" stated only one ant per cell.
It *happened* to be very immediate.
What about a protocol like this:
check each relevant square
choose where to go
ask the world to move you
if it refuses, try again with locking.
The old "locks are usually not contended" idea.
I think one process per cell of the world may make sense.
Richard O'Keefe
On 10 Oct 2008, at 1:51 pm, jm wrote:
> To
> create a process for each square and then use a naming convention for
> the processes, eg world_x_y where x, y are the co-ordinates of the
> square. For an 80 x 80 world this would be 6400 processes just for the
> world plus 49 ant processes which I thought might be a bit of an over
> kill. I was also concerned that the process name look up may be a
> bottle
> neck.
First, I was originally talking about dividing the world
up into *patches*, not *cells*. In an 80x80 world,
patches might be 10x10, which is only 64 patches.
Second, why on earth would you *name* the patch processes?
Let's now switch to cell processes, not patch processes.
A cell needs to know its neighbours.
element_number(nw) -> 1;
element_number(n) -> 2;
element_number(ne) -> 3;
element_number(e) -> 4;
element_number(se) -> 5;
element_number(s) -> 6;
element_number(sw) -> 7;
element_number(w) -> 8.
cell() ->
cell_start({0,0,0,0,0,0,0,0}).
cell_start(Neighbours) ->
receive
go -> cell_loop(Neighbours, 0, 0, no_ant)
; {D,N} -> cell_start(setelement(
element_number(D), Neighbours, N))
end.
cell_loop(Neighbours, Pheromone, Food, Ant) ->
....
startup() ->
create an 80 x 80 array of processes
all running cell/0 using spawn_link
set up all the neighbour links
send each cell a !go message
Something along those lines.
Processes normally shouldn't *have* names, and in
this problem there certainly doesn't seem to be any
reason for any process to have a name, so
process name lookup can't be a bottleneck.
Moving is a little tricky because we need to change the
state of two cells (if doing cells) or possibly two
patches (if doing patches).
_______________________________________________
Roger Critchlow
> Moving is a little tricky because we need to change theCan you live with an ant occupying two squares at once? Then enter the
> state of two cells (if doing cells) or possibly two
> patches (if doing patches).
new location first before leaving the old location.
It would also break the graphical display of the simulation if the number of ants fluctuated from frame to frame.
-- rec --
jm
>
> That would break the transactional consistency that the example has in
> Clojure: You have a thing you want to move from one place to another,
> you don't want it to be in both places, and you don't want it to be no
> place.
>
> It would also break the graphical display of the simulation if the
> number of ants fluctuated from frame to frame.
>
to ants)? Just thinking aloud, how about one of empty, moving, and
occupied? No, that doesn't work either. How about asking the current
square to move the ant to the next square? I don't think this works
either though.
There must be something wrong with the way I'm looking at this.
Oh well, back to the day job.
Brian Zhou
> I haven't really checked the Clojure code that closely but it seems like a
> reasonable problem.
>
> Do you know if it "turn based" or do the all the ants just move after their
> own clocks in a parallel way?
their own clock.
>
> A first approximation would be to have one process per ant and one for the
> world. The only problem would be handling atomic
> look-at-the-immediate-world-around-me-and-make-a-move.
>
Strictly speaking, the world state should be version'ed, the world
process should reject the move if the world has changed since the ant
looked, the ant process then should retry
look-decide-and-request-move. As an optimization, I guess the world
process can just check whether the FPA (food, pheromone, ant) value of
the target cell has changed.
I wrote a rough first cut based on the above idea:
http://pastebin.ca/1224362 - It's not completed yet, TODO:
1. pheromone evaporation
2. initialization of the world, spawn world process, spawn ant processes
3. scoring candidate cells
Am I on the right track?
> The really difficult bit is displaying it. :-)
>
I'm not there yet.
Thanks,
-Brian
Roger Critchlow
Versioning of world state would need to restrict itself to the part of the world that the ant looked at, forcing a retry any time any part of the world had changed would be excessive.
And I think that only moves resulting in ant-ant collisions need to be rejected -- that the rewards of moving might change between the time we make the decision and the time we enact the decision is unfortunate, but all too real. The clojure ants are making decisions based on a snapshot, too, and only retrying on collisions.
Capturing the snapshot for display should be simple, just return the world_loop State.
-- rec --
Daniel Goertzen
Dan.
Rick R
How about 1 process for each cell, but no processes for the ants. The ants exist as state inside each cell and as messages interrogating neighboring cells. I think you'll get nice fine-grained localized transactions this way.
Dan.
Using that method, I think you'll still have the same issue with transactions. For instance: if two cells decide to move their ant to the same adjacent cell, you will have the same conflict and one ant will have to be rolled back.
It may not even be more efficient message-wise because instead of the ant sending a message to an adjacent cell, the cell simply sends the same message to the adjacent cell on behalf of the ant.
Of course we could go existentialist and say that there is no board except what the ants perceive, and since they can only see one square in any direction, that would imply that there is 1 process for each ant and no process for a board (or any data for that matter). This would mean that if there are no ants on a section of board it would cease to exist. The only way to reconstitute it would be to mathematically prove that it exists. e.g. The ant was at 5,5 and moved 3 east, 8 < 64, therefore, the board exists.
One could extend this method with a Paxos algorithm so that the ants could achieve consensus as to the existence of Board.
David Mercer
Actually Danny G’s approach has merit. Ant on square A wants to move to square B. The messages passed are quite simple:
- A: B ! {A, 'I have an ant who wants to move to you'}
- B: Either:
- A ! 'Your ant moved here successfully'
- A ! 'No can do, mate; I’m already occupied'
In the case of 2a, square A marks itself vacant and can now respond with its own 'Your ant moved here successfully' message when another square requests passage for its ant. In case of 2b, square A tries another square.
DBM
Rick R
Better than decreasing the amount of messages, it avoids having to transact (or resolve conflicts) at all.
The cell can have three states, empty, full, or pending. Pending would be that it is waiting for a response from an adjacent cell on whether it's ant can move there. It would simply delay any of its own responses until receiving a response from it's suitor.
One could argue for a fourth state which is empty-but-expecting. But if an ant is guaranteed to travel to your location once you've agreed to let it, then this state is as good as full.
Not treating the ant as its own actor does take the fun (and the expense) out it.
"Have more than thou showest,
Speak less than thou knowest,
Lend less than thou owest,
Ride more than thou goest."
-- The Fool to King Lear