Adaptive sampling in robotic sensor networks for environmental applications

Observation and monitoring of complex environmental processes that occur in the earths hydrosphere are critical to our understanding of the environment and its health. Such processes occur as spatio-temporal distributions and trends of environmental variables at multiple spatial and temporal scales. In recent years, technologies such as distributed sensor networks and mobile sensor platforms (e.g. Autonomous Underwater Vehicles, or AUVs) have emerged and enable much more pervasive in situ observation of such processes. However, effective deployment of such advanced instrumentation in remote and hostile environments requires extensive planning and logistic management as well as high deployment and maintenance costs.;This thesis is concerned with the development of algorithms to guide an adaptive exploration of an unknown region through systematic choice of sampling locations and appropriate cooperative routing of vehicles to acquire this information. This work focuses on the observation of environmental phenomena that occur as spatial distributions of physical, chemical, and biological variables in two and three dimensions. While traditional methods of observation utilize uniform grid search, that approach is not the most efficient for non-uniform (non-homogeneous) distributions when information gain is weighted against sampling costs.;While several different approaches are discussed here, including statistical and geometric views of the problem, the principal focus of this research is a class of algorithms based on reformulation of the problem from a perspective of multiresolution signal processing. In particular, variation sensitive multiresolution sample distributions are achieved through an adaptive sampling mechanism that represents an iterative solution for the estimation of the unknown process. The resulting Multi-Scale Adaptive Sampling (MSAS) Algorithms are studied using two classes of selection criteria, greatest residue and expectation maximization. In addition, the consistency, stability, sensitivity, and noise immunity of the algorithms are examined and compared to alternative methods.;The four principal contributions of this thesis will be: (1) The adaptive sampling problem is formulated in a signal processing framework. This approach leads to a novel systematic global representation of existing observations and a basis for prediction of variations through model residue analysis, as described in (3) below. (2) A class of geometric algorithms that achieve sample distribution through variation sensitive partitioning of the domain are developed and evaluated. In this approach, piecewise linear models are employed as surrogate models. For unmodeled processes for which little or no prior knowledge base exists, the Iterative Curvature-based Adaptive Sampling Algorithm (ICASA) is shown to achieve effective incremental adaptive sampling of two-dimensional regions. (3) A class of multiscale adaptive sampling (MSAS) algorithms achieves consistent reconstruction through interpolating constraints on the adaptive non-uniform sampling process and incorporating hierarchical multiscale basis functions that facilitate coarse to fine modeling of the underlying function. The resulting MSAS Algorithms leverage the features of a hierarchical multiscale model on a grid to adaptively guide variation sensitive sampling. Two selection mechanisms have been studied: (1) Greatest Residue (MSAS-GR) and (2) Greatest a-priori Correlation (MSAS-GC). The effectiveness of the adaptive selection mechanisms is demonstrated via comparison to random selection, and a sensitivity analysis of the sample distribution to measurement noise has also been conducted. (4) MSAS class of algorithms is augmented with path planning module that generates an efficient path through the sample distribution. The realizability of the sample distributions is evaluated for the simulated deployment of AUV platforms. The performance of MSAS is compared with two different non-adaptive strategies for realization of uniform sample distribution that are commonly employed. The performance of the sampling algorithms is then characterized in terms of the localization of the functions. It is shown that MSAS maximizes sampling in the critical region, and consequently affords considerable savings in measurement costs when compared uniform sampling techniques. It is shown that for functions with localized features, variation sensitive sampling yields significant savings in measurement and travel costs. In addition, the relative performance of the algorithms under different sensor and vehicle profiles is evaluated, and it is shown that amongst the algorithms evaluated, MSAS is the least sensitive to changes in mission profile and is thus a viable for a larger class of mission scenarios.