Exact Pareto-optimal coordination for two translating polygonal robots on an acyclic roadmap

Hamid Chitsaz, Jason M. O'Kane, Steven M. LaValle
In Proc. IEEE International Conference on Robotics and Automation 2004.

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.

Download

BibTeX

@inproceedings{ChiOKaLav04,
  author       = {Hamid Chitsaz and Jason M. O'Kane and Steven M. LaValle},
  title        = {Exact {P}areto-optimal coordination for two translating
		 polygonal robots on an acyclic roadmap},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  pages        = {3981--3986},
  year	       = {2004}
}

O'Kane's home page
O'Kane's publication list

Wed Sep 20 09:19:46 EDT 2017