AI-assisted A* algorithm reduces node expansion with search corridors

Summary

This preprint proposes using machine learning models (GraphSAGE, Random Forest) to predict a narrowed 'search corridor' before A* planning begins. The approach integrates a post-hoc verification step through a full A* comparison with adaptive expansion. On a medium-scale synthetic graph, the GraphSAGE variant reduced node expansions in only 23.6% of cases, while leading to a 6.5% failure rate in verification.

Why it matters

A* remains the cornerstone of optimal path planning in robotics and logistics; however, its cost increases inefficiently with graph size. Any method that can safely prune the search space without sacrificing optimality holds direct practical value for autonomous navigation. However, the contribution here is incremental: it wraps the existing optimal algorithm with a learned pre-filter rather than changing the search paradigm.

Highlights

• The GraphSAGE corridor reduced expansions in 23.6% of medium-scale graph cases; it matched A* in 69.9% of cases; verification failed in 6.5% of cases
• The Oracle (perfect) corridor outperformed A* in 55.1% of cases; this indicates that theoretical upper bounds are approximately twice the level achieved by the learned model
• The evaluation is limited to small and medium-scale synthetic geometric graphs; no real-world or large-scale comparisons were reported

Critical take

The verification step re-runs full A* to confirm the corridor's path. This means the worst-case computational cost remains unchanged. The 'efficiency gain' is only realized when the corridor is correct; as the authors note, this condition is not met in 6.5% of trials. Given the modest 23.6% improvement and the absence of real-world or large-scale testing, the practical advantage over simply tuning A*'s heuristic function remains debatable.