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.

I. Introduction

Task and Motion Planning (TAMP) is the problem of achieving a goal by organising actions for an executive moving in physical space. Garrett et al [1] describe the problem as lying “between discrete ‘high-level’ task planning and continuous ‘low-level’ motion planning”. In fact, these problems interact, each constraining the other, so that the optimal solution resolves the requirements of both. In this paper, we explore TAMP in a multi-agent setting in which multiple executives cooperate in the achievement of goals, acting concurrently in a shared physical space. Examples arise in managing a fleet of autonomous robots in an automated warehouse, manufacturing facility, or assembly line.