Altruistic Autonomy: Beating Congestion on Shared Roads

Erdem Biyik, Daniel A. Lazar, Ramtin Pedarsani, Dorsa Sadigh

TL;DR

This paper explores how autonomous vehicles (AVs) can be programmed to behave "altruistically"—willingly taking slightly longer routes to alleviate overall traffic congestion. By modeling roads shared by selfish human drivers and coordinated AVs, the authors demonstrate that even a small degree of altruism can reduce total system latency by a factor of four compared to worst-case selfish behavior.

What Problem Does This Paper Address?

Traffic congestion is a massive economic and social drain, often caused by the "Price of Anarchy"—the inefficiency that arises when every driver selfishly chooses the quickest route for themselves. While previous research has looked at using tolls or incentives to manage traffic, this paper investigates a new lever: the inherent programmability of autonomous vehicles.

The challenge lies in the "mixed-autonomy" transition period, where AVs must share the road with unpredictable, selfish human drivers. Standard routing models often assume that road latency simply increases with flow. However, real-world traffic has a "congested regime" where, past a certain density, flow actually decreases as latency skyrockets (think bumper-to-bumper traffic). The authors set out to model how AVs—which can increase road capacity through platooning—can be routed to keep the entire network out of this high-latency congested state.

Methods

The authors develop a formal model of traffic flow based on the Fundamental Diagram of Traffic, which relates vehicle density to flow.

Key methodological contributions include:

  • Mixed-Autonomy Latency Model: A mathematical framework that accounts for how the "autonomy level" (the fraction of AVs on a road) shifts the critical density point where a road becomes congested.
  • Robust Best Nash Equilibrium (RBNE): An algorithm to find the "best" selfish equilibrium that is also resilient to unforeseen spikes in traffic demand.
  • Best-case Altruistic Nash Equilibrium (BANE): A strategy for a social planner to route AVs based on an "altruism profile"—a distribution of how much extra delay AV users are willing to accept (e.g., "I'm okay with a route that is 20% longer if it helps the city").
  • Optimization Algorithms: The authors provide polynomial-time algorithms ($O(N^4)$ for selfish robustness and $O(|K|N^5)$ for altruistic routing) to solve these complex coordination problems.

Datasets

The paper does not use a static dataset. Instead, the authors validate their theoretical models using SUMO (Simulation of Urban Mobility), a high-fidelity microscopic traffic simulator. They simulated realistic driving scenarios, such as a network of parallel roads in Los Angeles (e.g., Coldwater Canyon vs. the 405 freeway), to compare theoretical predictions with simulated vehicle behavior.

Key Insights and Ideas

  • Capacity is Dynamic: AVs don't just follow routes; they change the road itself. By maintaining shorter headways (platooning), a high concentration of AVs effectively increases the "bandwidth" of a road.
  • The Power of Small Sacrifices: One of the most striking findings is that even with arbitrarily small levels of altruism, the total system latency can be "unboundedly better" than a purely selfish system. By taking a slightly longer path, an AV can prevent a primary road from hitting the "tipping point" into a congested, low-flow state.
  • Robustness is a Choice: In many traffic scenarios, multiple "best" selfish equilibria exist with the same total delay. The authors show we can specifically choose the one that has the most "spare capacity" to handle unexpected extra cars.
  • Counter-Intuitive BANE: Unlike selfish equilibria, the optimal altruistic routing might actually involve keeping the "longest" road congested to save the rest of the network, a property the authors prove is unique to the altruistic setting.

Key Results

  • Latency Reduction: In microscopic simulations of a two-road scenario, moving from a "worst-case" selfish equilibrium to a "best-case" selfish equilibrium halved the total latency. Adding altruistic AVs halved the latency again.
  • Theoretical Bounds: The authors proved that the best selfish equilibrium can be unboundedly better than the worst, highlighting the importance of active traffic management even before altruism is introduced.
  • Simulation Match: The linear model proposed by the authors closely matched the complex, non-linear outputs of the SUMO simulator, suggesting their simplified mathematical approach is robust enough for real-world planning.

Limitations and Future Work

  • Parallel Roads Only: The current mathematical proofs and algorithms are designed for networks of parallel roads. Real city grids are much more complex, with intersections and overlapping paths that require further study.
  • Centralized Coordination: The model assumes a "social planner" (like a city-wide GPS authority) can dictate or incentivize these routes. Implementing this in a world of competing AV manufacturers (Tesla vs. Waymo) presents a significant game-theoretic and policy challenge.
  • Stability of Congestion: While the paper notes that AVs can help stabilize congested flow, the authors acknowledge that highly congested regimes are inherently unstable and difficult to manage perfectly in real-time.
  • Human Behavior: The model assumes humans are perfectly selfish and rational; future work could incorporate more nuanced models of human driving psychology.

Summary updated

Abstract

Traffic congestion has large economic and social costs. The introduction of autonomous vehicles can potentially reduce this congestion, both by increasing network throughput and by enabling a social planner to incentivize users of autonomous vehicles to take longer routes that can alleviate congestion on more direct roads. We formalize these effects of altruistic autonomy on roads shared between human drivers and autonomous vehicles. In this work, we develop a formal model of road congestion on shared roads based on the fundamental diagram of traffic. We consider a network of parallel roads and provide algorithms that compute optimal equilibria that are robust to additional unforeseen demand. We further plan for optimal routings when users have varying degrees of altruism. We find that even with arbitrarily small altruism, total latency can be unboundedly better than without altruism, and that the best selfish equilibrium can be unboundedly better than the worst selfish equilibrium. We validate our theoretical results through microscopic traffic simulations and show average latency decrease of a factor of 4 from worst-case selfish equilibrium to the optimal equilibrium when autonomous vehicles are altruistic.
BibTeX
@inproceedings{biyik2018altruistic,
  author = {Erdem Biyik and Daniel A. Lazar and Ramtin Pedarsani and Dorsa Sadigh},
  title = {{Altruistic Autonomy: Beating Congestion on Shared Roads}},
  booktitle = {WAFR},
  year = {2018},
  url = {https://openreview.net/forum?id=z0jvxz5jO5H},
}

Loading related content...

Figure