# Fully Polynomial-Time Approximation Scheme (FPTAS) for Multi-Robot Motion Planning

- Source: arXiv cs.RO
- Published: 2026-10-21T04:00:00.000Z
- RoboHot: https://robohot.news/en/items/h5uht456pozxg9i1wpaz6qfz6
- Original: https://arxiv.org/abs/2610.20244

## Summary

This work presents the first fully polynomial-time approximation scheme (FPTAS) for the multi-robot motion planning problem, for a fixed number k of translating polygonal robots in a polygonal environment, covering the min-sum, min-max, and min-makespan objectives. The algorithm generalizes to polytope environments and polytope robots in any fixed dimension d, and it resolves the open problem raised by Agarwal et al. on an FPTAS for k=2 unit-square and unit-disk robots, while being simpler than existing results. The paper will be published at SODA 2027.