Multi-Agent Simulation Collision Avoidance of Complex System: Application to Evacuation Crowd Behavior

Introduction

Our work concerns the microscopic level of a complex system and more precisely the intercalations between crowd individuals in evacuation. The collision avoidance is a primordial phase in the interaction individuals-environment, whether the avoidance of static (wall) or dynamic obstacles (neighborhood individuals).

We distinguish several microscopic models of collision avoidance such as social forces (Helbing, Farkas, & Vicsek, 2000), rule-based models (Reynolds, 1987) and cellular automata models (Chenney, 2004), (Suwais, 2014). The difference between them is in the discretization of space and time. A (virtual) social force is analogous to real force such as repulsive interaction, friction force, dissipation, solving motion Newton's equations for each individual. In the rule-based model, the displacement of the crowd is governed by behavioral rules of the form “if condition then action”. Recently there has been a lot of work on crowds and their behavior as models that check the characteristics of complex systems (Reynolds, 1987; Lamarche & Donikian, 2004).

The first work of Reynolds (1987) on the concept of flocking describes the behavior of the units individually as a group using only local rules, some year after, Reynolds (1999) introduces the notion of autonomy for each agent to find its way so as to avoid collisions. The disadvantage of this approach is that it operates on the basis of local information, putting individuals in congested environments. The work of Musse (2000) is to create rules for managing directly a set of information, as a (Kirchner, Namazi, Nishinari, & Schadschneider, 2003) group of people operating in the environment. But this approach has the disadvantage of specializing the model, making again its generalization even more difficult.

However, in models of cellular automata, the space is represented by a grid of uniform cells; each cell to a local state which depends on a set of rules describes the behavior of individuals in which space and time are discrete (Chenney, 2004) and in behavioral domains we can cite the work of Hans and Marsland (2016), Roman, Nawaf, Darryl, and Abdallah, (2014) and Francesca (2016).

Musse and Thalmann (1997) focused on basic collision handling by proposing two techniques of collision avoidance. The first involves intersection of two lines and distance between two points in order to detect possible collision events. If two virtual humans are potentially colliding, only one will be allowed to go on first with its path. The second method is straight forward and it depends on the change of directions. An intelligent virtual human can avoid the collision by changing its directions through angular changes. Leitão, Vinhas, Machado, and Câmara (2014) proposed a genetic algorithm with two scenarios for inverse shortest path length problems.

The work of Foudil, Noureddine, Sanza, and Duthen (2009) inspired by the Reynolds model (1987) considers three types of collision between two agents:

• •

  Front Collision: Occurs if agents move towards each other;

• •

  Away Collision: When the agent is behind another agent;

• •

  Side Collision: Occurs if tow agents walk almost in the same direction.

Another collision technique that we can use for crowd system is proposed by Loscos, Marchal, and Meyer (2003). This technique presents collision detection between avatar and other objects (such as building). The strategy is to use collision map and grid system. The technique outlines three types of collision strategies which are frontal, following and perpendicular. The technique compares the direction of each agent, the velocity factor and the distance between the agents. In order to deviate from an appropriate angle, there are a few ways to decide either to slow down or to completely stop.