COORDINATION AND LEARNING ALGORITHMS FOR MULTI-ROBOT INFORMATION GATHERING

Abstract

With the rapid improvement in perception and planning technology, robots are being increasingly used as smart, adaptive sensors to gather information in applications such as environment monitoring, infrastructure inspection, and security and surveillance. To fully exploit the potential offered by robotic sensing, we need efficient and reliable decision-making techniques to decide when, where, and how to gather information. Such decision-making techniques need to account for the uncertainty and partial knowledge inherent in the working environment. The goal of this dissertation is to design algorithms to enable a multi-robot team to collectively and efficiently gather information on spatiotemporal fields without full knowledge of the environment. Our contributions span the full spectrum of the knowledge of the environmental conditions: from one extreme where the environmental model is fully known to the other extreme where the environmental model is unknown but can be learned from empirical data. We present several efficient (i.e., polynomial time) and effective (i.e., optimal or bounded approximation guarantees) algorithms for multi-robot information gathering.

In the first part of the dissertation, we study coordination algorithms when the environmental model is fully or partially known. Specifically, for the case where the environmental model is fully known, we consider the challenge imposed by the connectivity requirement of the team. We present an algorithm for connectivity-constrained submodular maximization for information gathering that requires intermittent communication among the robotic team. For the case where the environment is partially known, and uncertainty exists, we seek to make the multi-robot team robust to the possible failures caused by the uncertainty. When the uncertainty is upper-bounded, we present a constant-factor approximation algorithm for robust multiple-path submodular orienteering. When the uncertainty is stochastic, and the distribution is known, we introduce two risk-sensitive coordination problems for aerial-ground long-term information gathering.

In the second part of the dissertation, we study the case where the environmental model is initially unknown and needs to be learned from the data. Classically, such a learning process is independently conducted without considering the downstream task. By contrast, we present a framework that incorporates the downstream decision-making problem into the learning process. Such integration will help reduce the misalignment between the prediction model and the downstream task. The misalignment refers to a predictor that despite achieving high predictive accuracy in the learning phase may not necessarily result in good decisions in the downstream task. The general methodology to achieve such integration is tomake the combinatorial optimization differentiable, which then can be treated as a differentiable module in the learning process. In addition to algorithm design, we present empirical results for applications such as active target tracking, ocean monitoring, and persistent monitoring.