Random Mapping Method for Large-Scale Terrain Modeling

Xu Liu, Decai Li, Yuqing HeAAAI 2022 · DOI

Abstract

Modeling large-scale, unstructured terrain is a critical challenge for mobile robots, often hindered by sensor noise, occlusions, and the high computational costs of traditional methods like Gaussian Processes. This paper introduces the Random Mapping Method (RMM), which projects sensor data into a high-dimensional space using fixed random base functions, enabling efficient terrain reasoning via linear regression. RMM significantly reduces memory and computational overhead, achieving up to 860x faster training times than state-of-the-art methods while maintaining high accuracy on datasets with millions of points.

Introduction

When robots explore environments such as quarries or planetary surfaces, they generate massive point clouds. Creating a continuous 3D model from this data is difficult due to sensor uncertainty, incomplete coverage (occlusions), and the cubic computational complexity ($O(n^3)$) of standard regression techniques. Existing solutions often struggle with the trade-off between memory efficiency and real-time processing capabilities.

The Random Mapping Method (RMM)

The proposed RMM addresses these challenges through a two-step parametric approach:

  1. Random Feature Mapping: Input 2D coordinates are projected into a high-dimensional space using a fixed, randomly generated weight matrix ($W$) and a nonlinear activation function (e.g., sine or sigmoid). Unlike traditional neural networks, the weights in $W$ are not trained, which drastically simplifies the learning process.
  2. Linear Regression: In the high-dimensional feature space, the terrain data becomes approximately linearly distributed. The robot learns a set of linear weights ($\beta$) to predict elevation, a task that can be solved efficiently using Singular Value Decomposition (SVD) or Stochastic Gradient Descent (SGD).

This method is inherently parallelizable and parametric, meaning only the weights $\beta$ need to be stored, resulting in a highly compressed map representation.

Experimental Evaluation

The RMM was tested on three large-scale datasets:

  • Planet: 731,937 points of planetary-like terrain.
  • Quarry: An industrial site with nearly 40 million points.
  • Mountain: A 3km x 3km area with over 43 million points collected via UAV.

Key Results and Discussion

Accuracy and Convergence

A key theoretical and practical finding is that as the mapping dimension ($M$) increases, the model's training error converges toward zero. This allows for a tunable trade-off between model complexity and accuracy.

Figure 1: Convergence of training (a) and test (b) Mean Minimum Square Error (MMSE) as the mapping dimension increases across different activation functions.

As shown in the figure above, nonlinear activation functions like 'sin' and 'sigmoid' significantly outperform a simple linear baseline, particularly as the mapping dimension grows. The "lenear" (linear) baseline remains stagnant, highlighting the necessity of the nonlinear projection for effective terrain reasoning.

Computational Efficiency

RMM demonstrates remarkable scalability. On the planet dataset, it was approximately 860x faster in training and 1,000x faster in testing compared to Gaussian Process Regression (GPR). Memory usage is also drastically reduced; for the quarry dataset, RMM required only 0.017 Mb of storage, compared to over 1,500 Mb for competing methods.

Figure 2: Time consumption for training, testing, and mapping phases across different mapping dimensions.

The time consumption scales linearly with the mapping dimension, as illustrated in the figure above. This predictable scaling, combined with parallel processing capabilities, allowed the authors to process 43 million points in just 0.6 seconds on a standard 16-core CPU.

Conclusion

The Random Mapping Method provides a faster, leaner alternative for large-scale terrain modeling. By utilizing the power of random features, it bypasses the heavy computational requirements of non-parametric models. Future work will focus on automating hyperparameter selection and improving performance on non-stationary terrains with abrupt elevation changes.

Summary updated

BibTeX
@inproceedings{liu2022random,
  author = {Xu Liu and Decai Li and Yuqing He},
  title = {{Random Mapping Method for Large-Scale Terrain Modeling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20477},
}
Figure