A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by\n Persistently Optimizing a Switchable Action Dependency Graph

Abstract

In this paper we consider multiple Automated Guided Vehicles (AGVs)\nnavigating a common workspace to fulfill various intralogistics tasks,\ntypically formulated as the Multi-Agent Path Finding (MAPF) problem. To keep\nplan execution deadlock-free, one approach is to construct an Action Dependency\nGraph (ADG) which encodes the ordering of AGVs as they proceed along their\nroutes. Using this method, delayed AGVs occasionally require others to wait for\nthem at intersections, thereby affecting the plan execution efficiency. If the\nworkspace is shared by dynamic obstacles such as humans or third party robots,\nAGVs can experience large delays. A common mitigation approach is to re-solve\nthe MAPF using the current, delayed AGV positions. However, solving the MAPF is\ntime-consuming, making this approach inefficient, especially for large AGV\nteams. In this work, we present an online method to repeatedly modify a given\nacyclic ADG to minimize route completion times of each AGV. Our approach\npersistently maintains an acyclic ADG, necessary for deadlock-free plan\nexecution. We evaluate the approach by considering simulations with random\ndisturbances on the execution and show faster route completion times compared\nto the baseline ADG-based execution management approach.\n