Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap

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

Research output: Contribution to conferencePaper

Abstract

We consider planning optimal collision-free motions of two polygonal robots under translation. Each robot has a reference point that must lie on a given graph, called a roadmap, which is embedded in the plane. The initial and the goal are given for each robot. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. Our problem translates into shortest path problems in the coordination space which is the Cartesian product of the roadmap, as a cell complex, with itself. Our algorithm computes an upper bound on the cost of each motion in any Pareto-optimal coordination. Therefore, only a finite number of homotopy classes of paths in the coordination space need to be considered. Our algorithm computes all Pareto-optimal coordinations in time O(2m 1+n2 log(mn)), in which m is the number of edges in the roadmap, n is the number of coordination space obstacle vertices, and α = 1 + ⌊(5ℓ + r)/b⌋ where ℓ is total length of the roadmap and r is total length of coordination space obstacle boundary and b is the length of the shortest edge in the roadmap.

Original languageEnglish (US)
Pages179-182
Number of pages4
StatePublished - Dec 1 2008
Event20th Annual Canadian Conference on Computational Geometry, CCCG 2008 - Montreal, QC, Canada
Duration: Aug 13 2008Aug 15 2008

Other

Other20th Annual Canadian Conference on Computational Geometry, CCCG 2008
CountryCanada
CityMontreal, QC
Period8/13/088/15/08

Fingerprint

Robot
Motion
Costs
Cell Complex
Scalarization
Reference Point
Shortest Path Problem
Cartesian product
Homotopy
Collision
Planning
Upper bound
Path
Graph in graph theory
Strategy

ASJC Scopus subject areas

  • Geometry and Topology

Cite this

Chitsaz, H., LaValle, S. M., & O'Kane, J. M. (2008). Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap. 179-182. Paper presented at 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, Montreal, QC, Canada.

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

2008. 179-182 Paper presented at 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, Montreal, QC, Canada.

Research output: Contribution to conferencePaper

Chitsaz, H, LaValle, SM & O'Kane, JM 2008, 'Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap', Paper presented at 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, Montreal, QC, Canada, 8/13/08 - 8/15/08 pp. 179-182.
Chitsaz H, LaValle SM, O'Kane JM. Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap. 2008. Paper presented at 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, Montreal, QC, Canada.
Chitsaz, Hamidreza ; LaValle, Steven M. ; O'Kane, Jason M. / Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap. Paper presented at 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, Montreal, QC, Canada.4 p.
@conference{9c645fa83a9a4d8db9d0c3624e3d7761,
title = "Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap",
abstract = "We consider planning optimal collision-free motions of two polygonal robots under translation. Each robot has a reference point that must lie on a given graph, called a roadmap, which is embedded in the plane. The initial and the goal are given for each robot. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. Our problem translates into shortest path problems in the coordination space which is the Cartesian product of the roadmap, as a cell complex, with itself. Our algorithm computes an upper bound on the cost of each motion in any Pareto-optimal coordination. Therefore, only a finite number of homotopy classes of paths in the coordination space need to be considered. Our algorithm computes all Pareto-optimal coordinations in time O(25αm 1+5αn2 log(m2αn)), in which m is the number of edges in the roadmap, n is the number of coordination space obstacle vertices, and α = 1 + ⌊(5ℓ + r)/b⌋ where ℓ is total length of the roadmap and r is total length of coordination space obstacle boundary and b is the length of the shortest edge in the roadmap.",
author = "Hamidreza Chitsaz and LaValle, {Steven M.} and O'Kane, {Jason M.}",
year = "2008",
month = "12",
day = "1",
language = "English (US)",
pages = "179--182",
note = "20th Annual Canadian Conference on Computational Geometry, CCCG 2008 ; Conference date: 13-08-2008 Through 15-08-2008",

}

TY - CONF

T1 - Exact pareto-optimal coordination of two translating polygonal robots on a cyclic roadmap

AU - Chitsaz, Hamidreza

AU - LaValle, Steven M.

AU - O'Kane, Jason M.

PY - 2008/12/1

Y1 - 2008/12/1

N2 - We consider planning optimal collision-free motions of two polygonal robots under translation. Each robot has a reference point that must lie on a given graph, called a roadmap, which is embedded in the plane. The initial and the goal are given for each robot. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. Our problem translates into shortest path problems in the coordination space which is the Cartesian product of the roadmap, as a cell complex, with itself. Our algorithm computes an upper bound on the cost of each motion in any Pareto-optimal coordination. Therefore, only a finite number of homotopy classes of paths in the coordination space need to be considered. Our algorithm computes all Pareto-optimal coordinations in time O(25αm 1+5αn2 log(m2αn)), in which m is the number of edges in the roadmap, n is the number of coordination space obstacle vertices, and α = 1 + ⌊(5ℓ + r)/b⌋ where ℓ is total length of the roadmap and r is total length of coordination space obstacle boundary and b is the length of the shortest edge in the roadmap.

AB - We consider planning optimal collision-free motions of two polygonal robots under translation. Each robot has a reference point that must lie on a given graph, called a roadmap, which is embedded in the plane. The initial and the goal are given for each robot. Rather than impose an a priori cost scalarization for choosing the best combined motion, we consider finding motions whose cost vectors are Pareto-optimal. Pareto-optimal coordination strategies are the ones for which there exists no strategy that would be better for both robots. Our problem translates into shortest path problems in the coordination space which is the Cartesian product of the roadmap, as a cell complex, with itself. Our algorithm computes an upper bound on the cost of each motion in any Pareto-optimal coordination. Therefore, only a finite number of homotopy classes of paths in the coordination space need to be considered. Our algorithm computes all Pareto-optimal coordinations in time O(25αm 1+5αn2 log(m2αn)), in which m is the number of edges in the roadmap, n is the number of coordination space obstacle vertices, and α = 1 + ⌊(5ℓ + r)/b⌋ where ℓ is total length of the roadmap and r is total length of coordination space obstacle boundary and b is the length of the shortest edge in the roadmap.

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

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

M3 - Paper

AN - SCOPUS:84893366915

SP - 179

EP - 182

ER -