Pareto optimal coordination on Roadmaps

Robert Ghrist, Jason M. O'Kane, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceedingChapter


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 algorithm for reducing a coordination scheme to its Pareto optimal representative.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics VI
Number of pages16
ISBN (Print)9783540257288
StatePublished - 2005

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'Pareto optimal coordination on Roadmaps'. Together they form a unique fingerprint.

Cite this