Columbia University Joint CS/EE Networking Seminar Series


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

Sejoon Lim

Oracle Corporation

Apr. 19, 11:00AM, Interschool Lab, 750 CEPSR



Abstract: 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.

Speaker Biography: 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 systems, 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.