Computing pareto optimal coordinations on roadmaps

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

Research output: Contribution to journalArticlepeer-review


We consider the coordination of multiple robots in a common environment, each robot having its own (distinct) roadmap. Our primary contribution is a classification of and exact algorithm for computing vector-valued (or Pareto) optima for collision-free coordination. We indicate the utility of new geometric techniques from CAT(0) geometry and give an argument that curvature bounds are the key distinguishing feature between systems for which the classification is finite and for those in which it is not.

Original languageEnglish (US)
Pages (from-to)997-1010
Number of pages14
JournalInternational Journal of Robotics Research
Issue number11
StatePublished - Nov 2005


  • Coordination spaces
  • Motion planning
  • Multiple robots
  • Optimality
  • Roadmaps

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Computing pareto optimal coordinations on roadmaps'. Together they form a unique fingerprint.

Cite this