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.