2021/08/07 by Xifeng Gao, Gao, Xifeng, Zherong Pan +3
Computer Science · #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2108.03368
openalex publication_date 2021/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose an approach to solve multi-agent path planning (MPP) problems for complex environments. Our method first designs a special pebble graph with a set of feasibility constraints, under which MPP problems have feasibility guarantee. We further propose an algorithm to greedily improve the optimality of planned MPP solutions via parallel pebble motions. As a second step, we develop a mesh optimization algorithm to embed our pebble graph into arbitrarily complex environments. We show that the feasibility constraints of a pebble graph can be converted into differentiable geometric constraints, such that our mesh optimizer can satisfy these constraints via constrained numerical optimization. We have evaluated the effectiveness and efficiency of our method using a set of environments with complex geometries, on which our method achieves an average of 99.0% free-space coverage and 30.3% robot density within hours of computation on a desktop machine.