WA* - Yeni Harita

Bir önceki WA* denemesini uniform oluşturulmuş bir harita üzerinde yapmıştım. Yaşar Safkan haritamın tipini beğenmeyince oturdum haritaya elle 1-2 engel koydum :) . Ne kadar karmaşık oldu bilmiyorum ama harita ve A*'ın haritada bulduğu yol aşağıdaki gibi oldu;

A* algoritması. Yol uzunluğu = 33.89, node sayısı = 246.

A* algoritması. Yol uzunluğu = 33.89, node sayısı = 246.

\(W = 8\) verilmiş WA* ise aşağıdaki gibi çalıştı;

WA* (W = 8) algoritması. Uzunluk 36.87, node sayısı = 34.

WA* (W = 8) algoritması. Uzunluk 36.87, node sayısı = 34.

Son olarak \(W = 2\) WA* ise aşağıdaki gibi sonuç verdi.

WA* (W = 2) algoritması. Yol uzunluğu = 34.04, node sayısı = 39.

WA* (W = 2) algoritması. Yol uzunluğu = 34.04, node sayısı = 39.

Yine çok büyük fark çıkmadı ama en azından WA*'ı en kısa yoldan saptırabildim.

WA*

WA*, Planning as heuristic search makalesinde denk geldiğim, orada da referans olarak Heuristics kitabının verildiği bir A* optimizasyonu. Linkteki makalede ve diğer bir çok kaynakta heuristic inflation yöntemi olarak da geçiyor.

A* en iyi sonucu bulan fakat performans konusunda sıkıntısı olan bir algoritma. En iyi sonucu bulmanın çok da önemli olmadığı gerçek hayat problemleri için ise WA* önerilmiş. WA*'ın adındaki W, klasik

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

denkleminin

\[f(x) = g(x) + W \times h(x), W \ge 1\]

haline getirilmesinden geliyor. Makalede de belirtildiği üzere, \(W\) arttıkça sonuca daha çabuk ulaşıyoruz fakat bulduğumuz çözüm en iyi çözümden uzaklaşıyor. Bir ilginç nokta ise, \(W\) ile bulacağımız yeni yolun uzunluğu, en iyi yolun uzunluğunun en fazla \(W\) katı oluyor.

30 senelik makalede yanlış olacak değil tabii ki ama ben yine de, en azından sonuçları görebilmek için \(100 \times 100\)'lük uniform bir haritada denemeler yaptım. Örnek harita üzerinde A*'ın bulduğu sonuç aşağıdaki gibi;

a_star

100 x 100'lük haritada A*'ın verdiği sonuç. Uzunluk = 145.279, işlenen düğüm sayısı = 1918.

\(W=4\) verilmiş WA* ise aşağıdaki gibi bir sonuç bulacak.

a_star_hinf_4

100 x 100'lük haritada WA*'ın (W=4) verdiği sonuç. Uzunluk = 147.622, işlenen düğüm sayısı = 113.

Örnek haritada bulunan yol uzunlukları çok değişmese de işlenen düğüm sayısı çok azaldı.

Bu algoritma, özellikle tutarlı heuristic fonksiyonları ile kullanıldığında yol uzunluğunu \(W\) ile sınırlaması özelliği ile ömürboyu planlama algoritmaları ve anytime algoritmalarda epey kullanılıyor.

 

Double RRT

Double RRT benim uydurduğum bir isim. Muhtemelen literatürde daha düzgün bir adı vardır ama ben bulamadım :) . Yöntem, gördüğüm kadarıyla ilk kez LaValle ve Kuffner'in yazdığı Randomized Kinodynamic Planning makalesinde geçiyor ama makalenin içinde de normal RRT olarak verilmiş. Zaten RRT'den mantıksal olarak bir farkı yok, sadece bir iyileştirme denilebilir.

RRT, yani Rapidly-Exploring Random Tree, sürekli ortamlarda planlama yapmak için kullanılan algoritmalardan bir tanesiydi. Boş bir haritada basitçe görülebileceği üzere, bir noktadan başka bir noktaya rastgele sayılar ile ulaşmaya çalışıyorduk. Geniş haritada bunu denediğimizde de dallanma çok fazla oluyordu. Double yani iki taraftan çalışan RRT ise, çok fazla dallanmadan yol bulmaya yarayan bir iyileştirme. Mantığı ise, tek bir noktadan diğerine ulaşmaya çalışmaktansa, harekete 2 noktadan birden başlayıp ortada buluşmaya çalışmak üzerine kurulu. Yani aslında 2 noktadan başlayıp diğerine ulaşmaya çalışan 2 RRT çalıştırıyoruz. Eğer bu iki ağaç arasında uzaklıkları belirli bir sayının altında olan 2 düğüm bulabilirsek, bu iki düğümü birbirine bağlıyor ve algoritmayı bitiriyoruz.

Önceki denediğim haritadaki noktaları kullanarak aşağıdaki gibi bir yol elde edebiliyoruz;

double_rrt

 

\(20 \times 20\)'lik bir haritada, çeşitli maksimum adım boylarına göre iki algoritmayı 100'er kez denediğimde aşağıdaki sonuçları elde ettim;

rrt_comparison

 

Sonuç bir öncekine göre yine de daha iyi ama benim buradaki implementasyonum makalede anlatılana göre daha basit. Ben hesap maliyetinden kaçmak için sadece en uçtaki düğümler (leaf node) arasındaki uzaklıkları hesaplayıp diğerlerini yoksaydım. Kullandığım haritanın da oldukça farazi olduğu (bomboş iki boyutlu harita) düşünülürse gerçekte fark muhtemelen daha az olacaktır ama yine de Double RRT'nin (adamların bulduğu yönteme isim taktım :) ) iyi bir yöntem olduğunu söyleyebiliriz.

RRT

RRT, yani rapidly-exploring random tree, özellikle robotikte kullanılan yol planlama algoritmalarından bir tanesi. 1998 yılında, aynı zamanda "Planning Algorithms" kitabının da yazarı olan Steven LaValle ve James Kuffner tarafından geliştirilmiş.

RRT, bir başlangıç noktasından bitiş noktasına giderken rastgele noktalar seçip buralara dallanma ve sonuç noktasına belli bir mesafede kadar yakınlaşıncaya kadar bu işlemi tekrarlamak üzerine kurulu. Kendisinden daha önce geliştirilen algoritmalardan farklı olarak RRT bir sonraki nokta seçiminde daha önce bulunmuş noktaları hesaba katmıyor. En yakına gelmiş nokta vs. gibi hesaplar yapmaktansa haritada rastgele bir nokta seçiyor ve bu noktaya en yakın, daha önce bulunmuş başka bir noktadan bu doğrultuda hareket ediyor.

Hiçbir engel barındırmayan bir haritadan örnek vermek gerekirse;

Diyelim ki aşağıdaki haritada kırmızı noktadan yeşil noktaya gitmeye çalışıyoruz.

figure_1

RRT ile yapacağımız işlem, kırmızıdan başlayarak belirli uzaklıkta rastgele sayılar seçmek ve buralara dallanmak olacak. İlk adım sonunda haritadaki bağlantı aşağıdaki gibi olacak.

first_step

 

200 adım sonunda ise RRT aşağıdaki gibi dallanmış olacak.

200th_step

Böyle dallanarak sonunda aşağıdaki gibi bir yol elde etmiş olacağız.

final_step

RRT, diğer algoritmalar gibi (A* vs.) optimal değil, hatta tam olarak aynı kategoride oldukları da söylenemez. Arama uzayının sürekli olduğu durumlarda, mesela bir robotu bir hedefe ulaştırırken kullanmak için iyi bir algoritma. Basit simulasyonda anlaşılmayan, daha doğrusu benim uygulamadığım bir yönü de robot hareketleri için uygun yollar bulma imkanının daha iyi olması.

Burada gösterdiğim RRT'nin en basit hali. Smoothing RRT, RRT* gibi daha iyi sonuçlar veren varyasyonları da mevcut.

Son olarak, RRT ile ilgili LaValle'in yayınlarına bu adresten erişilebilir.

K-Point Crossover

Genetik algoritmalardaki crossing over kavramı malum; iki çözümü bir yerden kesip kesilen noktadan itibaren olan kısımları yer değiştiriyoruz, böylece elimizde 2 yeni sonuç oluyor.

 

OnePointCrossover.svg

 

Tek noktadan yapılan crossover işleminin yetersiz olması sonucu 2-point crossover, N-point crossover gibi yöntemler de çıkmış. Bu yöntemleri kullanarak çözümü birden fazla noktadan bölüp crossover'ı o noktalardan yapıyoruz. Maksat çözüm uzayındaki genetik çeşitliliği korumak.

 

kpoint

Aklıma gelen soru ise şu; bu crossover noktalarını uniform random olarak belirlediğimizi düşünelim. Bu olasılık da \(0.5\) olsun, yani bir noktanın crossover noktası (üstteki resimde yeşil çizgilerin kestiği noktalar yani) olma olasılığı \(0.5\). N-point crossover'daki N sayısının beklenen değeri bu durumda kaç olacaktır?

Her bölme noktasını var/yok şeklinde alacak olursak, elde edeceğimiz farklı bölme kombinasyonları, \(n\) çözüm kümesinin boyutu olmak üzere, \(|S| = 2^{n-1}\) tane olacak. Kesim noktalarının olduğu kümenin altküme sayısını bulmuş olduk aslında.

Bu \(2^{n-1}\) elemana bakarsak, çözümü hiç kesmediğimiz 1 durum, 1 kez kestiğimiz \(n-1\) durum ... olduğunu görürüz. Genel olarak bakınca her \(k\) noktadan kesme işlemini \(\binom{n-1}{k}\) defa yapıyoruz. Toplam durum sayısı da \(2^{n-1}\) olduğuna göre, \(E[n]\) beklenen değerini

\[E[n] = \frac{1}{2^{n-1}} \sum\limits_{k = 1}^{n-1} k \times \binom{n-1}{k}\]

ile hesaplayabiliriz. Bunu da uzun uzun hesaplamaya gerek yok çünkü yukarıdaki denklem bize \(B(n-1, 0.5)\) binom dağılımının ortalama değerini veriyor. \(B(n, p)\) dağılımının ortalaması

\[\mu=np\]

olduğuna göre, \(n\) elemanlı bir çözüm kümesi için sorunun cevabı \(\frac{n-1}{2}\) olacaktır.