Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment

Let $\mathscr{W} \subset \mathbb{R}^2$ be a planar polygonal environment with n vertices, and let $[k] = \{1, \ldots, k\}$ denote $k$ unit-square robots translating in $\mathscr{W}$. Given source and target placements $s_1, t_1, \ldots, s_k, t_k, \in \mathscr{W}$ for each robot, we wish to compute a collision-free motion plan $\boldsymbol \pi$, i.e., a coordinated motion for each robot $i$ along a continuous path from $s_i$ to $t_i$, so that robot $i$ does not leave $\mathscr{W}$ or collide with any other robot $j$. Moreover, we additionally require that $\boldsymbol \pi$ minimizes the sum of the path lengths; this variant is known as min-sum motion planning.