Multi-Agent Systems: The \"Eco Problem Solving\" Method

Multi-Agent Systems (MAS) were inspired by observing the social behaviors of insect colonies. Ant and bee colonies exhibit collective intelligence and distributed intelligence.

Reproducing or extending these observed behaviors is possible by simulating them with a computer, which effectively creates a Multi-Agent System, defined by the environment and the agents that operate within it.

There are countless applications that benefit from these systems. The agent takes a different form depending on the domain: a cell in biology, a robot in robotics, a human in sociology, a node in networking, a character in a video game, a vehicle in a transportation network...

MAS excel at simulating real-world phenomena and solving problems in complex systems.

For example, crowd simulation is done using a multi-agent system:

Vadere Crowd Simulation

An Agent

What defines an agent? It must be:

• Autonomous: Capable of acting without human intervention
• Reactive: Capable of responding to its environment
• Proactive: Actively pursues a goal
• Social: Capable of communicating and cooperating with other agents

To achieve this, we define:

• Its perception of its environment
• Its decision system (state machine, algorithm, neural network...)
• The actions it can apply to its environment
• Its goal

An Example of an Agent: A Mars Rover

• Its environment is physical: it's Mars
• Its perception is the set of information recorded by its sensors (camera, temperature, humidity...)
• Its actions are to move, collect samples, and transmit messages to Earth
• Its goal is to collect as many samples as possible, as diverse as possible, while maintaining its integrity

What Are the Advantages of This Approach?

Why bother adding this layer of abstraction when trying to solve a problem?

Agent-based modeling comes into its own when we consider environments with multiple agents. We then have a Multi-Agent System, capable of:

• Distribution: sharing responsibilities, computational loads, and decisions among multiple agents
• Decentralization: responsibility and control no longer belong to a single system
• Resilience: If one agent encounters an error, all the others adapt and the system remains functional
• Emergence: The interaction rules between agents give rise to behaviors more complex than what was initially defined
• Social behaviors: Behaviors that are difficult to replicate with a monolithic intelligence (by definition)

This is a rapidly developing field in the scientific community, though still not widely adopted in industry. There are still plenty of advantages waiting to be discovered.

Reactive Multi-Agent Systems

An agent's reflective capacity can be placed on a spectrum. At one end are cognitive agents, capable of complex reasoning, anticipation, learning, and prediction (we'll cover these in a future article). At the other end are reactive agents, which decide their actions by following simple stimulus-response rules.

Craig Reynolds: Boids (Simulated flocking)

For example, in the simulation of flocking behavior (the famous boids), each agent follows 3 predefined rules: separation, alignment, and cohesion. These 3 rules give rise to complex social behavior: the flock.

In a reactive MAS, agents have a limited representation of their environment and of other agents. They simply react to changes they perceive. It is from their interactions that intelligent collective behavior emerges, enabling problem resolution.

The advantage of reactive agents is their simplicity and robustness. They are inexpensive in terms of resources and adapt easily to environmental changes. Their drawback is the lack of advanced cognitive capabilities such as learning or anticipation.

The "Eco Problem Solving" Method

To apply the eco solving method, you need to redefine a problem so that its solution is the stability state of a multi-agent system. The system's agents are reactive and defined with the following 4 states:

• Satisfied: An agent is satisfied when it has reached its personal goal; it then does nothing
• Seeking satisfaction: When unsatisfied, it performs an action that brings it closer to its goal. If another agent blocks this action, it attacks
• Fleeing: The agent has been recently attacked; it no longer pursues its goal. It will exit the fleeing state after a waiting period
• Seeking escape: The agent is actively under attack; it performs the action that moves it farthest from its attacker

In the initial state, agents are unsatisfied and will all move toward their satisfaction. Agents interact by attacking and fleeing from each other. The system converges toward a stability state where all agents are satisfied. If the problem has been correctly formulated, this stability state will be the desired solution.

This approach makes it possible to find original and effective solutions to complex problems. However, it requires carefully defining the agents' decision rules to make them converge toward a good solution, and to avoid loops.

Illustration

In this illustration, the environment is a series of cells. An agent occupies a cell in the environment and is satisfied when it is in the cell assigned to it. When an agent is unsatisfied, it moves to a cell adjacent to the one it occupies. When an agent is fleeing, it moves to get away from the agent attacking it.

In this initial situation, the blue agent is satisfied because it occupies the cell assigned to it. The red agent is unsatisfied because it does not occupy the cell assigned to it.

The red agent attacks the blue agent because it is blocking the action that would bring the red agent closer to satisfaction. The blue agent is now in a fleeing state and performs the action that moves it away from its attacker. The blue agent will not exit its fleeing state until a certain time has passed.

The blue agent has continued to flee. Here it fled downward, but it could have fled to the right, in which case it would have ended up on the red agent's satisfaction cell. When it exited its fleeing state, it would have attacked the red agent, who would in turn have become the fleeing agent.

The red agent no longer needs to attack the blue agent and can reach its satisfaction state. When the blue agent exits its fleeing state, the path will be clear for it to reach its own satisfaction state. At that point, all agents will be satisfied and the system will be stabilized.

Application Example: 3D Packing

In this example, the objective is to arrange boxes in the smallest possible space:

In solving this problem, the algorithm is limited to simulating the agents' behavior. These agents must be correctly defined to obtain a system that converges toward stability.

Box

• Boxes are arranged in a line at problem initialization
• A box is always satisfied
• A box flees when it is attacked
• It flees in the direction where there is the most space
• It has a list of taboo actions that prevents it from repeating the same action multiple times
• When it has nowhere to flee, it attacks the other boxes around it

Container

• The container is created large enough to hold all the boxes arranged in a line
• It is satisfied when it reaches its target size
• It shrinks when it is unsatisfied
• It attacks boxes when they prevent it from shrinking

In this example, we observe the container's behavior as it seeks satisfaction (reaching the smallest possible size). The boxes are attacked when they block the container's satisfaction, and they move to make room. Ultimately, the emergent behavior of this multi-agent system is the self-organization of packages into the smallest possible space.

Conclusion

In this article, we explored reactive multi-agent systems, which represent just one part of the field. In future articles, we can explore the implementation of multi-agent system simulations and cognitive agents.