  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 in-field for two important environmental sensing
applications, lake and river monitoring, and simulation experiments performed
using several real world sensor network data sets.
