Pareto optimal coordination on Roadmaps

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

Research output: Chapter in Book/Report/Conference proceedingChapter

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

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics VI
PublisherSpringer-Verlag Berlin Heidelberg
Pages171-186
Number of pages16
ISBN (Print)9783540257288
DOIs
StatePublished - Jan 1 2005

Publication series

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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

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

  • Cite this

    Ghrist, R., O'Kane, J. M., & LaValle, S. M. (2005). Pareto optimal coordination on Roadmaps. In Algorithmic Foundations of Robotics VI (pp. 171-186). (Springer Tracts in Advanced Robotics; Vol. 17). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/10991541_13