Coordinated robot motion planning optimizes paths for multiple robots simultaneously. The standard objectives — minimize total time (makespan), minimize total distance (sum) — are well-studied but ignore a practical concern: safety. In many environments, certain regions are dangerous, and robots should spend as little time as possible outside protected zones.
De Berg et al. (arXiv:2603.16510) introduce the min-exposure objective: minimize the total time any robot spends outside protective regions. They solve it in O(n^4 log n) time for two robots navigating among n obstacles, where the obstacles define both the workspace geometry and the protection zones.
The min-exposure problem has different structure from makespan or sum-of-distances. It's not enough for robots to reach their goals quickly — they must route through protected regions even if longer paths result. The optimization trades path length for safety, and the tradeoff is geometrically complex because protection zones have arbitrary shapes and may require coordinated timing to share safely.
A byproduct of the analysis proves that the classical min-makespan and min-sum objectives are fixed-parameter tractable in the number of robots when the workspace is a continuous plane with obstacles. Previously, FPT results for these problems were known only on grid graphs. The extension to continuous geometry is non-trivial because the configuration space is infinite-dimensional — the robots can be anywhere, not just at grid vertices — and the FPT result requires a careful discretization that preserves optimality.
Three problems advanced by one paper. The new objective (min-exposure) solved efficiently for two robots. Two classical objectives (makespan, sum) proved tractable for any fixed number of robots in continuous geometry. The safety-motivated question generated complexity insights that apply far beyond its original motivation.