Keywords

1 Introduction

Vehicles nowadays contain many sensors for perception purposes and sometimes-complementary advantages. It has also many features such as forward collision warning (FCW), automatic emergency braking (AEB), and pedestrian detection (PD). In other words, today’s vehicle has all the necessary inputs that provide a rich environment perception. Moreover, with the emergence of V2X (which includes vehicle-to-vehicle V2V and vehicle to infrastructure V2I) will play a significant role in the intelligent transportation system (ITS). It provides the accurate speed heading, the status of the brake pedal, and more, which will increase the level of vehicle’s surroundings.

Traffic congestion becomes a complicated problem that continues to grow day  by day over the world. This phenomenon is correlated to urbanization and population growth. Especially during rush hours and in work zones, traffic congestion has important impacts on air pollution [1, 2], time loss, road fatalities, several economic consequences (such as increase in fuel consumption etc), social (such as waiting time and stress) [3], and environmental consequences [4].

According to the INRIX report in 2020, drivers in London lost the most time annually to traffic congestion with about 149 hours costing 1162 euros. For American drivers it was estimated a loss of 99 hours per year for each driver, costing $1377 per year.

As reported by World Health Organization (WHO), more than 1.35 million people over the world died in a road accident, and about 20–50 million injured, many of them keeping a disability as a result of their injuries. According to the same organization, the death rate for the traffic accident in Africa is the highest. It stands at 26.6 deaths per 100,000 population.

Today and thanks to the rapid progress of wireless communication, vehicles can communicate with the outside world. It can now receive the traffic status [5], and traffic collisions. Agents are used recently as infrastructure support for traffic management and as a decision support system for traffic control [5, 6].

Using the capabilities of the connected vehicle, we proposed multi-agent intersection management based on the reservation approach. In other words, to cross the intersection, the vehicle agent must send a request to an intersection agent to reserve a trajectory.

This system is proposed for the classical intersection model, which is shown in Fig. 1. It is composed of four possible directions. Each direction can be decomposed into an inbound direction and outbound direction or both. In each incoming and outgoing direction, there are two lanes.

Fig. 1
figure 1

An intersection management system based on multi-agent

Full size image

The rest of the paper organized as follows. Section 2 represents several research topics for intersection management including classical approaches and research based on multi-agent systems. Section 3 described the general architecture of the proposed system. The operation of components is presented in Sect. 4. Finally, Sect. 5 concludes this paper with future work.

2 Related Work

2.1 Classical Approaches

The most relevant classic approaches and algorithms, which have been proposed in order to improve the vehicle traffic flow since 1960, are below:

  • TRANSYT (Traffic Network Study Tool) [7]: it is based on offline optimization that generates optimal coordination plans between the traffic lights of a network for a given period. TRANSYT requires many input parameters, such as the geometry of the intersection arteries, the vehicle flow, the rate of vehicles on each outgoing lane of each intersection (set in advance), the minimum green light time, initial fire plans, and initial values for cycle times and phase shifts. From these parameters, a mathematical model is simulated and its performance is evaluated. Finally comes the optimization stage using a Hill-Climbing optimization algorithm, which is to say gradually improving the solution by modifying the duration of the green lights and offsets between adjacent intersections.

  • SCOOT: (Split Cycle and Offset Optimization Technique) [8] a fully adaptive traffic control system developed in the UK by Transport Laboratory in 1980. It is an efficient system for a signalized road, which is used in over 130 cities and towns in the UK and overseas. For this system, electromagnetic sensors are located on each section to measure vehicle flow, detect queues due to congestion and vehicles stopped for other reasons. In order to minimize the number of vehicles stops and the length of the queue at the intersection, all those information are used to define the duration of light phases for each of the intersections in the area monitored by the system.

  • SCATS (Sydney Coordinated Adaptive Traffic System) [9, 10] developed in the 1980s operates on real-time data. It collects information by sensors, which are located in a traffic light. The implementation of this strategy takes the same form as the SCOOT strategy, namely change cycle times, phases, and offsets. This approach is based on a concept of subsystems that group (1–10) intersections per subsystem. It used a real-time algorithm of the light plan for intersection and predefined libraries, which store about 10 sets of offsets and 4 sets of greenlight duration. From these sets, the algorithm reconstructs light plans for every cycle.

  • PRODYN [11] is a decentralized and adaptive system developed by CERT in France. It is used to optimize online traffic by using a dynamic program to minimize delays at intersections by relying on a model of traffic flow over the entire horizon. Its system allows communication with a neighbor intersection in order to anticipate the incoming flows. The strategy used by this system consists of analyzing at each time step (of 5 seconds), if changing the phase is the optimal decision.

2.2 Discussion About Classical Approaches

These systems, in particular the cyclic systems, limit actions to a certain number of possibilities, most often stemming from traditional regulation: modification of phase durations, cycles, and phase shifts between neighboring intersections. Other regulatory actions can however be considered to allow a more dynamic regulation. In addition, the connected vehicles make it possible to envisage new possibilities of action that can be used for regulation, for example, communicated on the control strategy of an intersection so that the vehicle adapts its acceleration profile. Some of these systems rely on flow models to make predictions of traffic evolution. Although it seems difficult to dispense with any predictive model in an anticipatory approach, the simplicity of the perceptions of these systems does not allow a dynamic adjustment of the predictions made. This criticism can be reinforced by the fact that the connected vehicles, by their communication and co-ordination capabilities, have different flow dynamics than conventional vehicles. The spread of this type of vehicle could make the predictions made by this type of system less and less relevant, and thus reduce the effectiveness of the regulation performed.

2.3 Approaches Based on Multi-agent

Various problems related to the regulation of urban traffic have been identified in the IT community, notably by the multi-agent community [12,13,14]. We describe here several works, in their diversity, that relate to the regulation or the coordination between vehicles, at the scale of an intersection or a wider zone. In the first case, the coordination and regulation at an intersection can be considered as a problem independent of the question of global regulation on a network and we speak of “isolated” intersection (the rest of the network not being taken into consideration). In the second case, coordination takes place between the intersections in order to achieve a more coherent regulation at the network level.

For an isolated intersection, different coordination problems between vehicles may be considered and different approaches are possible for each of these problems. Many of these difficulties relate to real-time traffic assignment and the right-of-way, i.e. the authorization for a vehicle to enter the intersection, is allocated to each vehicle. Some of these approaches require a regulatory agent that applies only a regulatory policy, others involve inter-vehicular coordination.

A first approach is discussed in [15]. In this work, each vehicle communicates the information it has to others to allow vehicles to coordinate with them. The different vehicles have trajectories intersecting on points called “points of conflict”. To allocate a transit date for each vehicle, the agents’ behavior is based on a collaboration plan. In the absence of any coordination, vehicles encounter conflicts. Based on a simple method of conflict assessment, vehicles push their respective dates of entry into the intersection one by one to avoid any conflict. The collaboration plan proposed by this method allows vehicles to change the order in which their transit dates are postponed. However, the authors do not provide details of the interaction mechanism and do not indicate its properties or guarantees it provides.

Balan and Luke [16] is based on the notion of fairness for traffic regulation, proposing a control policy for intersections based on the history of vehicles. This policy reduces the variance in the total time vehicles spend waiting at  traffic lights in intersections during their journey. Each intersection has a controller capable of producing different traffic lights planes. A  traffic lights plan is a combination of durations of green, yellow, and red for each approach to the intersection, and avoids any conflict. The controller uses different scoring functions based on efficiency and fairness to evaluate each possible regulation plan. The efficiency and justice of each plan are evaluated, for different grid sizes and different traffic loads.

Some work on the isolated intersection concerns the coordination of vehicles, and others concern the regulation performed by the intersection [17]. AIM (Autonomous Intersection Management) seeks to coordinate autonomous vehicles on the intersection. This coordination involves the agreement of the right of way to vehicles, and the AIM, thus realizes a regulation of the intersection with the help of various information relating to the vehicles. The following works below are related to AIM:

In Dresner and Stone [18] proposed a right-of-way mechanism for autonomous vehicles based on reservation. This is based on a policy called FCFS (First Come First Served), granting the right of way to each vehicle by making the request, as soon as possible. This mechanism takes into account human drivers by using a conventional  lights intersection policy for human drivers, and by providing transition dates for autonomous vehicles using the FCFS policy. Although this mechanism accommodates the presence of human drivers, its main benefits are due to the use of FCFS for autonomous vehicles.

Gregoire et al. [19] allows coordination between vehicles approaching an intersection by constructing a priority graph (oriented) determining the order of admission of the vehicles. The article proposes a characterization of a feasible priority graph.

Yan et al. [20] is based on the notion of “streams” representing the possible trajectories of vehicles at the intersection. For example, all vehicles arriving at the intersection from a lane south of the intersection to a lane east of it form a current. In this approach, groups of currents are formed so that none of the currents forming a group intersect. We talk about compatible currents between them. The currents of a group can simultaneously fire to green. The problem of assigning the right of way is then represented as a problem of scheduling tasks. From the compatible current groups, groups of vehicles are formed. These groups are represented as groups of tasks, and thanks to this representation, the total evacuation of the intersection are minimized by using an exact resolution method (separation and evaluation, dynamic programming).

Vasirani and Ossowski [21] proposes a market-inspired approach to AIM. When choosing their routes, drivers often opt for the fastest route after estimating the travel time for each of the potential routes. In this model, drivers must purchase a reservation from managing agents in order to cross intersections. This reservation system provides drivers with incentives to explore alternate routes. In this mechanism, each intersection manager must determine his booking fees to maximize his profit. With a few vehicles, the intersection manager gets a small profit, but with a large number of vehicles, it loses profit because of congestion.  It  must adjust his booking fees to attract an average number of vehicles. Intersection Managers use a Q-learning to adjust these booking fees.

Kamal et al. [22] proposes an approach to building multi-agent regulation policies using unsupervised machine learning methods. On an isolated intersection, vehicles can move and avoid collisions. A traffic authority collects the information and makes case-by-case reasoning based on experience to determine the solution to be applied to resolve the current situation. Then a standards manager transforms the solutions found into standards for vehicle agents, which apply these rules using a rule engine. A reduction in the number of standards necessary to achieve the goals of the system (avoid conflicts) is also made so that the number of rules to be checked by the vehicles remains reasonable.

3 Architecture of the Proposed System

In this research, we proposed a system to manage traffic congestion in intersection based on multi-agent. It consists of two agents: Vehicle Agent (VA), and Intersection Agent (IA). Each agent is equipped with wireless communication devices (I2V/V2I).

The Vehicle Agent VA is a system installed in each vehicle. It is responsible for communicating with the Intersection agent before a distance D of the intersection to request the trajectory reservation. While the intersection agent is installed in the intersection.

The system is based on the reservation of the vehicle trajectory. In other words to pass the intersection, each vehicle agent preplans its trajectory and then send it to the Intersection agent a request for passage reservation. In addition, based on the reservation list the intersection agent will make its decision. The reservation policy is the key to reduce collision, congestion in the intersection, and waiting time.

3.1 Messages from VA to IA

There are three types of messages sent from the VA Vehicle Agent to the IA Intersection Agent:

  • Request: a message sent by AV to reserve a trajectory. In this message, the AV specifies several parameters of the car (Direction, Vehicle ID, Priority, Vehicle Speed, Width, and Length, Position)

  • Change—Request: message sent if the driver wants to change the direction.

  • Accident: If the vehicle is down, at this moment an “accident” message is sent to the AI to inform it.

3.2 Messages from IA to VA

The Intersection agent can send to the vehicle agent three types of messages:

  • Confirmation: based on the reservation request that the VA send, the IA check the reservation table to verify if there is a conflict with other reservation requests by other vehicles. This message sent to the VA to inform it that his request is approved and that he can follow the proposed path.

  • Proposition: If the pre-planned trajectory is already occupied or a vehicle is  down in the intersection. The AI sends this message to propose to the AV to accelerate, decelerate the speed, or change the way.

  • Acknowledge: We send this message to VA if the IA receives the message “accident” (Fig. 2).

    Fig. 2
    figure 2

    An abstract view of the interaction between VA and IA

    Full size image

4 Agent Actions

For each agent, we specify many rules that should respect by the VA and IA to assure a good management of the traffic congestion.

4.1 Rules of the Vehicle Agent

The vehicle agent must respect the following orders:

  • Vehicles cannot cross the intersection without sending a passage reservation request.

  • Using an embedded system, the VA gets the dynamic information of the vehicle such as: speed, position, direction …

  • Before the distance D of the intersection, the vehicle agent consists of sending a request to reserve the trajectory.

  • Once the AV receives the confirmation message, it can follow the proposed path.

  • If the vehicle agent has received a confirmation message (following the last request) and the driver wants to change the trajectory, the AV Vehicle Agent must send a Change-Request message request with the new parameters. In this case, the old reservation request sent by the VA will be deleted, and the reservation list will be updated.

  • If the vehicle is broken down in the intersection, the VA sends the message “accident” to the IA.

The following figure shows the flow diagram of the vehicle agent (Fig. 3).

Fig. 3
figure 3

Vehicle agent behavior flow chart

Full size image

4.2 Rules of the Intersection Agent

The following rules must be respected:

  • Once the IA receives the reservation request, it verifies in its database to check if there is a possibility to accept it or not. If yes, then it sends the Confirmation message. Otherwise, it sends the message proposition that contains the unoccupied path.

  • If the VA sends the message “change-request”, the first reservation will be deleted from the database of reservation. And the IA verifies in its database to check if there is a possibility to accept the new reservation.

  • If IA receives the message “accident”, it must send the message Acknowledge to the vehicle, update the reservation list and alert other vehicles that pre-planned the same trajectory by proposing to decelerate or change the track completely.

To better explain the operation of the intersection agent, we present the following diagram (Fig. 4).

Fig. 4
figure 4

Intersection agent behavior flow chart

Full size image

5 Conclusion

In this paper, we proposed multi-agent intersection management based on the reservation approach. The main objective of this system is to reduce traffic congestion at intersections, waiting time, and fuel consumption.

We started the implementation of our system using the SUMO simulator and we want to test our system on more complicated traffic networks.

As part of future work, we would like to compare our approach with existing methods such as traffic light control and platoon-based multi-agent intersection management. Then evaluate the performance of our proposed system in different traffic conditions.