Shapebugs

CREDITS

Matt Baker

WHAT IS IT?

This is an implementation of the Shapebugs algorithm from

• Jimming Cheng, Winston Cheng, and Radhika Nagpal. Robust and Self-Repairing Formation Control for Swarms of Mobile Agents. In Proceedings of the Twentieth National Conference on Artificial Intelligence, p. 59--64, AAAI Press. 2005.

My program begins (via the setup button) by randomly dispersing the agents throughout the display. All agents start in the lost state and assume that they are outside of the desired shape. An agent inside the shape is assumed to have been found.

Each agent's movement is as follows:

• If a neighbor reaches a minimum distance the agent repels that neighbor
• If an agent finds itself inside of the desired shape, it will follow the above rules as long as such movement does not take it outside of the shape.
• If an agent is inside of the shape, and it determines that its next move will take it outside of the shape, it will instead do one of 2 things:
• Stay still: 90% probability
• Move either slightly to the right, left, up, or down: 10% probability

Agent colors:
* A red agent is an agent outside of the desired shape * A blue agent is an agent inside of the desired shape * A green agent is an agent that has been displaced

Agents can be added or removed dynamically via the slider. The shake button chooses a random square from the screen and moves all agents within that square in random directions away from their starting positions.

Note: I found that using 1,000+ agents seems to work best for modeling the shape.

CHANGES

20100623