Heterogeneous multirobot coordination with spatial and temporal constraints

Abstract

Although recent work in multirobot teaming targets challenging domains such as disaster response or planetary exploration, the lack of formal problem descriptions and benchmarks make it difficult to evaluate various coordination approaches. We formally describe the problem of scheduling a team of robots with heterogeneous capabilities to accomplish a set of joint tasks that are spatially distributed. Finding the optimal plan in these domains requires robots to integrate path planning and task allocation with scheduling, which existing approaches to multirobot coordination separate. We have developed a declarative framework for modeling the problem as a mixed integer linear programming (MILP) problem and a centralized anytime algorithm with error bounds. The anytime algorithm can outperform standard MILP solving techniques, greedy heuristics, and a market based approach which separates scheduling and task allocation. Generating improved plans is insufficient if the schedules cannot be repaired to accomodate new observations or hardware failures as the robots traverse the environment. We present a framework for schedule repair that leverages the expressive nature of the MILP representation and minimizes the plan disruption.