Agent based simulation modeling

A tag game simulator with simple agents.

Motivation and lessons learned

My first attempt of an agent based simulation model. The agents themselves are purely random in their behavior, which can make this project look incomplete. But the purpose of this exercise was to see if I can even manage to set it up and get it working.

I did this over the weekend and got allot of new experience thanks to it. I got to try out structopt a cli input tool which I absolutely love and can’t recommend enough. I also tried out Rayon for the first time. It was a good experience to fixing structs so that they become “send”. But in the end, rayon didn’t improve the performance of my particular code. It would require further deeper analysis to find out why exactly, but my very simple “benchmark” is bellow. Again, it was rather about the experience than about making the fastest possible multithreaded implementation possible.

The probably biggest experience I got out of this exercise was the use of Rc, RefCell and weak links.

When one agent needs to mutate another (tag) another. How can one object in a Vec change the one next to it. It has been a while since I was using RCs. But you can’t give a normal mutable ref to them, so I just tried it with RCs and thought it should be ok. I encountered a huge block and was totally lost when that didn’t work and I didn’t understand why. After a while, I found an example using weak links. I never used those before, but I gave it a try. I realized why I’m getting the error about the RC being already borrowed. Through the first RC I get to the Agent itself, and then I’m trying again to use the same RC from inside the Agent - that was the issue. This got solved by cloning the agent with its owned link. Thereby dropping the initially established connection. Now I can use the link from inside the cloned Agent. This works, but somehow it it doesn’t feel right. I still remember writing this code and I felt dirty. But the next challenge was right around the corner. When you try to print out sch an agent, it will try to resolve its link to the parent, finding again the same child, resolving it’s link to the parent and so on. With that I got possibly my first stack overflow in Rust. You can imagine my frustration at this point, I was still lost. But fortunately getting back to those weak links and the example in the Book solved this issue. A weak link doesn’t resolve immediately, causing this loop, but needs to be called explicitly. And it should be possible to call it, since it’s called from a clone, who’s link is not used anymore at that moment. This way, any time the link is used, a clone is being made. I still don’t know about a better solution. After this started working, I felt like getting away with murder and somehow still not happy, but at least with hope that I could finish this exercise.

Later when I changed the Rc for Arc, this loop issue solved with weak links became not necessary anymore. Since you have to lock Mutex also explicitly. But well, was still a good experience.

Simulation rules

Movement

All agents move on every tic one space in one of their neighboring directions (up, down, left right) on random. If they cross a wall, they pop out on the other side.

Tagging

At the start, one agent is chosen as “it” on random. If and another agent come next to each other (on one of the four directions) the tag is exchanged. The previously tagged agent becomes impossible to tag again, until another tag is exchanged.

Build

cargo build --release

Run

The most interesting use of this piece of code at this moment, is to see how the amount of exchanged tags can change when changing the options of the world. With the flags bellow, it is very easy to adjust the size of the world, the number of agents and how many moves they make.

  • Either the build result from the previous step.

    cd target/release/
    ./agent-tag
    
  • Or through cargo

    cargo run
    
    • add flags to the cargo format after --

      cargo run -- -h
      

Options

Please see the flags and options bellow. All of them have sensible defaults, so just running the program without any should give you still a reasonable result.

Help text

agent-tag --help
agent-tag 0.1.0
A tag game simulator with stupid agents

USAGE:
    agent-tag [FLAGS] [OPTIONS]

FLAGS:
    -d, --disable-grid      Adding this flag disables the output of the field (grid). For benchmarking, when printing
                            the grid on the cli is not required
    -h, --help              Prints help information
    -p, --print-announce    During a run, announce that in the next visible frame, a tag will occur. Otherwise it is
                            easy to miss it
    -V, --version           Prints version information

OPTIONS:
    -a, --agents <agents>    Number of agents [default: 40]
    -m, --moves <moves>      Number of moves (tics) before the program finishes. Important for benchmarking, otherwise a
                             simple kill ^C works too [default: 10]
    -s, --size <size>        Size of field (grid) [default: 25]
    -t, --time <time>        Number of ms between tics [default: 1000]

Very simple benchmark

Just running time (the common linux tool). This example runs with 10.000 moves. When -t0 is set, there is no thread sleep called between the moves. Toggling the -d flag shows how much time is spent on the graphical aspect of the program.

time target/release/agent-tag -t0 -m10000 -d

Without Rayon:

________________________________________________________
Executed in   19,63 millis    fish           external 
   usr time   19,61 millis  528,00 micros   19,08 millis 
   sys time    0,21 millis  215,00 micros    0,00 millis 

with Rayon:

________________________________________________________
Executed in  155,57 millis    fish           external 
   usr time  1208,72 millis  748,00 micros  1207,97 millis 
   sys time  541,37 millis    0,00 micros  541,37 millis 

The results are surprising. The refactor from Rc to Arc (and giving each agent it’s own RNG) didn’t slow down the run much. But when then used with Rayon, to use more threads for the many agents, the release binary actually ran 4x slower. Even when raising the number of agents from 40 to 400, the binary without Rayon (single threaded) was 4x faster. Sometimes the results can vary allot based on use case and that’s why these tests can be so useful when implementing parallelism. I left the two tested functions commented in the code with “# Raion”

Running just time is not a perfect benchmarking tool, especially for results under a second. But good enough for rough comparisons between different setups I guess.

Radim Janoš
Radim Janoš
Developer

Related