xBots: An Approach to Generating and Executing Optimal Multi-Robot Plans with Constraints

Abstract

In this report, we present an approach to optimal planning and flexible execution for a set of spatially distributed tasks related by temporal ordering constraints such as precedence, synchronization, or non-overlapping constraints. We integrate an optimal planner for task allocation and scheduling with cross-schedule dependencies with a flexible, distributed plan execution strategy. The integrated system performs optimal task allocation and scheduling for tasks related by temporal constraints, and ensures that plans are executed smoothly in the face of real-world variations in operation speed and task execution time. It also ensures that plan execution degrades gracefully in the event of task failure. We demonstrate the capabilities of our approach on a team of three pioneer robots operating in an indoor environment. Experimental results focus on the flexible execution strategy and illustrate that it effectively enables execution of the optimal plan and prevents constraint violations. The overall approach is thus demonstrated to be effective for constrained planning and execution in the face of realworld variations.