Spatio-temporal prioritized planning

Abstract

Using robot fleets have gained popularity in recent years in industrial logistics applications because of their flexible field of application. Therefore, the issue arises how to coordinate these robots. A commonly used approach to this problem is Prioritized Planning, where a coordinator plans all robot's routes sequentially avoiding already planned ones. This thesis presents a new approach for prioritized multi robot path planning. The proposed planner works centralized and generates synchronized and deadlock-free routes for robots. Applying search algorithms on pixel-maps is expensive, therefore, pixel-maps are reduced to search graphs using voronoi distillation. A single robot path planner for use inside a prioritized multi robot path planner is designed. This single robot path planner constrains the creation of new routes by adding already planned ones to the used search graph. To find solutions in this graph the single robot path planner is able to take temporal and spacial constraints into account. Furthermore, potential collisions and deadlocks between robots are avoided by extending the search graph with additional segments if a collision is detected. The global multi robot path planner includes a priority and speed rescheduler as well, to solve specific scenarios which are hard to solve using prioritized path planning. Because the routes are generated time-dependently, they are post-processed to add synchronization markers in form of preconditions for every robot. These preconditions have to be met before a robot is allowed to enter a segment. Selected scenarios with multiple robots are used to compare the proposed planner with state of the art approaches in a simulated environment. Also scenarios are shown to be solvable with the proposed planner, which are not solvable with currently used approaches.