TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
DOI 10.
34010/telekontran.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 Simulator Edukatif untuk Pembelajaran Algoritma Rapidly-exploring Random Tree (RRT) Educational Simulator for Teaching of Rapidly-exploring Random Tree (RRT) Algorithms Eka Setia Nugraha* Teknik Telekomunikasi.
Institut Teknologi Telkom Purwokerto Jl.
I Panjaitan No.
128 Purwokerto.
Indonesia *Email : eka_nugraha@ittelkom-pwt.
Abstrak Ae Paper ini mempresentasikan perancangan dan penggunaan simulator pendidikan untuk membantu pengajaran materi perencanaan gerak menggunakan algoritma Rapidly-exploring Random Tree (RRT).
Simulator ini dibuat menggunakan Laboratory Virtual Instrumentation Engineering Workbench (LabVIEW).
Pada simulator pendidikan ini dibuat juga beberapa variasi dari RRT, yaitu RRT*, bi-RRT dan RRT biased.
Keunggulan dari simulator ini adalah setiap subproses dari algoritma RRT dapat divisualisasikan sehingga akan membantu meningkatkan pemahaman dalam pembelajaran algoritma ini.
Parameter-parameter dari algoritma RRT juga dapat dengan mudah dimodifikasi sehingga dapat diamati pengaruhnya pada performansi keluaran dari RRT.
Pengujian performansi simulator dilakukan dengan membandingkan implementasinya pada beberapa kasus benchmark yang ada.
Karena salah satu hal penting dalam algoritma perencanaan jalur adalah mengenai waktu komputasi, maka pembuatan software simulator ini telah diefisiensikan agar diperoleh waktu komputasi sistem yang minimal.
Salah satu yang dilakukan agar meminimalkan waktu komputasi ini adalah dengan cara meminimalkan overhead pada program subVI.
Overhead pada subVI diminimalkan dengan menjadikannya sebagai subroutine.
Karena itu, pada perancangan simulator ini juga dihindari penggunaan fungsi-fungsi pada LabVIEW yang tidak bisa dijadikan sebagai subroutine.
Menggunakan salah satu kasus benchmark pada perencanaan jalur, algoritma RRT yang dirancang mampu menyusun jalur dalam waktu 185 milidetik adapun jika menggukan algoritma RRT*, perencanaan jalur dapat selesai dirancang dalam waktu 1273 milidetik.
Dengan memanfaatkan simulator ini diharapkan dapat membantu mahasiswa untuk mendapatkan pemahaman yang lebih baik mengenai algorima perencanaan gerak menggunakan RRT.
Kata Kunci : Perencanaan gerak.
Rapidly-exploring Random Tree, simulator, variasi RRT, visualisasi Abstract - This paper presents the design and use of educational simulators to assist in teaching motion planning material using the Rapidly-exploring Random Tree (RRT) algorithm.
This simulator is made using Laboratory Virtual Instrumentation Engineering Workbench (LabVIEW).
In this educational simulator also made several variations of the RRC, namely RRT*, bi-RRT and RRT biased.
The advantage of this simulator is that each subprocess of the RRT algorithm can be visualized so that it will help improve understanding in learning this algorithm.
The parameters of the RRT algorithm can also be easily modified so that they can be observed for the output performance of the RRT.
Simulator performance testing is done by comparing its implementation in several existing benchmark cases.
Because one of the important things in the path planning algorithm is about computational time, making this simulator software has been streamlined in order to obtain minimal system computing time.
Using one of the benchmark cases in path planning, the RRT algorithm is designed to be able to arrange a path in 185 milliseconds, whereas if using the RRT* algorithm, the path planning can be completed in 1273 milliseconds.
One of the ways to minimize this computation time is by minimizing overhead on subVI programs.
Subhead overheads are minimized by making them Therefore, the design of this simulator also avoids the use of functions in LabVIEW which cannot be used as subroutines.
Using this simulator is expected to help students to get a better understanding of the motion planning algorithm using RRT.
Keywords : Motion planning.
Rapidly-exploring Random Tree, simulators.
RRT variations, process TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
PENDAHULUAN
Algoritma perencanaan gerak atau jalur .
otion plannin.
adalah salah satu bidang penelitian mendasar dalam robotika .
Telah banyak metode yang sering digunakan untuk melakukan perencanaan jalur ini.
Algoritma pencarian seperti AD* .
dapat menemukan solusi optimal dalam kasus graph dinamis.
Namun, algoritma AD* hanya bias diterapkan pada ruang kerja yang telah didiskritisasi.
Metode pencarian jalur yang melibatkan diskritisasi ruang kerja ini memiliki kekurangan yaitu dapat mengalami penurunan kinerjanya dalam kasus dimensi yang tinggi.
Penelitian Pivtoraiko .
menggunakan perencanaan gerak konvensional yang digabungkan dengan algoritma pencarian Tetapi metode ini masih tetap membutuhkan diskritisasi ruang kerja.
Algoritma Ant Colony Optimization .
juga pernah diterapkan pada pencarian jalur robot.
Tetapi metode seperti ACO dapat terjebak pada solusi minimum local dan dapat berkinerja buruk pada kasus lingkungan yang memiliki celah sempit.
Metode perencanaan reaktif berbasis sensor juga pernah diteliti .
, .
, tetapi metode reaktif ini tidak dapat digunakan sebagai perencanaan jalur global atau jarak jauh.
Metode berbasis kontrol konvensional membutuhkan formulasi model yang tepat baik untuk robot maupun untuk lingkungan .
Pembuatan formulasi model yang akurat ini terkadang sulit untuk dilakukan.
Adapun algoritma perencanaan jalur berbasis pengambilan sampel atau Sampling Based Planning (SBP) memiliki keunggulan yaitu dapat memberikan solusi yang cepat pada masalah yang sulit .
Sejauh yang penulis ketahui, algoritma SBP yang paling umum digunakan adalah algoritma Probabilistic Roadmap Method (PRM) .
dan algoritma Rapidly-exploring Random Tree (RRT) .
Keunggulan dari algoritma PRM adalah dapat memberikan solusi yang optimal asimptotik, tetapi memiliki kekurangan yaitu waktu komputasi yang tinggi.
Adapun keunggulan algoritma RRT adalah memiliki waktu komputasi yang kecil, tetapi kekurangannya adalah hanya menyediakan solusi yang bersifat sub-optimal .
Algoritma RRT dikembangkan oleh Karaman menjadi RRT* .
Keunggulan RRT* adalah dapat menghasilkan solusi jalur yang bersifat optimal asimptotik .
Tetapi, waktu komputasi dari algoritma RRT* cukup tinggi.
Saat ini telah banyak algoritma variasi dari RRT* ini.
Akgun dan Stilman .
mengusulkan algoritma B-RRT *.
Algoritma B-RRT* ini meningkatkan optimasi dari jalur yang dihasilkan dengan cara menggunakan pencarian dua arah yaitu pencarian yang bermula dari titik awal dan titik akhir.
Kumar et al.
mengajukan algoritma RRTbiased.
Gammell et al.
mengajukan algoritma Informed RRT*.
Algoritma Informed-RRT* mengusulkan metode pengambilan sampel yang dilakukan hanya di daerah elips yang mengelilingi simpul awal dengan simpul akhir.
Nasir et al.
memperkenalkan algoritma RRT*-Smart.
RRT*Smart menggunakan dua fitur yang dinamakan, intelligent sampling dan route optimization.
Fitur dari RRT*-Smart dapat mempercepat laju Beberapa peneliti telah berhasil menerapkan algoritma RRT dan variasinya pada perencanaan gerak kendaraan otonom.
Tim MIT pada Darpa Urban Challenge menggunakan algoritma RRT-Closed Loop .
Karaman .
menerapkan algoritma RRT pada robot forklift.
Adapun mobil nuTonomy paa SingaporeAos OneNorth technology business district menggunakan algoritma RRT* .
Terdapat beberapa publikasi mengenai pembuatan toolbox dari algoritma RRT ini.
Sakai .
telah mempublikasikan toolbox robotic, menggunakan A*.
PRM.
RRT.
RRT*, dan masih ada lagi.
Tetapi Sakai menggunakan program Vahrenkamp juga telah mempublikasikan toolbox perencanaan jalur, tetapi dibuat menggunakan program C .
Corke .
mempublikasikan toolbox robotic tetapi dibuat menggunakan program MATLAB.
Sejauh yang diketahui oleh peneliti, belum ada penelitian yang membuat toolbox perencanaan jalur menggunakan LabVIEW.
Tujuan dari penelitian ini adalah untuk merancang perangkat lunak simulator sebagai alat bantu pengajaran materi perencanaan jalur .
otion plannin.
mengenai algoritma RRT.
Pada simulator ini juga dibuat beberapa variasi dari algoritma RRT, yaitu RRT*.
RRT biased dan algoritma bi-RRT.
Keunggulan dari simulator ini adalah dapat divisualisasikannya setiap subproses dari algoritma RRT sehingga dapat membatu meningkatkan pemahaman mahasiswa dalam mempelajari karakteristik algoritma RRT.
Pengguna juga dapat dengan mudah memodifikasi parameter-parameter dari RRT sehingga dapat perencanaan jalur ini.
Agar waktu komputasi dari program yang dibuat dapat diminimalkan, maka salah satu strategi yang dilakukan adalah dengan meminimalkan overhead pada subprogram LabVIEW .
Overhead pada subprogram LabVIEW diminimalkan dengan mengubahnya TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
menjadi subroutine.
Karena itu, pada perancangan simulator ini, dihindari penggunaan fungsi-fungsi dan subprogram pada LabVIEW yang tidak bisa dijadikan sebagai subroutine.
II.
METODE
Simulator pengajaran algoritma RRT ini dibuat menggunakan LabVIEW.
Algoritma dasar RRT yang digunakan ditunjukkan pada Gambar 1.
Terlihat bahwa terdapat beberapa proses yang RandomSample.
NearestNeighbor.
Steer dan InsertNode.
Proses RandomSample bertujuan mengambil sampel pada ruang pencarian, yang disebut sebagai .
NearestNeighbor mencari node pada pohon pencarian yang terdekat ke Node terdekat ini dinamakan sebagai .
Selanjutnya akan dibangun node baru diantara Node baru ini dinamakan Node akan berjarak .
Jika diantara ada hambatan, maka node akan ditambahkan ke pohon pencarian .
aris 7 dan .
Lalu iterasi akan berulang sebanyak kali .
aris 3 dan .
Ilustrasi dari algoritma RRT ini ditunjukkan pada Gambar 2.
Algorithm 1 :
Perbedaannya adalah adanya proses ChooseParent .
dan Rewire .
Detil algoritma ChooseParent ditunjukkan pada Gambar 4.
Pada proses ChooseParent, akan dicari node-node yang berjarak terdekat dari Node-node yang terdekat dari .
aris 8 pada Algorithm .
Diantara ini akan dicari node yang bila dihubungkan ke akan diperoleh jalur antara dan node awal yang paling minimal.
Node yang akan membuat jarak antara dan node awal minimal, akan dijadikan node parent dari (Algorithm .
Ilustrasi dari proses ChooseParent ini ditunjukkan pada Gambar 5.
Algorithm 2 :
Gambar 3.
Algoritma RRT* .
iadaptasi dari .
) Algorithm 3 :
Gambar 1.
Algoritma dasar dari RRT .
Gambar 4.
Operasi chooseparent pada algoritma RRT* .
iadaptasi dari .
) .
Gambar 2.
Ilustrasi proses algoritma RRT : .
baris 4, .
baris 5, .
baris 6, .
baris 8 pada Algorithm 1 .
iadaptasi dari .
) Adapun algoritma RRT* ditunjukkan pada Gambar 3.
Algoritma RRT* ini hampir mirip dengan algoritma RRT .
aris 1 Ae 6 algoritma pada Gambar 1 sama dengan baris 1 Ae 6 pada Gambar Adapun detil dari algoritma Rewire ditunjukkan pada Gambar 6.
Pada proses Rewire, akan dicari node-node yang terdejat dengan dimana jika node tersebut dihubungkan ke node awal melalui akan diperoleh jalur yang lebih dekat.
Maka parent baru dari node-node tersebut akan diubah menjadi Ilustrasi dari TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
proses Rewire ini ditunjukkan pada Gambar 7.
Sebelum proses rewire, node dengan node .
alur menukju node awal cukup jauh karena melalui jalur beliku-liku, lalu setelah proses rewire, node terhubung dengan menuju node awal, dimana jalur baru ini lebih minimal jaraknya daripada jarak sebelum proses Terdapat beberapa variasi dari algoritma RRT Diantaranya adalah algoritma RRT biased .
dan Bi-RRT .
Pada algoritma RRT biased, laju konvergensi ditingkatkan dengan cara membiaskan pertumbuhan pohon pencarian.
Metode yang digunakan adalah dengan cara saat hendak membangun node baru yang mengarah ke , maka node baru tidak dibuat hanya satu kali langkah saja, tetapi dibuat beberapa langkah hingga tercapai atau jalur yang dibuat terhalangi oleh hambatan.
Ilustrasi dari algoritma RRT biased ini ditunjukkan pada Gambar 8.
Gambar 8.
Ilustrasi algoritma RRT biased .
iadaptasi dari .
) .
Gambar 5.
Ilustrasi proses dari chooseparent RRT* : .
baris 8, .
baris 9 pada Algorithm 2 .
iadaptasi dari .
) Algorithm 4 :
Adapun algoritma Bi-RRT meningkatkan efisiensi dan optimalisasi jalur yang dihasilkan oleh algoritma dengan cara menggunakan versi dua arah pencarian dari algoritma RRT.
Pada algoritma Bi-RRT, salah satu pohon pencarian dimulai dari node awal dan secara bersamaan dibuat pohon pencarian lainnya yang dimulai dari node tujuan.
Ilustrasi dari proses algoritma BiRRT ini ditunjukkan pada Gambar 9.
Gambar 6.
Operasi rewire pada algoritma RRT* .
iadaptasi dari .
) Gambar 9.
Ilustrasi algoritma Bi-RRT.
Terdapat dua pohon pencarian yang berawal dari node start dan node goal i.
HASIL DAN DISKUSI
Gambar 7.
Ilustrasi dari proses rewire RRT* : .
pada keadaan awal node terhubung dengan node , .
setelah proses rewire, terhubung dengan Simulator pembelajaran algoritma RRT ini dapat memvisualisasikan proses pencarian jalur yang dilakukan oleh algoritma RRT.
Simulator pembelajaran algoritma RRT ini terdiri dari beberapa sub-program, yaitu :
Subprogram AuInisialisasi Data.
viAy Subprogram AuRandom Sampling.
viAy Subprogram AuGet Nearest List Index.
viAy Subprogram AuSteer.
viAy Subprogram AuCollision Check.
viAy Subprogram AuInsert Node.
viAy Subprogram AuDraw.
viAy TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Subprogram AuCheck Goal.
viAy Subprogram AuMake and Calculate Path.
viAy Subprogram AuDraw Complete Path.
viAy Subprogram AuInisialisasi Data.
viAy berfungsi untuk menerima gambar peta lingkungan yang akan di terapkan algoritma RRT.
Pengguna cukup membuat peta lingkungan pada software seperti MS paint.
Daerah yang boleh dilewati oleh algoritma RRT diwarnai putih, sedangkan hambatan yang tidak boleh dilewati algoritma RRT diwarnai hitam.
Titik Start dibuat dengan membuat titik warna merah .
engan nilai RGB :
R = 255.
G = 0.
B = .
Titik tujuan dibuat dengan membuat titik warna biru .
engan nilai RGB : R = 0.
G = 0.
B = .
Program AuInisialisasi Data.
viAy akan mencari kedua titik merah dan biru tersebut pada peta lingkungan yang diberikan, kemudian mengeluarkan koordinatnya untuk digunakan pada subprogram selanjutnya.
Block diagram dari AuInisialisasi Data.
viAy ditunjukkan pada Gambar Subprogram AuRandom Sampling.
viAy melakukan perintah baris 4 pada Algorithm 1.
Block diagram dari AuRandom Sampling.
viAy ditunjukkan pada Gambar 11.
Subprogram AuGet Nearest List Index.
viAy melakukan perintah baris 5 pada Algorithm 1.
Block diagram dari AuGet Nearest List Index.
viAy ditunjukkan pada Gambar Subprogram AuSteer.
viAy melakukan perintah baris 6 pada Algorithm 1.
Block diagram dari AuSteer.
viAyAy ditunjukkan pada Gambar 13.
Subprogram AuCollision Check.
viAy melakukan perintah baris 7 pada Algorithm 1.
Subprogram AuInsert Node.
viAy melakukan perintah baris 8 pada Algorithm 1.
Block diagram dari AuInsert Node.
viAy ditunjukkan pada Gambar 14.
Agar algoritma RRT dapat divisualisasikan prosesnya, maka dibuat subprogram AuDraw.
viAy yang akan mengvisualisasikan proses yang dilakukan oleh algoritma RRT untuk setiap Block diagram dari AuDraw.
viAy ditunjukkan pada Gambar 15.
Agar dapat diamati apakah solusi jalur yang dibuat oleh RRT bersifat konvergen atau tidak, maka akan dicatat histori solusi jalur lengkap yang telah menghubungkan node awal dengan node tujuan akan disimpan.
Pertama-tama subprogram AuCheck Goal.
viAy akan mengecek apakah pada pohon pencarian yang dikembangkan oleh RRT sudah mencapai node tujuan.
Jika telah ada node baru pada pohon pencarian yang berhasil mencapai node tujuan, maka oleh subprogram AuMake and Calculate Path.
viAy akan dibuat jalur lengkap yang menghubungkan node tersebut dengan node awal berdasarkan data dari pohon pencarian yang ada.
Lalu pada subprogram AuDraw Complete Path.
viAy, jalur lengkap yang sudah dibuat akan divisualisasikan menggunakan garis yang lebih tebal.
Block diagram dari AuCheck Goal.
viAy ditunjukkan pada Gambar 16, block diagram dari AuMake and Calculate Path.
viAy ditunjukkan pada Gambar 17 dan block diagram dari AuDraw Complete Path.
viAy ditunjukkan pada Gambar 18.
Gambar 10.
Block diagram AuInisialisasi Data.
viAy TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 11.
Block diagram AuRandom Sampling.
viAy Gambar 12.
Block diagram AuGet Nearest List Index.
viAy Gambar 13.
Block diagram AuSteer.
viAy Gambar 14.
Block diagram AuInsert Node.
viAy TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 15.
Block diagram AuDraw.
viAy Gambar 16.
Block diagram AuCheck Goal.
viAy Gambar 17.
Block diagram AuMake and Calculate Path.
viAy TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 18.
Block diagram AuDraw Complete Path.
viAy Agar waktu komputasi dapat minimal, maka overhead subVI diminimalkan dengan menjadikan subVI sebagai subroutine .
Program juga tidak menggunakan fungsi-fungsi bawaan LabVIEW yang tidak bisa dijadikan sebagai subroutine.
Hal menyelesaikan suatu kasus benchmark, program RRT yang dibuat dapat menyelesaikannya dalam waktu 185 milidetik.
Salah satu pengujian dilakukan dengan menggunakan peta benchmark yang diusulkan oleh Karaman pada .
Peta lingkungan yang digunakan untuk pengujian ditunjukkan pada Gambar 19.
Gambar peta tersebut dibuat pada program MS Paint.
Saat program dijalankan dapat diperoleh visualisasi seperti pada Gambar 20.
Pada visualisasi ini diperlihatkan posisi node random pada setiap iterasinya .
otak pin.
Dan akan terlihat juga adanya cabang baru yang menuju kearah node random tersebut.
Posisi node start diperlihatkan sebagai lingkaran berwarna merah.
Posisi node goal diperlihatkan sebagai lingkaran berwarna biru.
Gambar 21.
Contoh Visualisasi saat node baru dibangun.
Terlihat terdapat cabang baru menuju nore random .
otak pin.
Gambar 19.
Contoh peta lingkungan yang hendak digunakan untuk pengujian algoritma RRT.
Peta dibuat menggunakan program MS Paint.
Saat algoritma telah berhasil menemukan node yang berdekatan dengan node goal, maka akan dibangun jalur lengkap yang menghubungkan node awal dengan node tujuan.
Contoh jalur lengkap yang berhasil dibangun divisualisasikan dalam garis tebal seperti pada Gambar 22.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Selama iterasi berlangsung akan ada kemungkinan algoritma RRT menemukan alternatif jalur lengkap lainnya yang memiliki jarak tempuh lebih pendek daripada jalur lengkap yang sudah ada.
Maka jalur lengkap terpendeklah yang akan ditampilkan.
Gambar 23.
Visualisasi jalur lengkap terbaik yang diperoleh algoritma RRT setelah iterasi ke 366.
Jalur diperoleh dalam waktu 1273 milidetik Gambar 22.
Contoh visualisasi jalur lengkap yang menghubungkan node awal dan node tujuan.
Jalur diperoleh dalam waktu 185 Untuk pengujian menggunakan algoritma RRT*, dapat terlihat hasilnya seperti pada Gambar 23 dan Gambar 24.
Gambar 23 adalah jalur yang dihasilkan oleh algoritma RRT* pada iterasi ke 366.
Adapun Gambar 24 adalah jalur yang dihasilkan oleh algoritma RRT* pada iterasi Kedua gambar ini mencontohkan bahwa solusi jalur dari algoritma RRT* bersifat asimptotik optimal, yaitu solusi dari algoritma RRT* akan menuju solusi yang optimal jika waktu iterasi yang diberikan memungkinkan.
Hasil ini mendukung laporan yang dihasilkan oleh Karaman pada .
Karaman melaporkan contoh hasil algoritma RRT seperti pada Gambar 25 dan Gambar 26.
Gambar 25 menunjukkan hasil yang diperoleh Karaman pada iterasi ke 1500, dan Gambar 26 menunjukkan hasil yang diperolehnya pada iterasi ke 15000.
Untuk pengujian menggunakan algoritma RRT-biased, diperoleh hasil seperti pada Gambar Sesuai dengan prinsipnya bahwa node baru tidak dibuat satu kali, tetapi dibuat beberapa kali hingga node goal tercapai atau terhalang oleh hambatan, maka pada Gambar 27 dapat terlihat bahwa arah cabang yang sama terdapat garis lurus dimana diantara garis lurus tersebut terdapat node-node antaranya.
Hal ini membuat lebih sedikti jalur berliku yang ada.
Gambar 24.
Visualisasi jalur lengkap terbaik yang diperoleh algoritma RRT setelah iterasi ke 9271.
Jalur diperoleh dalam waktu 10644 milidetik Gambar 25.
Visualisasi jalur lengkap terbaik yang dilaporkan oleh Karaman pada .
setelah iterasi ke 1500 TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
diharapkan dapat membantu mahasiswa untuk mendapatkan pemahaman yang lebih baik menggunakan RRT.
Gambar 26.
Visualisasi jalur lengkap terbaik yang dilaporkan oleh Karaman pada .
setelah iterasi ke 15000 Gambar 28.
Visualisasi algoritma Bi-RRT
DAFTAR PUSTAKA