March | 2015 | Orhan Özalp | Page 2
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;
‘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;
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.
Tagged path planning, robot, yol planlama
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.
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.
200 adım sonunda ise RRT aşağıdaki gibi dallanmış olacak.
Böyle dallanarak sonunda aşağıdaki gibi bir yol elde etmiş olacağız.
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.