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