# Behaviour based on decision matrices for a coordination between agents in a urban traffic simulation

René Mandiau, Alexis Champion, Jean-Michel Auberlet, Stéphane Espie,
Christophe Kolski

► To cite this version:

René Mandiau, Alexis Champion, Jean-Michel Auberlet, Stéphane Espie, Christophe Kolski. Behaviour based on decision matrices for a coordination between agents in a urban traffic simulation. Applied Intelligence, 2008, 28 (2), pp.121-138. 10.1007/s10489-007-0045-3. hal-03269042

HAL Id: hal-03269042

https://uphf.hal.science/hal-03269042

Submitted on 15 Apr 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Behaviour based on decision matrices for a coordination
between agents in a urban traffic simulation

René Mandiau · Alexis Champion ·
Jean-Michel Auberlet · Stéphane Espié ·
Christophe Kolski

Received: 20 June 2006 / Accepted: 28 March 2007 / Published online: 20 May 2007
© Springer Science+Business Media, LLC 2007

**Abstract** This paper describes a multi-agent coordination mechanism applied to intersection simulation situations. In a goal of urban traffic simulation, we must consider the dynamic interactions between autonomous vehicles. The field of multi-agent systems provides us some studies for such systems, in particular on the coordination mechanisms. Conflicts between vehicles (i.e. agents) are very frequent in such applications, and they may cause deadlocks, particularly at intersections such as crossroads. Our approach is based on the solving of two player games/decision matrices which characterize three basic situations. An aggregation method generalizes to n-player games for complex crossroads. The objective of this approach consists in searching basic two-player matrices for solving n-agent problems. To explain the principle, we describe our approach for a particular case of crossroad with three agents. Finally, the obtained results have been examined via a tool of road traffic simulation, ARCHISIM. We assume also that the global traffic replicates the behavior of agents in different situations.

**Keywords** Multi-agent coordination · Traffic simulation · Conflict solving · Decision matrices · Autonomous vehicle

# 1 Introduction

Traffic congestion is one of the explanations of road accidents [21]. Moreover, recent studies in artificial intelligence suggest that the vehicle will become autonomous for the navigation and road-planning. If the vehicles are autonomous, it is clear that we must consider the complex and dynamic interactions between them in order to avoid accidents.

Traffic trials can last for several days or even several weeks in order to assess the infrastructures (impact of new roads, motorway entries/exits, new roundabouts, road signs, etc.) and/or perform research into the psychological aspects (the human being is included in the traffic loop and it is necessary to assess his/her behavior in specific contexts). Our aim is thus to put forward simulations which are very close to real traffic situations. This is why we take scenarios from a real traffic flow and test our propositions against them, carrying out a comparison on the microscopic level (behavior of the vehicles) and on the macroscopic level (interactions between the vehicles).

Traffic models can be distinguished on the basis of their design method (mathematical or behavioral), that is to say the concepts which they employ and on which they are based. At the present time, two radically different types of design model coexist. The oldest of these, mathematical models, appeared in the 1950s. So, historically, traffic simulation attempted to define a model of traffic in mathematical terms (which we can describe as a comprehensive approach) [2]. However, since the end of the 1980s a local “vehicle-centred” or behavioral approach towards traf-

<footnote>R. Mandiau (✉) · A. Champion · C. Kolski
LAMIH UMR CNRS 8530, Bat. Jonas 1, Université de
Valenciennes, 59313 Valenciennes, France
e-mail: Rene.Mandiau@univ-valenciennes.fr</footnote>

<footnote>C. Kolski
e-mail: Christophe.Kolski@univ-valenciennes.fr</footnote>

<footnote>A. Champion · J.-M. Auberlet · S. Espié
INRETS Arcueil, 2 Avenue du Général Malleret-Joinville, 94114
Arcueil, France</footnote>

<footnote>J.-M. Auberlet
e-mail: auberlet@inrets.fr</footnote>

<footnote>S. Espié
e-mail: espie@inrets.fr</footnote>
fic simulation has been developed. In contrast to mathematical models, the models based on the behavioral approach do not aim to model traffic as a flow but to model the actors involved in the traffic situation and the interactions between them. These models can be described as microscopic as they simulate individual entities. However, unlike microscopic mathematical models they do not reproduce traffic, traffic is generated. Thus, in a behavioral simulation model, a simulated entity takes account of its near and distant environment and adapts permanently to traffic conditions. Traffic phenomena (involvement in congestion, occupancy of traffic lanes, etc.) occur because they are the result of individual practices and interactions on the one hand and the variety (heterogeneousness) of behaviors (heterogeneous vehicles and driver behaviors) on the other. The complexity of the situations that are observed is therefore not the result of the complexity of the algorithm used but reflects the effects generated by the multiple interactions which take place between the entity and its environment.

In France, INRETS (acronyms for French Institute for Transport and Safety Research) has been researching into road traffic simulation based on the driving behavior of human drivers since the end of the 1980s. The simulation tool, ARCHISIM, has its origin in research into driving psychology. It can be considered as a virtual reality tool in which a human driver can interact within an environment of autonomous vehicles [13, 14]. In ARCHISIM, the traffic is the result of the individual actions and the developing interactions between the different actors present in a road situation (Fig. 1). The objective aims at making ARCHISIM an open tool for the study of the “traffic system”. Moreover, ARCHISIM has been developed such that the traffic model can host a driving simulator. In this case, the person in the driving simulator interacts with the traffic within the simulation model.

The principal advantage of this behavioral model is that simulation conditions can be dynamically modified (the degree of visibility which results from the weather, the driving preferences of the human driver, the characteristics of the

<figure><img src="image_2.png" /><figcaption>**Fig. 1** INRETS Driving simulator and visual environment simulated with ARCHISIM</figcaption></figure>

autonomous vehicle—cars, lorries, buses, pedestrians etc.) as can the road equipment (traffic signals, traffic signs, etc.). ARCHISIM is a simulation model and its implementation is based on the principles of multi-agent systems. Each autonomous vehicle (AV) is considered as an agent. It therefore possesses a model of its environment and interacts with the other agents, including a vehicle with a human driver (a driving simulator). A given road traffic situation is both a heterogeneous system and an open system (the number of AVs can vary), in which drivers or autonomous vehicles do not cooperate and have different objectives. The environment is non-deterministic and the system may have an infinite number of states. The information which is perceived by agents is geographically limited and incomplete.

The field of multi-agent systems (MAS) aims to provide studies for such complex systems [6, 15, 20, 22, 23]. Much research in the area of MAS has concentrated on coordination mechanisms [1, 17, 19, 24, 27]. Our research considers an original coordination approach applied to road traffic applications.

The rest of this paper deals essentially with critical driving situations: intersections and roundabouts (a roundabout is a particular kind of intersection that is often defined as being a succession of single intersections). In such situations, simulations naturally lead us to investigate non-trivial problems such as “livelocks” (situations in which no agent decides to enter) or, more seriously, “deadlocks” (situations leading to blockages in the middle of the intersection). These critical situations immobilize a part of the simulated traffic and at the same time invalidate an on-going traffic trial (The cost of a traffic trial can vary according to its complexity from several thousand to one million euros. Some simulations can involve tens of thousands of vehicles over periods of several hours, days or even weeks). To avoid this problem, we need to design and implement a distributed mechanism that coordinates the actions of AVs at intersections. It should be remembered that our aim is to put forward a realistic coordination model which is close to the real behavior of drivers in such situations.

This paper is structured as follows. Section 2 deals with the proposed mechanism applied to our problem. Section 3 gives an explanation of our proposal on a problem related to three agents. Section 4 presents our experimental results for a classical traffic application. Section 5 is a discussion of this work. Section 6 is a conclusion and suggests some directions for further research.

## 2 A description of the problem

### 2.1 Principles of a multi-agent coordination

Within the framework of a multi-agent simulation such as ARCHISM, simulating the behavior of drivers at an intersection situation can be reduced to a problem of multi-agent
coordination. Indeed, multi-agent systems allow the simulation of complex phenomena which are difficult to describe in an analytical manner. This approach often depends upon the coordination of agents whose overall actions and interactions bring about the emergence of the phenomenon to be simulated.

Multi-agent coordination work can be divided into two categories. The first category brings together the aspects of coordination seen from the cooperation viewpoint. These research projects are based on the hypothesis that the agents are collectively motivated for the achievement of a common goal. This is the case, for example, in distributed planning [12, 18] or in distributed research algorithms [31]. The second category groups together the works which consider that the agents are individually motivated for the achievement of their own individual goals whilst still trying to maintain certain properties on the group level. In [29], the authors introduce the notion of social laws which make it possible to restrict the actions of agents which are motivated by antagonistic goals (movement of robots in a limited area), and thus minimize the number of conflict resolutions. The coordination of competitive agents can also be perceived as being a problem of forming coalitions, consisting in finding an overall solution which is the most satisfactory for the majority of agents [3].

The characteristics of the task of driving to cross an intersection therefore naturally lead to considering the coordination of simulated drivers at a junction as a competitive coordination. The simulated drivers coordinate in order to resolve their conflicts and thus avoid accidents and roadblocks. The resolution of conflicts between mobile vehicles can be tackled from the multi-agent viewpoint.

In order to simulate a system of this type, specific coordination mechanisms must be designed in order to respond to complex situations. Situations in which two streams merge are not the only situations of blockage. We can identify two classes of critical situations: those which involve streams with different levels of priority, and those which involve streams with the same level of priority. In the first, a stream of vehicles can be blocked by a vehicle that has priority. There are no deadlocks, just the possibility of part of the traffic being blocked at a point on the network. In the second, there may be more than two streams and these may have the same level of priority. In such situations, there is a possibility of deadlocks and all the traffic in the area may be stopped for an indefinite period (which is unacceptable during a simulation) [7, 8, 10].

## 2.2 Application of the principle to an intersection

The initial idea is to consider a simulated traffic situation at an intersection as a game [25]. In the context of the behavioral simulation of road traffic, the playing agents are the AV

approaching or entering the intersection. In a driving system, an agent moves (or continues to move), decides to stop (or to brake to avoid a conflict), according to the context. The driver's objective is to travel in order to obtain his/her individual objective while avoiding accidents or deadlocks (a collective objective). For an agent, the driving can be represented as a compromise between safety and traffic flow capacity on the one hand and its own objective, which we characterize by a gain/payoff.

The possible actions of the players are to *accelerate* or to *brake* (these are extrapolations of the real objective being to move the AVs forward or stop them), the main characteristic of a mechanism being to constrain longitudinal acceleration (lateral acceleration, which is dependent on the former, is managed elsewhere). In what follows, we shall denote these actions by the words “*Go*” and “*Stop*”. It should be noted that each movement or braking action complies with the kinematic model for the movement of the AV. More precisely, the vehicles do not stop merely through the selection of the “Stop” action; they perform a braking procedure according to their physical constraints for a certain cycle. This means a certain number of simulation cycles are necessary in order to stop (provided, obviously, that this decision is not questioned in the subsequent iterations by any new information which has been received). We are not concerned with these physical models here, and shall therefore not describe them in this paper.

In the traffic situations that occur at intersections, the objective of drivers is to cross the intersection while avoiding involvement in an accident. In this context, the relationships which manage interactions are *priority relationships*. Priority changes as the situations change: in this context, we have considered priority in the broad (taking into account the Highway Code, obviously, but also the distance from the point of conflict, the time it will take to reach the point of conflict, queuing time, etc.).

We must stress here that each player can potentially play a different game from the others. Thus, for a given traffic situation in the intersection, each of the agents plays: (1) its own game, (2) taking account of its own opponents. This is because each agent only sees part of the overall situation. For example, a driver may consider that he/she has priority over another driver but the second driver does not necessarily see his/her relationship with the first in the same way. Apart from the issue of realism, this last point seems essential, in particular if a participant in the game is a human player who should obviously be unaware of the game that models the situation (the problem is physically distributed; indeed that the reasoning is related to each agent—AV or human driver). Consequently, in contrast with classical game theory in which it is assumed that all the players know the game matrix and therefore the payoffs received by each, all the players play their own game with their own adversaries
<figure><img src="image_3.png" /><figcaption>**Fig. 2** The three basic situations</figcaption></figure>

and can only know their own payoffs. In addition, they only know a part of the overall situation, and can therefore only make hypotheses about other players' payoffs.

We shall now express this mechanism for a situation with two agents/players.

## 2.3 Two-agent model

### 2.3.1 Basic situation of an intersection with two agents

Only X-shaped and T-shaped intersections need to be considered. We have made this choice because driving psychology research has shown that a complex intersection is perceived and managed by drivers like a succession of simple intersections. The situations are related to the priority notion. Let us note that the priority relationship such that A has priority over B is denoted by $Prio(A, B)$ and the priority relationship such that A does not have priority over B is denoted by $\neg Prio(A, B)$. Thus, for situations involving two AVs in an X-shaped intersection, three types of situation exist (Fig. 2).

(1) The first situation (game $X$) where $\neg Prio(A, B) \wedge \neg Prio(B, A)$: the two agents are not in conflict as neither has priority over the other (zero “point of conflict”);

(2) The second situation (game $Y$) where $Prio(A, B) \wedge \neg Prio(B, A)$: agent A has priority over B (one “point of conflict”);

(3) The last situation (game $Z$) where $Prio(A, B) \wedge Prio(B, A)$: each of the two agents has priority over the other (two points of conflict). For T-shaped intersections, these are a subset of those described above, as the situation involving two agents both with priority over the other does not exist in reality.

Once the situations are known, they can be modeled as games, that is to say the payoffs of the matrices can be determined. It should be noted that we defined the variables $x_i$ (eight variables called $x_1$ to $x_8$) for the $X$ game (in the same way, $y_i$ and $z_i$ are used for the $Y$ and $Z$ matrix). On the basis of the above comments, we have proposed decision matrices that simplify the model by reducing the number of variables that are manipulated and because of relationships of symmetry. This has led us to perform a study with 7 positive non null variables instead of the 24 initial variables (three matrices of four cells of two parameters) for the three situations. We suppose that the different variables are natural integers.

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 3** Two-player decision matrices</figcaption></figure>

In order to simplify the presentation of our model, we have made hypotheses about the behavior of each agent. Each agent must cross the intersection while managing any conflict(s). It may therefore have to cope with three different situations to which we shall assign payoffs to variables of three decision matrices (these payoffs are given for information only; these particular values are not justified, we consider that only their relative magnitudes are important):

(1) The player moves forward (it selects the strategy $Go$) but does not resolve the conflict which becomes real: the player is acting against its own interests; in this situation the payoffs associated with the $Go$ strategy must be negative (they are considered as therefore costs);

(2) The player moves forward (it selects the strategy $Go$) and avoids the conflict; in this situation, the payoffs associated with the $Go$ strategy must be positive (they are considered as gains);

(3) The player stops (selecting the strategy $Stop$): there is therefore no real conflict but the player cannot achieve its objective at the present instant; consequently, the payoffs associated with the $Stop$ strategy must be zero.

The above hypotheses lead us to constrain the values of the simple matrices (Fig. 3) by considering the strictly positive variables {$x_1, x_3, y_1, y_2, y_3, y_6, z_1, z_3$}.

### 2.3.2 Solving the game

They do not take account of the other agent's decision when selecting their strategies. In the framework of our study, an agent therefore selects a strategy that maximizes its gain, i.e. by considering the sum of the gains for each strategy. We are aware that our approach is very different from the classical game theory. However, our main aim is to justify its interest in the behavior and decisions of agents, in an application where blockage-free operation is essential, under major temporal constraints. The resolution of the game, without memory of the previous behaviors of agent, is the choice of ($S_A, S_B$) where the matrix $m_{A/B}$ characterizes the situation. In this context, the agent A considers the strategy $S_A$ (by
similar way, $S_B$ for the agent $B$):

$$ S_A = \{a^* \in \{Go, Stop\} | \\ g_A(B) = \max(m_{A/B}(a^*, Go) + m_{A/B}(a^*, Stop))\}, \quad (1) $$

$$ S_B = \{b^* \in \{Go, Stop\} | \\ g_B(A) = \max(m_{A/B}(Go, b^*) + m_{A/B}(Stop, b^*))\}. \quad (2) $$

Depending on the specified solution method it is possible to study and compare the following payoffs. We examine these payoffs, on a game-by-game basis, bearing in mind that games should be solved in a way that avoids unresolved conflicts (accidents) and deadlocks while favoring the realization of the players' objectives, we can conclude that:

(1) game $X$: $\{x_1 + x_3; 0\}$ for players A and B; indeed the solution must be $\{Go, Go\}$

(2) game $Y$: $\{-y_1 + y_3; 0\}$ for player A and $\{-y_2 + y_6; 0\}$ for player B. One of the players has priority over the other, this player must therefore receive a higher payoff for employing the Go strategy than the Stop strategy and vice-versa for the other player; this involves the inequalities: $y_3 > y_1$ and $y_2 > y_6$ which provide a solution $\{Go, Stop\}$;

(3) game $Z$: $\{-z_1 + z_3; 0\}$ for players A and B; if $z_1 < z_3$ the solution of the game is $\{Go, Go\}$, which means the conflict is not resolved; if $z_1 > z_3$ the solution of the game is $\{Stop, Stop\}$, which leads to a deadlock as neither of the players can hope to achieve its objective. This implies that $z_3 = z_1$ (this hypothesis is now considered).

It is worth pointing out that, on the basis of the matrices, it is simple to define different classes of driver behavior. We decided to propose values for variables which result in coherent overall behavior i.e. each agent wishes to achieve its aim without necessarily behaving aggressively. For example, we could easily describe an agent which is absolutely determined to have priority, even at the expense of refusing to yield priority to other agents.

This uncertainty concerning agents' respective behaviors can effectively lead to deadlock. In a real driving situation, human drivers can, through courtesy, yield their priority by stopping. As a matter of interest, in a situation of dual priority, the French Highway Code considers the date the driving license was issued to be the legal discriminant. For example, if we imagine the situation where agent A is “older” than agent B, the former can move, while agent B must stop. Another situation based on random selection, can also be used to differentiate between the agents.

It should be noted that in game Z, the equality described above results in four possible solutions. Irrespective of the strategies, the payoffs are equal (they are equal to zero:

<figure><img src="image_6.png" /><figcaption>Fig. 4 Use of a discriminant to obtain a single solution in the case of dual priority (note: $A^+$ that player A has an advantage over player B; idem for $B^+$)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5 Instantiation of two-player matrices</figcaption></figure>

$-z_1 + z_1$ for Go and $0 + 0$ for Stop). As it stands, this game does not allow the players to select a strategy. This uncertainty can be removed by introducing two discriminants which are to be defined. These discriminants (denoted by $d_1$ and $d_2$ where $d_1 > 0$ and $d_2 > 0$) must aim to favor one of the strategies for one player and the other strategy for the other player. This gives two possible matrices for the dual priority game (Fig. 4).

It is now possible to select values which satisfy the conditions imposed by these generic matrices. An example of this is given in Fig. 5. If we attempt to find a solution with these matrices; no deadlock occurs and all the conflicts are resolved: the players achieve their objectives on the basis of the priority relationships. These matrices with this resolution method are therefore optimal for situations involving two agents.

Furthermore, the solutions are those which drivers normally select in reality. Thus, (1) for the situation where none of the two players has priority over the other (i.e. they are not in conflict), the solution is $\{Go, Go\}$; (2) for the situation where the first player has priority over the second, the solution is $\{Go, Stop\}$; (3) for the situation where each of the two players has priority over the other, the solution is $\{Go, Stop\}$ in the situation when the first player has the advantage as a result of the discriminants.
In the specific case of two-player games, all the priority relationships are known for each player. It is possible to search for a solution using all this information. Consequently, a solution that maximizes collective gains can be sought, which can therefore be described as a cooperative method. It should be noted that the solutions obtained with this method are the same as with the non-cooperative individualistic method for the three matrices. This establishes the coherence of our approach.

## 2.4 Generalization to n agents

### 2.4.1 Definition

In a centralized approach, the method that enables a situation with n players to be modeled is identical to that used to model a two-player situation. It is necessary to pass, in a single aggregation step, from $n(n-1)/2$ two-player matrices to an n-player $2^n$ matrix. The aggregation method is described above.

Let us suppose a set $J = \{1, 2, \dots, n\}$ of n players. The payoff $G_k$ of player k for the outcome $S = (S_1, S_2, \dots, S_k, \dots, S_n)$ in the n-player game is described by the following formula:

$$ \forall k \in J, \quad S_k = \left\{ k^* \in \{Go, Stop\} \mid G_k = \sum_{i \in \{1, 2, \dots, n\}-k} g_k(i) \right\} $$

where $g_k(i)$ is the payoff received by player k in the two-player games between players k and the other agents. The same operation must be performed for all the game outcomes and for the other players. The size of the matrix thus obtained is $2^n$, and the game vectors are n values.

Distribution is necessary as, in both reality and simulation, each driver does not generally possess full information about the entire situation. In a real driving situation, the driver generally only evaluates accurately the relationships he or she maintains with other drivers and, as the work-load would in many cases be excessive, is unable to determine the nature of the relationships between two other vehicles. Likewise, in multi-agent road traffic simulation, the simulated drivers cannot have direct and systematic information about the relationships which exist between two other agents. The game that models a situation is therefore a game with incomplete information except for two-player games which still have complete information.

In the presentation of this approach, we assumed that the decision matrices are identical. It seemed difficult to present the mechanism on different matrices and to explain how it functions on different reasoning processes. In fact, to be precise, each agent builds the different decision matrices which correspond to the interactions perceived with the other agents (agents are considered not to be perceived by another agent if the infrastructure does not allow it to see

them, or because it has decided that the other agents in question are not directly involved in the interaction). Obviously, the agent can be wrong. Following its perception of agents involved in interaction and its interpretation of the priority rules, the agent builds decision matrices which it will attempt to aggregate according to the rule given.

It is necessary to determine the constraints (inequalities) that can be used to calculate the two-player matrices that give the best possible results (that is to say with no unresolved conflicts and the minimum number of deadlocks) in order to solve the n-player games. When applying a solution to the system of inequalities, the difficulty is obviously that an increasing number of inequality systems must be solved as the number of players/agents rises. So, for example, the two-player matrices that are the most effective for four-player games are not necessarily the most effective for games with five or more players. However, if we know the most effective two-player matrices for five-player games, these are also valid for games with four players or less.

Our idea was therefore to solve the inequality systems which are valid for games involving the largest possible number of players. Unfortunately, this task was too great to be carried out in its entirety, we were unable to work on calculating two-player matrices for games with more than ten players. However, extending the rules we observed during our work on the inequality systems revealed a subset of values for two-player matrices which allows us to construct n-player matrices which give the best possible results for solving these games.

### 2.4.2 Critical analysis

The results given in Fig. 6 show clearly that the number of deadlocks increases proportionately to the number of players as the amount of known information diminishes. This reduction in information is marked and rapid.

The total number of interactions possible for n agents is in fact defined by $(n(n-1))/2$ decision matrices. Each agent can perceive all the other agents in the best of cases, that is $(n-1)$ decision matrices. The information handled by the

<figure><img src="image_8.png" /><figcaption>Fig. 6 Efficiency of the distributed multi-agent coordination mechanism</figcaption></figure>
agent is therefore, in the best case, a ratio of the number of
decision matrices it can assess over the total number of de-
cision matrices corresponding to the whole of the situation
at a given moment (ideal case when the decision mechanism
can be considered as being centralized), that is 2/n. With
four players, each player perceives approximately only half
of the situation it is faced with, but with ten players, each
player only perceives a fifth of the situation it is faced with.
The increase in the number of deadlocks should theoreti-
cally also be proportional, but this is not the case. With four
players, deadlocks occur in approximately a fifth of the pos-
sible games, which is relatively few in comparison with the
amount of information that is available (half of all the infor-
mation). This partly offsets the fact that all the games do not
have a completely satisfactory outcome.

To continue this line of reasoning, we must begin by
remembering that the number of unresolved conflicts and
deadlocks is an instantaneous value. That is to say that when
a deadlock occurs, it only lasts for a certain duration. Once
this period is over, another game is calculated and solved,
the new game being based on the new inter-player relation-
ships. However, if there is a deadlock, the new inter-player
relationships can and must change in order to assist the re-
moval of the deadlock. An agent that is blocked must take
account of the fact and modify its behavior.

We can also state the complexity of the associated algo-
rithm, that is to say, the size of memory required (memory
complexity) and the number of operations required to run
it (temporal complexity). It should be noted that the results
given here are only intended to give a general idea as they
do not take account of any optimization that may be per-
formed in the future. The amount of memory used by the al-
gorithm is given by the *n* matrices (one for each player) that
model the traffic situation. That is to say, 2ⁿ × *n* whole num-
bers. The memory complexity is therefore low when only
a few players are involved but increases quite rapidly. The
calculations are performed in two stages: the construction,
by aggregation, of the *n* player matrix from the two-player
matrices on the one hand and the solving of the game on the
other hand. Aggregation requires 2ⁿ × *n* × (*n* − 1) additions.
Resolution requires: 2ⁿ × (*n* − 1) additions for each of the
*n* players, i.e. 2ⁿ × *n* × (*n* − 1) additions. Together, these
give 2ⁿ+¹ × (*n²* − *n*) addition operations. As with the mem-
ory complexity, the temporal complexity is very low when
a small number of players are involved but increases quite
rapidly.

To summarize, we have proposed a totally distributed
mechanism which allows each agent to model a conflict sit-
uation using a game so that it can manage its conflicts with
the other agents by solving this game coordination mech-
anism. Our analysis of this distributed coordination mech-
anism has allowed us to validate our approach mathemati-
cally and shows that the theoretical results are good for a

small number of players. However, it is important to take
into account that the number of players, indeed agents in
conflict, is not necessarily very high in the intersection con-
text we are concerned with. It is, in fact, possible for each
player to consider as players only the other agents which are
really, and most significantly, in conflict with it: for exam-
ple, by considering as players only the agents which are the
most strongly in conflict with it, and dealing with the others
later.

In the next section, our approach is explained for a par-
ticular case: a situation with three agents.

3 Particular case: mechanism for 3 agents

3.1 Explanation

The design of the coordination mechanism therefore con-
sists of defining the rules and the resolution method. The
dynamic temporal aspect is important as it plays a major
role in a given traffic situation This dynamic is taken into
account by using priority relationships at an early stage, in
order to enable the game to be created. Time therefore does
not exist for the players: only the instant a situation lasts is
modeled as a game, a traffic situation at an intersection is
a succession of instants therefore of games. Thus, the play-
ers and the relationships between them are unknown before
the situation is analyzed, that is to say before each simula-
tion. The game which a player will take part in is therefore
unknown beforehand. Furthermore, each traffic situation is
potentially different as it can change at any instant as vehi-
cles that are present leave and as new vehicles approach the
intersection. Consequently, the modeling of a traffic situa-
tion in an intersection consists of the following stages:

(1) step 1: each agent approaching an intersection an-
nounces itself as a player (it may perceive the other
ones);

(2) step 2: it determines which other agents it will play with (according to the crossroad infrastructures);

(3) step 3: it determines its priority relationships with the other players;

(4) step 4: it determines the game (calculates the matrix) in which it will play;

(5) step 5: it solves its game by choosing what it considers
to be the most advantageous strategy.

The strategic representations of the matrices are deter-
mined by the priority relationships between two players.
When more than two players are involved in the situation,
the matrix that models the game must also be based on these
relationships and, consequently, on two-player matrices. To
achieve this, the three two-dimensional matrices must be ag-
gregated to form a single matrix. The aggregation method
<table><caption>**Table 1** Payoffs for a player for the possible three-player matrices</caption><thead><tr><th>Matrix A\B</th><th>Matrix A\C</th><th>Go payoff</th></tr></thead><tbody><tr><td>][Prio(A, B) ∧ ]Prio(B, A)</td><td>][Prio(A, C) ∧ ]Prio(C, A)</td><td>4(x<sub>1</sub> + x<sub>3</sub>)</td></tr><tr><td>][Prio(A, B) ∧ ]Prio(B, A)</td><td>Prio(A, C) ∧ ]Prio(C, A)</td><td>2(x<sub>1</sub> + x<sub>3</sub> - y<sub>1</sub> + y<sub>3</sub>)</td></tr><tr><td>][Prio(A, B) ∧ ]Prio(B, A)</td><td>][Prio(A, C) ∧ Prio(C, A)</td><td>2(x<sub>1</sub> + x<sub>3</sub> - y<sub>2</sub> + y<sub>6</sub>)</td></tr><tr><td>][Prio(A, B) ∧ ]Prio(B, A)</td><td>Prio(A<sup>+</sup>, C) ∧ Prio(C, A<sup>+</sup>)</td><td>2(x<sub>1</sub> + x<sub>3</sub> + d<sub>1</sub>)</td></tr><tr><td>][Prio(A, B) ∧ ]Prio(B, A)</td><td>Prio(A, C<sup>+</sup>) ∧ Prio(C<sup>+</sup>, A)</td><td>2(x<sub>1</sub> + x<sub>3</sub> - d<sub>2</sub>)</td></tr><tr><td>Prio(A, B) ∧ ]Prio(B, A)</td><td>Prio(A, C) ∧ ]Prio(C, A)</td><td>4(-y<sub>1</sub> + y<sub>3</sub>)</td></tr><tr><td>Prio(A, B) ∧ ]Prio(B, A)</td><td>][Prio(A, C) ∧ Prio(C, A)</td><td>2(-y<sub>1</sub> + y<sub>3</sub> - y<sub>2</sub> + y<sub>6</sub>)</td></tr><tr><td>Prio(A, B) ∧ ]Prio(B, A)</td><td>Prio(A<sup>+</sup>, C) ∧ Prio(C, A<sup>+</sup>)</td><td>2(-y<sub>1</sub> + y<sub>3</sub> + d<sub>1</sub>)</td></tr><tr><td>Prio(A, B) ∧ ]Prio(B, A)</td><td>Prio(A, C<sup>+</sup>) ∧ Prio(C<sup>+</sup>, A)</td><td>2(-y<sub>1</sub> + y<sub>3</sub> - d<sub>2</sub>)</td></tr><tr><td>Prio(A<sup>+</sup>, B) ∧ Prio(B, A<sup>+</sup>)</td><td>Prio(A<sup>+</sup>, C) ∧ Prio(C, A<sup>+</sup>)</td><td>4d<sub>1</sub></td></tr><tr><td>Prio(A<sup>+</sup>, B) ∧ Prio(B, A<sup>+</sup>)</td><td>Prio(A, C<sup>+</sup>) ∧ Prio(C<sup>+</sup>, A)</td><td>2(d<sub>1</sub> - d<sub>2</sub>)</td></tr><tr><td>Prio(A, B<sup>+</sup>) ∧ Prio(B<sup>+</sup>, A)</td><td>Prio(A, C<sup>+</sup>) ∧ Prio(C<sup>+</sup>, A)</td><td>-4 - 2d<sub>2</sub></td></tr></tbody></table>

sums the payoffs of the two-player games in order to obtain the payoffs for the three-player game. The same operation must be performed for all the game outcomes and for the other players. This calculation is extremely tedious and, above all, when trying to solve the 24 games one must bear in mind that there can be more than one solution and the criteria which allow the solution(s) to be identified are non-trivial. Solving the 24 possible three-player games reveals no deadlock and all the conflicts are resolved. This is therefore a semi-formal demonstration of the overall efficiency of the result.

For a situation with three players, there are four two-player matrices: $][Prio(A, B) ∧ ]Prio(B, A)$ (game X); $Prio(A, B) ∧ ]Prio(B, A)$ (game Y); $Prio(A^+, B) ∧ Prio(B, A^+)$ (game Z$^+$); $Prio(A, B^+) ∧ Prio(B^+, A)$ (game Z$^-$). Therefore, combining two of these four matrices will give all the possible three-player games for a given player.

Thus, for a player in a situation involving three players, there are 12 possible three-player matrices. Table 1 sets out the payoffs that result from the two strategies for each of the 12 possible three-player games (let us note that the payoff for the action “Stop” is zero). For each of situations presented to a player, it must thus determine if the sum of the payoffs for the Go strategy is greater than zero or not.

We therefore obtain 12 inequalities (Table 2) on the basis of the payoffs that result from each of the two strategies (Table 1) and the inequalities that characterize the two-player matrices: $x_1 > 0$; $x_3 > 0$; $y_1 > 0$; $y_6 > 0$; $z_1 > 0$; $d_1 > 0$; $d_2 > 0$; $y_3 > y_1$; $y_2 > y_6$.

It is not possible to predetermine the sign of some inequalities. Without these signs, it is not possible to solve the system. It is therefore impossible to obtain the two-player matrices, and therefore also to calculate a three-player matrix. The other inequalities (those whose signs are known) are obtained directly from the inequalities derived from the

<table><caption>**Table 2** Inequalities characterizing the two-player matrices with the best results for three-player matrices</caption><thead><tr><th>Go payoff</th><th>Inequality</th><th>Stop payoff</th></tr></thead><tbody><tr><td>4(x<sub>1</sub> + x<sub>3</sub>)</td><td>&gt;</td><td>0</td></tr><tr><td>2(x<sub>1</sub> + x<sub>3</sub> - y<sub>1</sub> + y<sub>3</sub>)</td><td>&gt;</td><td>0</td></tr><tr><td>2(x<sub>1</sub> + x<sub>3</sub> - y<sub>2</sub> + y<sub>6</sub>)</td><td>&lt;</td><td>0</td></tr><tr><td>2(x<sub>1</sub> + x<sub>3</sub> + d<sub>1</sub>)</td><td>&gt;</td><td>0</td></tr><tr><td>2(x<sub>1</sub> + x<sub>3</sub> - d<sub>2</sub>)</td><td>&lt;</td><td>0</td></tr><tr><td>4(-y<sub>1</sub> + y<sub>3</sub>)</td><td>&gt;</td><td>0</td></tr><tr><td>2(-y<sub>1</sub> + y<sub>3</sub> - y<sub>2</sub> + y<sub>6</sub>)</td><td>&lt;</td><td>0</td></tr><tr><td>2(-y<sub>1</sub> + y<sub>3</sub> + d<sub>1</sub>)</td><td>&gt;</td><td>0</td></tr><tr><td>2(-y<sub>1</sub> + y<sub>3</sub> - d<sub>2</sub>)</td><td>&lt;</td><td>0</td></tr><tr><td>4d<sub>1</sub></td><td>&gt;</td><td>0</td></tr><tr><td>2(d<sub>1</sub> - d<sub>2</sub>)</td><td>&lt;</td><td>0</td></tr><tr><td>-4 - 2d<sub>2</sub></td><td>&lt;</td><td>0</td></tr></tbody></table>

two-player games and do not constrain the system any more than the first: they can therefore be ignored.

As there is a lack of information concerning the overall situation, the solution of the three-player matrices may not always be optimal. Consequently, it would seem worthwhile to try to find the signs of the inequalities which are still unknown in order to find two-player matrices which allow us to move as far as possible towards an optimum. The following procedure is adopted to achieve this:

(1) All the possible systems are solved if they can be (some systems may not have a solution);

(2) The values obtained by solving the systems define, for each system which is solved, a set of four two-player matrices;

(3) For each set of two-player matrices that is identified, the 24 possible three-player games are calculated then solved. The efficiency of the solution of each set of two-
<figure><img src="image_9.png" /><figcaption>**Fig. 7** A numerical example of two-player matrices for three-player games</figcaption></figure>

player matrices is measured by software that counts the number of unresolved conflicts and the number of dead-locks;

(4) The most effective set of two-player matrices is selected.

The results have been obtained by solving the inequality systems by means of a script run using the SciLab software [28]. They show that the most efficient system is that in which all the inequalities have less-than signs. In a context of three agents, the solving of system gives the constraints about the two-player matrices, for the variables (strictly positive integer) where:

$$ \left\{ \begin{array}{ll} y_3 > y_1, & d_2 > d_1, \\ y_2 > x_1 + x_3 + y_6, & d_2 > x_1 + x_3, \\ y_2 > -y_1 + y_3 + y_6, & d_2 > -y_1 + y_3. \end{array} \right. \qquad (3) $$

The values for the solutions of this system are set out in Fig. 7.

## 3.2 Example of a situation with three agents

We shall now present (Fig. 8) an example of an critical application of modeling and solution to a situation with three agents {A, B, C}. These agents are approaching the intersection and A will turn right, B will turn left and C will continue straight ahead. A and B arrive opposite each other and C arrives to the right of A and to the left of B. A situation is characterized by the matrices representing the different games/matrices (X, Y and Z).

All the games involved here can be solved by a single one of the three agents, or by a third party, coordinating, agent located in the intersection in question. On the basis of the priority relationships that are laid down in the French Highway Code, the situation is as follows: A has priority over B and B does not have priority over A; A does not have priority over C and C does not have priority over A (they are not in conflict); B has priority over C and C does not have priority over B.

<figure><img src="image_10.png" /><figcaption>**Fig. 8** Example of a situation involving three agents</figcaption></figure>

Thus, an agent does not perceive the overall situation but only its local environment. Consequently, for a three-player situation, player A can consider only four relationships ($A\B$, $B\A$, $A\C$, $C\A$) out of the six which exist ($A\B$, $B\A$, $A\C$, $C\A$, $B\C$, $C\B$). Even if a player does not have all the information about the situation, it must be able to model this situation in order to reason. The method we have already described for calculating the three-player matrix by aggregating two-player matrices is used. However, in the present case, for player A for example only two two-player matrices ($A\B$ and $A\C$) are known out of the three which exist ($A\B$, $A\C$ and $B\C$). Player A is therefore only able to calculate its own payoffs and not those of the two other players as it does not know part of the information. The same operation must be performed by player A for all the game outcomes but, in contrast with a centralized mechanism, it cannot be performed for the payoffs of players B and C. The latter both calculate their own three-player matrix.

Thus, if we consider the priority relationships that are laid down in the French Highway Code, we will obtain the following representations for each player:

(1) Player A knows the following data: A has priority over B and B does not have priority over A; A does not have priority over C and C does not have priority over A (they are not in conflict).

(2) Player B knows the following: B does not have priority over A and A has priority over B; B has priority over C and C does not have priority over B.

(3) Player C knows the following: C does not have priority over A (they are not in conflict) and A does not have priority over C; C does not have priority over B and B has priority over C.

This analysis will therefore give us two two-player matrices which characterize the situation for each of players A, B and C (Fig. 9).

Using its two matrices, each of the three players is now able to calculate its three-player matrix. They aggregate their two two-player matrices, which gives the three three-player matrices shown in Fig. 10.
<figure><img src="image_11.png" /><figcaption>**Fig. 9** The two-player matrices that model the situation for each of the three players</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>**Fig. 10** The three-player matrices that model the situation for each of the three players</figcaption></figure>

According to the Fig. 10 and the numerical instantiation given in the Fig. 7, the deduced results are described in the Fig. 11.

Once the players know the game that models their situation, they simply need to take a decision. The solution method applied is that which favors the individual behavior. The solutions, for each of the players, are as follows: For player A: $S_A = Go$ (because: $-1 + 1 + 2 + 1 - 1 + 1 + 2 + 1 > 0$); for player B: $S_B = Stop$ (because $-4 - 1 + 1 - 1 - 4 + 2 + 1 + 2 < 0$); for player C: $S_C = Stop$ (because $1 - 4 + 1 - 4 + 1 + 1 + 1 + 1 + 1 < 0$). Consequently, agent A passes through the intersection and agents B and C have to wait for the first to leave the conflict zone. The strategy for three agents is (Go, Stop, Stop).

By similar reasoning, in this case where the conflict situation is managed in a different way from that proposed by a centralized coordination mechanism (the agents perceive all informations of the environment). In this case, the resolution method will give us the solution $S = (Go, Stop, Go)$. Thus, the agents A and C can pass through the intersection, while the agent B must wait for at least one of the other two agents is no longer in conflict with it.

Here, only player A decides to move while in the case of centralized management two players could move forward. The explanation for this is that, at the instant in question, player C cannot know B's actions and cannot therefore reasonably take the risk of moving forward as B may do so too: in the event of an accident, C would in this case be deemed to have been responsible. It should nevertheless be noted that in a number of appropriate cases the distributed mechanism can allow at least one other agent to pass through the intersection at the same time depending on the type of interactions which exist between the agents that are present.

The next section describes the manner in which the coordination mechanism can be applied to the simulation of traffic situations at intersections.

# 4 Experimental results

The ultimate aim of the coordination mechanism described in this paper is to simulate an urban network, and in particular critical situations, at intersections. We describe three applications.

## 4.1 Application with two agents

This experimentation is the first step to the validation of the coordination mechanism. The objective is to validate the behavior of a mobile approaching a crossroad. Let us consider
<figure><img src="image_13.png" /><figcaption>**Fig. 12** Two vehicles in conflict approaching a crossroad</figcaption></figure>

the simplest situation: two vehicles approaching a crossroad where right priority applies (Fig. 12). The two vehicles are potentially in conflict and in such a situation, a driver who has priority slows down when he/she perceives the other vehicle and then re-accelerates after being persuaded that it is going to let him/her go through the crossroad safely. Both drivers are in interaction as soon as they perceive themselves and manage dynamically their conflict.

In simulation, in case both mobiles would strictly give
obedience to the Traffic rules, the mobile having priority
would not slow down and the other mobile would slow down
to let it clear the crossroad. On the other hand, as soon as the
notions of priority related to the time, to conflict, and to the
relative position are implemented and considered by the mo-
biles, the behavior of the mobile having priority changes:
as long as it did not clear the crossroads, it slows down
(Figs. 13(a) and 13(b)) even if it is not the closest to the
crossroad.

These simulated behaviors allow us to validate the sim-
ulated mobiles’ behavior in such a situation. The mobile
correctly interact with the other mobile and, that is impor-
tant, even if it is a driving simulator. Moreover, the subject
driving the simulator also interacts correctly with the simu-
lated mobile.

Let us now consider more complex situations to let the
simulated mobiles evolve in a more complex environment.

4.2 Application with 3 agents

This experiment has two objectives. The first one is to val-
idate the behavior of a mobile when it has to wait before
engage into the crossroad, that is when it does not have ab-
solute priority. The second objective is to manage the live-
locks produced by some situations not solved with a single
one-turn game. Let us consider a situation involving three
vehicles A, B and C. This situation is circular because A
(according to the Traffic rules) has priority on B, B has pri-
ority on C and C has priority on A (Fig. 14).

The situation is blocking for the drivers: after a certain
time, one of the driver decides to go and cross the intersec-
tion. The situation is unblocked. Then a second driver (the
one who has priority) goes and cross the intersection, letting
it cleared for the last driver. These behaviors are of for the
drivers' dynamic management of the situation. To free the

<figure><img src="image_14.png" /><figcaption>**Fig. 13** a Speeds resulting where the human driver has the priority (crossroad with two agents). b Speeds resulting where the mobile has the priority (crossroad with two agents)</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Fig. 14** Circular situation
leading to livelocks</figcaption></figure>

situation, the drivers communicate their intentions and then,
if this does not solve the problem and if the wait takes too
long, the impatience gets the upper hand and they try to go
through. The most impatient driver goes first.

In simulation, it is extremely difficult to make mobiles
communicate. It is so necessary to consider the waiting time
and the impatience by implementing a priority relative to
these two notions, which should counterbalance the prior-
ity stemming from the Traffic rules in this type of situation.
So, once the mobiles are blocked, when one of the mobiles
considers that it has been waiting for a long time, it gets im-
patient and considers it gets priority on the others. The prior-
ities relations change and lead to a non-blocking new game:
a situation with three autonomous mobiles (Fig. 15(a)) and
<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /><figcaption>**Fig. 15** **a** The agents' behaviors in a blocking situation. **b** Behaviors in a blocking situation involving a human driver</figcaption></figure>

a situation with two mobiles and a human subject via the driving simulator (Fig. 15(b)).

The figures show a coherent behavior of different agents (autonomous agent or human driver) in a such context.

The simulated behaviors allow us to validate the simulated mobiles' behavior in such a situation. This validate the coordination mechanism in a local point of view. Now, we need to carry out other experiments involving traffic, that is numerous mobiles on a large road network, to validate the coordination mechanism in a global point of view.

## 4.3 Complex intersection

### 4.3.1 Characteristics

The starting point for this process is invariably to look for an intersection at which real data has been measured in order to use this as the input data for the simulation model. The more accurate and complete this data is, the more detailed and valuable the possible simulation is. One of the difficulties is therefore to start the validation process as, unfortunately, high quality data is extremely rare, in spite of

<figure><img src="image_18.png" /><figcaption>**Fig. 16** 3D representation of the Roma-Zerbi intersection—an example of a scene</figcaption></figure>

the ever-increasing number of sensors that are buried under the carriageways of our towns and cities. In this situation, we therefore worked with the Italian university of Reggio Calabria in order to simulate an X-shaped intersection. This university has measured traffic at an intersection located in the city centre. It should be noted that driving rules are similar in several countries, in particular in France and in Italy (our explanations therefore remain valid). The essential differences are to be found in the behavior of the drivers. An example of this is in the context of an arrival at a Stop sign-post: the average waiting time is around 3 seconds in France, whereas it is virtually zero in Italy.

We shall now describe this intersection and the measurements. It is distinguished by the fact that it is located in the very centre of the city and connects to a motorway in addition to some streets. Traffic at the intersection is particularly dense, especially during the lunch-time rush hour. The intersection in question is the junction between the Via Roma and the Via Zerbi in the city of Reggio Calabria in Italy. The Via Zerbi runs North-South while the Via Roma runs East-West. The intersection is not signalized (the lack of traffic signals is fundamental for our objective because traffic signals tend to remove a maximum number of conflicts which does not suit our purposes), but two Stop signs have been installed on the Via Roma. The Via Zerbi is therefore the priority road. The northern, eastern and southern legs of the intersection have two entry lanes and two exit lanes while the western leg has one entry lane and two exit lanes.

This intersection configuration requires a large internal area in the case of an X-shaped intersection, so a few vehicles can be stored temporarily there while crossing the intersection. Figure 16 shows a three-dimensional model of this intersection.

All movements are permitted, each driver can either continue straight ahead, or turn left or right. In addition, in principle, no lane is dedicated so drivers are free to choose the
<table><caption>**Table 3** Aggregate traffic demand data</caption><thead><tr><th>Access</th><th>Total flow (vh/h)</th><th>Lorries (%)</th><th>Left-turning (%)</th><th>Straight ahead (%)</th><th>Right-turning (%)</th></tr></thead><tbody><tr><td>South</td><td>816</td><td>1.5</td><td>16</td><td>77</td><td>7</td></tr><tr><td>North</td><td>685</td><td>1.2</td><td>1</td><td>82</td><td>17</td></tr><tr><td>East</td><td>428</td><td>6</td><td>43</td><td>2</td><td>55</td></tr><tr><td>West</td><td>26</td><td>0</td><td>36</td><td>36</td><td>28</td></tr></tbody></table>

lane or path they prefer. Consequently, the number of possible conflicts is high, fourteen for this particular X-shaped intersection (i.e. there are 14 points where two paths cross: for example, the right-hand lane of the South–North route and the right-hand lane of the East–West route intersect). The traffic data supplied to us by the University of Reggio Calabria was measured manually within the intersection between 12.30 and 13.30 on a normal weekday. The data has been aggregated over five minutes periods. The flow was measured on each access leg and for each movement (right turn, left turn, straight ahead). The types of vehicles were also recorded: light vehicles, motorcycles, bicycles, buses and lorries.

Table 3 presents a summary of the data provided by Reggio Calabria University which was used as input data for the simulation. Once the configuration of the network and the traffic demand are known, simulation can be performed.

### 4.3.2 Simulation parameters

The first important point to note is that the agents' behavior is randomly generated (waiting time, speed, etc.), and therefore the results given in the following sections are in fact averages resulting from several simulations. We shall now present in turn the values of parameters used for the simulation described in the previous section (also used in Sects. 4.1 and 4.2):

(1) The vehicles cannot be generated at the point where the measurements were made (i.e. inside the intersection) but must be generated upstream on the access legs. It was therefore decided to generate the vehicles at four points, each 200 meters from the intersection entry.

(2) As speed data was not available, in order to avoid introducing an additional unknown, it was decided that all the vehicles should travel at the maximum speed (50 km/h) inside the intersection when there were no other vehicles present and at 45 km/h when there were. These are the default values in urban areas and the natural choice; they are not, therefore, in the case of this intersection, a constraint on autonomous vehicles. However, we can state that the desired speed does not have a direct influence on the behavior of the

vehicles and, by extension on that of the traffic as the situations are such that it is almost always dangerous to drive at this speed.

(3) The minimum waiting time at a stop sign (impatience threshold), which applies here to all the vehicles coming from the Via Roma before entering the intersection, was— in view of the amount of traffic and of the Italian driver's practices—reduced to a selected minimum (i.e. 0 second). This does not mean that the priority vehicles enter the intersection as soon as they arrive, but that they start to seek a gap as soon as they reach the stop sign. Consequently, as a large number of vehicles arrive from the other access legs, the non-priority vehicles wait when they arrive at the intersection, on average longer than the three seconds laid down by the law.

(4) The minimum valid gap acceptance time has been fixed at 2.5 seconds for all vehicles. This value is fairly standard and increasing it significantly increases queue lengths and therefore reduces flow. Reducing it further increases accident risk and some accidents may actually occur, which is not acceptable. We can deduce from this that these two parameters are quite constraining as they are fixed at their minimum value for this application.

(5) The minimum distance to conflict point, which obliges any vehicle which has to stop as a result of a conflict to do so within this distance, has been fixed at one meter. This is a standard value and extremely important as lengthening it increases the fluidity of traffic. However, it leads to less intensive use of the space within the intersection (in the case of the studied intersection, vehicles will no longer tend to be stored within the intersection, which is not realistic). Reducing this distance produces the opposite effects but, in the case of the studied intersection, leads to no perceptible improvement (for one to occur, the intersection would have to be wider).

(6) Last, the turning movement percentages are known but the positioning of the drivers on the lanes with reference to their direction is not: we therefore do not know what the drivers' habits are and the extent to which they use the different lanes. During the simulation, the vehicles were therefore totally autonomous with regard to the choice of their approach lane. The lane choice algorithm used is the simulation model's default algorithm. All the possible conflict points will probably be simulated, but their relative rates of occurrence may not be accurately reproduced. However, we have to assume that all these hypotheses and the traffic demand are correct and do not have a major impact on the results obtained.

### 4.3.3 Results

In order to collect data during simulation, virtual sensors were installed near the intersection on each access leg and
<figure><img src="image_19.png" /><figcaption>**Fig. 17** a Result of the simulation at the Roma-Zerbi intersection in the North-South/South-North directions. b Result of the simulation for the Roma-Zerbi intersection for the East-West/West-East directions</figcaption></figure>

each exit leg. The four sensors on the access legs enabled us to compare the entry flows with the measured data. The four sensors on the exit legs allowed us to check the turning movement percentages. Several simulations had to be performed in order to find the parameters which gave the best results.

To begin with, we must make it clear that the simulation was conducted on each of the access legs and that the flow was generated in its entirety. It is also important to emphasize that no permanent deadlock occurred and that each deadlocked situation involving several autonomous agents was satisfactorily managed and solved by these agents individually. With regard to accidents, a detection system operated throughout the simulation and to record each collision and its characteristics in a file. No collision was detected either in the intersection approaches or within it. From a visual standpoint, when seen from above, the individual vehicles and the traffic in general behaved in a way which seemed quite consistent and non-random. However, the waiting times within the intersection occasionally seem slightly too long (by a few seconds). With regard to entry flows (the unit for the flows is noted $v_h/h$ for vehicles/hour), the results obtained from simulation are given in Figs. 17(a)

and 17(b). The first two graphs (Fig. 17(a)) are for Via Zerbi, the priority road. These results are completely convincing as the simulated flows, both for North-South or South-North traffic are almost identical with the real flows.

In addition to this flow data we must also consider queuing. This is because in the same way that it is necessary to check that the number of vehicles entering the intersection is correct, it is also necessary to make sure that crossing the intersection is not too easy. The best way of doing this is to compare queue lengths. Unfortunately, as we have no measured data we can just state that the simulated queues vary in length from 0 to several tens of meters over time and depending on the access leg, which quite closely matches the information we have about the real situation.

The last two graphs (Fig. 17(b)) are for the Via Roma, the non-priority road. As these results are less satisfactory in the East-West direction than those for Via Zerbi as although the simulated flows generally match the real flows, the peaks are not attained.

We have also observed that a considerable number of vehicles use the space inside the intersection for a temporary stop between two of their points of conflict. There are often
one, or even two, vehicles in the zone throughout the simulation.

### 4.3.4 Analysis of the results

The analysis of the results must deal with both the visual and the statistical aspects. We can consider that the simulations have validated the visual aspect. Some details still need to be settled. The mechanism is therefore not at fault in this area, it is the algorithm that computes vehicle trajectories which must be improved in order to take better account of the characteristics of urban infrastructures. We can add that at no time do the vehicles behave erratically; their movement consists of a succession of clearly distinct, smooth, phases. To conclude, apart from the minor trajectory problems, vehicles behave in a way which should not surprise an observer or an actor involved in the simulation such as a subject at the wheel of a driving simulator.

For the purpose of statistical validation we can use indicators that allow us to compute the error rate. One of the most frequently used indicators is also probably the most constraining, namely the relative standard deviation (RSD), which is given by the following formula:

$$RSD = 100 \sqrt{\frac{\sum_i (x_i - y_i)^2}{\sum_i y_i^2}} \quad (4)$$

where $x_i$ is the simulated traffic measured over the period $i$ and $y_i$ is the real traffic measured over the period $i$. Generally, simulation data are considered to be excellent if the RSD is below 10 and fairly satisfactory if it is lower than 15. These are standard thresholds in the context of traffic simulation.

Another indication is the correlation ($R$) which makes it possible to verify the closeness of the linear match between the simulated data and the real measured traffic data. The correlation is considered to be satisfactory if its values are above 0.80. The correlation is defined as follows:

$$R = \frac{1}{(n-1)} \sum_{i} \frac{(x_i - X)(y_i - Y)}{(\sigma_x - \sigma_y)} \quad (5)$$

where:

(1) $x_i$ is the simulated traffic measured over the time period $i$;

(2) $y_i$ is the real traffic measured over the time period $i$;

(3) $X$ is the average of all the values measured during simulation;

(4) $Y$ is the average of all the real measured values;

(5) $\sigma_x$ is the standard deviation of the values measured during simulation;

(6) $\sigma_y$ is the standard deviation of the real measured values;

(7) $n$ is the number of time periods.

<table><caption>**Table 4** Statistical analysis indicators of the simulation results</caption><thead><tr><td>Access leg</td><td>RSD</td><td>R</td></tr></thead><tbody><tr><td>South</td><td>6</td><td>0.95</td></tr><tr><td>North</td><td>3</td><td>0.85</td></tr><tr><td>East</td><td>15</td><td>0.31</td></tr><tr><td>West</td><td>32</td><td>0.87</td></tr></tbody></table>

The results for the calculation of the RSD and the correlation indicator for simulation of the Roma-Zerbi intersection are set out in the table below (Table 4).

It is immediately apparent that the values of the indicators in the table confirm the good results obtained for the priority road (the Via Zerbi running North-South). For the non-priority road (the Via Roma running East-West), the RSD confirms what could be seen on the graphs in the previous section. In this case, although the access leg exhibits a satisfactory error rate, the error rate for the opposite leg is quite poor. However, the correlation for the western access is much better than for the eastern access.

We can draw conclusions of three types from these values. Firstly, simulation of the priority road is good, while for the non-priority road it is not completely satisfactory, although the results are more than just encouraging. Secondly, the error rate for the western access is very high because flow in the simulated intersection is very low on this leg. Because of this, a slight difference in the number of agents generates a large error (i.e. a small increase in the number of agents generates a high percentage of errors and a high RSD). We need therefore not attach too much importance to the error rate for the western access leg. However, it does allow us to highlight the first point we have just made: the non-priority access legs are not as accurately simulated as the priority access legs. Thirdly, although its error rate is good, correlations for the access are mediocre. This means that the simulation data is not sufficiently correlated with the real measured data, which may mean that the (manually) measured data contain some errors; we cannot, however, do other thing than to ignore this.

# 5 Discussion

## 5.1 Discussion concerning the intersection problem

As we have already shown, a junction is defined as being a set of roads which intersect to form a space in which traffic circulates (the centre of the junction), allowing the vehicles either to change direction by joining a new traffic flow (flow fusion) or to continue its journey on the same axis by crossing one or several contrary flows (flow crossing).

Amongst the existing tools capable of simulating traffic at a junction, two categories can generally be distinguished:
there are tools which are based on empirical models and others which use analytical models. The empirical models work through regression of the data collected concerning real junctions. The analytical models are based on the pa- rametering of a large number of variables such as the geom- etry of the junction, the monitoring time of a vehicle, etc. The tools using an analytical model can again be divided into two categories according to their capacity to simulate a junction with or without traffic lights.

The tools which make it possible to simulate intersec-
tions which are not managed by traffic lights (VISSIM [30],
AIMSUN [2]) are based on a simplification of the problem
which consists in considering the solution of conflicts at in-
tersections to be a problem of the centralized organization
of the different incoming flows. The vehicles approaching
the junction are stored in waiting queues and the central or-
ganizer seeks an insertion point meeting various constraints
for the vehicle at the top of each queue. The first constraint
is that the time between two vehicles must be sufficient to
allow insertion into or crossing of a flow (principle of gap
acceptance). Other constraints make it possible to limit the
combinations of different turning movements for each axis
(left, right, straight ahead) so that the trajectories of the ve-
hicles at the centre of the junction are not really conflicting.
Finally, various simple rules are added making it possible
to limit the phenomena of waiting and queuing at the cen-
tre of the junction. Users of the AIMSUN software can thus
parameterize a variable called “yellow box” which defines
the minimum speed the vehicles must use at a junction point
whilst still letting other vehicles enter the area.

Such approaches can be sufficient when used to study
traffic phenomena occurring before or after the junction
from a statistical point of view. Provided that the model has
been parameterized appropriately, these software tools make
it possible to obtain flows at the entry and the exit of a junc-
tion which are close to those measured in reality. On the
other hand, when the study is based on the junction itself,
these tools reveal their limitations as they avoid a good num-
ber of phenomena which can be observed in real life at the
centre of junctions: queues of vehicles, partial blockage of
certain lanes, vehicles moving up queues inside the intersec-
tion, etc.

## 5.2 Discussion concerning the described mechanism

A constraint of this application is that there is clearly a need
for a large number of agents, under real time constraints.
Another important factor is that we must take into account
that the size of the memory space required for the coor-
dination mechanism which must be implemented in each
agent. It should be noted that memory space is not gener-
ally considered in research on multi-agent systems. We have
done so because there are a lot of the functionalities of the

agents and the number of items of information manipulated
in a traffic problem. In the context of realistic traffic simula-
tion, each agent has physical capacities (vehicle types), and
a representation of the environment (roads, other vehicles,
traffic signs, pedestrians, etc.). In this situation, the number
of interacting agents is at least a thousand agents/vehicles
which makes real time simulation more complex. We have
consequently suggested approximations in response to these
computational and memory requirements, while neverthe-
less still proposing realistic traffic simulations. Our work
based on the use of matrices to resolve conflicts, is clearly
valid both in relation to objective and subjective criteria.

In order to resolve these critical intersection situa-
tions, the methods implemented by mathematical models
(KNOSIMO [9]) and automaton-based behavioral [26] mod-
els are often centralized (the agents are thus “driven” by a
single coordinating process) or use the classical approach
of allowing only one vehicle at a time a given traffic lane.
Moreover, the automaton does not know what decision to
take and will stop, for obvious reasons of safety, until there
is no vehicle opposite it. However, if a large number of vehi-
cles arrive in an intersection under the same conditions, the
automaton will remain blocked for a completely unaccept-
able period of time. Many recent theoretical studies aimed
at improving our understanding of multi-agent systems have
already used this model in the similar applications of in-
tersections [4, 11, 16]. Our approach more “computational”
is quite different by considering the agents take decisions
only on the basis of decision matrices. Furthermore, Baz-
zan’s goal is based on an optimized coordination of the traf-
fic signals (the agents) [4]. In our case, the motivation aims
to describe a “realistic” traffic where the agents are the au-
tonomous vehicles (and also human drivers).

The crossroad is in this paper characterized by an aggre-
gation of two-player matrices. The choice of matrices for
the proposed model may allow an evaluation dynamically.
In such situations, the population formed by these agents
evolves as a function of the gains. Applications are often
in fields where the real time aspect is crucial, in particular
in virtual environments. In this work, we have decided not
to take account of the memorization of previous informa-
tion. At first sight this hypothesis may seem simplistic, but
it is quite justified in the framework of this study. By do-
ing this, we have adopted an approach which has a low cost
in terms of the data memorized by each agent. Finally, in a
model like ARCHISIM, such methods cannot be considered
as the mechanism that is implemented must, while being as
generic as possible, be realistic both locally (visually) and
comprehensively (as regards traffic). However, the nature of
the model and its constraints mean that this task is complex.
On the other hand, to its advantage, some possibilities are
available which are not with other types of model.
## 5.3 Discussion concerning the experimental results

The results obtained and the analysis we have presented encourage the view that the coordination method described in this paper is an effective way of resolving the problem of traffic simulation in urban areas. However, the results are still imperfect and with the current state of the mechanism it is quite apparent, after the large number of simulations that have been performed, that better parametering is very difficult.

As a large part of the problem stems from the fact that the priority road is given a slight advantage over the non-priority road, the modifications must relate to the interaction between the various priorities in order to allow the agents arriving from the non-priority access legs to gain priority a little more rapidly. If these agents are given more priority than they are at present, we should probably give slightly less priority to agents arriving from priority access legs. This is quite possible in practice as the results are excellent for these. There is also another possible way of achieving an improvement that is linked to a problem we have already mentioned. Some agents that stop inside the intersection seem to be too slow to react and therefore wait too long; it would seem worthwhile to correct this problem which is, in local terms, not really problematic, but which, from the point of view of traffic, must slow down the flow of agents.

# 6 General conclusion

The aim of this paper was to show how a coordination mechanism based on decision matrices could contribute to realistic road traffic simulations, particularly at intersections in a urban context. These applications involve agents whose decisions depend on temporal constraints.

We should not forget that the deadlocks or blockages which may occur after accidents are critical problems for traffic studies. The economic stakes involved in the obtaining of extremely realistic simulation tools are crucial. Most of the simulators (including those based on a microscopic approach) consider that the junction is a “black box” (or, more precisely, in the research documents we talk of “yellow boxes”): they only consider the flow levels at the entry and the exit of the junction. We also know that the junction is a sensitive place which is crucial in terms of interaction between vehicles and thus in terms of dynamic evolution of traffic in an urban situation. With a view to understanding the phenomenon of highly meshed networks (urban context) and also in order to obtain a better result in terms of junction realism, we chose to study this problem more precisely and try to develop an efficient approach. We also had ensure that the traffic kept to a globally realistic and coherent behavior in order to reduce interblockages which hinder the various

studies performed: for example, we can mention traffic simulations, experiments involving human beings placed in a virtual environment, training of the drivers of heavy goods vehicles.

Apart from the fact that the coordination mechanism is envisaging an approach to a problem considered to be difficult, i.e. the problem of junctions in urban situations, the interest of this proposition is also to be found in its procedure which can be used in other applications. Indeed, the principle may seem simple a priori, but the process is made up of two main stages. The first step consists in looking for the various agents’ possible actions (two actions characterize our application), and the relations which define the interactions envisaged between the agents (the relation of priority is the basis for interaction in the application studied). The second stage is intended to build decision matrices. These decision matrices describe the gains linked to the possible interactions, using simplification hypotheses such as the specific properties of the different relations (for example, relations of symmetry), at the same time trying to keep and/or guarantee an interactional behavior which will make it possible to avoid unwanted situations. In this paper, the unwanted situations are characterized by blockages between vehicles. The last step is the use of matrices enabling the agent to make decisions. To sum up, in this paper we have therefore presented a coordination mechanism based on the assessment of interaction between agents.

We have noted that with a simple coordination model, the theoretical results show that the construction of matrices, and the interpretation of a situation by each agent, is optimal with a reasonable number of agents in conflict situations. In fact, in view of the amount of information that is available, this mechanism is, in our opinion, efficient for fewer players. For situations with more players its efficiency is only moderately satisfactory as, even if there is very little available information, the number of deadlocks is, in absolute terms, quite high. In defense of this mechanism we should nevertheless mention that, at the present time, most studies of games do not consider situations with more than two players.

Furthermore, we have validated the coordination mechanism on the basis of various simulations, one of them have been described in this paper. These simulations are very correct, in terms of realism—the individual behavior of the various simulated agents (vehicles or human beings) and the overall behavior of traffic—and in terms of collective behavior when analyzed using the statistical criteria used for road traffic.

This work is currently being continued in order to study this model for successions of intersections in urban contexts, still with the objective of reducing the percentage of deadlocks during traffic simulations. Finally, this matrix description of the estimated gain from an interaction seems similar
to the theories dealing with the influence of one agent on another one initially proposed by Castelfranchi [5].

**Acknowledgements** We would like to thank Professor Dominico Gattuso (Italian University of Reggio Calabria), for granting us permission to exploit his measured data for the Roma-Zerbi intersection. The authors thank also the anonymous reviewers for their numerous constructive remarks.

The present research work has been supported by the “Délégation Régionale à la Recherche et à la Technologie”, the “Ministère de l’Éducation Nationale, de la Recherche et de la Technologie”, the “Fonds Européen de Développement Régional” (projects MIAOU, EU-CUE), the “Centre National de la Recherche Scientifique”. We gratefully acknowledge the support of these institutions.

## References

1. Adam E, Mandiau R (2005) Roles and hierarchy in multi-agent organizations In: Pechoucek M, Petta P, Varga LZ (eds) Multi-agent systems and applications IV, 4th international central and Eastern European conference on multi-agent systems: CEEMAS 2005, Budapest, Hungary, September 2005. Lecture notes in artificial intelligence, vol 3690. Springer, Berlin, pp 539–542.

2. AIMSUM2 V3.3 (1999) User's manual, Getram transport simulation systems

3. Aknine S, Pinson S, Shakun MF (2000) New coalition formation methods for multi-agent coordination. In: Group decision and negotiation, Glasgow, Scotland, July 2000

4. Bazzan ALC (2005) A distributed approach for coordination of traffic signal agents. J Auton Agents Multi-Agent Syst 10(2):131–164

5. Castelfranchi C (1998) Modeling social action for AI agents. Artif Intell 103:157–182

6. Chaib-Draa B, Moulin B, Mandiau R, Millot P (1992) Trends in distributed artificial intelligence. Artif Intell Rev 6:35–66

7. Champion A, Espié S, Mandiau R, Kolski C (2001) Multi-agent road traffic simulation: the coordination issue. In: Giambiasi N, Frydman C (eds) Proceedings of the 13th European simulation symposium, London, October 2001, pp 903–908

8. Champion A (2003) Mécanisme de coordination multi-agent à base de jeux: application à la simulation comportementale de trafic routier en situation de carrefour. PhD thesis, University of Valenciennes, France, December 2003 (in French)

9. Chan PL, Teply S (1991) Simulation of multi-lane stop-controlled T-intersections by Knosimo in Canada. In: Brilon W (ed) Intersections without traffic signals II. Springer, Berlin

10. Doniec A, Espié S, Mandiau R, Piechowiak S (2005) Dealing with multi-agent coordination by anticipation: application to the traffic simulation at junctions. In: Gleizes MP, Kaminka GA, Nowé A, Ossowski S, Tuyls K, Verbeeck K (eds) Proceedings of the 3rd European workshop on multi-agent systems, Brussels, Belgium, December 2005

11. Dressner K, Stone P (2004) Multi-agent traffic management: a reservation based intersection control mechanism. In: Proceedings of the 3rd international conference on autonomous agents and

multiagent systems: AAMAS 04, New York, July 2004, pp 530–537

12. El Fallah Segrouchni A, Demgirmenciyan-Cartault I, Marc F (2004) Modelling, control and validation of multi-agents plans in highly dynamic context. In: Proceedings of the 3rd international conference on autonomous agents and multi-agent systems: AAMAS’04, New York, July 2004, pp 44–51

13. Espié S, Saad F, Schnetzler B (1994) Microscopic traffic simulation and driver behavior modeling: the ARCHISIM project. In: Proceedings of the strategic highway research program and traffic safety on two continents, Lille, France

14. Espié S (1999) Vehicle driven simulator versus traffic-driven simulator: the INRETS approach. In: Proceedings of driving simulation conference (DSC’99), Paris, France

15. Ferber J (1999) Multi-agent systems: an introduction to distributed artificial intelligence. Addison-Wesley, Reading

16. Findler N, Stapp J (1992) Distributed approach control of street traffic signals. J Transp Eng 118(1):99–110

17. Genesereth MR, Ginsberg ML, Rosenschein JS (1986) Cooperation without communication. In: Proceedings of the 5th American association for AI

18. Georgeff MP (1983) Communication and interaction in multi-agent planning. In: Proceedings of the 3rd national conference on artificial intelligence (AAAI’83), pp 125–129, August 1983

19. Jennings N (1996) Coordination techniques for distributed artificial intelligence. In: Foundation of distributed artificial intelligence. Wiley, New York, pp 187–210

20. Jennings N, Sycara K, Wooldridge M (1998) A roadmap of agent research and development. J Agents Multi-Agent Syst 1(7):7–38

21. Leutzbach W (1998) Introduction to the theory of traffic flow. Springer, Berlin

22. Mandiau R, Grislin-Le Strugeon E, Agimont G (1999) Study of the influence of the organizational structure on the efficiency of a multi-agent system. Netw Inf Syst J 2:153–179

23. Mandiau R, Grislin-Le Strugeon E, Peninou A (2002) Organisation et applications des SMA. Hermès, Paris (in French)

24. Ossowski S (1998) Coordination in agent artificial agent societies: social structures and its implications for autonomous solving agents. In: Lecture notes of artificial intelligence, vol 1535. Springer, Berlin

25. Prentice JW (1974) The evasive action decision in an intersection accident: a game theory approach. J Saf Res 6(4):146–149

26. Reece DA, Shafer SA (1993) A computational model of driving for autonomous vehicles. Transp Res A 27(1):23–50

27. Rodriguez S, Hilaire V, Koukam A (2003) Towards a methodological framework for holonic multi-agent systems. In: Proceedings of the 4th international workshop of engineering societies in the agents, Imperial College London, UK, 29–31, October 2003

28. SciLab (2006) http://www-rocq.inria.fr/scilab

29. Shoham Y, Tennenholz M (1995) On social laws for artificial agents societies: off-line design. Artif Intell 1–2(73):231–252

30. PTV Planung Transport Verkehr AG (2003) VISSIM 3.70 User Manual, Karlsruhe, Germany

31. Yokoo M (2001) Distributed constraint satisfaction: foundations of cooperation in multi-agent systems. Springer, Berlin