A Fast Rescheduling Algorithm for Real-Time Multi-Robot Coordination [Extended Abstract]

One area of research in Multi-Agent Path Finding (MAPF) is to determine how re-planning can be efficiently achieved in the case of the delay of an agent. One option is to determine a new wait ordering to find the most optimal new solution that can be produced by re-ordering the wait order. We propose to use an Edge-Switchable Temporal Plan Graph and an augmented A* algorithm, called Switchable-Edge Search, to approach finding a new optimal wait order. While this is a work in progress still, we have discovered several optimizations for this algorithm, and the results show promising increases in efficiency for the algorithm. We have analyzed our present efficiency in a variety of conditions by measuring re-planning speed in different maps, with varying numbers of agents and randomized scenarios for agents

Authors

• Adittyo Paul
• Ying Feng
• Jiaoyang Li 0001

Keywords

• Search In Robotics
• Time
• Memory
• And Solution Quality Trade-offs
• Search In Goal-directed Problem Solving
• Real-life Applications