pipette
ENEnglish

FPTAS for Polygonal Multi-Robot Motion Planning

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, Jie Xue

PreprintDice ser un gran avance

En palabras de los autores

We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain with vertices and robots translating in each of which is represented by a polygon of constant complexity. Given a source configuration and a target configuration of the robots in , the goal of the problem is to find a collision-free motion plan from to that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed . The algorithm directly generalizes to the problem in any fixed dimension , with a polytope environment and polytope robots. Our result settles an open question of Agarwal, Halperin, Sharir, Steiger [SODA'24] and Agarwal, Holmgren, Steiger [SODA'26], who gave an FPTAS for unit-square robots and a bicriteria-approximation algorithm for a fixed number of unit-square or unit-disk robots, respectively. Compared to the previous results, our algorithm is substantially simpler.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: To appear in SODA 2027