Yapay Zeka Destekli A* Algoritması, Arama Koridorlarıyla Düğüm Açılımını AzaltıyorAI-assisted A* algorithm reduces node expansion with search corridors

ÖzetSummary

Bu ön baskı, A* planlaması başlamadan önce daraltılmış bir 'arama koridoru' tahmin etmek için makine öğrenmesi modellerini (GraphSAGE, Random Forest) kullanmayı öneriyor. Yaklaşım, adaptif genişletme ile tam A* karşılaştırması üzerinden yapılan bir sonradan doğrulama adımını birleştiriyor. Orta ölçekli sentetik graf üzerinde GraphSAGE varyantı, yalnızca vakaların %23,6'sında düğüm genişletmelerini azaltırken, %6,5'lik bir kısmın doğrulanamamasına yol açtı.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.

Neden ÖnemliWhy it matters

A*, robotik ve lojistikte optimal yol planlamasının temel taşı olmaya devam ediyor; ancak maliyeti graf boyutuyla birlikte verimsiz bir şekilde artıyor. Arama uzayını optimaliteyi feda etmeden güvenle budayabilen her yöntem, otonom navigasyon için doğrudan pratik değer taşıyor. Ne var ki buradaki katkı kademeli nitelikte: Mevcut optimal algoritmayı öğrenilmiş bir ön filtreyle sarmalıyor, arama paradigmasını değiştirmiyor.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.

Öne ÇıkanlarHighlights

• GraphSAGE koridoru, orta ölçekli graf vakalarının %23,6'sında genişletmeleri azalttı; %69,9'unda A* ile eşleşti; %6,5'inde doğrulama başarısız olduThe 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
• Oracle (mükemmel) koridor, vakaların %55,1'inde A*'dan daha iyi performans gösterdi; bu da teorik üst sınırların, öğrenilmiş modelin ulaştığı seviyenin yaklaşık iki katı olduğunu gösteriyorThe 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
• Değerlendirme yalnızca küçük ve orta ölçekli sentetik geometrik graf sınırlı; gerçek dünya veya büyük ölçekli kıyaslamalar raporlanmadıThe evaluation is limited to small and medium-scale synthetic geometric graphs; no real-world or large-scale comparisons were reported

EleştiriCritical take

Doğrulama aşaması, koridorun yolunu teyit etmek için tam A*'ı yeniden çalıştırıyor. Bu da en kötü durumdaki hesaplama maliyetinin değişmediği anlamına geliyor. 'Verimlilik kazancı' yalnızca koridorun doğru çıktığı durumlarda elde ediliyor; yazarların da işaret ettiği gibi bu koşul denemelerin %6,5'inde sağlanamıyor. Modest %23,6'lık iyileşme ile gerçek ortam veya büyük ölçekli testlerin yokluğu göz önüne alındığında, A*'ın sezgisel fonksiyonunu basitçe ayarlamaya kıyasla pratik üstünlük hâlâ tartışmalı.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.