Robust Environmental Mapping by Mobile Sensor Networks

Hyongju Park, Jinsun Liu, Matthew Johnson-Roberson, Ram Vasudevan

Abstract

Constructing a spatial map of environmental parameters is a crucial step to preventing hazardous chemical leakages, forest fires, or while estimating a spatially distributed physical quantities such as terrain elevation. Although prior methods can do such mapping tasks efficiently via dispatching a group of autonomous agents, they are unable to ensure satisfactory convergence to the underlying ground truth distribution in a decentralized manner when any of the agents fail. Since the types of agents utilized to perform such mapping are typically inexpensive and prone to failure, this results in poor overall mapping performance in real-world applications, which can in certain cases endanger human safety. This paper presents a Bayesian approach for robust spatial mapping of environmental parameters by deploying a group of mobile robots capable of ad-hoc communication equipped with short-range sensors in the presence of hardware failures. Our approach first utilizes a variant of the Voronoi diagram to partition the region to be mapped into disjoint regions that are each associated with at least one robot. These robots are then deployed in a decentralized manner to maximize the likelihood that at least one robot detects every target in their associated region despite a non-zero probability of failure. A suite of simulation results is presented to demonstrate the effectiveness and robustness of the proposed method when compared to existing techniques.

Introduction

Environmental mapping—whether for tracking chemical leaks, monitoring forest fires, or generating elevation models—is increasingly performed by Mobile Sensor Networks (MSNs). While using a fleet of small, inexpensive robots is cost-effective and scalable, it introduces a major vulnerability: hardware failure. Most existing mapping algorithms assume robots are perfectly reliable. If a robot responsible for a specific sector fails, that area often remains unmapped or produces erroneous data.

Furthermore, traditional "optimal" strategies, such as those based on mutual information, are computationally expensive—often scaling exponentially with the number of robots—and require centralized coordination. This paper addresses these challenges by introducing a decentralized, scalable deployment strategy that allows a fleet of failure-prone mobile robots to map an environment accurately and robustly.

Methodology

The proposed framework addresses robustness and complexity through three main components:

Higher-Order Voronoi Partitions

In a standard Voronoi diagram, a region is assigned to the single nearest robot. This research utilizes Order-$k$ Voronoi partitions, where each region is associated with its $k$ nearest neighbors. By setting $k > 1$, every point in the environment is monitored by multiple robots, providing built-in redundancy. If one robot fails, its neighbors in the Order-$k$ cell maintain coverage, ensuring the system can tolerate up to $k-1$ failures in a given area without data loss.

Optimal configuration using the robust method with higher-order Voronoi partitions.

Decoupled Sensor Model and Gradient Descent

To avoid the exponential computational complexity of traditional information-theoretic approaches, the authors decouple detection (the probability a robot sees a target) from measurement (the estimation of the value at that point). This simplification allows robots to compute movement gradients with linear complexity relative to the number of sensors. Each robot independently calculates its movement path to minimize the probability of missed detections within its assigned Voronoi region using decentralized gradient descent.

Bayesian Mapping

The system reconstructs the map using a Sequential Importance Resampling (SIR) particle filter. To ensure a more uniform distribution of "belief particles" across the map compared to standard random sampling, a Halton-Hammersley sequence is employed. This quasi-random sequence improves the efficiency of the Bayesian update process.

Experimental Evaluation

The algorithm was evaluated using simulated environments based on real-world Digital Elevation Models (DEM) from mountainous regions in Oregon and Connecticut, USA. Simulations involved up to 100 mobile robots, with up to 20% of the fleet experiencing sensor failures. The proposed "Robust" method was benchmarked against "Non-robust" (standard Voronoi) and "Max Information Gain" (centralized) techniques.

Results and Discussion

The robust method (k=2) demonstrated significant resilience to hardware failure. In scenarios where 20% of sensors failed, the robust method produced a reconstructed map with significantly lower Root Mean Square Error (RMSE) than the non-robust version.

Comparison of ground truth elevation with mapping results and RMSE for non-robust vs. robust methods.

While centralized "Max Information Gain" approaches technically achieve the lowest error in perfect conditions, the proposed decentralized robust method was nearly as accurate while being much faster to compute and significantly more resilient to real-world failures. Convergence analysis using K-L divergence confirmed that the method consistently converges toward the ground-truth map even under network degradation.

Conclusion

By treating redundancy as a geometric property through spatial partitioning, this approach achieves robustness without the need for complex error-checking code. The decoupling of sensing and measurement ensures scalability for large-scale deployments. Future work will focus on adapting the strategy for dynamic targets, such as spreading gas clouds, and validating the range sensor model through physical multi-robot experiments.

Summary updated

Abstract

Constructing a spatial map of environmental parameters is a crucial step to preventing hazardous chemical leakages, forest fires, or while estimating a spatially distributed physical quantities such as terrain elevation. Although prior methods can do such mapping tasks efficiently via dispatching a group of autonomous agents, they are unable to ensure satisfactory convergence to the underlying ground truth distribution in a decentralized manner when any of the agents fail. Since the types of agents utilized to perform such mapping are typically inexpensive and prone to failure, this results in poor overall mapping performance in real-world applications, which can in certain cases endanger human safety. This paper presents a Bayesian approach for robust spatial mapping of environmental parameters by deploying a group of mobile robots capable of ad-hoc communication equipped with short-range sensors in the presence of hardware failures. Our approach first utilizes a variant of the Voronoi diagram to partition the region to be mapped into disjoint regions that are each associated with at least one robot. These robots are then deployed in a decentralized manner to maximize the likelihood that at least one robot detects every target in their associated region despite a non-zero probability of failure. A suite of simulation results is presented to demonstrate the effectiveness and robustness of the proposed method when compared to existing techniques.
BibTeX
@inproceedings{park2018robust,
  author = {Hyongju Park and Jinsun Liu and Matthew Johnson-Roberson and Ram Vasudevan},
  title = {{Robust Environmental Mapping by Mobile Sensor Networks}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2018},
  url = {https://openreview.net/forum?id=hGa_3MzhEZ},
}
Figure