Pareto optimal coordination on roadmaps

Robert Ghrist, Jason M. O'Kane, Steven M. LaValle
In Proc. International Workshop on the Algorithmic Foundations of Robotics
pp. 185–200

Abstract Given a collection of robots sharing a common environment, assume that each possesses an individual roadmap for its C-space and a cost function for attaining a goal. Vector-valued (or Pareto) optima for collision-free coordination are by no means unique: in fact, continua of optimal coordinations are possible. However, for cylindrical obstacles (those defined by pairwise interactions), we prove a finite bound on the number of optimal coordinations. For such systems, we present an exact subquadratic algorithm for reducing a coordination scheme to its Pareto optimal representative.

  author = {Robert Ghrist and Jason M. O'Kane and Steven M. LaValle},
  booktitle = {Proc. International Workshop on the Algorithmic Foundations
               of Robotics},
  pages = {185--200},
  title = {{P}areto optimal coordination on roadmaps},
  year = {2004}

O'Kane's home page
O'Kane's publication list
Last updated 2022-09-20.