Multiagent Reinforcement Learning for Urban Traffic Control Using Coordination Graphs

Kuyer, Lior; Whiteson, Shimon; Bakker, Bram; Vlassis, Nikos · 2008 · Crossref

DOI: 10.1007/978-3-540-87479-9_61

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of optimizing urban traffic flow by applying multiagent reinforcement learning (MARL) to control traffic lights. While existing MARL approaches allow individual agents to learn locally optimal policies, they lack coordination, often resulting in global inefficiencies. The authors propose a method that introduces explicit coordination between neighboring traffic lights using coordination graphs and the max-plus algorithm. This approach aims to decompose the global coordination problem into local problems, enabling scalable joint action selection even in large networks. The study utilizes the Green Light District (GLD) microscopic traffic simulator, where each vehicle is modeled individually with dynamic speeds and behaviors. The authors combine a vehicle-based model-based reinforcement learning approach with the max-plus algorithm. In this framework, intersections connected by roads are treated as neighbors in a coordination graph. The max-plus algorithm approximates the optimal joint action by iteratively exchanging locally optimized messages between these neighbors. The system was tested on both small and large networks (up to 15 agents) under three scenarios: a baseline with uniform destinations (high local traffic), nonuniform destinations (no local traffic), and long routes (no local traffic). Performance was evaluated using average trip waiting time (ATWT), ratio of stopped vehicles, and total queue length. The results demonstrate that the benefit of coordination is strongly correlated with the amount of local traffic. In scenarios with significant local traffic, the coordinated max-plus method performed similarly to non-coordinated baselines (TC-1 and TC-SBC). However, in scenarios where vehicles traversed multiple intersections, max-plus substantially outperformed the other methods. For instance, in the long routes scenario on small networks, max-plus achieved an average total queue length of 0.0, compared to 9,259.7 for TC-1. Furthermore, the performance gap widened in larger networks, indicating that the need for coordination increases with system scale. The study also provides empirical evidence that max-plus performs effectively on cyclic graphs, despite theoretical convergence guarantees existing only for tree-structured graphs. The significance of this work lies in demonstrating that explicit coordination among traffic lights is crucial for handling non-local traffic flows in saturated networks. The findings suggest that as the number of agents and network complexity grow, coordinated learning becomes increasingly advantageous. Additionally, the successful application of max-plus to a large-scale, cyclic graph problem validates its efficacy in realistic settings, offering a robust solution for scalable urban traffic control that outperforms previous uncoordinated reinforcement learning methods.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• traffic density