xBots: An Approach to Generating and Executing Optimal Multi-Robot Plans with Cross-Schedule Dependencies

In this paper, we present an approach to bounded optimal planning and flexible execution for a robot team performing a set of spatially distributed tasks related by temporal ordering constraints such as precedence or synchronization. Furthermore, the manner in which the temporal constraints are satisfied impacts the overall utility of the team, due to the existence of both routing and delay costs. We present a bounded optimal offline planner for task allocation and scheduling in the presence of such cross-schedule dependencies, and a flexible, distributed online plan execution strategy. The integrated system performs task allocation and scheduling, executes the plans smoothly in the face of real-world variations in operation speed and task execution time, and ensures graceful degradation 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 demonstrate that the approach is effective for constrained planning and execution in the face of real-world variations.