Pareto optimal coordination on roadmaps

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.

@inproceedings{GhrOKaLav04,
  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}
}