Lead Investigators:

Amarjeet Singh, Maxim Batalin, Bill Kaiser (UCLA) in collaboration with Andreas Krause and Carlos Guestrin (Carnegie Mellon University)

Overview

In many sensing applications, including environmental monitoring, measurement systems must cover a large space with only limited sensing resources. One approach to achieve required sensing coverage is to use robots to convey sensors within this space. Planning the motion of these robots -- coordinating their paths in order to maximize the amount of information collected while placing bounds on their resources (e.g., path length or energy capacity) -- is a NP-hard problem. In this paper, we present an efficient path planning algorithm that coordinates multiple robots, each having a resource constraint, to maximize the "informativeness" of their visited locations. In particular, 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 characterize the amount of information collected. We provide strong theoretical approximation guarantees for our algorithm by exploiting the submodularity property of mutual information. In addition, we improve the efficiency of our approach by extending the algorithm using branch and bound and a region-based decomposition of the space. We provide an extensive empirical analysis of our algorithm, comparing with existing heuristics on datasets from several real world sensing applications.

Approach

When monitoring algae biomass, or in many other real world sensing tasks, planning the motion of such robots – coordinating their paths in order to maximize the amount of information collected – is a fundamental task. Often however, such robots have resource constraints, such as storage battery energy, that limit the distance they can travel, or the number of measurements they can acquire. We thus seek to find informative paths for a collection of robots, placing a bound on the cost incurred by each robot, e.g., on the battery capacity.

To optimize the path of these robots, we must first characterize the notion of informativeness. Since we are addressing spatial phenomena, a common approach in spatial statistics is to use a rich class of probabilistic models called Gaussian Processes (GPs). Using such models, informativeness can be viewed in terms of the uncertainty about our prediction of the phenomena, given the measurements made by the mobile robots. In particular, we use the mutual information (MI) criterion of Guestrin et al. [2005] to quantify the reduction in uncertainty provided by the measurements made along the selected robot paths. Like many other notions of informativeness, mutual information is a submodular function [Guestrin et al., 2005], i.e., it satisfies an important diminishing returns property: More the locations that are already sensed, lesser will be the information gained by sensing a new location.

In this work, we present the first efficient path planning algorithm (eMIP) that coordinates multiple robots, each having a resource constraint, in order to obtain highly informative paths, i.e., paths that maximize some given submodular function, such as mutual information. By exploiting the submodularity, we provide strong theoretical approximation guarantees for our algorithm. We propose an approach, sequential allocation, for extending any single robot algorithm to the multi-robot setting, with minimal effect on the approximation guarantee. Using spatial decomposition and branch and bound techniques, we develop a practical approach for the single robot case, with theoretical guarantees. Using sequential allocation, we then extend our approach to the multi-robot case.

Systems/Experiments

We provide extensive experimental analysis of our algorithm on several real world sensor network data sets, including data collected by the robotic boats in a lake. Our main set of experiments is on measurements of the biomass content in Lake Fulmor, James Reserve. We used data collected by a boat carrying a temperature sensor around the lake, of width around 50 meters and length around 250 meters. Temperature was previously found to be strongly correlated with the algal bloom in the lake. The average speed of the boat was approximately 0.4 m/s. Half of the total measurements (218 different sensing locations) were used to learn a nonstationary Gaussian Process model by maximizing the marginal likelihood, and the rest of the measurements were used for experimentation. We divided the lake into 22 cells, with distance between adjacent cell approximately 21 meters. Based on the average speed, and motivated by a typical measurement duration of roughly 25 seconds, we set the experiment cost to be 10.5 meters.

As our second dataset, we used the existing deployment of 52 wireless sensor motes to learn the amount of temperature variability at Intel Research Berkeley. We divided the complete region into a uniform grid containing 20 equal sized cells, and determined the experimental cost to be 9m (distance to travel between adjacent cells). We learned a GP model using a similar approach as discussed for Lake Fulmor data.

Thirdly, we explored the performance of our algorithm on a precipitation dataset collected from 167 regions during the years 1949-1994. We followed the preprocessing and model learning as described for Lake Fulmor data.

Accomplishments

1. Visiting scholar, Machine Learning Department, Carnegie Mellon University (April, 06 - June, 06)
2. Week long deployment at San Joaquin river, Merced, California, observing the mixing effects and salt load concentration at the river confluence zone.
3. Week long deployment at Lake Fulmor, California, characterizing the growth patterns of phytoplankton in a lake environment.

Future Directions

1. Run the multi-robot path planning approach in real environment using robotic boats at Lake Merced, California, during a deployment planned in February.
2. Extend the work to incorporate specific environmental models (known about the sensing phenomena) as informed priors to improve the model specification for improved sampling fidelity.
3. Work towards multi-robot coordination between robotic systems of different forms, such as NIMS (cable based robotic system) and NAMOS (consisting of buoys for static measurements and boats for surface measurement of the phenomena distribution).

People

Faculty:

• Bill Kaiser, Electrical Engineering, UCLA
• Carlos Guestrin, Machine Learning, Carnegie Mellon

Staff:

• Maxim Batalin, CENS, UCLA

Graduate Students:

• Amarjeet Singh, UCLA
• Andreas Krause, Carnegie Mellon

External Research Partnerships

Machine Learning Department, Carnegie Mellon University