In

2008

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

@inproceedings{ChiLavOKa08, author = {Hamid Chitsaz and Steven M. LaValle and Jason M. O'Kane}, booktitle = {Proc. Canadian Conference on Computational Geometry}, title = {Exact {P}areto-optimal coordination for two translating polygonal robots on a cyclic roadmap}, year = {2008} }