Kanca
Okul kütüphanesinde kitap taşıyan küçük bir araç düşün. Çıkış noktası belli, teslim masası belli; arada raflar ve bırakılmış sandalyeler var. "İleri git" yetmez. Araç, daha hareket etmeden geçebileceği kareleri birbirine bağlamalı.
Ya şunu denesen? Bir engelin boyutunu iki katına çıkarsan planlayıcılar hâlâ yol bulur mu?
Ne oldu
Planlayıcı alanı karelere böler. Boş kare "burada durabilirim", yanındaki boş kare "buraya geçebilirim" demektir; engelli kareler bu karar haritasından çıkarılır.
A* ("A yıldız") başlangıçtan ararken hem atılan adımların maliyetini hem hedefe kalan yaklaşık uzaklığı izler. Ekrandaki rota, birbirine bağladığı boş karelerin sırasıdır. Geçidi kapatırsan bu zincir kurulamaz. "Yol bulunamadı" bir çökme değil, başlangıç ile hedefin mevcut haritada bağlı olmadığını hareketten önce bildiren geçerli bir planlama sonucudur.
Gerçek dünyada
Kütüphane yerine bir hastane koridoru, sera sırası ya da depo geçidi koyabilirsin. Haritanın resmi değişir; planlama sorusu değişmez: başlangıçtan hedefe, kapalı bölgelere girmeyen bir rota var mı? Bu dersteki A* modeli tam olarak bu soruyu çözüyor.
Dene
Önce tek geçit bırakan bir raf duvarı kur. Aracı çalıştırmadan rotanın hangi taraftan geçeceğini tahmin et, sonra çalıştırıp karşılaştır.
Şimdi son geçidi de kapat — başlangıçla hedef arasında artık hiçbir yol kalmasın. Robotu çalıştırmadan önce tahminini kilitle:
Sonraki
Robot bir yol buldu — ama bulduğu yol her zaman EN KISA yol mu? Sıradaki ders tam bunu soruyor.