Pareto optimal coordination on roadmaps

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


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},
  title        = {{P}areto optimal coordination on roadmaps},
  booktitle    = {Proc. International Workshop on the Algorithmic
		 Foundations of Robotics},
  pages        = {185--200},
  year	       = {2004}

O'Kane's home page
O'Kane's publication list

Wed Sep 20 09:19:46 EDT 2017