  Realistic path planning applications often require optimizing with respect to
several criteria simultaneously. Here we introduce an efficient algorithm for
bi-criteria path planning on graphs. Our 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. The
efficiency and accuracy of our algorithm is tested on Probabilistic Roadmap
graphs to minimize the distance of travel subject to a constraint on the
overall threat exposure of the robot. We also present the results from field
experiments illustrating the use of this approach on realistic robotic systems.

Robotics;Systems and Control