Efficient Informative Sensing using Multiple Robots

By Amarjeet Singh, Andreas Krause, Carlos Guestrin, William J. Kaiser. Journal of Artificial Intelligence Research, 2014

385 citations recorded by the source corpus.

The need for efficient monitoring of spatio-temporal dynamics in large environmental applications, such as the water quality monitoring in rivers and lakes, motivates the use of robotic sensors in order to achieve sufficient spatial coverage. Typically, these robots have bounded resources, such as limited battery or limited amounts of time to obtain measurements. Thus, careful coordination of their paths is required in order to maximize the amount of information collected, while respecting the resource constraints. In this paper, we present an efficient approach for near-optimally solving the NP-hard optimization problem of planning such informative paths. In particular, we first develop eSIP (efficient Single-robot Informative Path planning), an approximation algorithm for optimizing the path of a single robot. Hereby, 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 quantify the amount of information collected. We prove that the mutual information collected using paths obtained by using eSIP is close to the information obtained by an optimal solution. We then provide a general technique, sequential allocation, which can be used to extend any single robot planning algorithm, such as eSIP, for the multi-robot problem. This procedure approximately generalizes any guarantees for the single-robot problem to the multi-robot case. We extensively evaluate the effectiveness of our approach on several experiments performed infield for two important environmental sensing applications, lake and river monitoring, and simulation experiments performed using several real world sensor network data sets.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/48310889bab1e618356e4441ddc4d4b132258c6f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Sampling-based robotic information gathering algorithms (2014, background): “Such problems have been shown to be NP-hard (Singh et al., 2009), or even PSPACE-hard (Reif, 1979), depending on the form of the objective function and the space of possible trajectories.”
Learning to soar: Resource-constrained exploration in reinforcement learning (2015, background): “Active and informative path planning algorithms developed by Singh et al. (2009) and Hollinger et al. (2013) have exploited the submodularity property of information gain to select the most informative set of sensing locations, while Stachniss et al. (2005), Amigoni and Caglioti (2010) and Levine…”
Sensor planning for a symbiotic UAV and UGV system for precision agriculture (2013, methodology): “[7] presented an approximation algorithm to find a path maximizing mutual information between “cells” that are sampled and not sampled, subject to a distance budget based on the algorithm in [8].”
A Bayesian exploration-exploitation approach for optimal online sensing and planning with a visually guided mobile robot (2009, background): “In Singh et al (2009), a sound way of exploiting sub-modularity in these planning and sensing domains is proposed.”