Is A* better than previous path finding algorithms?

‘Pathfinding’—or planning a route to a destination that bypasses obstacles—is a great problem in AI recently. In this regard, the A* search algorithm has garnered much attention for its ability to solve path complexities. However, according to Stack Overflow, there are situations in which A* may not be the best algorithm to solve a problem with. Although, there are a number of parameters to assess what constitutes the best algorithm for finding a solution.

Current bottlenecks in resolving ‘Pathfinding’

In 2020, Science Direct published a paper titled, ‘A Systematic Literature Review of A* Pathfinding’, by computer scientists Daniel Foead, Alfio Gefari, Marchel Budi Kusuma, Novita Hanafiahb, and Eric Gunawan, which proposed that A* algorithms are not foolproof algorithms, and in multiple scenarios, they require supplementary algorithms or an alteration to perform trickier tasks. Moreover, as noted in Multi-agent pathfinding problems, A* faces many obstacles, like conflicting pathways. The traditional baseline A* algorithm cannot keep up with the increasing demands of pathfinding and is evidently fading out of usage, particularly in the context of complex problems. Still, its improved and properly designed variants are preferred to maintain pace with increased efficiency. 

Overcoming the classic A* algorithm problem 

Experts from different sectors have also emphasised the efficiency and defects of the A* algorithm. In a recent research paper, Yogendra Arya, associate professor at J.C. Bose University of Science and Technology—along with other researchers: Huanwei Wang, Jing Jing, Shangjie Lou, and Wei Liu—puts it this way: ‘Given the speculation, we propose three methods for improving the conventional A* algorithm, including expansion distance, bidirectional search, and smoothing for better pathfinding problems’. The paper compares the previous pathfinding algorithms and solves the existing A* obstacles while also explaining that informed search algorithms like A* are more efficient than Dijkstra or breadth-first search (BFS) through A* optimization methods in optimising its efficiency. 

Arya and his team fully acknowledge that, over the past decades, several applications have demonstrated different path planning methods for automated vehicles and robots. Classical path planning algorithms consist of ant colony optimization algorithms, genetic algorithms, and the A* algorithm. At the same time, the A* algorithm is based on the concept of graph searching and is one of the highly used pathfinding methods. 

They further focused on the research of other scholars but pointed to current defects concerning small distances between the path and right angle turn speed change, affecting the performance of planned paths holistically. To improve the efficiency of the traditional A* algorithm, path smoothing and expansion distance are introduced in the proposed algorithm. The team also stated that to avoid collisions and maintain distance from obstacles—and for the extended nodes to no longer travel—they designed the new algorithm to enhance the speed of path planning.

A novel approach 

The research work titled, ‘The EBS-A* algorithm: An Improved A* algorithm for Path Planning’, proposed a new approach to solving the problems faced by conventional A* algorithms. 

Given traditional A* algorithm aspects and problems, the method proposed in the paper formed a new algorithm called ‘EBS-A*’. Simulation tests conducted in the research support the proposed theory to show the compared results within conventional A* and EBS-A* in the context of path speed and robustness. 

The study suggested another way to overcome the shortcomings of the A* algorithm, ensuring a smooth path. It proposed a global planning method that perceives the characteristics of the local environment. This method will allow the A* algorithm to design the globally optimal path in a known static atmosphere—thereby eliminating redundant nodes and developing local sequence nodes on the eliminated global path to optimise it on the global path, hence guaranteeing the A* performance in a dynamic atmosphere. 

Till now, there has been no existing algorithm pointing growth towards the comprehensive performance of the A* algorithm. But the improved algorithm is believed to play a crucial role in the autonomous navigation of mobile robots. Since mobile robots are largely adopted in the real world, it's important to propose a strong and highly efficient A* algorithm that is capable of catering to potential applications and bringing commercial value to the industrial sector. 

Juxtaposing A* algorithm efficiency with Dijkstra, DFS, and BFS 

When you compare the earlier Dijkstra algorithm with the A* algorithm, the latter indeed trumps the productivity of the Dijkstra algorithm. While both cater to the problem of finding the shortest path solution, Dijkstra doesn't pay much attention to the pragmatism of the solution. Even after consisting of traversal algorithms like DFS and BFS, A* becomes the preferred path solver in light of the disadvantages of Dijkstra, DFS, and BFS in requiring traversing the map completely—thereby leading to a large emphasis on calculation, low productivity, and weak collision aspect. The long calculation time from earlier algorithms decreases the efficacy with the growth of the map scale, wherein A* algorithm stands out with its ability to provide the shortest path on the map by traversing around nodes and involving the minimum path cost.