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
StatePublished - Jul 5 2004
EventProceedings- 2004 IEEE International Conference on Robotics and Automation - New Orleans, LA, United States
Duration: Apr 26 2004May 1 2004

Fingerprint

Robots
Travel time

ASJC Scopus subject areas

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

Cite this

Exact pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap. / Chitsaz, Hamidreza; O'Kane, Jason M.; Lavalle, Steven M.

In: Proceedings - IEEE International Conference on Robotics and Automation, Vol. 2004, No. 4, 05.07.2004, p. 3981-3986.

Research output: Contribution to journalConference article

@article{f418baf9a0e04ac1ad64b23c23b78763,
title = "Exact pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap",
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.",
author = "Hamidreza Chitsaz and O'Kane, {Jason M.} and Lavalle, {Steven M}",
year = "2004",
month = "7",
day = "5",
language = "English (US)",
volume = "2004",
pages = "3981--3986",
journal = "Proceedings - IEEE International Conference on Robotics and Automation",
issn = "1050-4729",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

TY - JOUR

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

AU - Chitsaz, Hamidreza

AU - O'Kane, Jason M.

AU - Lavalle, Steven M

PY - 2004/7/5

Y1 - 2004/7/5

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

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

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

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

M3 - Conference article

AN - SCOPUS:3042620606

VL - 2004

SP - 3981

EP - 3986

JO - Proceedings - IEEE International Conference on Robotics and Automation

JF - Proceedings - IEEE International Conference on Robotics and Automation

SN - 1050-4729

IS - 4

ER -