The use of a multi-agent approach in the design of a traffic simulation tool is innovative since most of actual tools are still based on mathematical approach. In this paper we present a multi-agent approach to simulate in a realistic way the traffic phenomenon at junction. We use a multi-agent coordination approach which is improved by an anticipation algorithm based on constraints processing. The resulting tool is validated by comparison between simulated flow and real flow measured at a real junction.
the different moves (inside the intersection) have to be limited in order to reduce the number of conflicts Moreover each tool uses its own internal rules to limit the occupancy of the inner space of the intersection. In AIMSUN [1] for example, users can configure a specific parameter called "yellow box" and thus define a minimal speed that the vehicles inside the crossroad have to practice so that other vehicles can enter.
Such tools are sometimes sufficient for superficial traffic studies, but are not acceptable when the question is to mimic actual behavior. Indeed, no more than two vehicles are present inside the intersection at the same time which is not realistic at all. Moreover these tools allow neither a good accuracy of traffic flow (and jam...) for high density traffic, nor the simulation of a surrounding traffic for a driving simulator.
In opposition to this "mathematical approach", the "behavioral approach" produces an emerging traffic
by managing interactions between various actors of the road situations (car drivers, pedestrians, road
operator, ...). The resulting traffic is therefore the sum of all actors’ individual actions. ARCHISIM is a behavioral
traffic simulation tool developed by INRETS [
The computing model of ARCHISIM follows a multi-agent architecture. Each simulated driver is an autonomous software agent which evolves in a virtual environment and interacts with the other agents of the simulation performing its goals according to its skills and the current situation.
At each simulation step, an agent receives a set of information describing the surrounding situation in the environment. Thanks to these informations, each agent takes its own decision which results in a longitudinal and lateral acceleration for the next time step.
The novelty of ARCHISIM lies in the ability for a driving simulator to take part in the traffic simulation. In other words, ARCHISIM is able to generate a surrounding realistic traffic for a human driver in a simulator. The agents interact with the driving simulator like with any other vehicles of the simulation.
The traffic model of ARCHISIM has been validated for highway situation [
When crossing an intersection a real driver has to solve its conflicts with other vehicles. In our simulation context, this driving task can be expressed as a multi-agent coordination issue: all agents reaching a crossroad have to coordinate their actions in order to avoid accidents and deadlocks.
Coordination concerns all local processes that allow to achieve a global state of the system. Many
definitions exist in literature, each of them highlights a particular point of view. For Jennings, coordination
is the process which allows an agent to reason about its own actions and the actions of other agents in order
to ensure that the global system correctly behaves [
Originally, first works on multi-agent coordination have investigated the coordination from a cooperative
viewpoint. They made the assumption that all agents were motivated to achieve a common goal. We can
quote for instance Lesser and Corkill’s works whose model was based on exchanged messages describing
aims, priorities and preference of the agents [
More recently, this background of cooperative agents has been discussed and coordination has been
considered from a competitive way. The idea is that each agent has individual motivation, acts to achieve
its own goal and interacts with other agents to ensure some global properties of the system. In [
Crossing an intersection is a driving task which differs from one country to another. In the south of Europe, this task is mostly competitive especially for latin drivers. In the northern countries, the crossing is less competitive and more cooperative. The coordination mechanism has to be flexible in order to reproduce the large variety of drivers’ behavior. 3.2
The coordination mechanism used in ARCHISIM is based on the modeling of conflicts inside the intersection. This modeling applies a breaking down of the complex interactions between agents in elementary situations involving two agents.
An actual driver perceives a complex crossroad as a succession of elementary intersections of type T or X. A roundabout for example is a succession of T intersections. The interactions between drivers in an elementary intersection are regulated by priority relations defined in the Highway Code. Such a priority relation can be expressed by the predicate . In a X intersection, four interactions are possible and can be illustrated by the following conjunction: 1. 2. 3.
over : no conflict exists between the agents
and :
comes from a minor road or has a sign and consequently has no priority : this situation is the dual of the previous situation : and
both have the priority, the figure 1 is an illustration of such a situation
The coordination mechanism has the following dynamics. An agent near an intersection searches all
vehicles with which it is conflict. For each of them, the agent assesses the priority relation it has. Each
priority relation is used as a local rule which indicates to the agent if it has to accelerate or slow down.
When multiple priority relations are involved in its current situation, the agent chooses the behavior which
induces the lower speed. The figure 2 is a synthesis of the coordination mechanism. For a more complete
description of this coordination mechanism, the reader can refer to [
In order to obtain a valid overall traffic flow, the behavior of agents inside the intersection has to be as realistic as possible. The individual practices differ from one country to another. For example the Highway Code is barely respected by latin drivers and some psychology studies show that in other countries drivers tend to develop their own informal rules [2].
To take these features of the driving task into account, the agents have the possibility to alter the rules of the Highway Code with more informal rules during the second step of the coordination algorithm. For example, the following priorities can be considered by an agent: priority relating to speed: a driver arriving at an intersection and having priority (from the Highway Code point of view) tends to lose his priority if he perceives a vehicle approaching with a high speed priority relating to impatience: a driver stopped for a long time tends to consider he has priority on the other vehicles
The introduction of such abilities improves the local behavior of agents and consequently, by emergence, improves the global traffic obtained. In specific conditions such practices can lead to deadlocks inside the intersection. Indeed, the non-respect of several rules promotes the occupancy of the inner center of the crossroad but increases the risk of having a deadlock (figure 3).
We claim that if agents have opportunistic behavior they also need anticipation abilities in order to avoid undesired situations like deadlocks. 4 4.1
Anticipation is a general concept and many definitions exist. Rosen’s one is usually the most used in
literature: An anticipatory system is a system containing a predictive model of itself and / or of its environment
that allows it to change current state at an instant in accord with the model predictions pertaining to a later
instant [
In the field of multi-agent system, anticipation is used to construct adaptive and complex behavior like
in video game for instance [
UndesiredStatesList out: ActionsList
) begin propagation( for each )
, undesiredStateSearch( then ,$ ) undesired states. In this context, anticipation is viewed as a process trying to keep the system in a desired state.
- A mental representation of an agent is a triplet in which:
We introduce a formal framework for preventive anticipation by using constraint processing techniques [
Based on this representation, each agent tries to predict the future state of the system, in other words it
tries to determine how the actions of the agent will make the system evolve. In our framework of anticipation,
we consider that each action has direct and indirect effects. A direct effect of an action is modeled by adding
or deleting a relation in the set . Indirect effects are computed by using propagation techniques over direct
effects.
induce an undesired state. Undesired states are expressed as a domain list which is a parameter of the
algorithm. The first step of the procedure anticipate starts by making a first propagation over . This is
performed by an external propagation function. Classic algorithm like AC-3 [
The function undesiredStateSearch scans the list and verifies that the undesired state it holds are not present in the mental representation .
end end defining the domain of each agent in - function undesiredStateSearch(in: , $ UndesiredStatesList ) begin for each if
do domainSearch( , then ) ’.
return(true) end end A in its mental representation , this means that has inferred that will be blocked Here we present the use of our formal framework to avoid deadlocks when simulating traffic at junction in the ARCHISIM tool. To explain our model, we consider an agent located at the entrance of a crossroad (figure 6).
The set can be built with the agents present inside the intersection and perceived by . The domain associated to each agent of is temporal and expresses the next time step. For example, if an agent has during the interval to .
The set is composed with blocking relation. Three types are considered: 5.1
The application of the anticipation algorithm gives the following reasoning: $ & Finally, has no other option and has to stop. The anticipation algorithm applied by does not change its actions list. With the notion of impatience, it considers it has priority after a sufficient time and decides to accelerate. The evaluation of our multi-agent model has been led in two parts. The first one results in tests and visual analysis of individual behaviors. As the analysis of the individual behaviors is completely subjective, we use different scenarii allowing to place the agents in situations of traffic suitable for the appearance of deadlocks.
signalized intersection with different traffic densities unsignalized intersection with different traffic densities sequences of double left-turn (with and without long vehicle)
The figure 7 shows how our anticipation algorithm reduces the number of deadlocks during the simulation of a non-signalized intersection. For a one hour simulation with non-anticipatory agents, the number of deadlocks varies from 0 to 35 according to the flow. When the agents have anticipation abilities, the number of deadlocks remains almost constant and close to zero for simulated flows going up to 800 vehicles/hour per axis.
To be more accurate in our evaluation, we have tried to simulate the traffic of a real crossroad and compare the traffic data obtained by simulation with real measures. 6.2
The intersection used for this evaluation is located in the city of Reggio (Calabria) in Italy. This intersection makes the junction between a main road going from north to south and a secondary street (from east to west). It is signalized by two stop signs installed on the secondary trunk road. Each arm of the junction has two lanes and the inner center is large enough to allow storage of vehicles.
The traffic data was measured manually by the University of Reggio Calabria within the intersection between 12:30 AM and 1:30 PM on a normal weekday. For each arm of the intersection, the entry flow is expressed in a number of vehicles per hour and perrcentage of turning movement (right or left turn, straight ahead).
From this data, we have generated a traffic demand which has been used in ARCHISIM to generate simulated vehicles two hundred meters before the intersection. Virtual sensor has been used to measure the flow of vehicles.
Simulations were carried out according to two experimental conditions. In the first experiment, only the
coordination mechanism [
The figures 8 to 11 draw the comparison between the simulated flows obtained with or without anticipation and the real flow measured. For all graphs, the time is expressed as five minutes’ period. The figures 8 and 9 relate to the principal axis. The figures 10 and 11 describe the flows of the secondary axis. 30 Time (min) 30 Time (min) 30 Time (min)
In all cases the best results are obtained by using anticipatory agents. To qualify more precisely these
30 Time (min) 40 50 60
The values obtained are, for three out of the four axis, lower than 0,1 what corresponds to an error lower than 10% (table 1). In the literature, a good simulation of traffic often offers an error rate lower than 15%. The results of the curve of the figure 11 are not very representative since the simulated flows are weak and not very significant.
North/South South/North East/West West/East reference behaviour 0,06 0,03 0,15 0,32
anticipatory behaviour 0,04 0,03 0,06 0,30
Min Max 600 900 680 980 300 600 0 60 In this article, we have presented the use of a multi-agent approach in the design of traffic simulation tool. In particular, we have introduced an original framework for anticipation in a multi-agent system based on constraint processing techniques.
This framework has been instantiated and used to avoid deadlocks when simulating traffic at junction. The resulting simulation tools have been evaluated by comparison with a real intersection. These experimental results confirm the relevance of the use of multi-agent techniques to develop a traffic simulation tool.
Researches are actually made to improve the realism of simulation at junctions. In particular, the multiagent model will be extended to manage lateral acceleration and give more realistic behavior to simulated drivers.
[1] Aimsun. AIMSUN 5.0 Microsimulator User’s Manual. TSS-Transport Simulation Systems, 2005. [2] Gunilla M. Björklund and Lars Åberg. Driver behaviour in intersections: Formal and informal traffic rules. Transportation Research Part F, 8:239–253, 2005.