Multi-Robotnavigation and Planning

For a multi-robot-system it is an essential requirement that the path planning of the individual robots are somehow coordinated in order to avoid collisions, minimize path lengths or to avoid deadlock situations. Path planning in the robotic context means to calculate the optimal route from the current or estimated position to the next assigned goal position within a given metrical map. While the solution for a single robot system is quite straight forward and well analyzed in research, the same approaches cannot be applied for a mobile multi robot system, because the computational expensed for path planning grows exponentially with the numbers of robots included. Path planning can be regarded as a NP-hard problem, because each path of the individual robot has to be analyzed in the robots configuration time-space.