RRT (Rapidly-exploring Random Tree)
RRT (Rapidly-exploring Random Tree) membangun jalur dengan menumbuhkan pohon dari titik start ke arah sampel acak di ruang. Untuk tiap sampel, dicari node terdekat lalu ditarik (steer) satu langkah ke arahnya; jika terhalang rintangan langkah ditolak, jika tidak node baru ditambahkan ke pohon hingga cukup dekat dengan goal. Visualisasi menunjukkan cabang-cabang acak yang tumbuh menghindari balok rintangan sampai rute mencapai target.
Perencanaan gerak lengan robot atau drone yang mencari lintasan bebas tabrakan di ruang dengan banyak rintangan.
RRT membangun jalur dengan menumbuhkan pohon acak dari titik start, melangkah sedikit demi sedikit ke arah sampel acak sambil menghindari rintangan.
- ·Memahami cara pohon tumbuh menuju titik-titik sampel acak
- ·Menjelaskan langkah steer dan penolakan bila terhalang rintangan
- ·Menerapkan RRT untuk merencanakan lintasan bebas tabrakan
- ·Mulai pohon hanya dengan node start
- ·Ambil satu titik sampel acak di ruang
- ·Cari node pohon terdekat ke sampel itu
- ·Steer satu langkah kecil dari node terdekat ke arah sampel
- ·Tolak langkah bila menabrak rintangan, kalau bebas tambahkan node baru sampai dekat goal
- ·Pohon (tree)
- ·Koordinat 2D
- ·Perencanaan gerak lengan robot agar tidak menabrak benda
- ·Drone mencari lintasan bebas halangan di ruang penuh rintangan
- ·Mobil otonom merencanakan manuver di area sempit
Kompleksitas O(n log n) untuk n sampel dengan pencarian tetangga terdekat