Efficient Planning of Informative Paths for Multiple Robots

Amarjeet Singh, Andreas Krause, Carlos Guestrin, William Kaiser, Maxim Batalin

In many sensing applications, including environmental monitoring, we must cover a large space with limited resources. One approach is to use robots to move sensors around this space. Planning the motion of these robots - coordinating their paths in order to maximize the amount of information collected while placing bounds on their resources (e.g., path length or battery capacity) - is an NP-hard problem. In this paper, we present an efficient path planning algorithm that coordinates multiple robots, each having a resource constraint, that maximizes the "informativeness" of their visited locations. In particular, we use a Gaussian Process to model the underlying phenomenon, and use the mutual information between the visited locations and remainder of the space to characterize the amount of information collected. We provide strong theoretical approximation guarantees for our algorithm by exploiting the submodularity property of mutual information. In addition, we improve the efficiency of our approach by extending the algorithm using branch and bound and a region-based decomposition of thespace. We provide an extensive empirical analysis of our algorithm, comparing with existing heuristics on datasets from several real world sensing applications.