Simplified Algorithms and Improved Bounds for Motion Planning

Abstract

We investigate coordinated motion planning (CMP) for unit square robots in the plane under the $L_1$ metric. Given two arrangements of $k$ robots, we seek a movement schedule minimizing one of three objectives: the Min-Sum objective (sum of distances), the Min-Makespan objective (latest time of arrival) and the Min-Exposure objective (a new objective). For Min-Sum and Min-Makespan, we provide a simplified approach and improved bounds, compared to Eiben, Ganian and Kanj (SoCG 2023). To this end, we partition the configuration space based on the relative ordering of the robots. This leads to a simple and efficient framework to discretize the search space. Our results extend to several settings in the plane, including convex robots in convex domains and vertex robots in rectangular grids. Finally, we apply our results to the new Min-Exposure objective. Given a set of polygonal regions that provide cover, the task is to find a schedule with minimal elapsed time during which at least one robot is not fully covered. We give an $\mathcal{O}(n^4\log n)$ time algorithm that computes exposure-minimal schedules for $k=2$ robots, and an XP algorithm for arbitrary $k$.

arXiv comment10 pages, 5 figures