A General Framework for Dynamic MAPF using Multi-Shot ASP and Tunnels
This addresses the need for flexible path planning in real-world applications such as warehouses with human presence, though it appears incremental as it builds on existing MAPF methods.
The paper tackles the Dynamic Multi-Agent Path Finding (D-MAPF) problem, which involves adapting plans for multiple agents in environments with changes like agents entering/leaving or obstacles moving, by introducing a general framework and an ASP-based method with tunnels, and evaluates it through experiments on computational performance and solution quality.
MAPF problem aims to find plans for multiple agents in an environment within a given time, such that the agents do not collide with each other or obstacles. Motivated by the execution and monitoring of these plans, we study Dynamic MAPF (D-MAPF) problem, which allows changes such as agents entering/leaving the environment or obstacles being removed/moved. Considering the requirements of real-world applications in warehouses with the presence of humans, we introduce 1) a general definition for D-MAPF (applicable to variations of D-MAPF), 2) a new framework to solve D-MAPF (utilizing multi-shot computation, and allowing different methods to solve D-MAPF), and 3) a new ASP-based method to solve D-MAPF (combining advantages of replanning and repairing methods, with a novel concept of tunnels to specify where agents can move). We have illustrated the strengths and weaknesses of this method by experimental evaluations, from the perspectives of computational performance and quality of solutions.