Efficient, collision-free multi-robot navigation in an environment abstraction framework

Abstract

Industrial automation deploys a continuously increasing amount of mobile robots in favor of classical linear conveyor systems for material flow handling in manufacturing and intralogistics. This increases flexibility by handling a larger variety of goods, improves scalability by adapting the fleet size to varying system loads, and enhances fault tolerance by avoiding single points of failure. However, it also raises the need for efficient, collision-free multi-robot navigation. This core problem is first precisely modeled in a form that differs from existing approaches specifically in terms of application relevance and structured algorithmic treatability. Collision-free trajectories for the mobile robots between given start and goal locations are sought so that the number of goals reached per time is as high as possible. Based on this, a decoupled solution called the Collaborative Local Planning Framework (CLPF), is designed and implemented, which, in contrast to existing solutions, aims at avoiding deadlocks with the greatest possible concurrency. Moreover, this solution includes the handling of dynamic inputs consisting of both moving and non-moving robots. For testing, performance analysis, and optimization, due to the complexity of multi-robot systems, the use of simulation is common. However, this also creates a gap between real and simulated robots. These issues can be reduced by using several different simulators---albeit with the disadvantage of further increasing complexity. For this purpose, the Robot Experimentation Framework (REF) is introduced to write robotic experiments with a unified interface that can be run on multiple simulators and also on real hardware. It facilitates the creation of experiments for performance assessment, (parameter) optimization and runtime analysis. The framework has proven its effectiveness throughout this thesis. Lastly, experimental proof of the viability of the solution is provided based on a case study of a complete (simulated) assembly system of decentralized autonomous agents for the production of highly individualized automobiles. This integrates all developed concepts into a holistic application of industrial automation. Detailed evaluations of more than 800 000 solved scenarios with more than 5 700 000 processed goals have experimentally proven the robustness and reliability of the developed concepts. Robots have never crashed into each other in any of the conducted experiments, empirically proving the claimed safety guarantees. A fault-tolerance analysis of the decentralized assembly system has experimentally proven its resilience to failures at workstations and, thus, specifically revealed an advantage over linear conveyor systems.