A Sampling-Based Approach for Heterogeneous Coalition Scheduling with Temporal Uncertainty

Andrew Messing
Georgia Tech
Jacopo Banfi
Massachusetts Institute of Technology
Martina Stadler
Massachusetts Institute of Technology
Ethan Stump
US Army Research Laboratory
Harish Ravichandar
Georgia Tech
Nicholas Roy
Massachusetts Institute of Technology
Seth Hutchinson
Georgia Tech
Paper Website

Paper ID 107

Session 14. Multi-Robot and Aerial Systems

Poster Session Friday, July 14

Poster 11

Abstract: Scheduling algorithms for real-world heterogeneous multi-robot teams must be able to reason about temporal uncertainty in the world model in order to create plans that are tolerant to the risk of unexpected delays. To this end, we present a novel sampling-based risk-aware approach for solving Heterogeneous Coalition Scheduling with Temporal Uncertainty (HCSTU) problems, which does not require any assumptions regarding the specific underlying cause of the temporal uncertainty or the specific duration distributions. Our approach computes a schedule which obeys the temporal constraints of a small number of heuristically-selected sample scenarios by solving a Mixed-Integer Linear Program, along with an upper bound on the schedule execution time. Then, it uses a hypothesis testing method, the Sequential Probability Ratio Test, to provide a probabilistic guarantee that the upper bound on the execution time will be respected for a user-specified risk tolerance. With extensive experiments, we demonstrate that our approach empirically respects the risk tolerance, and generates solutions of comparable or better quality than state-of-the-art approaches while being an order of magnitude faster to compute on average. Finally, we demonstrate how robust schedules generated by our approach can be incorporated as solutions to subproblems within the broader Simultaneous Task Allocation and Planning with Spatiotemporal Constraints problem to both guide and expedite the search for solutions of higher quality and lower risk.