Kanca
Bir haritada iki nokta arasındaki mesafeyi cetvelle ölçmek kolaydır. Ama bir bilgisayara "buradan oraya git" dedirtmek için önce sonsuz sayıda olası noktayı SAYILABİLİR bir kümeye indirgemen gerekir. İşte grid tam bunu yapar.
Ya şunu denesen? Bir engelin boyutunu iki katına çıkarsan planlayıcılar hâlâ yol bulur mu?
Ne oldu
lib/robotics/planners/astar.ts içindeki A* planlayıcısı, çalışma
alanını sabit boyutlu küçük hücrelere (varsayılan 0.05 birim) böler.
Her hücre bir "düğüm" olur. İki komşu hücre arasında geçiş yapmanın bir
maliyeti vardır — düz komşuya geçmek 1 hücre-genişliği, çapraz
komşuya geçmek √2 hücre-genişliği kadar maliyetlidir (Öklid mesafesi).
Bir yolun toplam maliyeti, o yolu oluşturan tüm adımların maliyetlerinin toplamıdır:
maliyet(yol) = Σ mesafe(hücre[i], hücre[i+1])
Yukarıdaki sahnede "Yol uzunluğu" sütunu tam olarak bu toplamı gösteriyor. Hücre boyutu ne kadar küçük olursa yol o kadar gerçek düz çizgiye yaklaşır — ama hücre sayısı da o kadar artar, hesaplama o kadar yavaşlar. Bu bir ödünleşim (trade-off): hassasiyet ile hız arasında.
Gerçek dünyada
Bir depoda robotların gezindiği zemin de aslında görünmez bir ızgaraya bölünmüştür — çevrim dışı programlama yazılımları haritayı hücrelere ayırıp planlamayı bu hücreler üzerinden yapar. Hücre boyutu ne kadar küçükse harita o kadar hassas ama planlama o kadar yavaş olur; mühendisler bu ikisi arasında bir denge noktası seçer.
Dene
Başlangıç ile hedef arasına düz bir engel koy, robot çapraz mı yoksa düz mü hareket ederek dolanıyor gözlemle. Sonuç tablosundaki yol uzunluğunu, engel olmadan bulunan düz çizgi mesafesiyle (yaklaşık olarak gözünle) karşılaştır.
Sonraki
Grid ve maliyeti gördün. Sıradaki ders, A*'ın bu maliyeti kullanarak gereksiz hücreleri nasıl atladığını () anlatıyor.