Sampling-based Motion Planning for Robotic Information Gathering

We propose an incremental sampling-based motion planning algorithm that generates maximally informative trajectories for guiding mobile robots to observe their environment. The goal is to find a trajectory that maximizes an information metric (e.g., variance reduction, information gain, or mutual information) and also falls within a pre-specified budget constraint (e.g., fuel, energy, or time). Prior algorithms have employed combinatorial optimization techniques to solve these problems, but existing techniques are typically restricted to discrete domains and often scale poorly in the size of the problem. Our proposed Rapidly-exploring Information Gathering (RIG) algorithm extends ideas from Rapidly-exploring Random Graphs (RRGs) and combines them with branch and bound techniques to achieve efficient optimization of information gathering while also allowing for operation in continuous space with motion constraints. We provide a rigorous analysis of the asymptotic optimality of our approach, and we present several conservative pruning strategies for modular, submodular, and time-varying information objectives. We demonstrate that our proposed approach finds optimal solutions more quickly than existing combinatorial solvers, and we provide a proof-of-concept field implementation on an autonomous surface vehicle performing a wireless signal strength monitoring task in a lake.