*Improved A Algorithm Enhances Indoor Robot Navigation Efficiency**
In the rapidly evolving field of robotics, one of the most persistent challenges has been enabling autonomous machines to navigate complex indoor environments efficiently and safely. While numerous algorithms have been developed to address this issue, the A (A-star) algorithm has long stood out as a foundational method for path planning in two-dimensional spaces. Its widespread use in aerospace, agriculture, manufacturing, and warehouse logistics stems from its ability to calculate the shortest path between a starting point and a destination using a heuristic approach. However, despite its strengths, the traditional A algorithm has several well-documented limitations—particularly when applied to mobile robots operating in cluttered indoor settings.
These shortcomings include excessive computational overhead, the generation of redundant waypoints, and jagged, non-smooth trajectories that complicate robot movement and reduce tracking accuracy. As demand grows for smarter, faster, and more agile indoor robots—from delivery bots in hospitals to autonomous cleaners in homes—researchers have intensified efforts to refine existing navigation algorithms. A recent breakthrough from Guizhou University in China offers a promising solution, introducing a significantly enhanced version of the A* algorithm that addresses multiple performance bottlenecks simultaneously.
Led by Zihao Liu, a graduate researcher at the School of Mechanical Engineering at Guizhou University, in collaboration with Professor Jin Zhao and colleagues Chang Liu, Kuncheng Lai, and Xiqiao Wang, the team has developed a novel improvement to the classic A framework. Their work, published in the peer-reviewed journal Computer Engineering and Applications, demonstrates a multi-stage optimization strategy that drastically reduces computation time, shortens travel distance, and produces smoother, more robot-friendly paths. The study, titled “Path Planning of Indoor Mobile Robot Based on Improved A Algorithm,” presents a comprehensive enhancement that could influence the design of future robotic navigation systems.
The core innovation lies in a three-phase approach: first, a key-point selection mechanism inspired by jump point search theory; second, a reverse dynamic search for secondary path refinement; and third, a dynamic circular smoothing technique applied at turning points. Each phase targets a specific weakness of the conventional A* method, collectively transforming a once rigid and computationally heavy algorithm into a leaner, more adaptive navigation tool.
Traditional A* operates by evaluating every adjacent node in a grid-based map, maintaining two critical data structures—the open list (nodes to be evaluated) and the closed list (nodes already evaluated). While effective in theory, this exhaustive search becomes inefficient in large or densely populated environments. The algorithm often processes thousands of nodes that ultimately contribute nothing to the final path, consuming memory and slowing response times. Moreover, because movement is restricted to eight possible directions (up, down, left, right, and diagonals), the resulting paths are typically stair-stepped, requiring frequent turns that are inefficient for real-world robots with physical turning radii.
Liu and his team recognized that much of this inefficiency stems from a lack of strategic foresight in the search process. Instead of blindly expanding in all directions, they proposed embedding prior environmental knowledge into the algorithm through a key-point selection strategy. This approach draws inspiration from jump point search (JPS), a technique originally developed for video game pathfinding, which skips over large swaths of uniform terrain by identifying “jump points”—locations where the path must change direction due to obstacles or geometry.
By integrating JPS principles, the researchers replaced the traditional node-by-node expansion with a more intelligent search that focuses only on critical decision points. When the robot moves through open space without obstacles, the algorithm identifies the straight-line trajectory and bypasses intermediate nodes entirely, selecting only the endpoint as a key point. This dramatically reduces the number of nodes processed, thereby cutting down memory usage and processing time.
However, in environments with obstacles, the path cannot always be a straight line. Here, the team introduced the concept of “forced key points”—locations where a turn is unavoidable due to the presence of barriers. These points are determined by a geometric condition: if the sum of vectors from the current node to a potential turning point and from that point to the goal is shorter than any alternative detour, then that point is marked as a forced key point and must be evaluated. This ensures that the algorithm does not overlook critical waypoints while still avoiding unnecessary computations.
The result is a leaner search process that maintains the optimality of A while drastically improving efficiency. In simulation tests conducted on grid maps of varying sizes—15×15, 30×30, and 50×50 cells—the improved algorithm reduced average computation time to just 56.09% of the original A runtime. For a 50×50 grid, the speedup was even more pronounced, with execution times dropping from tens of thousands of microseconds to under half that amount. This level of performance gain is particularly valuable in dynamic environments where robots must replan their routes in real time due to moving obstacles or changing conditions.
But speed alone is not enough. Even with faster computation, a path riddled with sharp turns is impractical for physical robots. Each abrupt direction change requires the robot to decelerate, rotate, and accelerate again, consuming energy and increasing travel time. Furthermore, frequent turning reduces stability and can lead to tracking errors, especially on slippery or uneven surfaces.
To address this, the research team implemented a second phase: reverse dynamic search for secondary path optimization. After generating the initial path using the key-point method, the algorithm performs a backward pass, starting from the goal and working toward the start. It attempts to connect distant waypoints directly, checking whether the straight line between them intersects any obstacles. If no collision occurs, the intermediate points are eliminated, effectively “cutting corners” and shortening the path. If an obstacle lies in the way, the algorithm iteratively tests shorter segments—halving the distance each time—until a safe, direct connection can be made.
This recursive refinement process ensures that the final path contains only the minimal set of necessary waypoints. In one test scenario, the original A* path included over 300 centimeters of travel with multiple zigzags, while the optimized version reduced the distance to 293.4 cm—a 2.7% reduction. Though seemingly modest, such improvements compound over repeated missions, leading to significant energy savings and longer operational life for battery-powered robots.
More importantly, the number of turning points was drastically reduced. In real-world trials using a TurtleBot3 Burger robot—a popular open-source platform equipped with a Raspberry Pi 3 and OpenCR controller—the improved algorithm produced paths with only one major turn, compared to six in the traditional A* output. Fewer turns mean smoother motion, less wear on motors, and better overall navigation performance.
Yet even after secondary optimization, the path may still contain sharp angles unsuitable for continuous motion. Most robots, especially wheeled ones, cannot make instantaneous 90-degree turns; they require a certain turning radius. To accommodate this physical constraint, the third and final stage of the algorithm applies a dynamic circular smoothing technique.
Rather than relying on computationally expensive methods like Hybrid A*, which combines discrete search with continuous motion planning, the team developed a lightweight alternative. At each remaining corner, the algorithm identifies the two adjacent path segments and constructs perpendicular lines at their midpoints. The intersection of these perpendiculars serves as the center of a circular arc that smoothly connects the two segments. By replacing the sharp vertex with a curved trajectory, the robot can maintain momentum and follow the path more naturally.
This method strikes a balance between smoothness and computational efficiency. While the resulting curves may not be as mathematically optimal as those generated by more complex algorithms, they are sufficient for indoor navigation and require far fewer resources. In practical terms, this means the robot can execute the path in real time without overloading its onboard processor—a critical advantage for low-cost or resource-constrained platforms.
The experimental validation of the improved A* algorithm was conducted in both simulated and real-world environments. Simulations were run across multiple grid sizes and randomized obstacle configurations, with each setup tested 15 times to ensure statistical reliability. The results consistently showed superior performance across all metrics: faster computation, shorter paths, and fewer turning points.
In the physical tests, the TurtleBot3 was deployed in a 12×12 grid environment with a cell size of 15 cm, mimicking a typical indoor office or home layout. The robot successfully navigated from a starting coordinate (2,2) to a target (7,11), following the path generated by both the traditional and improved algorithms. The onboard system recorded execution times, path lengths, and the number of directional changes. The data confirmed the simulation findings: the improved algorithm completed the task in 461 microseconds, compared to 997 microseconds for the standard A*, representing a 54% reduction in processing time. The path length decreased from 132.84 cm to 130.26 cm, and the number of turns dropped from six to one.
These improvements are not merely academic—they have tangible implications for the deployment of autonomous systems in real-world applications. In healthcare settings, for example, delivery robots must navigate narrow corridors and doorways efficiently. A smoother, shorter path means less time spent moving, reducing delays in transporting medication or supplies. In warehouses, where hundreds of autonomous mobile robots (AMRs) operate simultaneously, even small gains in individual efficiency can translate into major productivity boosts across the entire fleet.
Moreover, the algorithm’s adaptability makes it suitable for a wide range of robot types and environments. Because it operates on a grid-based representation of space—a common format in robotics—it can be easily integrated into existing robotic software frameworks such as ROS (Robot Operating System). Its modular design allows developers to implement only the components they need—key-point search for speed, reverse optimization for path shortening, or circular smoothing for motion quality.
The research also highlights a broader trend in robotics: the shift from brute-force computation to intelligent, knowledge-driven algorithms. As robots move beyond controlled factory floors into unpredictable human environments, their navigation systems must become more adaptive, efficient, and context-aware. The work by Liu, Zhao, and their team exemplifies this shift, demonstrating how combining classical algorithms with modern optimization techniques can yield substantial performance gains.
Looking ahead, the researchers suggest several potential extensions. One is the integration of dynamic obstacle avoidance, allowing the algorithm to react to moving people or objects in real time. Another is the adaptation of the key-point strategy for three-dimensional spaces, which would benefit drones or flying robots. Additionally, machine learning techniques could be used to predict optimal key points based on historical navigation data, further reducing computational load.
The success of this improved A* algorithm also underscores the growing role of Chinese institutions in advancing robotics and artificial intelligence. Guizhou University, located in southwest China, has been steadily building its reputation in intelligent systems and automation. Supported by funding from the National Natural Science Foundation of China and provincial science and technology programs, this research reflects a national commitment to innovation in smart technologies.
In conclusion, the work presented by Zihao Liu, Jin Zhao, Chang Liu, Kuncheng Lai, and Xiqiao Wang represents a significant step forward in indoor robot navigation. By rethinking the fundamental assumptions of the A* algorithm and introducing a multi-layered optimization strategy, they have created a solution that is faster, shorter, and smoother—three qualities that are essential for the next generation of autonomous machines. As robots become increasingly integrated into daily life, such advancements will play a crucial role in making them more capable, reliable, and user-friendly.
Improved A* Algorithm Enhances Indoor Robot Navigation Efficiency
Zihao Liu, Jin Zhao, Chang Liu, Kuncheng Lai, Xiqiao Wang, School of Mechanical Engineering, Guizhou University, in Computer Engineering and Applications, doi:10.3778/j.issn.1002-8331.2007-0156