Exact pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap

Hamidreza Chitsaz, Jason M. O'Kane, Steven M. LaValle

Research output: Contribution to journalConference article

Abstract

We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of piecewise-linear paths is given on which the two robots move. The robots have a maximum speed and are capable of instantly switching between any two arbitrary speeds. Each robot would like to minimize its travel time independently. The Pareto-optimal solutions are the ones for which there exist no solutions that are better for both robots. The algorithm computes exact solutions in time O(mn2 log n), in which m is the number of paths in the roadmap, n is the number of coordination space vertices. An implementation is presented.

Original languageEnglish (US)
Pages (from-to)3981-3986
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
Volume2004
Issue number4
DOIs
StatePublished - 2004
EventProceedings- 2004 IEEE International Conference on Robotics and Automation - New Orleans, LA, United States
Duration: Apr 26 2004May 1 2004

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Exact pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap'. Together they form a unique fingerprint.

  • Cite this