Multirobot Sequential Composition

Abstract

Conventional path planning algorithms compute a single path through the configuration space. There is no guarantee that a physical robot will be able to track the trajectory while avoiding collisions, particularly in the presence of environmental perturbations and errors in the process model. Sequential composition combines planning and control by computing a sequence of controllers to execute rather than a single trajectory, offering greater safety guarantees. In this paper, we apply sequential composition to multirobot systems in a scalable fashion using M*, an advanced multirobot path planning algorithm. Controllers will vary in size and geometry, and thus take different amounts of time to execute. To handle these differences, we introduce the time augmented joint prepares graph and the approximate time augmented joint prepares graph which simplifies implementation by discretizing time. We validate our approach in a mixed reality test framework.