Realistic path planning applications often require optimizing with respect to several criteria simultaneously. For example, if you are driving from Ithaca to New York City you might want to minimize distance traveled. However, you may also want to take into account other criteria such as fuel used, money spent on tolls, idle time in traffic, or number of exits taken.

In this talk I will present a new, efficient algorithm for bi-criteria path planning on graphs. The approach is based on augmenting the state space to keep track of the "budget" remaining to satisfy the constraints on secondary cost. The resulting augmented graph is acyclic and the primary cost can be then minimized by a simple upward sweep through budget levels.

I will illustrate the efficiency and accuracy of the algorithm on robotic path-planning applications where the underlying state space is represented by a PRM graph. I will also present the results from field experiments illustrating the use of this approach on realistic robotic systems.

This is joint work with Alexander Vladimirsky, Dennis Ding, William M. Sisson, Thomas A. Frewen, and Brendan Englot.