Abstract
For multi-Agent path finding (MAPF) problems, finding the optimal solution has been shown to be NP-Complete. Here we present WSCaS (Walk, Stop, Count, and Swap), a decentralized multi-Agent path-finding algorithm that can provide theoretical completeness and optimality guarantees. That is, WSCaS is able to deliver a worst case \mathbf {\mathcal {O}(1)}-Approximate distance-optimal solution to MAPF instances on square grids without narrow passages. Moreover, the algorithm's cost is independent of the swarm's size with respect to computation complexity, memory complexity, as well as communication complexity, therefore the algorithm can scale well with the number of agents in practice. The algorithm is executed on 1024 simulated agents as well as 100 physical robots, the results show that the WSCaS is robust to real-world non-idealitys.
| Original language | English (US) |
|---|---|
| Article number | 8962201 |
| Pages (from-to) | 1119-1126 |
| Number of pages | 8 |
| Journal | IEEE Robotics and Automation Letters |
| Volume | 5 |
| Issue number | 2 |
| DOIs | |
| State | Published - Apr 2020 |
Keywords
- Path planning for multiple mobile robots or agents
- distributed robot systems
- swarms
ASJC Scopus subject areas
- Control and Systems Engineering
- Biomedical Engineering
- Human-Computer Interaction
- Mechanical Engineering
- Computer Vision and Pattern Recognition
- Computer Science Applications
- Control and Optimization
- Artificial Intelligence