Adapting to Planning Failures in Lifelong Multi-Agent Path Finding

Abstract

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents operating in the same environment. In Lifelong MAPF (LMAPF), these agents continuously receive new destinations, and the task is to constantly update their paths while optimizing for a high throughput over time. Therefore, many MAPF sub-problems must be solved over time in order to solve a single LMAPF problem. LMAPF problems manifest in real-world applications, such as automated warehouses, where strict responsiveness requirements limit the amount of time allocated to planning. MAPF algorithms occasionally fail to produce a plan within the allotted time. We propose a system design for LMAPF that is robust to such planning failures. Then, we explore different approaches to avoid planning failures, reduce their severity, and handle them when they occur. In particular, we describe and analyze different Fail Policies that are applied when planning failures occur and ensure collisions and unnecessary degradation of throughput are avoided. To our knowledge, while such Fail Policies are used in practice in the industry, they have yet to be researched academically.