Congestion-Aware Traffic Routing for Large-Scale Multi-Agent Systems

Combined interview with Computer Science and Engineering and the University of Michigan's Transportation Research Institute.
Traffic congestion is a serious world-wide problem. Drivers have little knowledge of historical and real-time traffic congestion for the paths they take and often tend to drive suboptimal routes. The availability of traffic data provides a great opportunity for developing more intelligent solutions to the transportation problem. However, the following questions need to be addressed: How can we turn available traffic data into a useful form? How can we develop a practical algorithm that use these data and find a good path under uncertainty and congestion? How can we reduce city-scale congestion? In this talk, I will present practical algorithms for these questions and their implementation in a city-scale environment.

First, I will present a stochastic route planning algorithm that finds the best path for a group of mobile agents to achieve time-critical goals guaranteeing the highest probability of task achievement while dealing with uncertainty of travel time. Second, I will present a distributed congestion-aware multi-agent path planning algorithm that minimizes aggregate travel time of all the agents in the system. As the number of agents grows, congestion created by agents °~ path choices should be considered. Using a data-driven congestion model, we develop a practical method for determining the optimal paths for all the agents in the system. Third, I will demonstrate a path planning system using the proposed algorithms and traffic sensor data. We predict the traffic speed and flow for each location from a large set of sensor data collected from roving taxis and inductive loop detectors. Our system uses a data-driven traffic model that captures important traffic patterns and conditions using the two sources of data. We evaluate the system using a rich set of GPS traces from 16,000 taxis in Singapore and show that the city-scale congestion can be mitigated by planning drivers °~~ routes, while incorporating the congestion effects generated by their route choices.
Dr. Sejoon Lim received a Ph.D. degree in Electrical Engineering and Computer Science from MIT. His research interests lie in traffic data analysis, traffic modeling and estimation, vehicle routing under uncertainty, multi-agent routing algorithm, and intelligent transportation systems. He is currently a Senior Member of Technical Staff at Oracle Corporation, focusing on parallel server technology and cloud computing systems.