Uncertainty-Aware Planning for Heterogeneous Robot Teams using Dynamic Topological Graphs and Mixed-Integer Programming

Multi-robot planning and coordination in uncertain environments is a fundamental computational challenge, since the belief space increases exponentially with the number of robots. In this paper, we address the problem of planning in uncertain environments with a heterogeneous robot team comprised of fast scout vehicles for information gathering and more risk-averse carrier robots from which the scout vehicles are deployed. To overcome the computational challenges associated with multi-robot planning in the presence of environmental uncertainty, we represent the environment and operational scenario using a topological graph, where the edge weight distributions vary with the state of the robot team on the graph. While this belief space representation still scales exponentially with the number of robots, we formulate a computationally efficient mixed-integer program which is capable of generating optimal multi-robot plans in seconds. We evaluate our approach in a representative scenario where the robot team must move through an environment while minimizing detection by observers in positions that are uncertain to the robot team. We demonstrate that our approach is sufficiently computationally tractable for real-time re-planning in changing environments, can improve performance in the presence of imperfect information, and can be adjusted to accommodate different risk profiles.