OVERVIEW

A series of new challenges accompany the development and application of NIMS for environmental monitoring. A primary example lies in the accurate reconstruction of distributed environmental phenomena, including, for example the measurement of microclimate dynamics. Here, the accurate determination of space- and time-dependent variables of temperature, water vapor concentration, and solar illumination within the complex environment is essential to the investigation of global change phenomena. These variables must be sampled in a vast three-dimensional volume while both spatial and temporal variations are unknown and initially are unpredictable. Thus, while NIMS capabilities offer the ability to explore large volumes, it is now required that sampling strategies be properly devised such that the density of sampling points is dynamically and autonomously adjusted using information derived from sensor systems. This requires a combination of new sampling algorithms, coordinated mobility, and proper dynamic selection of sensor assets. In some applications, this will also require the coordination of multiple sensor nodes. Objectives for optimization may include the accurate reconstruction of variable distribution or may include the optimization of accuracy associated with a variable set derived from combined, distributed measurements.

The NIMS sensor node motion is limited by mechanical means to a minimum resolvable unit, referred to here as a pixel, indicated schematically in Figure 1. Pixels represent the upper bound on spatial sampling frequency. Exhaustive sampling of the environment at all pixels may generally be prohibitively expensive in time and resource cost. Indeed, for many examples, an attempt to sample at highest spatial resolution may result in an unacceptable latency with respect to visiting environmental regions, resulting in errors in the reconstruction of dynamically varying environmental phenomena. Thus, the development of a NIMS sampling policy is required in order to minimize reconstruction error for a set of finite resources in node mobility. Our approach assigns the NIMS nodes to operate as “statistical agents” that are commissioned to acquire data regarding variable distributions by appropriately scheduled exploration. This approach is intended to apply to environmental conditions where no prior knowledge exists regarding variable distribution. However, it is also intended to be applicable to instances where domain knowledge may be applied to superimpose rules that focus exploration and sampling (for example, to those regions estimated by domain knowledge to require the highest spatiotemporal sampling rate).

Optimal designs for estimators have been studied extensively in the statistics literature. These approaches often assume a parametric form for the estimate. Given a generic learning algorithm, the problem of optimal design is much harder. Optimal designs for simple kernel methods were previously studied where it was found that the best placement of points depends on the second derivative of the function; places with high curvature should have relatively more points than other regions. Others have studied designs for local linear smoothing, ultimately proposing a batch-sequential algorithm. The NIMS Fidelity Driven Sampling algorithms are designed with the goal of sequentially constructing a sampling pattern where at each step, samples are chosen that improve the estimate of the sensed field.  Other studies show sampling plans in the context of kernel smoothing. Points are added one at a time, chosen so as to reduce an estimate of the integrated squared error. The same problem has been characterized using neural networks as their estimators known as active learning. To describe the Fidelity Driven Sampling process one can select points to minimize an information criterion or study the mean squared error. In each case, it is assumed the bias is negligible and attention is focused on the variance of the estimator. Some also introduced the notion of path constraints on the samples, a topic that will be important in our ultimate deployment of Fidelity Driven Sampling.

The Fidelity Driven Sampling algorithm reported here relies on a mean squared error estimation approach and an underlying learning algorithm based on a local linear smoother. Further, a variable bandwidth is assumed based on nearest neighbors. This algorithm, termed Fidelity Driven Sampling (FDS), attempts to reduce mean square error at each sampling point by adjusting point density and location. It will be further described and evaluated below. Mean squared error can be decomposed into a bias component and a variance component. In our application of solar illumination mapping, measurement noise is a negligible fraction of the overall signal hence our greatest concern will be bias. In other applications, bias may not be dominant, and other estimation methods will be needed. In these other regimes, attention will likely focus on tasks other than field estimation, or if a snapshot of the field is desired, a longer learning process involving repeated measures in time will be required. This is all the subject of future work. Throughout the sampling process, FDS maintains an estimate of the field being observed. In this paper, a local linear fitting routine is chosen, with its bandwidth varying to include a fixed number of nearest neighbors. Using this estimate, the FDS loop identifies regions or strata exhibiting a high degree of misfit. At each step in the sampling process, FDS adds points to that stratum with the largest error. In so doing, the FDS algorithm reduces the distance between neighbors and effectively lowers the bandwidth of the local linear fit within the stratum. The algorithm continues adding points to poor fitting strata until either an overall sample budget is exhausted or a desired fidelity limit is achieved. Local linear fits have been chosen because these can tie the notion of sampling with the resolution of structures expected in the variable field. In principle, any nonparametric procedure could be employed including thin plate splines or other radial basis functions.

Figure 2 shows pseudo code description of the Fidelity Driven Sampling adaptive algorithm. The NIMS robotic system continues Fidelity Driven Sampling for the entire period of operation in the environmental mapping state. The FDS algorithm then calls the procedure predict-frame() which returns the estimate of the environmental variable field. The algorithm follows a procedure of stratifying a sampling region and according to observed measurements in the region and for each stratum, adjusting the number of sampling points. In addition, in the experiment section below, the performance of Raster Scanning, and the new Fidelity Driven Sampling algorithms are compared through simulation of each sampling method with actual experimental data. It is important to note that Fidelity Driven Sampling provides an autonomous system that seeks to assign sampling points to achieve a specified threshold error value (or a specified stratification rank). By estimating error magnitudes, Fidelity Driven Sampling can actively adapt to achieve a sampling fidelity objective. This differs fundamentally from raster scan methods that are not informed of residual errors. It is most important to note that Fidelity Driven Sampling, being adaptive, requires no prior knowledge of the environmental variable field characteristics and will rather report these characteristics. This predict-frame() procedure starts by inserting a root stratum in a queue. Here, the root stratum corresponds to the entire transect that is the entire region of study. The predict-frame() procedure then initiates a loop that extracts strata with highest product of mean square error and area. It determines the sampling points to be added to the strata and then the mobile sensor moves to visit those points and sample corresponding data. After sampling points in the strata, it performs a local linear kernel regression and reevaluates the estimate of the phenomenon. Error is computed in terms of the absolute difference between estimated and sampled values. If the computed error in the strata falls below a threshold, predict-frame() exits the inner loop and proceeds to examine more strata or otherwise divides the strata into horizontal or vertical substrata depending on which division leads to the greatest reduction in error. Following Fidelity Driven Sampling operation (or raster scanning data acquisition) the returned variable field with its distribution of sample points was then supplied to a standard estimation algorithm (that performs estimation) and returns an environmental field map. This final result is referred to as the reconstruction of the variable field. Experimental results and evaluation of reconstructions will be discussed in experimental section below for varying field characteristics.

SYSTEMS / EXPERIMENTS

As described above, Fidelity Driven Sampling exploits mobile sensing capabilities to explore the variable field, stratify this into regions of greatest required sample density, and then sample in these regions adaptively to minimize estimated sampling error. Fidelity Driven Sampling operates in an iterative architecture seeking to reach a desired threshold error. While multiple error threshold policies may be applied, two are explored here: 1) an error threshold defined as a maximum tolerated mean squared error estimate across the entire environmental field, and 2) a maximum allowed stratification rank. Adjustment of these thresholds permits the mobile sensor node to return an environmental field map with a specified estimated fidelity without the requirement for any prior knowledge of the field characteristics. An inability to reach a specified estimated error (within a given time or rank level limit) will be reported by the Fidelity Driven Sampling algorithm. This then provides the user with yet further assurance of proper sampling and confidence in returned data.

Fidelity Driven Sampling is evaluated here by subjecting the algorithm to two environmental variable fields having two extremes case in their curvature characteristics. For one limit, the environmental variable field was created by placing many obstacles in the illumination field to emulate the characteristically most complex patterns observed in the natural environment. In addition, the algorithm was also subjected to an environmental variable field that showed low curvature created by casting only diffuse shadowing on the transect. This latter case is characteristically similar to the least complex fields observed under clear forest canopy structure.

The performance of the Fidelity Driven Sampling algorithm was evaluated by allowing the algorithm to autonomously operate and return a sample distribution. This distribution then was supplied to the estimator to return a reconstructed variable map. Finally, this map was compared with the actual measured data obtained by exhaustively moving the node at his highest resolution through the variable field. This returned a ground truth map of the scene.

The results of Fidelity Driven Sampling were then compared with conventional raster scanning data acquisition that performs the role of a conventional pre-planned and non-adaptive sampling strategy. Fidelity Driven Sampling algorithm shows a value of Mean Squared Error for its reconstruction compared to ground truth that meets or is superior to that of raster scanning. However, this must be achieved without preplanning and must be independent of the nature of the field characteristic. We examined both the returned reconstruction as well as its mean of squared error over the entire transect. It is important that Fidelity Driven Sampling shows a monotonic decrease in mean squared error for an increase in stratification rank level. We compared the result of FDS with raster scanning for both rough and smooth phenomena.

A test of the performance of this approach is shown in Figure 5. Note that the actual mean squared error (computed between the reconstruction and ground truth across the transect) reduces with increasing stratification rank. Also, Figure 6, shows the dependence of mean squared error on sample density for Fidelity Driven Sampling (Adaptive) and raster scanning (Raster) methods.

Fidelity Driven Sampling vs. Rough Phenomena

Figure 3 at left shows a map of both ground truth and the positions of both strata and actual sample points selected by Fidelity Driven Sampling during an experimental session. Note that the sample point density increases in regions of greatest field curvature. This experimental result was captured as the Field Driven Sampling system passed through stratification rank 5 and had selected 489 sample points within the transect. Figure 3 at right shows the reconstruction resulting from this. Close agreement in field shapes is observed.

Fidelity Driven Sampling vs. Smooth Phenomena

The sample distribution results and reconstruction results for a rank level of 5 are shown in Figures 4 for an environmental field showing dramatically less curvature than that of Figure 3. A comparison of mean squared error performance between Fidelity Driven and raster scanning is shown in Figure 6. Note that for this reduced curvature, not only does Fidelity Driven Sampling converge to a specified mean squared error; it is equal or superior to raster scanning in efficiency with respect to numbers of sample points. The combination of these tests provides a successful evaluation of the performance of Fidelity Driven Sampling for autonomously adjusting sample density through appropriate motion control and sampling of the mobile sensing system. As has been discussed this sampling method seeks to establish a reconstructed variable field with a specified maximum sampling error without requiring prior knowledge or planning.

PEOPLE

FACULTY

Deborah Estrin
William J. Kaiser
Mark Hansen
Gaurav S. Sukhatme

STAFF

Mohammad Rahimi

GRADUATE STUDENTS

Yan Yu