Dual Algorithm Upgrade Accelerates Indoor Robot Navigation by Eighty-Five Percent

Roboticists have developed an integrated navigation framework that accelerates indoor wheeled robot path planning by over eighty-five percent while constraining spatial mapping errors to under two percent across complex environments. The investigation, published in Discover Robotics by Ershen Wang, Wenqiang Huo, Song Xu, Pingping Qu, and La Na, tackles two long-standing bottlenecks in autonomous ground vehicle deployment: cumulative odometric drift during real-time map generation and excessive node computation during global route calculation. Indoor mobile robots operating in automated warehouses, clinical facilities, and emergency response operations depend on Simultaneous Localization and Mapping to construct spatial representations while simultaneously tracking their coordinates. However, discrepancies between physical wheel rotation and mathematical odometry regularly compromise map fidelity, while traditional grid search algorithms expend substantial computational power exploring redundant travel paths. By pairing an Extended Kalman Filter that fuses inertial angular velocity with wheel encoders alongside a dynamic bidirectional heuristic search, the engineering team demonstrated significant simultaneous improvements in mapping precision and trajectory computation speed across rigorous computer simulations and physical indoor validation trials.

The first structural challenge addressed by the study involves the vulnerability of probabilistic grid-mapping routines to rotational wheel slippage and high-frequency motion disturbances. Classic probabilistic estimation techniques like Gmapping rely heavily on wheel encoder readings to update kinematic state equations and predict particle distributions before incorporating planar laser scans from light detection and ranging sensors. While linear, forward-travel trajectories generate comparatively accurate spatial approximations, rapid turns and floor vibrations introduce severe rotational discrepancies. In uncorrected systems, wheel slippage corrupts heading angle calculations, causing successive map updates to distort room geometry, produce ghosted wall boundaries, and fail closed-loop alignment tests. The research team evaluated single-odometry performance using open-access benchmarking datasets, revealing that trajectories matched ground truth closely along straight corridors but deviated sharply following consecutive turns. Scan-matching methods such as Hector SLAM omit odometry entirely, which limits positional accuracy whenever turning velocities increase.

To overcome these rotational inaccuracies without introducing burdensome computational overhead, the researchers engineered the Multi-Sensor Fusion Improved Gmapping algorithm, termed MSFI-Gmapping. Rather than ingesting raw linear acceleration data from low-cost inertial measurement units—which often introduces sensor noise and requires complex adaptive filtering—the team deliberately fused only high-frequency angular velocity from the inertial unit with wheel encoder feedback inside an Extended Kalman Filter. The discrete filter tracks a three-element state vector representing planar Cartesian coordinates and orientation heading in the world frame. During the prediction stage, wheel encoder increments drive nonlinear state propagation and covariance estimation. During the measurement update stage, the filter ingests the inertial measurement unit’s angular increment as an observation, computing the Kalman gain to adjust the heading estimate and refine the error covariance matrix.

Validation in simulated environments substantiated the precision gains realized by the inertial fusion framework before field trials commenced. The researchers established three distinct indoor environments within Gazebo on an Ubuntu operating system: a circular corridor measuring 9.75 by 7.5 meters to evaluate mapping with weak geometric features; a 10.25 by 9.75 meter zone containing triangular and right-angled partitions to assess complex boundary reconstruction; and an irregular 9.85 by 7.10 meter area featuring asymmetric internal obstacles. Across all testbeds, MSFI-Gmapping competed against Hector, Karto, and traditional Gmapping. Quantitative analysis of fixed architectural feature points revealed Hector generated mean dimensional errors between 4.1 and 5.7 centimeters, translating to error rates between 2.5 and 3.3 percent. Karto produced mean errors between 2.9 and 4.7 centimeters, representing error rates from 1.6 to 3.0 percent. Standard Gmapping exhibited errors between 2.6 and 4.8 centimeters, or 1.7 to 2.9 percent. In contrast, MSFI-Gmapping limited mean dimensional errors to 1.4, 1.7, and 2.7 centimeters, achieving error rates of 0.6, 1.1, and 1.4 percent, with variance and ninety-five percent confidence interval metrics demonstrating superior measurement stability.

Physical verification within occupied facilities confirmed the robust mapping performance of the sensor-fused Gmapping architecture under real-world floor conditions. The experimental platform mapped three distinct test scenarios: a structured 7.5 by 13-meter space with rectangular pillars and counters; a 15.5 by 6.8-meter apartment corridor with multiple recessed doorways; and a dense 8.2 by 18.5-meter office environment exhibiting an obstacle density of 17.4 percent. Hector SLAM suffered extensive contour ghosting, with mean errors spanning 4.7 to 6.8 centimeters and error percentages reaching 5.7 percent. Karto recorded average errors between 3.1 and 5.8 centimeters, peaking at a 9.8-centimeter positional error on a challenging corner. Unmodified Gmapping yielded mean errors of 3.3 to 4.0 centimeters, corresponding to error rates of 2.4 to 4.1 percent. The MSFI-Gmapping system constrained average errors to 2.0, 2.8, and 1.6 centimeters across the respective environments, maintaining real-world error rates between 1.1 and 1.9 percent, avoiding wall doubling and loop closure failures at corners.

Having established geometrically accurate digital grid maps, the researchers focused on solving the secondary bottleneck of autonomous mobility: computational latency during global path generation. Standard A-star algorithms calculate optimal trajectories between designated origin and destination cells by balancing actual transit costs with an estimated heuristic cost. However, standard unidirectional A-star expands outward in eight discrete grid directions from start to finish, generating massive queues of unpromising exploration nodes across broad open spaces. Furthermore, standard implementations depend entirely on static heuristic formulations. Pure Euclidean distance heuristics bias exploration toward straight sightlines without adequately recognizing intervening barrier topology, whereas Manhattan distance models restrict movement to orthogonal axes, inflating search operations within expanded neighborhoods. Sampling-based alternatives like Rapidly-exploring Random Trees converge sluggishly around tight obstacles, and unguided breadth-first algorithms like Dijkstra inspect excessive grid regions. In contrast, the research team recognized that an efficient pathfinder must dynamically adapt its heuristic weights based on ambient obstacle density while simultaneously searching inward from both endpoints.

The resulting Improved Bidirectional A-star algorithm, designated IB-A*, introduces a mathematically adaptive heuristic evaluation function paired with an expanded neighborhood search geometry. The cost function modifies the heuristic term through an environmental weighting factor determined by map obstacle density, computed as the ratio of occupied obstacle cells to total grid dimensions. When navigating sparse layouts, the algorithm amplifies the heuristic weight to constrain lateral exploration and aggressively prioritize rapid forward progress toward the target; conversely, in heavily congested zones, the heuristic weight is attenuated to avoid local minima and facilitate safe detour routing around dense structures. Additionally, IB-A* modulates a secondary dynamic balancing weight between Euclidean and Manhattan formulations based on relative distance to target: Euclidean distance dominates early search phases to drive rapid straight-line closure, whereas Manhattan metrics govern terminal phases to preserve grid-aligned maneuvering. Crucially, the algorithm replaces the conventional eight-neighborhood expansion pattern with a twenty-four-neighborhood structure evaluated across twelve radial directions, gathering richer local spatial context while bypassing redundant grid nodes.

Algorithmic pathfinding benchmarks executed in MATLAB across thirty-by-thirty and fifty-by-fifty cell grids highlighted marked performance advantages for the bidirectional scheme. When evaluated against standard A-star and unmodified Bidirectional A-star across identical start-to-goal coordinates, IB-A* drastically curtailed planning overhead. In the thirty-by-thirty simulated environment, IB-A* reduced computational planning duration by 87.1 percent compared to traditional A-star, while slashing the total volume of evaluated search nodes by 49.6 percent. In the fifty-by-fifty environment, the algorithm achieved an 87.9 percent decrease in calculation time alongside a 42.7 percent drop in visited nodes. While total resulting trajectory lengths remained closely comparable among the three competing algorithms, the computational economy of IB-A* proved distinct. The authors conducted formal Student’s t-distribution hypothesis testing across repeated experimental runs, establishing at a five percent significance level that the observed execution time reductions exceeding eighty-five percent were statistically significant and not artifacts of randomized trial variability.

For global transit, the robot localized within established occupancy maps using Adaptive Monte Carlo Localization fed by EKF-fused odometry, while global path planning was delegated to IB-A* inside the Move_base navigation package. In real-world comparative trials across the three physical test spaces, traditional A-star required 3.51, 1.85, and 8.92 seconds to solve global routes, whereas IB-A* solved the identical trajectories in 0.57, 0.29, and 1.34 seconds. These numbers represent planning time reductions of 83.8, 86.1, and 85.0 percent, accompanied by node reductions of 47.2, 47.8, and 49.6 percent. Follow-up t-distribution analysis confirmed that the real-world operational speedups exceeding eighty-three percent were statistically significant across all experimental runs.

The engineering team validated dynamic path adjustment by introducing unmapped physical obstacles along pre-planned transit corridors while the autonomous robot traveled toward set navigation goals. The mobile robot tracked its primary IB-A* trajectory while deploying the Dynamic Window Approach local planner, which continuously evaluates immediate velocity vectors and LiDAR proximity data to bypass suddenly introduced barriers. When researchers obstructed established paths with unexpected objects, the robot adjusted its motion trajectories without stalling, detouring around local obstructions before rejoining its global path to achieve the designated target poses. The authors noted that future development will target industrial warehouse automation, healthcare mobile platforms, and reconnaissance across hazardous operating environments, with underlying research datasets accessible from the corresponding author upon reasonable academic request.

Subject of Research: Autonomous indoor wheeled robot navigation using multi-sensor fusion Gmapping and improved bidirectional path planning

Article Title: Autonomous navigation of indoor wheeled robots based on improved Gmapping and improved Bidirectional A*

Article References: Wang, E., Huo, W., Xu, S., Qu, P., & Na, L. (2025). Autonomous navigation of indoor wheeled robots based on improved Gmapping and improved Bidirectional A*. Discover Robotics, 1(1), Article 7. https://doi.org/10.1007/s44430-025-00007-z

Image Credits: AI Generated

DOI: 10.1007/s44430-025-00007-z

Keywords: mobile robotics, autonomous navigation, SLAM, Gmapping, Extended Kalman Filter, inertial measurement unit, wheel odometry, sensor fusion, bidirectional A-star, heuristic search, path planning, obstacle density, robot operating system, LiDAR mapping, indoor localization, Raspberry Pi 4B