## 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(mn^{2} 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

@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}
}

*Wed Mar 4 12:52:19 EST 2020
*