Simon GAY

Multi-Agent System

Resources:

Project report (fr): SMA.pdf

Executable .jar: SMA3.jar

Source code : SMA3.7z

Description :

This simulator is a project I developed during my third year. It illustrates the principle of multi-agent systems, principally how a complex collective behavior can emerge from a group of simple agents. In this simulator, three types of resources (red, green and blue), are randomly allocated on a grid. the agents move randomly on this grid, observing these simple rules:

-an agent can take a resource with a probability inversely proportional to the number of resources of a same type around the agent.
-an agent can pose a resource on an empty cell with a probability proportional to the number of resources of a same type around the agent.

These two rules have for consequences the progressive regrouping of each type of resource. Indeed, the isolated resources have a high probability of being taken, and a high probability to be posed on a group of resources.

sma1a — Before/After: The resources are grouped by a team of 50 agents.

sma1b — Before/After: The resources are grouped by a team of 50 agents.

The subject of the project involved the use of "pheromones" to improve the system. Inspired by ant colonies, the first version of this mechanism allowed the agents to set traces on the environment. These traces modified the movements of the agents that approach them to make them following the path. Unfortunately, this mechanism did not improve the system. Sometime resources needed long time to be grouped. The explanation is that, unlike ants, agents do not have a start point and a end point. Thus, path can be created between two heaps of resources, but as exchanges are bidirectional, the size of these heaps stay constant. An other problem can appear if an agent make a loop: it can then stay trapped of its own path, that became a trap for other agents that approach it.

sma2a — Left: the environment. Right: traces set by "pheromones". Some agents are trapped by their own paths (red rectangle)

sma2b — Left: the environment. Right: traces set by "pheromones". Some agents are trapped by their own paths (red rectangle)

I then developed a second version equipped with a new mechanism based on this principle: when a agent poses a resource, it set traces on n steps after the pose. Only agent that search a resource are attracted by these paths. As the length of the path is constant regardless of the size of the heap, little heaps will be attractive on large surfaces, but stay weakly attractive for agent that carry a resource. This mechanism reduces by 4 the number of steps required to have resources regrouped in three heaps.

sma3a — The new mechanism: the little red heaps on bottom-left corner is very attractive for its size. It will be absorbed some hundred steps later.

sma3b — The new mechanism: the little red heaps on bottom-left corner is very attractive for its size. It will be absorbed some hundred steps later.

A last functionality was added: a point of attraction. This point attracts agents that pass in its attraction field. It results a formation of heaps around the point. In the final version of the project, it is possible to set the position of the point, its strength and its range.

sma4a — Grouping around the point of attraction (yellow disc in right panel).

sma4c — Grouping around the point of attraction (yellow disc in right panel).

Software description:

The final version of the system uses a graphic interface that allow the user to control the simulation and modify some parameters during the run. This interface is composed of four parts:

-The Superior panel: it allows to set the initial parameters of the simulation,
It is composed of the initialization panel, that define the size of the environment, the number of agents and of resources.

The panel of probability allows modifying the probability for an agent to take or pose a resource.

The launch panel initialize the simulation. The turbo button can run the specified number of cycle at hight speed (there are, however, no display update nor the possibility to change setting during the run).

-the central panel display, in the left part, the environment with agent and resources, and in the right part, pheromones, attraction point and last movements of agents.

-The inferior panel allows the user to control the simulation run and modify some parameters.
It is composed of the management panel that display the number of agents and resources, and to add or remove agents or resources. (Attention: remove an agent that carry a resource also remove the resource).

The control panel gives control of the simulation: run, stop, step by step, and speed (delay between two steps).

The LightPoint panel sets parameters of the light point: position, range and attraction strength.

-The histogram, in an other window, display the delay between two pick up, two poses, carry and empty delay of the last agent of the list. The panel display these delay with bar graphs. Scale is a line for 100 steps.