Conflict-Based Task and Motion Planning for Multi-Robot, Multi-Goal Problems

Task and Motion Planning (TAMP) is the problem of planning goal-directed behaviour for robotic systems in which the physical movement of the robots constrains the ways that actions can be performed. Task-planning has, traditionally, been seen as a model-based reasoning problem, solved using symbolic action representations, while motion planning involves finding paths in continuous configuration spaces. These problems are more complicated in the context of multi-agent problems, such as a fleet of autonomous robots operating in a warehouse, performing pick-and-pack tasks and delivering pallets to target locations. When multiple mobile agents are operating concurrently in shared space, the task and motion planning problems become highly interdependent and classical decompositions cease to provide high quality solutions. These challenges are explored and a novel solution is presented that combines temporal task planning and motion planning techniques to iteratively resolve conflicts and converge towards optimized solutions. The approach segments collision regions using a collision detector, enabling efficient task organization and trajectory management. The approach is evaluated by considering its performance on motivating example problems and in diverse scenarios to demonstrate the effectiveness and advantages over alternative approaches.