Yol Bulma Algoritmaları ve Jump Point Search

Grid yapılarında en kısa yolu bulmak için klasik arama algoritmaları kullanılabilir. Bunlar Depth-First Search (DFS) gibi uninformed, yani arama stratejisi hedefin konumuna göre değişmeyen algoritmalar olabileceği gibi A* gibi informed algoritmalar da olabilir.

DFS optimal bir algoritma olmamasıyla, Breadth-First Search (BFS) ise bellek kullanımının üstel olmasıyla arama ağacının derin olduğu durumlar için uygun değildir. Pratikte bu tarz bir problemde kullanmayacak olsak da en azından karşılaştırma yapmak için bu algoritmaların sonuçlarını da ekledim.

A* algoritması, heuristic fonksiyonlar kullanarak optimal sonucu elde eder. Yapı olarak Best-First Search algoritmasının modifiye edilmiş halidir, yani o an için elindeki hedefe en yakın node hangisiyse onu seçip ilerler. Best-First Search'ten farkı ise bunu sadece heuristic (\(h(x)\)) fonksiyonu kullanarak değil, o ana kadarki maliyeti de (\(g(x)\)) tutarak

\[f(x) = g(x) + h(x)\]

fonksiyonu ile yapar. Wikipedia sayfasındaki Optimality bölümünde, doğru heuristic fonksiyonla nasıl en iyi çözümü bulduğu daha ayrıntılı olarak okunabilir.

A* algoritmasının bir özelliği de çözüme birer adım atarak yaklaşmasıdır, bu özelliği yüzünden çok fazla node'u ziyaret edebilir. Grid yapıları düşünüldüğünde, önünde herhangi bir engel olmayan büyük bir boş alanda her noktada durup tekrar tekrar baştan yol planlamanın bir anlamı yoktur. Jump Point Search ise A*'ın bu özelliğinin iyileştirilip bellek kullanımının ve çalışma zamanının iyileştirilmiş bir versiyonudur.

Jump Point Search kısaca prune (budama) ve jump adımlarından oluşur.

- Prune: Buradaki temel varsayım şudur. \(x\) o an bulunulan konum ve \(parent(x)\), \(x\)'ten bir önceki konum olmak üzere; \(parent(x) -> x -> y_i\) şeklinde, \(parent(x)\)'ten başlayıp \(y_i\)'de biten iki adım atıldığında, \(y_i\)'ye ulaşan en kısa yolların hepsi \(x\)'ten geçiyorsa \(y_i\) değerlendirmeye alınır, diğer node'lar yoksayılır. Eğer \(x\)'in etrafındaki bir engelden dolayı \(y_i\) bu kümeye dahil oluyorsa \(y_i\) forced (zoraki) komşu, eğer her koşulda dahil olan bir node ise doğal komşu olarak adlandırılır.

- Jump: \(x -> y_i\) doğrultusunda, \(y_i\)'nin herhangi bir zoraki komşusu yoksa, bir adım daha atılabilir.

Algoritmanın detayı buradan okunabilir.

Denerken kullandığım şekil aşağıdaki gibi. Siyah kutular duvar, mavi kutu başlangıç ve kırmızı kutu da bitiş noktası olarak alınıyor.

 

figure_1

Depth first search bu harita üzerinde aşağıdaki gibi bir yol izleyecektir. Bulduğu çözüm beklendiği gibi optimal değil.

figure_2

BFS, A* ve Jump Search ise optimal çözümlere ulaşacaktır.

figure_3

DFS dışındaki algoritmaların hepsi aynı performansı göstermiş gibi görünse de, aşağıdaki tablodaki node expansion sayıları ile fark anlaşılabilir.

 

Algoritma Mesafe Node sayısı
DFS 10.65 12
BFS 8.07 24
A* 8.07 17
JPS 8.07 9

3 thoughts on “Yol Bulma Algoritmaları ve Jump Point Search

  1. Pingback: Swamp Search | Orhan Özalp

  2. Pingback: Theta* | Orhan Özalp

  3. Pingback: Moving AI | Orhan Özalp

Comments are closed.