PhD Proposal: On the Complexity of Motion Planning with Traffic

Talk
Philip Dasler
Time: 
10.14.2015 10:00 to 11:30
Location: 

AVW 3450

Traffic congestion is a complex and pervasive problem with significant economic ramifications. Practical engineering solutions will require consideration of myriad issues, including the physical limitations of vehicle motion and road conditions, the complexities and dynamics of traffic and urban navigation, external issues such as accidents and break-downs, and human factors. This work is motivated by the question of whether the field of algorithm design can contribute positively to such solutions, with the aim to identify fundamental optimization problems that are simple enough to be analyzed formally, but realistic enough to contribute to the eventual design of actual traffic management systems.
More specifically, this work introduces the traffic crossing problem, a simple and fundamental geometric optimization problem that involves coordinating the motions of a set of vehicles moving through a system of intersections. This problem is shown to be NP-complete in its general form, but a constrained version allows for a simple algorithm that solves this problem in O(n log n) time. Finally, a solution to the discrete version of the problem is given and its asymptotic optimality (in terms of the maximum delay of a vehicle) is proven.
Moving forward, this work will attempt to further generalize the problem formulation, find a good approximation algorithm or formally prove the problem's inapproximability, and explore the limits of the solution methods already discovered.
Examining Committee:
Committee Chair: - Dr. David Mount
Dept's Representative - Dr. Dana Nau
Committee Member(s): - Dr. Samir Khuller