TL;DR
This paper introduces NAVIS, a novel indoor positioning system for Unmanned Ground Vehicles (UGVs) that leverages an improved Maximum Likelihood Estimation (IMLE) algorithm for laser scan matching. NAVIS achieves centimeter-level accuracy in large indoor environments, overcoming limitations of existing methods that struggle with accumulated errors and computational demands.
What Problem Does This Paper Address?
Accurate and reliable indoor positioning for mobile robots, particularly UGVs, is a critical challenge for applications like navigation, asset tracking, and first-aid. While Global Navigation Satellite Systems (GNSS) are standard outdoors, their signals are unreliable indoors. Existing indoor positioning techniques, such as those based on WiFi, Bluetooth, or UWB, have varying degrees of accuracy and availability. Laser scan matching, a core component of Simultaneous Localization and Mapping (SLAM), is promising but faces significant hurdles:
- Accuracy Drift: Traditional methods like Iterative Closest Point (ICP) and Iterative Closest Line (ICL) can suffer from accumulated errors, especially when scan frequencies are low, leading to a loss of positioning accuracy over time.
- Computational Cost: While Maximum Likelihood Estimation (MLE) offers better accuracy, it typically requires high-resolution maps and extensive search, making it computationally expensive and difficult to achieve real-time performance on onboard computers, especially for large areas.
- Scalability: Storing and processing high-resolution maps for large indoor spaces demands significant memory and processing power, posing a challenge for resource-constrained UGVs.
This paper aims to bridge this gap by developing a system that is both accurate and computationally efficient for real-time, large-area indoor positioning.
Methods
The NAVIS system employs a novel fusion positioning algorithm that combines the strengths of different approaches:
- Improved Maximum Likelihood Estimation (IMLE): This is the core of the proposed system. IMLE builds upon traditional MLE by incorporating several key improvements:
- ICP Preprocessing: The Iterative Closest Point (ICP) algorithm is used first to obtain a rough initial position estimate. This rough estimate significantly narrows down the search scope for the subsequent MLE step, reducing computational load.
- Multi-Resolution Patch-Divided Likelihood Map: To handle large areas efficiently, the likelihood map is divided into manageable patches. This allows for dynamic loading and unloading of map data, reducing memory requirements. Furthermore, a multi-resolution approach is used, with different layers offering varying levels of detail, enabling faster searches in less critical areas and more detailed searches where needed.
- Brute Search on Multi-Resolution Layers: A comprehensive brute-force search is performed across these multi-resolution map layers. By leveraging the likelihood values within the refined search scope, the algorithm aims to find the global optimum position for each scan.
- Line-Feature-Based Likelihood Determination: To improve robustness, especially in environments with sparse features or noise, a strategy is employed to extract line features from laser scans. This helps in more accurately representing environmental features for likelihood calculations.
- NAVIS Platform: The system is implemented on a custom UGV platform named NAVIS, built on a low-cost robot (iRobot®) equipped with an IBEO LUX laser scanner and an odometer.
Datasets
The paper describes experiments using both simulated data and real-world field test data.
- Simulated Data: Simulated laser range data was generated using a ray-cast algorithm with specific parameters (angular resolution, field of view, noise variance) to mimic real-world sensor behavior. The simulated environment was a simple T-shape.
- Field Test Data: Real-world data was collected from a corridor on the second floor of the Finnish Geodetic Institute (FGI) building. This environment presented challenges such as glass walls and plants, which introduced noise.
The paper does not introduce a new benchmark dataset but rather uses these datasets to evaluate the performance of NAVIS against existing methods.
Key Insights and Ideas
- Fusion is Key: The success of NAVIS lies in its fusion approach, combining the speed of ICP for initial localization with the accuracy of MLE for refinement. This hybrid strategy effectively balances computational cost and precision.
- Hierarchical Maps for Scalability: The multi-resolution, patch-divided likelihood map is a crucial innovation for handling large indoor spaces. By breaking down the map and loading data dynamically, it overcomes memory and processing limitations.
- Line Features Enhance Robustness: Incorporating line features for likelihood calculation improves the system's ability to handle environments with less distinct point features or noisy sensor data.
- Centimeter-Level Accuracy Achieved: The proposed IMLE algorithm demonstrates the capability to achieve centimeter-level positioning accuracy, a significant improvement over many existing methods.
Key Results
- Simulated Data:
- IMLE achieved RMS errors of 0.02 m in the local coordinate frame, significantly outperforming ICP (1.2 m) and Monte Carlo (0.77 m).
- The system provided consistent positioning with centimeter accuracy.
- Field Test Data:
- IMLE achieved RMS errors of 0.09 m, with a mean error of 0.06 m and a maximum error of 0.52 m.
- ICP and Monte Carlo showed significantly higher errors (RMS: 4.4 m and 0.86 m, respectively).
- The system achieved an updating frequency of 12 Hz in feature-rich environments and 2 Hz in feature-poor environments, enabling real-time applications.
- Real-Time Performance:
- Average scan matching times were: ICP (32 ms), Monte Carlo (45 ms), and IMLE (112 ms). While IMLE is slower, its accuracy gain is deemed worthwhile.
- The system demonstrated efficient handling of large areas (up to 300x300 m) with manageable time costs due to dynamic map loading.
Limitations and Future Work
- Environmental Dependency: The authors acknowledge that the IMLE algorithm's performance is heavily dependent on the complexity of the environment. This might limit its applicability in certain scenarios.
- Noise Sensitivity: While improved, the system can still be affected by noisy sensor data, particularly from transparent surfaces like glass walls, as observed in field tests.
- Future Work: The authors propose integrating additional sensors, such as cameras and gyroscopes, into the NAVIS platform. This is intended to enhance system stability and broaden its applicability across various fields.
Summary updated