Planning and Control of Multiple Mobile Robots for Intralogistics

Abstract

In this thesis we consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill 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, due to its inherent complexity, solving the MAPF is time-consuming, making this approach inefficient, especially for large AGV teams. To address this challenge, we present a novel concept called a Switchable Action Dependency Graph (SADG) which is used as the basis for a shrinking and receding horizon control scheme to repeatedly modify an acyclic ADG to minimize route completion times of each AGV using an optimization based approach. Our control strategies persistently maintain an acyclic ADG, necessary for deadlock-free plan execution. The proposed control strategies are evaluated in a simulation environment and show a reduc- tion in route completion times when a fleet of AGVs is subjected to random delays. Finally, the methods are also implemented using ROS and validated in the Gazebo simulation envi- ronment to illustrate practical feasibility when applied to real systems.