An enhancement of A* search algorithm with K-step look ahead by Kevin Chen for real road networks

ABSTRACT: This study presents an enhancement of the A* Search Algorithm with k-step look-ahead heuristics, initially introduced by Kevin Chen, to improve path-finding efficiency in real-world road networks. While Chen’s approach improved heuristic accuracy, it exhibited significant computational inefficiencies particularly in large-scale graphs making it less suitable for real road network systems such as GPS navigation. This research addresses those limitations through three key enhancements – heuristic caching, look-ahead parallelization, and the adoption of a 4-ary heap data structure. Each enhancement targets a specific bottleneck in Chen’s original algorithm. Heuristic caching reduces redundant calculations by using precomputed estimates, improving responsiveness when revisiting nodes and delivering runtime gains of up to 23.11%. This contributes to faster route computation, allowing real-time route planning becomes more responsive. Look-ahead parallelization distributes k-step expansions across threads, validating simultaneous path evaluations. This addresses the sequential bottleneck in Chen’s method and submit the highest improvement, with runtime reductions up to 48.05%, further enhancing scalability for large maps and allowing the system to handle large-scale road networks. Additionally, switching to a 4-ary heap enhances priority queue performance by reducing tree depth, improving runtime by up to 14.69% in dense urban environments. This supports faster algorithm processing and better overall application efficiency. These enhancements were validated on real-world road networks of varying scales; Mattawa (small), Jersey City (medium), and New York City (large), showing consistent percentage improvements. Furthermore, the researchers identifies performance-affecting factors that influence algorithmic efficiency. By successfully addressing the limitations of Chen’s K-step look-ahead heuristics, this study opens the way for further advancements in real-world path-finding algorithms, establishing greater efficiency in large-environments.

Filipiniana