Alleviating Road Traffic Congestion with Artificial Intelligence

1 Introduction

Traffic congestion is one of the world's most costly and pressing problems. It leads to lost time and productivity, reduced air quality, and increased operating expenditures. While infrastructure expansions may help mitigate this problems, they are costly, disruptive, and require predicting demand and capabilities years, if not decades, into the future. On the positive side, recent advancements in AI pave a path towards improved utilization of existing infrastructure through autonomous and self-learning controllers.

A large body of work [Kockelman et al., 2017; Zantalis et al., 2019] was devoted in recent years to AI technology integration within intelligent transportation systems. In this paper, we present and discuss a subset of these works which relate to congestion alleviation. Specifically, we discuss three applications where AI controllers present significant potential towards congestion mitigation.

1. Intersection Management. Road intersections introduce traffic bottlenecks which are a known and well studied source of traffic congestion [Tirachini, 2013]. We discuss two established AI approaches towards optimized intersection management. Namely, signal control optimization through deep reinforcement learning and reservation based trajectory coordination.
2. Road Pricing for Optimized Traffic Flow. Selfinterested drivers follow routes which optimize their own personal utility while potentially acting suboptimal with respect

to the entire system (utility summed over all drivers). This phenomena, measured by the price of anarchy [Roughgarden and Tardos, 2002], is a known source of avoidable congestion. We discuss two established AI approaches towards road pricing protocols which attempt to align the drivers' personal utility with that of the system's. Namely, a game theoretical approach and a reinforcement learning approach.

(3) Fully or Partial Autonomous Driving. Erratic driving, of even a single vehicle, can lead to congestion that is induced by shock waves [Richards, 1956], which are also known as stop-start traffic waves, ghost jams, or traffic shocks. Recent autonomous driving controllers present a viable approach towards mitigating such adverse behaviors. We discuss AI approaches towards autonomous motion planing and control that stabilizes traffic flow progression by damping shock waves.

We conclude the paper by presenting open challenges relating to safety assurances in reinforcement learning, performance guarantees, interpretable and foreseeable autonomous control, warm start learning in reinforcement learning and knowledge transfer issues, public and governmental acceptance issues, and infrastructure compatibility issues.

2 IntersectionManagement

Travel time studies in urban areas show that 12-55% of commute travel time is due to delays induced by signalized intersections (stopped or approach delay) [Tirachini, 2013]. Hence, optimized intersection management has the potential of reducing commute time, traffic congestion, emissions, and fuel consumption, while requiring minimal infrastructure changes. A line of publications attempted to harness modern AI techniques towards this control optimization problem. This section surveys two such approaches. Namely, signal control optimization and reservation-based coordination.

2.1 Signal Control Optimization

A signalized intersection is composed of incoming and outgoing roads where each road is affiliated with one or more lanes. A signal controller must assign right of passage to phases where each phase is affiliated with a specific traffic movement through the intersection (incoming to outgoing roads/lanes). Two phases are defined to be in conflict if they cannot be enabled simultaneously (their affiliated traffic movement is intersecting). During the signal operation, vehicles are assumed to continuously arrive on incoming roads where each vehicle is associated with a specific outgoing road. At every time step, the signal controller is required to assign rightof-passage (green light) to a set of non-conflicting phases such that some utility measurement is optimized. The utility to be optimized is commonly defined as the sum of vehicles' delay imposed by the intersection [Mousavi et al., 2017; Ault et al., 2020].

Given that signalized intersections vary in their layout and demand profile, optimized control policies are unique and instance dependent. Consequently, signal controllers should be trained and optimized according to observed conditions at the associated intersection. Such online optimization of signal controllers requires: (a) sensing the state of approaching traffic (e.g., number and position of approaching vehicles, approaching speeds, vehicle queue length, waiting times) aggregated by approaching lanes, and (b) defining a controller that takes the current state of traffic as input and outputs the next phases to be enabled (which is translated to a green, yellow, and red assignment for each light box).

Recent publications [Mousavi et al., 2017; Ault et al., 2020] proposed to utilize state-of-the-art reinforcement learning (RL) algorithms for online optimization of signal controllers. In this approach, the state of the intersection is usually defined by the set of incoming vehicles (incoming lane, speed, waiting time, queue length) and the current signal (enabled phase) assignment. An RL agent is tasked with optimizing a policy which maps states to signal (phase) assignment. Such learning is commonly done using a value-based approach (specifically a deep Q-learning approach [Mnih et al., 2015]) which attempts to learn the expected future utility from every action at a given state. The controller is then directed towards actions that maximize the expected future utility. Such an approach showed a potential reduction of up to 73% in vehicle delays when compared to fixed-time actuation [Mousavi et al., 2017].

Recent work showed further potential for accumulated delay reductions when utilizing Multiagent RL for coordinated control of multiple adjacent intersections [Chen et al., 2020].

2.2 Reservation-based Coordination

Looking towards a future when most vehicles are autonomous and connected, researchers are developing reservation-based intersection management protocols. By relying on the fine and accurate control of connected and autonomous vehicles (CAVs) along with their communication capabilities, intersection management protocols coordinate multiple vehicles simultaneously across an intersection. Such protocols have been shown to lead to significant traffic delay reductions when compared to traditional traffic signals. One prominent example of such a protocol is the autonomous intersection management (AIM) protocol [Dresner and Stone, 2008]. The AIM protocol defines two types of autonomous agents: intersection managers (IMs), one per intersection, and driver agents, one per vehicle. An intersection manager is responsible for directing incoming vehicles through its assigned intersection, while the driver agents are responsible for controlling the CAV to which they are assigned. To improve the throughput and efficiency of the system, the driver agents "call ahead" to an intersection manager and request path reservations (space-time sequence) within the intersection. The IM then determines whether or not this request can be met by checking whether it conflicts with any previously approved reservation or any potential human operated vehicles (HVs). If the IM approves a driver agent's request, the driver agent must follow the assigned path through the intersection. On the other hand, if the IM rejects a driver agent's request, the driver agent may not pass through the intersection but may attempt to request a new reservation.

A line of publications followed Dresner and Stone's 2008 seminal work by considering variants of the originally presented reservation based approach. These approaches include reservation coordination methods that are modeled as a quadratic program [Riegger et al., 2016], a model predictive control [Kim and Kumar, 2014], and a joint optimization (path coordination and trajectory control) problem [Malikopoulos et al., 2021]. Other approaches consider platooning and batch reservations [Bashiri et al., 2018], game theoretic/incentive based [Sayin et al., 2018], auction based [Levin and Boyles, 2015], and RL-based [Wu et al., 2019] techniques for allocating reservations. Recent work also considered mixed traffic scenarios where human operated vehicles and CAVs coexist [Sharon and Stone, 2017].

3 Dynamic Road Pricing for Optimized Traffic Flow

Another significant sources of traffic congestion stems from the fact that drivers are self-interested when making travel choices: for instance, they (quite naturally) select the route that optimizes their own utility. Under such conditions, the sum total of individual travel times (i.e., the social welfare) can be arbitrarily worse than it would be were a centralized controller to assign routes for the purpose of achieving maximum social welfare [Roughgarden and Tardos, 2002]. In order to combat this inefficiency, researchers have devised various approaches for computing and assigning optimized travel routes. A line of publications assume the ability to assign dynamic road pricing per road segment and that by doing so, the route choice of self-interested drivers can be manipulated. In this sense, the problem of assigning optimized travel routes is reduced to assigning a set of road prices that induce optimized flow.

3.1 Game-theory Approach

Self interested agents that are routed in a congestible network, such as vehicles in a road network, impose a user equilibrium (UE) that is often far worse than the system optimum (SO) flow [Roughgarden and Tardos, 2002]. Charging marginal cost tolls (MCT), in which each agent is charged a toll equivalent to the damage it inflicts on all other agents, results in a UE that achieves SO performance [Pigou, 1920].

Calculating the MCT for a given passenger, on a given path, i.e., the damage that the passenger inflicts on other passengers by traversing the path in question, is challenging without making several simplifying assumptions (e.g., welldefined and known latency functions) that do not hold in most traffic models and certainly not in real-life traffic. Recent work [Sharon et al., 2017a; Sharon et al., 2017b] suggested a model free technique, denoted∆-tolling, for evaluatingMCT. ∆-tolling was proven to result in exact MCT only when traffic accumulation follows the Bureau of Public Roads (BPR) latency function [Moses and Mtoi, 2017]. By contrast, when the BPR assumption does not hold, ∆-tolling provides only an evaluation of the true MCT. Nonetheless, experimental results using a cell transmission model [Daganzo, 1994] presented a reduction of up to 32% in total system travel time when using ∆-tolling and up to 52% when tuning the affiliated hyper parameters with standard black-box optimization techniques [Mirzaei et al., 2018].

Looking towards real-world application of MCT-based systems, recent publications examined various implementation issues. Among them, the impact of partial participation in a MCT scheme [Sharon et al., 2018; Hanna et al., 2019] and worst-case performance guarantees for imposing inaccurate (evaluation-based) MCT [Sharon et al., 2019].

3.2 Reinforcement-learning Approach

RL approaches for learning and setting pricing policies were considered in previous publications [Chen et al., 2018]. In such cases, multiagent RL formalization is used to train a pricing policy. The state space is defined as the observed traffic flow per road segment. A set of priced road segments in a given road network defines the action space as a Cartesian product of the allowed price change over these road segments. The reward function is simply minus total system travel time per time step. The pricing policy is trained such that the expected sum of future rewards is maximized.

Chen et al. 2018 showed that applying a policy gradient approach within an actor-critic architecture can outperform ∆-tolling by up to 15% (reduced total system travel times) when only a subset of road segments can be priced in a given network. These results are to be expected as ∆-tolling-and any MCT based pricing scheme for this matter-assume that all road segments can be priced.

4 Autonomous Driving

Erratic or unpredictable driving of even a single vehicle can lead to substantial traffic congestion due to shock waves [Richards, 1956]. Luckily, autonomous vehicles (AVs) provides a viable way towards predictable and smooth vehicle control. Moreover, such AV technology showed potential for proactively stabilizing traffic flow and thus lead to reduced congestion. AV technology has evolved significantly in recent years to a point where many researchers agree that it is not a question of 'if' but a question of 'when' will the technology be viable.

4.1 Motion Planning

Researchers have proposed to address the AV motion control problem using classic Motion planning techniques [Frazzoli et al., 2002]. However, it is challenging to apply such techniques in highly dynamic and stochastic environments such as the driving domain. The uncertainties introduced by other actuators (e.g., vehicles, pedestrians, traffic signals) and control objectives (e.g., Car-following, lane-keeping, trajectory following, merging) necessitate a large variety of coordinated low-level control tasks as well as frequent replanning operations. Consequently, many researchers turn towards RL techniques that can learn a general and robust control policy.

Aradi 2020 provided a survey on deep RL hierarchical motion planning approach in which different layers of motion planning, namely, strategic decisions, trajectory planning, and control, are presented and combined to create the desired robust driving control policy. In a more specific example, Shalev-Shwartz et al. 2016 addressed the high-level task of long term driving strategies and trajectory planning. They addressed this planning problem by applying the REINFORCE algorithm [Williams, 1992] (Monte-Carlo policy gradient) along with a Q-estimator as a baseline. Both the policy and the Q-estimator were defined using deep neuralnetworks. This approach was shown to increase driving stability and predictability while satisfying safety constraints.

4.2 Stabilizing Traffic Flow

Leveraging previously proposed trainable AV motion controllers, researchers examined incorporation of flow stabilizing behaviors. This is noteworthy as traffic flow instabilities are known to contribute to adverse congestion, e.g., through traffic shock waves. Zheng et al. 2020 demonstrated how few AVs can potentially stabilize mixed (human operated vehicles and AVs) traffic flow progression. Such stabilizing is usually achieved through speed and headway distance control that optimize string stability. Results by Zheng et al. suggest that as few as 5% AV presence can lead to 6% increase in traffic flow speed. Vinitsky et al. 2018 suggested a deep RL approach for AV control with the objective of stabilizing traffic flow when entering a road bottleneck. Example of such a bottleneck is a bridge with a reduced number of lanes as compared to its incoming road. Vinitsky et al. showed that training AVs towards flow stabalizing behavior using trust region policy optimization (TRPO) [Schulman et al., 2015] can lead to 25% throughput improvement at high inflows when as little as 10% AV penetration levels are considered. Addressing the scalability issues in these approaches, Cui et al. [Cui et al., 2021] proposed to apply a transfer RL approach that can handle open-road settings where vehicles can dynamically join and leave a traffic flow composed of hundreds of vehicle.

Finally, Stern et al. 2018 provided a real-world demonstration of how flow-stabilizing AV controllers contribute to smooth and predictable driving which mitigates adverse shock waves. Moreover, Stern et al. demonstrated how a single AV can actively dampen shock waves initiated by other vehicles in a real-world setting.

5 Open Challenges

Several open challenges hinder the real-world implementation of the aforementioned technologies. Next, we briefly highlight some of these challenges.

Safety concerns. Common reinforcement learning (RL) algorithms rely on extensive exploration of the state and action space to discover an optimized control policy. In the discussed traffic domains, such exploration can lead to unacceptable safety violations. Notably, a large body of work was devoted towards safe RL [Garcıa and Fern´andez, 2015] and stable performance during RL training [Schulman et al., 2015]. Still, applicability and algorithmic adaptations studies towards the discussed traffic applications need to be established.

Predictability. Due to the non-deterministic nature of realworld control problems, RL-based controllers are commonly limited to a single-step planning horizon. That is, given the current state of the environment, the RL agent computes an action to be taken at the current time step, but does not commit to any future actions. While allowing the RL agent flexibility to immediately adapt and respond to the environment, this fact reduces the ability to regulate the RL agent's behavior and predict its actions. Moreover, the aforementioned traffic applications involve environments where multiple actuators (in the form of vehicles, infrastructure, pedestrians) operate in conjunction. In such cases, actuator predictability can foster more efficient and safe coordination and should thus be aspired for.

Efficient Controller Training. Training an RL controller is often slow, sample inefficient, and brittle. When it comes to traffic applications, such training can be prohibitively expensive. As a result, integration of warm start learning from demonstrations [Hester et al., 2018] and knowledge transfer approaches [Parisotto et al., 2015] should be examined and adapted towards RL-based traffic applications.

Public and Governmental Acceptance. Following the aforementioned safety, predictability, and efficiency concerns, some people deem AI technology as not trustworthy when safety-critical tasks are considered. Such trust issues can lead to reduced public and governmental willingness to apply the discussed AI-based methods. AI algorithms and approaches that integrate legal, ethical, societal and economic impact considerations can address such trust issues and should thus be sought after. Relevant impact considerations can be found in legal documents such as the framework for trustworthy AI proposed by the European Commission [European Commission Press Release, 2021].

Infrastructure Compatibility. Real-world implementation of traffic controllers is restricted by stringent standards and regulations. In the area of traffic controls, the National Transportation Communications for Intelligent Transportation Systems Protocol (NTCIP) [NEMA, 1996] is a family of standards that provides protocols and the vocabulary necessary to allow electronic traffic control equipment from different manufacturers to operate with each other as a system. In spite of such well defined protocols, AI-based traffic controllers are often developed with no regards to standardization. This inconsistency might lead to substantial infrastructure compatibility issues and should thus be avoided.

Acknowledgments

Much of the research leading up to, and presented in, this paper was a joint effort with Peter Stone, Stephen Boyles, Josiah Hanna, James Ault, and Aaron Parks-Young.