Distributed, Scalable and Resilient Information Acquisition for Multi-Robot Teams

Advances in robotic mobility and sensing technology have the potential to provide new capabilities in a wide variety of information acquisition problems including environmental monitoring, structure inspection, localization and mapping of unknown environments, and search and rescue, amongst many others. In particular, teams composed of multiple robots have shown great potential in solving these problems, though it is challenging to design efficient algorithms that are distributed and scale well, and even more complex in hazardous or challenging environments. The purpose of this dissertation is to provide novel algorithms to the capabilities of multi-robot teams to gather information which are distributed, scalable, and resilient. The first part of the dissertation introduces the single-robot information acquisition problem, and focuses on algorithms that may be used for individual robots to plan their own trajectories. The methods presented here are search-based, meaning that an individual robot has a finite set of actions and is seeking to efficiently build a search tree over a known planning horizon. The first method presented details how to use the concept of algebraic redundancy and closeness to achieve a smooth trade-off of completeness in the exploration process, as an anytime planning algorithm. Next we show how a single robot can compute an admissible and consistent heuristic which guides the search towards the most informative regions of the state space, using the classic A* planning algorithm, drastically improving the search efficiency. The next chapter of the dissertation focuses on how to build on the single robot planning algorithms to create efficient algorithms for multi-robot teams, which operate in a distributed manner and scalable manner. The first method presented is coordinate descent,5otherwise known in the literature as sequential greedy assignment. This algorithm is implemented in a multi-robot target tracking hardware experiment. Next, we formulate an energy-aware multi-robot information acquisition problem, which allows for heterogeneity and captures trade-offs between information and energy expenditure. However, this results in a non-monotone objective function. Therefore we propose a new algorithm based on distributed local search, which achieves performance guarantees through a diminishing returns property known as submodularity. The final chapter focuses on hazardous or failure prone environments that necessitate resilience to a fixed number of failures in the multi-robot team. We provide a definition of resilience, and formulate a resilient information acquisition problem. We then propose the first algorithm that solves this problem through an online application of robust trajectory planning, and provide theoretical guarantees on its performance. We then present three unique applications of the resilient multi-robot information acquisition framework, including target tracking, occupancy grid mapping, and persistent surveillance which demonstrate the efficacy of our approach