Kanca
RRT'ye "en kısa yolu bul" demezsin — "rastgele dene, dene, dene, sonunda bir yol bulursan bul" dersin. Garip bir strateji gibi görünür. Ama yüksek boyutlu uzaylarda (bir robot kolunun 6 eklemi gibi) A*'ın ızgarası patlarken, bu "rastgele deneme" stratejisi hâlâ çalışır.
Ya şunu denesen? Bir engelin boyutunu iki katına çıkarsan planlayıcılar hâlâ yol bulur mu?
Nasıl hesaplandı?Tablodaki yol uzunluğu, ham (x, y) nokta dizisinin toplam mesafesidir — dizinin kendisi burada.
Her algoritmanın döndürdüğü PlanResult.path, ardışık (x, y) noktalarından oluşur; yukarıdaki tablonun “Yol uzunluğu” sütunu bu dizideki ardışık noktalar arası mesafelerin toplamıdır (pathLength, lib/robotics/planners).
Karşılaştırma
Ne oldu
RRT (Rapidly-exploring Random Tree): start noktasından bir ağaç büyütür. Her adımda:
- Uzayda rastgele bir nokta örnekle (küçük bir olasılıkla doğrudan hedefi seç —
goalBias) - Ağaçtaki en yakın düğümü bul
- O düğümden örneklenen noktaya doğru sabit bir adım (
stepSize) kadar ilerle - Yeni nokta ve oraya giden segment çarpışmasızsa ağaca ekle
- Yeni düğüm hedefe yeterince yakınsa (
goalTolerance) bitir
Bu, lib/robotics/planners/rrt.ts içindeki plan() fonksiyonunun birebir
akışı. Bulduğu yol genelde verimsiz görünür — zikzaklı, gereksiz uzun.
Çünkü RRT optimal yolu değil, bir yolu arar, mümkün olduğunca hızlı.
RRT*: Aynı rastgele genişlemeyi yapar, ama iki ek adımla yolu zamanla kısaltır:
- Yeni düğümü eklerken, en yakın komşu yerine en düşük maliyetli
komşuyu ebeveyn seçer (
rewireRadiusiçindeki komşular taranır) - Ekledikten sonra, o komşulardan hangileri yeni düğüm üzerinden daha ucuza bağlanabilir diye kontrol eder ve gerekirse onları yeniden bağlar (rewire)
RRT hedefe ulaşır ulaşmaz durur. RRT* hedefe ulaştıktan SONRA da aramaya devam eder — amaç artık "bir yol" değil, "giderek kısalan bir yol". Yukarıdaki sahnede iki algoritmayı aynı engel düzeninde çalıştırıp sonuç tablosundaki "Yol uzunluğu" sütununu karşılaştır.
PRM (Probabilistic Roadmap): RRT/RRT* "tek seferlik" planlayıcılardır —
her start/goal çifti için ağacı baştan kurarlar. PRM farklı çalışır: önce
uzayda rastgele çok sayıda nokta örnekleyip birbirine yakın olanları
çarpışmasız kenarlarla bağlayarak bir "yol haritası" (roadmap) kurar —
bu kurulum pahalıdır ama BİR KERE yapılır. Sonra herhangi bir start/goal
çifti için bu hazır haritada en kısa yolu arar (A*'a benzer bir arama ile).
Aynı sahnede çok sayıda farklı start/goal sorgusu yapılacaksa PRM RRT'den
daha verimlidir; tek bir sorgu için RRT genelde daha hızlıdır. Bu platform
şu an PRM'i çalıştırılabilir bir sahne olarak sunmuyor (bkz.
docs/03-yol-haritasi.md Faz 2 kapsamı) — burada sadece RRT ailesiyle
karşılaştırmalı olarak tanımı veriliyor.
Gerçek dünyada
Yüksek serbestlik dereceli robotlar (6-7 eksenli kollar) için konfigürasyon uzayı 6-7 boyutludur; A*'ın grid'i bu boyutta pratik olarak kurulamaz (hücre sayısı boyutla üstel artar). Endüstriyel yazılımları ve ROS'un MoveIt hareket planlama kütüphanesi bu yüzden RRT/RRT* ailesini varsayılan planlayıcı olarak kullanır.
Dene
Sahneye birkaç engel yerleştir (aralarında dar bir geçit bırak), sonra "Yarıştır"a bas. RRT'nin yolunun ne kadar zikzaklı olduğuna, RRT*'ınkinin ise daha düz bir çizgiye yaklaştığına dikkat et. Şimdi engelleri temizleyip tekrar yarıştır — açık alanda iki algoritma arasındaki fark küçülür mü, büyür mü? Neden?
Kaynak kodu: RrtPlanner, RrtStarPlanner
Sonraki
RRT ve RRT*'ı aynı sahnede çalıştırdın, birinin hızlı-kaba diğerinin yavaş-iyi olduğunu gördün. Sıradaki ders bu ödünleşimi (trade-off) daha sistemli ele alıyor: A*'ı da tabloya katıp üç algoritmayı birden karşılaştırıyor.