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:
- 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.
- 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.
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.
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