Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment

Let W ⊂ R 2 be a planar polygonal environment (i.e., a polygon potentially with holes) with a total of n vertices, and let A, B be two robots, each modeled as an axis-aligned unit square, that can translate inside W. Given source and target placements s A , t A , s B , t B ∈ W of A and B, respectively, the goal is to compute a collision-free motion plan π * , i.e., a motion plan that continuously moves A from s A to t A and B from s B to t B so that A and B remain inside W and do not collide with each other during the motion. Furthermore, if such a plan exists, then we wish to return a plan that minimizes the sum of the lengths of the paths traversed by the robots, |π * |. Given W, s A , t A , s B , t B and a parameter ε > 0, we present an n 2 ε -O(1) log n-time (1 + ε)-approximation algorithm for this problem. We are not aware of any polynomial time algorithm for this problem, nor do we know whether the problem is NP-Hard. Our result is the first polynomial-time (1 + ε)-approximation algorithm for an optimal motion planning problem involving two robots moving in a polygonal environment.