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
Pages171-186
Number of pages16
Volume17
StatePublished - 2005

Publication series

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

Fingerprint

Cost functions
Robots

ASJC Scopus subject areas

  • Artificial Intelligence
  • Electrical and Electronic Engineering

Cite this

Ghrist, R., O'Kane, J. M., & Lavalle, S. M. (2005). Pareto optimal coordination on Roadmaps. In Algorithmic Foundations of Robotics VI (Vol. 17, pp. 171-186). (Springer Tracts in Advanced Robotics; Vol. 17).

Pareto optimal coordination on Roadmaps. / Ghrist, Robert; O'Kane, Jason M.; Lavalle, Steven M.

Algorithmic Foundations of Robotics VI. Vol. 17 2005. p. 171-186 (Springer Tracts in Advanced Robotics; Vol. 17).

Research output: Chapter in Book/Report/Conference proceedingChapter

Ghrist, R, O'Kane, JM & Lavalle, SM 2005, Pareto optimal coordination on Roadmaps. in Algorithmic Foundations of Robotics VI. vol. 17, Springer Tracts in Advanced Robotics, vol. 17, pp. 171-186.
Ghrist R, O'Kane JM, Lavalle SM. Pareto optimal coordination on Roadmaps. In Algorithmic Foundations of Robotics VI. Vol. 17. 2005. p. 171-186. (Springer Tracts in Advanced Robotics).
Ghrist, Robert ; O'Kane, Jason M. ; Lavalle, Steven M. / Pareto optimal coordination on Roadmaps. Algorithmic Foundations of Robotics VI. Vol. 17 2005. pp. 171-186 (Springer Tracts in Advanced Robotics).
@inbook{281c82f4bb0a496698cdb6ab24426546,
title = "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 algorithm for reducing a coordination scheme to its Pareto optimal representative.",
author = "Robert Ghrist and O'Kane, {Jason M.} and Lavalle, {Steven M}",
year = "2005",
language = "English (US)",
isbn = "9783540257288",
volume = "17",
series = "Springer Tracts in Advanced Robotics",
pages = "171--186",
booktitle = "Algorithmic Foundations of Robotics VI",

}

TY - CHAP

T1 - Pareto optimal coordination on Roadmaps

AU - Ghrist, Robert

AU - O'Kane, Jason M.

AU - Lavalle, Steven M

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84862146102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862146102&partnerID=8YFLogxK

M3 - Chapter

AN - SCOPUS:84862146102

SN - 9783540257288

VL - 17

T3 - Springer Tracts in Advanced Robotics

SP - 171

EP - 186

BT - Algorithmic Foundations of Robotics VI

ER -