Theta*

2 boyutlu haritalarda yol bulmak için kullanılan algoritmalardan biri de Theta*. Bu algoritma da Jump Point Search (JPS), Swamp Search ve diğer hemen tüm yol bulma algoritmaları gibi A* tabanlı.

JPS, gereksiz node’ları atlayarak en kısa yolu bulduğu için gayet iyi bir algoritma. Fakat JPS’nin optimal olduğu durumlar, en azından ilk halinde, hareketin sadece 8 yöne yapıldığı durumlar için geçerli (Her açıda hareket için de bir JPS versiyonu var, o makaleyi henüz okumadım). Theta* ise bu kısıtı kaldırarak, hareketin herhangi bir açıyla yapıldığı durumdaki en kısa yolu buluyor.

En kısa yolu garanti etme kısmı A*’ın doğru h(x) fonksiyonu ile kullanıldığı zaman optimal çözümü bulması ile aynı. Burada değişen kısım ise, g(x) fonksiyonu olarak bir önceki node’un maliyetini almaktansa 2 önceki node’dan mevcut node’a uzaklığı hesaplıyoruz.

Diyelim ki aşağıdaki haritada maviden kırmızıya gideceğiz.

initial

A*, JPS veya diğer tüm sadece 8 yöne hareket eden algoritmaların bulacağı yol aşağıdaki gibi olacak.

a_star

Theta*’ın farkı ise burada ortaya çıkıyor. Adım adım incelersek, Theta* algoritması ilk adımı aşağıdaki gibi atacak.

theta_1

Başlangıç noktasına p_0, ilk adımdan sonra ulaştığımız noktaya ise p_1 diyelim. Sonrasındaki adımda ise kırmızı noktaya ulaşacak. Ulaştığında ise, sonucu dönmektense bu noktaya p_0‘dan direkt olarak bir yol var mı diye kontrol edip, eğer varsa p_1‘i sonuçtan çıkaracak ve sonuç p_0 -> p_1 olacak.

theta_2

Böylece 2 nokta arasındaki Öklid uzaklığını yani en kısa yolu bulmuş olduk.

Theta*, özellikle JPS’ye göre daha maliyetli bir algoritma. A*’a getirdiği ek maliyet ise her adımda daha kısa bir yol var mı diye kontrol edilmesi.

Son olarak, uzaklıkların farkının görülebilmesi açısından aşağıdaki gibi bir haritada deneme yaptım.

last_1 Sonuçlar aşağıdaki gibi;

Algoritma Yol Uzunluğu
A* 7.242
JPS 7.242
Theta* 7.064

Swamp Search

Grid şeklindeki haritalar, yapıları basit olduğundan ve grid üzerinde hareket edecek olan nesnenin (robot, oyun karakteri vs.) hareketi gerçek bir nesneden çok daha basit olduğundan bu haritalar için birçok heuristic yöntemi üretilebilir. Jump Point Search algoritmasında olduğu gibi yeni algoritmaların genelde iyileştirmeye çalıştıkları konu değerlendirilen node sayısı oluyor. Swamp Search algoritması da node sayısını iyileştiren algoritmalardan bir tanesi.

swamp

Algoritma harita içindeki swamp, yani bataklık alanları buluyor. Bataklık alanları şöyle açıklayabiliriz: Elimizde, grid üzerinde bir nokta kümesi olduğunu varsayalım. Bu kümenin dışında kalan tüm nokta çiftlerinin arasındaki en kısa yolları da hesapladığımızı düşünelim. Eğer bu kısayollardan hiçbiri elimizdeki kümeden geçmiyorsa bu alan bataklık olarak adlandırılır (Yukarıdaki resimde S = \{S1, S2, S3, S4\} kümesi bataklık olarak değerlendirilebilir). Eğer tüm bataklık alanları hesaplayabilirsek, iki nokta arasındaki yolu hesaplarken bu alanları yoksayabiliriz. Bu da çok fazla engelin olduğu bir haritada işimizi epey kolaylaştıracaktır. En azından şimdilik öyle görünüyor. Bakalım :)

Algoritmanın ilk adımında seed (tohum) olarak adlandırılan noktaları bulmak gerekiyor. Bu noktalar için basitçe bataklıkların yetişeceği noktalar denilebilir. Kendisi bir engel olmayan, düşey ve yatay eksende en az birer komşusu engel olan noktalar seed noktalar olarak alınabilir. Örneğin yukarıdaki resimdeki S4 noktası solundaki ve yukarısındaki noktalarda engel olduğu için bir seed noktasıdır.

İkinci adımda r=1 yarıçapı ile başlayarak seed noktayı genişletmek gerekiyor. Her seferinde seed noktadan en fazla r adımda ulaşılabilecek noktaları buluyoruz. Bu bizim bataklık olarak belirlediğimiz bölge oluyor.

Son adımda ise, ikinci adımda belirlediğimiz bataklıktaki noktaların sağlamasını yapmamız gerekiyor (gereksiz yere bir noktayı bataklığa dahil ettiysek çıkarmamız gerekecek). Bunun için bataklık bölgenin sınırındaki noktaları alıyoruz. (Sınırdaki noktalar = Bataklığa komşu olan ve bataklığa dahil olmayan noktalar). Sınırdaki her nokta çifti için en kısa yolu hesaplıyoruz. Eğer yeni bulduğumuz bataklık bu iki nokta arasındaki yolu uzatmışsa, yol üzerinde bulunan ve bataklığa dahil olan tüm noktaları bataklıktan çıkarıyoruz.

2. ve 3. adımları her seed nokta için, r‘yi arttırarak tekrarlayabiliriz. Bataklığı büyütme işi maksimum yarıçap, maksimum bataklık büyüklüğü gibi çeşitli kriterlere göre sınırlanabilir.

Benim bu algoritmada sevmediğim şey çok fazla statik olması. Evet hesaplama bittikten sonra A*’ın çalışmasını epey azaltabiliyor ama asıl sancılı olan da bu hesaplama süresi. Büyük haritalarda r kısıtını yüksek tutmak gerektiğinden değişken haritalar için kullanılabilir bir yöntem olmayacaktır. Az engelin bulunduğu haritalar içinse A*’ın çalışma zamanına yakınsayacaktır.

Neticede çok kullanışlı bir algoritma olmasa da mantığı ilginç. Detaylı okuma buradan yapılabilir.

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

(1)   \begin{equation*} f(x) = g(x) + h(x) \end{equation*}

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