Modeling and Delay Analysis of Unmanaged Intersections with Microscopic Vehicle Interactions
BY CHANGLIU LIU
With the emergence of autonomous vehicles, it is important to understand how the microscopic interactions of those vehicles affect the delay of the macroscopic traffic flow, especially at unmanaged intersections.
There are two major types of traffic models that support the analysis of delay and congestion: 1) microscopic simulation models where every car is traced and 2) macroscopic flow models where traffic is described by relations among aggregated values such as flow speed and density, without distinguishing its constituent parts.
Though microscopic simulation models provide precise description of inter-vehicle interactions, it can be time-consuming to obtain the micro-macro relationships by simulation. Only ``point-wise" evaluation can be performed in the sense that a single parametric change in vehicle behavior requires new simulations. To gain a deeper understanding of the micro-macro relationships, an analytical model is desirable.
Macroscopic flow models provide a tractable mathematical structure with few parameters to describe interactions among vehicles. However, existing models can only account for simple first-in-first-out (FIFO) policies at intersections. A vehicle policy refers to a principle of action adopted by the vehicle, which determines how that vehicle responds to others.
In order to quantify the traffic delay generated under different vehicle policies at unmanaged intersections, we introduce a novel analytical traffic model, which absorbs the advantages of both the microscopic simulation models and the macroscopic flow models. The new model is event-driven, whose dynamics encodes equilibria resulting from microscopic vehicle interactions.
The Traffic Model
Microscopic Interactions
It is assumed that vehicles at intersections have fixed paths. The desired traffic-free time for vehicle i to pass the intersection is denoted tio. At each time step, vehicle i decides its passing time ti based on its desired time tio and its observation of others' passing times at the last time step, according to its policy.
Nash Equilibrium
The Nash Equilibrium among the first i vehicles is a state that no vehicle is willing to change its passing time before the arrival of the (i+1)th vehicle. It is assumed that an equilibrium can be achieved in negligible time. Hence, the system moves from the (i)th equilibrium to the (i+1)th equilibrium when the (i+1)th vehicle is included. The projected passing time for a vehicle may change from one equilibrium to another equilibrium, but will eventually converge to the actual passing time.
Macroscopic Model
The macroscopic traffic model then describes the transitions among consecutive equilibriums. It is an event-driven stochastic system with the state being the traffic delay at all lanes and the input being the incoming traffic (the lane number and the arrival time of the next vehicle) as shown in the figure below.
The problems of interest are:
* Does the sequence of the distributions of delay converge? Divergence corresponds to the formation of congestion.
* If converged, what is the steady state distribution of delay?
Under the model, the questions can be answered either through direct analysis or event-driven simulation. Both methods are more efficient than conventional time-driven traffic simulation.
Example
Consider the above intersection with four incoming lanes. A conflict is identified if two incoming lanes intersect with each other. These relationships are described in the conflict graph on the right with the nodes being the incoming lanes and the links representing conflicts.
When there are conflicts, vehicles from the corresponding lanes cannot occupy the intersection at the same time. The left figure illustrates the desired time of occupancy (centered at tio) for vehicles coming in the four lanes. According to the conflict graph, the scenario is infeasible as vehicles 1, 2, 3, and 4 cannot occupy the intersection at the same time.
To resolve the conflicts, the vehicles may act according to the FIFO policy or the flexible order (FO) policy. We assume that all vehicles are homogeneous. Under FIFO, the vehicles should pass the intersection according to the order determined by their desired passing times. Hence, vehicles 2 and 3 yield to vehicle 1, and so on. The middle figure shows the actual time of occupancy when all vehicles adopt the FIFO policy. Under FO, high priority vehicles may yield to low priority vehicles if low priority vehicles can arrive earlier. The effect of FO is illustrated in the right figure above. Vehicles in the same direction tend to form groups and pass together. These two scenarios generate different delays. The proposed traffic model is able to predict the distribution of delay without traffic simulation.
Traffic Delay Analysis
The following two components in a vehicle policy strongly influence the traffic delay: 1) determination of the passing order, and 2) the required temporal gap between two consecutive vehicles to pass the intersection. The following figure illustrates how the expected vehicle delay is affected by the passing order (FIFO and FO), temporal gap, and traffic density λ in a two-lane intersection. The expected delay is computed through direct analysis.
For all scenarios, FO results in smaller delay than FIFO. However, FO sacrifices fairness by not obeying the passing order determined by the desired passing time. As a consequence, certain vehicles may experience larger delay compared to that in the FIFO case. The tradeoff between fairness and efficiency in different policies will be studied in the future.
In general, a larger temporal gap results in larger delay. The temporal gap is a design parameter in vehicle policies, which is affected by the uncertainty in perceptions. When there are larger uncertainties in perception, in order to stay safe, vehicles tend to maintain larger gaps to other vehicles. The trade-off between safety and efficiency under imperfect perception will also be studied in the future.
Applications of the Model
The analytical model helps us understand the consequences of the microscopic behaviors on the macroscopic system. It can be applied toward multiple directions, such as vehicle policy optimization, infrastructure optimization, traffic prediction, and traffic optimization.
In the future, we will extend the analysis to more complex vehicle policies, more complex road topologies, multiple intersections, and heterogeneous traffic scenarios.
Changliu Liu is a postdoc at Stanford, supported by the CARS postdoctoral fellowship in transportation. She received her PhD degree from Berkeley in 2017 and will join the Robotics Institute at Carnegie Mellon University as an assistant professor January 2018.
References:
C. Liu, and M. Kochenderfer, "Analytically modeling unmanaged intersections with microscopic vehicles interactions", under review in Intelligent Transportation Systems Conference (ITSC), 2018. arXiv:1804.04746
C. Liu, and M. Kochenderfer, "Analyzing traffic delay at unmanaged intersections", under review in IEEE Transactions on Intelligent Transportation Systems Conference, 2018.
