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.

İTÜYM Finalinden Bir Soru

Geçen haftasonu ITU IEEE Yazılım Maratonu finali vardı. Etkinlik 2 gün sürdü ve her gün ayrı ayrı şirketlerin hazırladığı 3’er soru soruldu. Ben bir kez daha şunu farkettim ki başlangıçta her ne kadar soruyu çözen algoritmayı bulmak daha zor görünse de asıl zor olan hatasız kod yazabilmek. Ya da ben çok iyi bir günümde değildim bilmiyorum :) . 20 takım arasından 10. oldum, seneye daha iyi yaparım artık. Takım arkadaşım olmadan en azından sonuncu olmadım diye kendimi avutuyorum :) .

Yarışmada sorulan ve benim kodunu düzgün yazamadığım için kaçırdığım güzel bir soru vardı: Elimizde 3 harften (A, B ve C olsun) oluşan bir alfabe ve bu alfabeden türetilen rastgele kelimeler var. Kelimeler arasında ise şöyle bir ilişki var;

– A ile biten bir kelimeden sonra B ile başlayan bir kelime gelmeli
– B ile biten bir kelimeden sonra C ile başlayan bir kelime gelmeli
– C ile biten bir kelimeden sonra A ile başlayan bir kelime gelmeli

Elimizdeki kelime dağarcığını kullanarak K (K \leq 10^{18}) kelime uzunluğunda bir yazı yazmak istiyoruz. Kaç farklı yazı yazabiliriz?

Her kelime çeşidini (A,B,C ile başlayan ve A,B,C ile biten toplam 9 olasılık) bir düğüm olarak düşünürsek  aslında soruda sorulmak istenen şey şu; herhangi bir düğümden başlayarak herhangi başka bir düğüme, aradaki her düğümü istediğimiz kadar ziyaret ederek K adımda kaç farklı şekilde varabiliriz? Bir düğümden başlayarak diğer bir düğüme, her düğümü istediğimiz kadar ziyaret etme işine graph theory’de walk (yürüyüş) diyoruz. Belirli bir uzunluktaki yürüyüşlerin sayısını bulmak için ise komşuluk matrisinin şu özelliğinden faydalanacağız;

A komşuluk matrisi olmak üzere, A^K matrisinin A_{i,j} değeri, n_i düğümünden n_j düğümüne yapılan K uzunluktaki yürüyüşlerin sayısını verir.

O zaman ilk olarak komşuluk matrisini oluşturmamız gerekiyor. İhtiyacımız olan 3 \times 3 lük bir komşuluk matrisi, satır indeksi bize kelimenin ilk karakterini, sütun indeksi ise kelimenin son karakteri ile gidebileceğimiz kelime grubunun ilk karakterini verecek. Örneğin A için 0, B için 1 ve C için 2 değerlerini atarsak, “ABAB” kelimesinin satır indeksi, ilk karakter A olduğu için 0, sütun indeksi ise B’den sonra C geleceği için 2 olacak. Her bir kelimenin bu matriste denk geldiği hücreyi bulup bir arttıracağız.

Son olarak ise A^K değerini hesaplamamız gerekiyor. K‘nın çok büyük olduğunu göz önünde bulundurursak A‘yı art arda K kez çarpmak iyi bir yöntem değil, onun yerine 2’li üs alma yöntemini kullanabiliriz.

Bu işlem karmaşıklığı O(K \times N^3)‘ten O(N^3 \times logK)‘ya düşürecek. En sonunda yapacağımız işlem ise tüm hücre değerlerini toplamak.

Benim yarışmada yaptığım hata ise, mul fonksiyonunda matrisleri çarparken indeksleri karıştırmak :) .

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.