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

Let W ⊂ ℝ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 sA,tA,sB, tB ∈ 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 sA to tA and B from sB to tB 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,sA,tA,sB,tB and a parameter ɛ > 0, we present an n2ɛ-°(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.