ECML PKDD 2008

Multiagent Reinforcement Learning for Urban Traffic Control using Coordination Graphs

Since traffic jams are ubiquitous, optimizing traffic lights for efficient traffic flow is critically important. Though most traffic lights use simple protocols, more efficient controllers can be discovered via multiagent reinforcement learning, where each agent controls a single traffic light. However, in previous work, agents select only locally optimal actions without coordinating their behavior. We extend this approach to include coordination between traffic lights using max-plus, which estimates the optimal joint action by sending messages among connected agents. We present the first application of max-plus to a large-scale problem and thus verify its efficacy in realistic settings. We also provide empirical evidence that max-plus performs well on cyclic graphs, though it is proven to converge only for tree-structured graphs. Furthermore, we provide a new understanding of when such coordination is beneficial and show that max-plus outperforms previous methods on networks with those properties.