TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
DOI 10.
34010/telekontran.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 Studi Performansi Algoritma Perencanaan Jalur diantara PRM.
RRT.
RRT* dan Informed-RRT* Performance Study of Path Planning Algorithm between PRM.
RRT.
RRT* and Informed-RRT* Nelci Dessy Rumlaklak1,*.
Yelly Y.
Nabuasa2.
Tiwuk Widiastuti3
1,2,3
Program Studi Ilmu Komputer Fakultas Sains dan Teknik Universitas Nusa Cendana Jl.
Adisucipto.
Lasiana.
Kelapa Lima.
Kupang.
Nusa Tenggara Timur 85228.
Email: dessyrumlaklak@gmail.
Abstrak Ae Tujuan dari penelitian ini adalah melakukan studi perbandingan performansi dari beberapa algoritma perencanaan jalur.
Penelitian ini membandingkan empat algoritma perencanaan jalur yang terkenal, yaitu algoritma Probabilistic Roadmap (PRM).
Rapidly-exploring Random Tree (RRT).
RRT* dan Informed-RRT*.
Pengujian dilakukan melalui eksperimen berbasis simulasi menggunakan python.
Pengujian dilakukan menggunakan beberapa kasus benchmark yang ada, yaitu lingkungan narrow, maze, trap dan clutter.
Kriteria optimalitas yang dibandingkan adalah biaya jalur, waktu komputasi dan jumlah total node pada pohon yang dibutuhkan.
Dari hasil pengujian, terlihat bahwa algoritma RRT memiliki waktu komputasi yang tercepat tetapi memiliki kualitas jalur yang kurang baik.
Algoritma RRT*, informed-RRT* dan PRM memiliki kualitas jalur yang mirip.
Algoritma PRM memiliki waktu komputasi tertinggi dibandingkan algoritma RRT.
RRT* maupun informed-RRT*.
Hasil penelitian ini akan memberikan informasi kepada pembaca mengenai algoritma mana yang paling cocok untuk digunakan pada aplikasi pengguna dimana terdapat beberapa parameter kerja yang hendak dioptimalkan.
Kata Kunci : Perencanaan jalur.
PRM.
RRT.
RRT*.
Informed-RRT* Abstract - This paper will discuss a comparative performance review of several path planning algorithms.
This study compares five well-known path planning algorithms, namely the Probabilistic Roadmap (PRM).
Rapidly-exploring Random Tree (RRT).
RRT* and Informed-RRT* algorithm.
Testing is done through simulation based experiments using python.
The test was conducted using several existing benchmark cases, namely narrow, maze, trap and clutter environment.
The optimality criteria compared are path costs, computational time and the total number of nodes in the tree needed.
From the test results, it appears that the RRT algorithm has the fastest computing time but has a poor path quality.
RRT *, informed-RRT * and PRM algorithms have similar path quality.
PRM algorithm has the highest computational time compared to the RRT.
RRT * and informed-RRT * algorithms.
The results of this study will provide information to readers about which algorithm is most suitable for use in user applications where there are several working parameters to be optimized.
Keywords : Motion planning.
PRM.
RRT.
RRT*.
Informed-RRT* PENDAHULUAN Perencanaan jalur .
ath plannin.
adalah salah satu tugas penting dalam proses pengendalian robot otonom.
Tujuan dari perencanaan jalur adalah menghasilkan jalur bebas tabrakan dari posisi awal ke posisi tujuan dengan pada lingkungan yang memiliki hambatan statis maupun dinamis.
Algoritma perencanaan jalur akan mencari jalur dengan biaya jalur optimal atau mendekati optimal.
Aplikasi perencanaan jalur pada robot otonom memiliki banyak kegunaan seperti pada mobil otonom .
elf driving ca.
Unmanned Aerial Vehicle .
, forklift pada industry .
, ataupun pada operasi pengawasan dan misi luar angkasa .
Keterbatasan dari algoritma perencanaan jalur klasik adalah dibutuhkannya model lingkungan yang akurat sebelum algoritma perencana jalur dapat diterapkan.
Agar tidak perlu membuat model lingkungan yang akurat, salah satu TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
perencanaan jalur berbasis sensor.
Metode perencanaan jalur berbasis sensor memungkinkan robot untuk bekerja secara mandiri di lingkungan yang belum dipetakan.
Gerakan robot dihasilkan langkah demi langkah, dengan mengumpulkan semakin banyak informasi mengenai lingkungan.
Salah satu metode lainnya adalah dengan menggunakan metode perencanaan jalur berbasis Algoritma pencarian jalur berbasis graph yang sering digunakan adalah Djikstra .
A* .
D* .
ataupun AD* .
Metode perencanaan jalur lainnya yang sering digunakan adalah algoritma Sampling Based Planning (SBP).
Algoritma SBP dapat memberikan solusi yang cepat untuk masalah yang kompleks dan memiliki Algoritma
SBP
menggunakan pengambilan sampel acak pada ruang pencarian .
, .
Mungkin algoritma SBP yang paling terkenal adalah Probabilistic Roadmap Method (PRM) .
dan Rapidlyexploring Random Tree (RRT) .
Algoritma RRT diusulkan oleh Lavelle .
dimana Lavelle berhasil menerapkannya pada masalah komplek hingga dua belas derjat kebebasan.
Tetapi kekurangan dari algoritma RRT adalah jalur yang dihasilkan tidak optimal.
Karaman dan Frazzoli .
mengusulkan variasi dari algoritma RRT yang dinamakan RRT*.
Menggunakan dua fitur tambahan yaitu ChooseParent dan Rewire, algoritma RRT* memiliki kualitas keluaran yang bersifat asimptotik optimal.
Gammell dkk.
lalu mengembangkan algoritma RRT* menjadi algoritma yang dinamakan Informed-RRT*.
Algoritma informed-RRT* membatasi ruang pengambilan sample pada algoritma RRT yaitu hanya pada suatu daerah elips yang melingkupi titik awal dan titik akhir.
Teknik pengambilan sample pada algoritma informed-RRT* ini diklaim dapat mempercepat laju konvergensi dari algoritma RRT*.
Penelitian ini bertujuan untuk membandingkan performansi beberapa algoritma perencanaan jalur yang sering digunakan.
Algoritma performansinya adalah PRM.
RRT.
RRT* dan Informed-RRT*.
Memang telah ada beberapa penelitian yang melakukan perbandingan performansi dari beberapa algoritma perencanaan jalur.
Karaman .
melakukan perbandingan total jarak tempuh dan tingkat konvergensi antara algoritma RRT dan RRT*.
Zaheer .
melakukan perbandingan performansi antara algoritma RRT.
PRM.
Artificial Potential Field (APF).
A* dan Free Configuration Eigen-spaces (FCE).
Noreen .
melakukan perbandingan performansi antara RRT.
RRT* dan RRT*-Smart.
Elbanhawi .
melakukan perbandingan performansi antara RRT, biased RRT dan Bidirectional RRT.
Gamell .
melakukan perbandingan performansi antara RRT* dan informed-RRT*.
Nasir .
melakukan perbandingan performansi antara algoritma RRT* dan RRT*-Smart.
Noreen .
melakukan perbandingan performansi antara RRT.
RRT* dan RRT*-AB.
Tetapi sepanjang yang penulis ketahui, belum ada penelitian yang membandingkan performansi algoritma PRM.
RRT.
RRT* dan Informed-RRT* secara bersamaan pada kasuskasus lingkungan narrow, maze, trap dan clutter.
Makalah ini akan membahas studi perencanaan jalur yang sering digunakan, yaitu PRM.
RRT.
RRT* dan Informed-RRT*.
Pengujian menggunakan program python.
Pengujian dilakukan menggunakan beberapa kasus benchmark pada permasalahan perencanaan jalur, yaitu lingkungan narrow, maze, trap dan clutter.
Kriteria optimalitas yang dibandingkan pada pengujian adalah biaya jalur, waktu komputasi dan jumlah total node pada pohon yang dibutuhkan.
Hasil penelitian ini akan memberikan informasi kepada keterbatasan dari setiap algoritma.
Serta akan memberikan informasi mengenai algoritma mana yang paling cocok untuk kebutuhan aplikasi pengguna.
II.
METODE
Penelitian performansi dari empat algoritma perencanaan jalur yang sering digunakan.
Algoritma yang dibandingkan adalah PRM.
RRT.
RRT* dan Informed-RRT*.
Algoritma PRM yang digunakan terdiri dari dua proses.
Proses pertama adalah pembangkitan sample point dan membangun roadmap, selanjutnya adalah membangun jalur berdasarkan roadmap yang ada menggunakan algoritma Djikstra.
Algoritma proses yang pertama ini ditunjukkan pada Gambar 1, adapun algoritma proses yang kedua ditunjukkan pada Gambar 2.
Ilustrasi dari proses pengambilan sample dan pembangunan roadmap ditunjukkan pada Gambar 3.
Ilustrasi proses yang pembangunan Djikstra ditunjukkan pada Gambar 4.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Algorithm 1 : Generate Sample Point and Roadmap Construction Algorithm Input :
: number of nodes to put : number of closest neighbors to examine for each configuration Output : A roadmap a random configuration in Until is collision-free end while for all the closest negihbors of chosen from according to for all is collision-free then end if end for Gambar 1.
Algoritma PRM untuk membangkitkan sampel dan membuat roadmap .
iadaptasi dari .
] Algorithm 2 : Solve Query Algorithm Input :
: the initial configuration : the goal configuration : the number of closest neighbors to examine for each configuration : the roadmap computed by algorithm 1 Output : A path from or failure the closest neighbors of from according to the closest neighbors of from according to set to be the closest neighbor of NIL then set to be the next closest neighbor of end if until a connection was successful or the set is empty set to be the closest neighbor of NIL then set to be the next closest neighbor of end if until a connection was successful or the set is empty using Djikstra Algorithm if is not empty then return failure end if Gambar.
Algoritma PRM untuk membangkitkan jalur final .
iadaptasi dari .
) TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Algoritma RRT yang digunakan ditunjukkan pada Gambar 5.
Pada setiap iterasi, node dipilih secara acak dari ruang konfigurasi Node terdekat ke dari pohon pencarian lalu dipilih dan dinamakan Selanjutnya akan dibuat cabang baru dari pohon pencarian Cabang baru ini dan menuju arah Cabang baru ini dengan node baru bernama akan ditambahkan ke pohon pencarian tidak ada hambatan.
Algoritma RRT* yang digunakan ditunjukkan pada Gambar 4.
Pengembangan fitur RRT* adalah adnaya operasi ChooseParent (Gambar .
dan operasi Rewire (Gambar .
Seperti pada algoritma RRT, algoritma RRT secara bertahap membangun pohon pencarian mengambil sampel secara acak pada ruang .
aris 4 Algorithm .
Kemudian menambahkan lintasan baru memperluas node terdekat dari pohon pencarian dengan node .
aris 5 Ae .
Jika node baru tersebut tidak bertabrakan dengan RRT menambahkan node baru kepada pohon pencarian lalu melanjutkan iterasi selanjutnya.
Algorithm 4 :
Input :
: the configuration where the tree is rooted : maximum iteration Output : A roadmap to do .
Gambar 3.
Ilustrasi pembangkitan sampel node dan roadmap oleh algoritma PRM : .
peta lingkungan sebelum pembangkitan sampel dan roadmap, .
peta lingkungan setelah pembangkitan sampel dan roadmap .
iadaptasi dari .
) Gambar 6.
Algoritma RRT* Gambar 4.
Ilustrasi pembangkitan jalur final oleh algoritma PRM Algorithm 3 :
Input :
: the configuration where the tree is rooted : maximum iteration Output : A roadmap to do Algorithm 5:
Gambar 7.
Operasi ChooseParent pada algoritma RRT* Gambar 5.
Algoritma RRT TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Algorithm 6:
Gambar 8.
Operasi Rewire pada algoritma RRT* Perbedaan algoritma RRT* dengan RRT adalah pada saat memilih node yang akan dijadikan induk dari node baru.
Algoritma RRT* mempertimbangkan semua simpul terdekat dari .
aris 8 algorithm .
dan mengecek biaya jalur dari masing-masing node terdekat Node terdekat yang akan menghasilkan jalur terpendek diantara dijadikan induk bagi node .
Proses Rewire, yang dijelaskan pada algorithm 6, akan memeriksa setiap node mengetahui apakah menjangkau Gambar 10.
Contoh lingkungan pengujian maze Gambar 11.
Contoh lingkungan pengujian trap akan menghasilkan jarak yang lebih dekat ke Ketika koneksi diperoleh jalur yang lebih pendek dari sebelumnya, maka program akan melakukan proses rewire dengan mengubah induk Lalu algoritma akan berlanjut ke iterasi selanjutnya.
Pengujian dilakukan menggunakan simulasi berbasis python.
Kami menggunakan toolbox PythonRobotics yang dikembangkan oleh Sakai .
Kami mengambil beberapa lingkungan khusus yang sering digunakan pada pengujian algoritma perencanaan jalur, yaitu narrow .
elah sempit, seperti Gambar .
, maze .
abirin, seperti Gambar .
, trap .
uangan dengan celah sempit untuk masuk atau keluar, seperti Gambar .
serta clutter .
ingkungan dengan banyak rintangan yang berantakan, seperti Gambar .
Kriteria optimalitas yang diukur dan dibandingkan adalah adalah biaya jalur, waktu komputasi dan jumlah total node pada pohon yang dibutuhkan.
Gambar 9.
Contoh lingkungan pengujian narrow Gambar 12.
Contoh lingkungan pengujian clutter i.
HASIL DAN DISKUSI
Mengikuti contoh yang dilakukan oleh Karaman .
, untuk membandingkan kinerja algoritma RRT dan RRT*, maka pada penelitian ini keempat algoritma akan diuji pengujian dengan cara dijalankan sebanyak 500 kali.
Lalu dirata-ratakan jarak jalur yang dihasilkan, waktu komputasi dan jumlah node dari setiap iterasi.
Hasilnya ditunjukkan pada Gambar 10 - 13.
Terlihat bahwa algoritma dasar RRT cenderung menghasilkan jalur yang berliku-liku (Gambar 10.
, 11.
, 12.
Hal ini salah satu yang mengakibatkan algoritma RRT bersifat sub-optimal.
Adapun algoritma RRT* maupun informed-RRT* mampu membangun jalur yang tidak berliku-liku (Gambar 11.
, 12.
, 13.
, serta 14.
Hal ini karena RRT* menggunakan fitur ChooseParent dan Rewire yang cenderung mencari rute dengan jalur yang terpendek, dan jalur terpendek adalah jalur yang tidak berbelokbelok.
Tetapi keunggulan algoritma RRT adalah mampu membangun jalur dengan sangat cepat.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Untuk kasus lingkungan narrow, algoritma RRT dapat membangun jalur sekitar tiga kali lebih cepat daripada RRT* maupun informed-RRT*.
Walaupun algoritma PRM dapat menghasilkan jalur yang terpendek, tetapi waktu komputasinya sangat tinggi.
Untuk kasus lingkungan narrow, waktu komputasi algoritma PRM hingga 6000 kali lebih lambat daripada algoritma RRT.
Tentu saja waktu komputasi dari algoritma PRM ini akan sangat dipengaruhi oleh jumlah sampel yang Pada penelitian ini, digunakan 500 sampel node pada algoritma PRM.
Penelitian Zaheer pada .
juga menunjukkan tingginya waktu komputasi PRM dibandingkan RRT ini.
Prinsip dari algoritma Informed-RRT* adalah membatasi ruang sampling, yaitu hanya disekitar daerah elips yang melingkupi node awal dan node Maka dapat terlihat pada Gambar 10.
, 11.
, 12.
, bahwa arah penyebaran pohon pencarian tidak terlalu melebar kemanamana, tetapi seolah-olah dibatasi oleh lingkaran .
elips tak terlihat yang titik pusatnya di node awal dan node akhir.
Dibandingkan dengan algoritma RRT* seperti pada Gambar 10.
, 11.
, 12.
, pohon pencarian menyebar kemanamana.
Strategi membatasi ruang pencarian cukup membantu algoritma informed-RRT* untuk memangkas waktu komputasinya.
Dapat terlihat pada Gambar 10, 12 dan 13, bahwa waktu komputasi algoritma informed-RRT* lebih kecil daripada waktu komputasi algoritma RRT* untuk lingkungan narrow, clutter dan maze.
Adapun untuk kasus lingkungan trap, rata-rata waktu komputasi algoritma informed-RRT* memang masih lebih lama daripada waktu komputasi algoritma RRT*.
Hal ini dapat dipahami karena tingkat kesulitan lingkungan tersebut, dimana membatasi ruang pencarian sampel dalam bentuk elips tidak terlalu memungkinakan dalam kasus .
Gambar 10.
Perbandingan performansi pada lingkungan dengan celah sempit .
Algoritma RRT : rata-rata jarak jalur = 542,485.
rata-rata jumlah node = 185.
rata-rata waktu komputasi = 5,36 ms .
Algoritma RRT* : rata-rata jarak jalur = 441,238.
rata-rata jumlah node = 158.
rata-rata waktu komputasi = 17,44 ms .
Algoritma Informed-RRT* : rata-rata jarak jalur = 538,573.
rata-rata jumlah node = 147.
rata-rata waktu komputasi = 13,98 ms .
Algoritma PRM : rata-rata jarak jalur = 535,309.
rata-rata jumlah node = 500.
rata-rata waktu komputasi = 33.
324,3 ms TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 11.
Perbandingan performansi pada ruangan dengan celah sempit untuk masuk atau keluar .
Algoritma RRT : rata-rata jarak jalur = 1069,79.
rata-rata jumlah node = 1013.
rata-rata waktu komputasi = 32,2 ms .
Algoritma RRT* : rata-rata jarak jalur = 840,667.
rata-rata jumlah node = 1074.
rata-rata waktu komputasi = 121,9 ms .
Algoritma Informed-RRT* : rata-rata jarak jalur = 790,84.
rata-rata jumlah node = 1190.
rata-rata waktu komputasi = 145,55 ms .
Algoritma PRM : rata-rata jarak jalur = 788,524.
rata-rata jumlah node = 500.
rata-rata waktu komputasi = 18.
398,5 ms Hal lain yang menarik untuk diperhatikan juga adalah implementasi keempat algoritma ini pada kasus lingkungan trap.
Pada kasus ini, algoritma RRT.
RRT*, dan informed-RRT* menunjukkan pengujian dalam lingkungan yang lain.
Tetapi algoritma PRM justru menunjukkan penurunan waktu komputasi dibandingkan pengujian dalam lingkungan yang lain.
Hal ini menunjukkan bahwa pada algoritma pengambilan sampel .
eperti RRT.
RRT*, dan informend RRT*) akan mengalami peningkatan waktu komputasi jika diterapkan pada kasus ruangan dengan celah sempit untuk masuk dan keluar.
Tetapi mungkin algoritma PRM cukup tepat untuk diterapkan pada lingkungan trap ini.
Walau waktu komputasi algoritma PRM ini masih tinggi, tetapi dengan menurunkan jumlah sampel yang digunakan pada algoritma PRM, maka waktu komputasi dari algoritma PRM ini dapat dikurangi.
Untuk memberikan pemahaman lebih lanjut performansi dari masing-masing algoritma, maka pada Tabel I Ae Tabel XII disajikan rincian performansi keluaran rata-rata, minimal dan maksimal dari setiap algoritma.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 12.
Perbandingan performansi pada lingkungan dengan banyak halangan berantakan .
Algoritma RRT : rata-rata jarak jalur = 755,501.
rata-rata jumlah node = 245.
rata-rata waktu komputasi = 14,7 ms .
Algoritma RRT* : rata-rata jarak jalur = 612,358.
rata-rata jumlah node = 198.
rata-rata waktu komputasi = 33,4 ms I Algoritma Informed-RRT* : rata-rata jarak jalur = 594,469.
rata-rata jumlah node = 143.
rata-rata waktu komputasi = 24,95 ms .
Algoritma PRM : rata-rata jarak jalur = 593,192.
rata-rata jumlah node = 500.
rata-rata waktu komputasi = 27.
240,5 ms TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 13.
Perbandingan performansi pada lingkungan labirin :
Algoritma RRT : rata-rata jarak jalur = 1180,79.
rata-rata jumlah node = 3584.
rata-rata waktu komputasi = 51,05 ms .
Algoritma RRT* : rata-rata jarak jalur = 843,805.
rata-rata jumlah node = 3483.
rata-rata waktu komputasi = 248,6 ms I Algoritma Informed-RRT* : rata-rata jarak jalur = 831,799.
rata-rata jumlah node = 2189.
rata-rata waktu komputasi = 189,6 ms .
Algoritma PRM : rata-rata jarak jalur = 859,724.
rata-rata jumlah node = 500.
rata-rata waktu komputasi = 1,579.
8 ms TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Tabel I.
Perbandingan jarak jalur pada lingkungan narrow Algoritma InformedRRT* RRT* RRT Minimum Maksimum Rata-rata Minimum Maksimum Rata-rata RRT* InformedRRT* Tabel i.
Perbandingan waktu komputasi pada lingkungan narrow .
alam milideti.
RRT Minimum Maksimum Rata-rata Algoritma InformedRRT* RRT* Minimum Maksimum Rata-rata Algoritma InformedRRT* RRT* Minimum Maksimum Rata-rata RRT* InformedRRT* Tabel VI.
Perbandingan waktu komputasi pada lingkungan trap .
alam milideti.
RRT Minimum Maksimum Rata-rata Algoritma InformedRRT* RRT* PRM Tabel VII.
Perbandingan jarak jalur pada lingkungan clutter
RRT
Minimum
Maksimum
Rata-rata Algoritma
InformedRRT* RRT* PRM
RRT
RRT*
InformedRRT* Tabel IX.
Perbandingan waktu komputasi pada lingkungan clutter .
alam milideti.
RRT Minimum Maksimum Rata-rata Algoritma InformedRRT* RRT* PRM Tabel X.
Perbandingan jarak jalur pada lingkungan maze Algoritma InformedRRT* RRT* RRT Minimum Maksimum Rata-rata PRM Tabel XI.
Perbandingan jumlah node pada lingkungan maze
Algoritma
PRM
Tabel V.
Perbandingan jumlah node pada lingkungan trap
Algoritma
RRT
Minimum Maksimum Rata-rata PRM Tabel IV.
Perbandingan jarak jalur pada lingkungan trap
RRT
Tabel VII.
Perbandingan jumlah node pada lingkungan clutter
Algoritma
PRM
Tabel II.
Perbandingan jumlah node pada lingkungan narrow
Algoritma
RRT
Minimum
Maksimum
Rata-rata RRT
RRT*
InformedRRT* Tabel XII.
Perbandingan waktu komputasi pada lingkungan maze .
alam milideti.
RRT Minimum Maksimum Rata-rata Algoritma InformedRRT* RRT* PRM Pada Tabel I dapat terlihat bahwa jalur terbaik yang dihasilkan oleh algoritma RRT .
ilai minimu.
, masih belum sebaik jalur terjauh yang dihasilkan oleh RRT* .
ilai Mengenai rentang kualitas/panjang jalur yang dihasilkan oleh algoritma RRT*.
Informed-RRT* maupun PRM memang masih saling mendekati.
Tetapi kekurang besar dari algoritma PRM memang adalah waktu komputasinya seperti terlihat pada Tabel i.
VI.
IX, dan XII.
Dapat terlihat bahwa pada perbandingan jumlah node di table II.
VII, maupun XI tidak menyertakan algoritma PRM.
Hal ini dikarenakan jumlah node pada algoritma PRM merupakan setingan parameter awal.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
IV.
KESIMPULAN
Dari hasil pengujian pada lingkungan trap, narrow, maze maupun clutter, dapat terlihat beberapa karakteristik dari algoritma RRT.
RRT*.
Informed-RRT* dan PRM.
Algoritma RRT memiliki waktu komputasi yang tercepat, tetapi memiliki kualitas jalur yang kurang baik.
Bahkan berdasarkan pengujian di lingkungan trap, kualitas jalur terbaik algoritma RRT masih kalah dibandingkan kualitas jalur terburuk algoritma RRT*.
Algoritma RRT*, informed-RRT* dan PRM memiliki kualitas jalur yang mirip.
Pada kasus lingkungan trap, menunjukkan peningkatan waktu komputasi yang tinggi pada algoritma RRT.
RRT* dan informed-RRT*, tetapi tidak pada algoritma PRM.
Tetapi algoritma PRM tetap memiliki waktu komputasi tertinggi dibandingkan algoritma RRT.
RRT*, maupun informed-RRT*.
Algoritma RRT dapat memiliki waktu komputasi yang cepat karena algoritma-nya yang sederhana.
Adapun algoritma PRM dapat memiliki waktu komputasi yang tinggi karena melakukan pengecekan kepada seluruh node yang ada untuk memperoleh jalur yang terpendek.
DAFTAR PUSTAKA