In

pp. 3981–3986

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.

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