TELEKONTRAN.
VOL.
NO.
APRIL 2022
DOI : 10.
34010/telekontran.
TELEKONTRAN,
VOL.
NO.
APRIL 2022
p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 LabVIEW Libraries untuk Algoritma Perencanaan Jalur Robotik LabVIEW Libraries for Robotic Path Planning Algorithms Muhammad Aria Rajasa Pohan Teknik Elektro.
Universitas Komputer Indonesia Jalan Dipati Ukur No 112 Ae 116 Bandung.
Indonesia Email : muhammad.
aria@email.
Abstrak Ae Makalah ini mempresentasikan pengembangan library yang dapat digunakan untuk membuat algoritma perencanaan jalur untuk sistem robotik.
Laboratory Virtual Instrumentation Engineering Workbench (LabVIEW) digunakan untuk membuat library algoritma perencanaan jalur ini.
Algoritma perencanaan jalur yang dapat dibuat menggunakan library ini adalah Rapidly-exploring Random Tree (RRT).
RRT*.
RRT*Connect.
Informed RRT*.
Informed RRT*-Connect.
Probabilistic Roadmap (PRM).
A*.
Dijkstra.
Particle Swarm Optimization (PSO), dan RRT-Ant Colony System (ACS).
Kelebihan dari library ini adalah setiap subproses dapat divisualisasikan, waktu komputasi yang cepat, tersedia tools untuk analisis, skenario pengujian dapat dibuat secara fleksibel, serta parameter algoritma dapat dengan mudah diubah untuk melihat bagaimana pengaruhnya terhadap kinerja keluaran algoritma.
Kinerja dari library ini dievaluasi dengan membandingkan implementasi library pada skenario benchmark dari publikasi peneliti lain.
Karena waktu komputasi merupakan faktor penting dalam algoritma perencanaan jalur, pengembangan perangkat lunak library ini telah disederhanakan untuk mencapai waktu komputasi sistem sesingkat mungkin.
Dengan menjadikan setiap SubVI di library ini sebagai subroutine, overhead program subVI telah berhasil dikurangi.
Akibatnya, waktu komputasi library ini berkurang.
Hasil pengujian meggunakan beberapa kasus benchmark menunjukkan bahwa library yang diusulkan memiliki waktu komputasi lebih cepat daripada library Implementasi library pada sistem robotik diuji menggunakan LabVIEW Robotics Simulator.
Kami juga memberikan contoh beberapa pengembangan yang dapat dilakukan dengan menggunakan library Dengan menggunakan library ini, diharapkan mahasiswa lebih memahami dan mempermudah dalam pengembangan algoritma perencanaan jalur untuk sistem robotik.
Kata Kunci : Perencanaan jalur.
LabVIEW library, rapidly-exploring random tree, waktu komputasi, analysis tools Abstract - This paper presents the development of a library that can be used to create path planning algorithms for robotic systems.
Laboratory Virtual Instrumentation Engineering Workbench (LabVIEW) was used to create this library of path planning algorithms.
Path planning algorithms that can be created using this library are Rapidly-exploring Random Tree (RRT).
RRT*.
RRT*-Connect.
Informed RRT*.
Informed RRT*-Connect.
Probabilistic Roadmap (PRM).
A*.
Dijkstra.
Particle Swarm Optimization (PSO), and the RRT-Ant Colony System (ACS).
The performance of this library is evaluated by comparing the implementation of the library in benchmark scenarios from other researchers' publications.
The advantages of this library are that each subprocess can be visualized, computation time is fast, tools are available for analysis, test scenarios can be created flexibly, and algorithm parameters can be easily changed to see how it affects the algorithm's output Since computation time is an essential factor in path planning algorithms, the software development of this library has been streamlined to achieve the shortest possible system compute time.
making every SubVI in this library a subroutine, the overhead of subVI programming has been reduced.
As a result, the computation time of this library is reduced.
The test results show that the proposed library has a faster computation time than the comparison library.
The library implementation on the robotic system was tested using the LabVIEW Robotics Simulator.
We also provide examples of some developments that can be done using this library.
By using this library, it is hoped that students will understand and make it easier to develop path planning algorithms for robotic systems.
Keywords : Path planning.
LabVIEW library.
Rapidly-exploring Random Tree, computation time, analysis TELEKONTRAN.
VOL.
NO.
APRIL 2022
PENDAHULUAN
Algoritma path planning atau perencanaan jalur adalah bidang penelitian mendasar pada robotika .
Algoritma perencanaan jalur dapat dibagi menjadi beberapa kelas, diantaranya: metode graph search dan metode incremental search .
Contoh metode graph search adalah Dijkstra .
dan A* .
Kelemahan metode graph search adalah optimalitas algoritma hanya dapat dijamin jika resolusi diskritisasi ruang keadaan cukup baik.
Namun, resolusi yang baik mungkin sulit dicapai dalam ruang berdimensi tinggi .
Algoritma Probabilistic Roadmaps (PRM) .
juga dikategorikan sebagai metode graph search oleh Paden .
Metode incremental search menggunakan metode berbasis sampel agar tidak memerlukan diskritisasi ruang keadaan.
Hal ini membuat metode incremental search lebih efektif pada ruang berdimensi tinggi .
Contoh metode incremental search adalah Rapidly-exploring Random Tree (RRT) .
dan RRT* .
Algoritma RRT dapat membuat jalur dengan cepat, tetapi solusi yang dihasilkan suboptimal .
Algoritma RRT* dapat membuat jalur yang optimal asimtotik .
, tetapi tingkat konvergensi RRT* lambat .
Banyak metode telah dikembangkan untuk meningkatkan kualitas algoritma RRT dan RRT*.
Kuffner dan Lavalle memperkenalkan versi dualtree dari RRT, yaitu RRT-Connect .
Klem dkk.
memperkenalkan algoritma RRT*-Connect .
, yang menggabungkan RRT-Connect dengan RRT*.
Gammel dkk memperkenalkan algoritma Informed RRT* .
, yang menggunakan sampling terinformasi pada RRT* setelah solusi pertama Prosedur pengambilan sampel dilakukan di area elips yang mengelilingi node awal dan tujuan.
Area sampling akan semakin kecil dan lebih fokus jika jalur yang menghubungkan node awal ke node tujuan menjadi lebih pendek.
Mashayekhi dkk.
memperkenalkan algoritma Informed RRT*-Connect yang berperilaku seperti RRT*-Connect hingga jalur pertama ditemukan.
Setelah solusi pertama ditemukan, area pengambilan sampel dari Informed RRT*-Connect dibatasi seperti pada Informed RRT*.
Beberapa perencanaan jalur berbasis swarm intelligence.
Pohan dkk.
memperkenalkan algoritma perencanaan jalur menggunakan hibridisasi algoritma RRT dan Ant Colony System (ACS).
Algoritma tersebut dinamakan RRT-ACS.
Li dkk.
menggunakan Particle Swarm Optimization (PSO) sebagai dasar untuk melakukan perencanaan jalur.
Berbagai peneliti telah melakukan publikasi dengan subyek pembuatan toolbox algoritma perencanaan jalur.
Sakai toolbox perencanaan jalur yang diberi nama PythonRobotics .
Beberapa algoritma perencanaan jalur yang dapat dibuat menggunakan PythonRobotics adalah Dijkstra.
PRM.
A*.
RRT.
RRT*.
Informed RRT*.
Namun.
PythonRobotics yang dibuat Sakai hanya dapat digunakan pada program python.
Sedangkan program python memiliki waktu komputasi yang lama .
Lingkungan pengujian yang dapat digunakan untuk PythonRobotics juga hanya obstacle berbentuk lingkaran.
Vahrenkamp mempublikasikan toolbox perencanaan jalur yang ditulis dalam C .
Tetapi algoritma perencanaan jalur yang tersedia pada toolbox Vahrenkamp sebagian besar hanya didasarkan pada algoritma RRT.
Corke mempublikasikan toolbox robotic yang ditulis dalam bahasa pemrograman MATLAB .
Beberapa algoritma perencanaan jalur yang dapat dibuat menggunakan toolbox robotik Corke adalah A*.
D*.
PRM, dan RRT.
Variasi dari algoritma RRT .
eperti RRT*.
Informed RRT*, maupun RRT-ACS) tidak terdapat pada toolbox robotik Corke.
Padahal, salah satu algoritma yang paling banyak digunakan untuk perencanaan jalur adalah algoritma RRT* .
Nugraha telah membuat simulator edukatif untuk pembelajaran algoritma RRT menggunakan LabVIEW .
Kumar dan Goswami .
melaporkan bahwa LabVIEW memiliki waktu komputasi yang cepat.
Waktu komputasi toolbox RRT yang dibuat Nugraha juga telah diminimalkan dengan mengurangi overhead program subVI .
Tetapi, algoritma perencanaan jalur yang dapat dibuat menggunakan toolbox Nugraha hanya algoritma RRT dan RRT* saja.
Berdasarkan studi state of art diatas, terdapat beberapa kekurangan dalam mengembangkan algoritma library path planning.
Beberapa kekurangan ini diantaranya toolbox dengan waktu komputasi yang lambat, tidak ada alat untuk membantu analisis, skenario pengujian yang tidak fleksibel .
anya dapat melibatkan rintangan berbentuk lingkaran atau perseg.
, dan kurangnya variasi dari algoritma RRT* yang ada.
Sedangkan, algoritma RRT* tergolong algoritma perencanaan jalur yang paling populer saat ini .
Penelitian dan makalah ini bertujuan untuk mengembangkan library algoritma perencanaan jalur untuk sistem Library algoritma perencanaan jalur ini Laboratory Virtual Instrumentation Engineering Workbench (LabVIEW).
Dengan menggunakan library ini.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
dapat dibuat algoritma perencanaan jalur seperti RRT.
RRT*.
RRT*-Connect.
Informed RRT*.
Informed RRT*-Connect.
PRM.
A*.
Dijkstra.
Particle Swarm Optimization PSO, dan RRT-ACS.
Keunggulan dari library ini antara lain adalah kemampuan untuk memvisualisasikan setiap subproses, waktu komputasi yang cepat, tersedianya alat untuk membantu analisis, kemampuan untuk membuat skenario pengujian yang fleksibel, dan kemampuan untuk dengan mudah mengubah parameter algoritma untuk melihat bagaimana pengaruhnya terhadap kinerja keluaran algoritma.
Kinerja library ini diukur dengan membandingkan implementasinya dalam skenario benchmark dari publikasi peneliti lain.
Hasil pengujian menggunakan beberapa kasus benchmark menunjukkan bahwa library yang diusulkan memiliki komputasi yang lebih cepat daripada library pembanding.
Simulator Robotika LabVIEW digunakan untuk menguji implementasi library pada sistem robotik.
Kami juga menunjukkan beberapa perkembangan yang dapat dilakukan dengan library ini.
Diharapkan dengan menggunakan library ini, mahasiswa akan lebih mengembangkan algoritma perencanaan jalur untuk sistem robotik.
RandomSample, dilakukan pengambilan sampel acak, yang dinamakan ycycycaycuycc .
Setelah diperoleh nilai ycycycaycuycc , proses selanjutnya adalah mencari node-node pada ycN yang berjarak kurang dari suatu nilai threshold ke ycycycaycuycc .
Node-node tersebut dinamakan sebagai ycEyeayeIyeCyee .
Lalu dipilih node pada ycEyeayeIyeCyee yang berjarak terdekat dengan ycycycaycuycc .
Node dengan jarak terdekat tersebut dinamakan sebagai ycycuyceycaycyceycyc .
Selanjutnya akan dibuat suatu cabang baru dari node ycycuyceycaycyceycyc yang menuju ke ycycycaycuycc dengan jarak OIyc dari ycycuyceycaycyceycyc .
Node baru tersebut dinamakan sebagai ycycuyceyc .
Selanjutnya akan dilakukan pemeriksaan apakah ada hambatan diantara ycycuyceycaycyceycyc dengan ycycuyceyc .
Jika diantara ycycuyceycaycyceycyc dengan ycycuyceyc tidak terdapat hambatan, maka node ycycuyceyc akan dimasukkan ke ycN .
Selanjutnya akan diperiksa apakah ada node pada ycN saat ini yang berjarak cukup dekat dengan node tujuan atau ycyciycuycayco .
Jika terdapat node yang berjarak cukup dekat dengan node tujuan, maka akan dibangun rute ycU ycayc , yaitu rute yang menghubungkan node awal dengan node tujuan .
Proses ini akan berulang sehingga dipenuhi kondisi berhenti.
Proses looping dapat memiliki beberapa syarat yang bervariasi untuk berhenti, misalnya jika node tujuan sudah tercapai atau jika jumlah iterasi maksimal sudah terpenuhi.
II.
METODE
Algoritma perencanaan jalur yang dapat dibuat menggunakan library ini adalah berbagai variasi algoritma RRT, yaitu RRT*.
RRT*-Connect.
Informed RRT*.
Informed RRT*-Connect, dan RRT-ACS.
Karena algoritma RRT* dan variannya merupakan algoritma perencanaan jalur yang paling banyak digunakan saat ini .
, maka penjelasan tentang algoritma perencanaan jalur pada Bab II dibatasi pada algoritma RRT dan Library ini masih berisi algoritma PRM.
A*.
Dijkstra, dan PSO, namun penjelasannya tidak disertakan dalam tulisan ini.
Pembaca dapat merujuk ke referensi yang terkait langsung dengan algoritma tersebut sebagaimana yang dijelaskan dalam Bab I.
Algoritma
RRT
menggunakan library ini ditunjukkan pada Gambar 1.
Pertama-tama dilakukan inisialisasi pohon pencarian yang disimbolkan sebagai ycN.
Lalu pada ycN ditambahkan posisi node awal, yaitu ycycnycuycnyc .
Hal ini akan membuat proses pencarian jalur akan berawal dari posisi ycycnycuycnyc .
Selanjutnya algoritma akan melakukan looping untuk mengembangkan pohon pencarian ycN.
Pada proses looping, fungsi pertama yang dilakukan adalah RandomSample.
Pada proses Algoritma 1: ycU ycayc IaRRT.
cycnycuycnyc , ycyciycuycayco , ycoycayc.
% ========== Initialization ycN Ia yaycuycnycycnycaycoycnycyceycNycyceyce() ycN Ia yaycuycyceycycycAycuyccyce(OI, ycycnycuycnyc , ycN) while ycyceycycoycnycuycaycycnycuycu ycaycuycuyccycnycycnycuycu ycuycuyc ycoyceyc do ycycycaycuycc Ia ycIycaycuyccycuycoycIycaycoycyycoyce.
ycEyeayeIyeCyee Ia ycAyceycaycycAycuyccyceyc.
cN, ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycaycuyc.
cycycaycuycc , ycEycuyceycayc , ycN) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycN Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycN) end if if yaycaycuyaycuycuycuyceycaycyceycc.
cyciycuycayco , ycN) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cN, ycyciycuycayco ) end if 15: end while Gambar 1.
Algoritma RRT.
Nomor baris akan digunakan untuk menjelaskan library LabVIEW yang dibuat.
Algoritma
RRT*
diperlihatkan pada Gambar 2.
Algoritma RRT* merupakan algoritma RRT dengan penambahan proses choose parent .
aris 10-.
dan rewire .
Pada proses choose parent, pertama-tama akan dipilih node-node pada ycN yang berjarak kurang dari suatu nilai threshold ke ycycycaycuycc .
Node-node tersebut dinamakan sebagai ycEyeayeIyeCyee TELEKONTRAN.
VOL.
NO.
APRIL 2022
Lalu pada node-node di ycEyeayeIyeCyee akan dicari node yang jika terhubung dengan ycycuyceyc akan berakibat jalur diantara node awal dan ycycuyceyc akan menjadi lebih pendek.
Node tersebut dinamakan sebagai ycycoycnycu .
, dan akan dijadikan node parent dari ycycuyceyc .
Adapun untuk proses Rewire, akan dilakukan pencarian node-node pada ycEyeayeIyeCyee yang jika node tersebut dihubungkan ke ycycuyceyc , maka akan diperoleh jalur yang lebih dekat dari node awal ke node tersebut.
Maka node ycycuyceyc akan dijadikan sebagai parent baru dari node tersebut.
melingkupi node tujuan dan node awal.
Luas area elipsoid akan dipengaruhi oleh nilai ycaycayceycyc .
Maka proses sampling nilai ycycycaycuycc hanya dilakukan pada area elipsoide tersebut saja .
Adapun Gambar 5 menunjukkan algoritma Informed RRT*-Connect.
Algoritma Informed RRT*-Connect adalah versi dua pohon pencarian dari Informed RRT*.
Proses InformedSample dan CalculateShortestPathLength pada Gambar 5 adalah sama dengan proses pada Gambar 4 yang telah dijelaskan sebelumnya.
Adapun proses PruneTree adalah proses penghilangan cabangcabang pada ycN yang berada diluar area elipsoid pada proses informed sampling.
Proses PruneTree akan meningkatkan algoritma dikarenakan node-node yang perlu diperiksa pada ycN akan dibatasi hanya pada area ellipsoid yang akan semakin mengecil .
, .
Algoritma 2: ycU ycayc IaRRT*.
cycnycuycnyc , ycyciycuycayco , ycoycayc.
% ========== Initialization ycN Ia yaycuycnycycnycaycoycnycyceycNycyceyce() ycN Ia yaycuycyceycycycAycuyccyce(OI, ycycnycuycnyc , ycN) while ycyceycycoycnycuycaycycnycuycu ycaycuycuyccycnycycnycuycu ycuycuyc ycoyceyc do ycycycaycuycc Ia ycIycaycuyccycuycoycIycaycoycyycoyce.
ycEyeayeIyeCyee Ia ycAyceycaycycAycuyccyceyc.
cN, ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycaycuyc.
cycycaycuycc , ycEycuyceycayc , ycN) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycEyeayeIyeCyee Ia ycAyceycayc.
cN, ycycuyceyc ) ycycoycnycu Ia yaEaycuycuycyceycEycaycyceycuyc.
cycuyceyc , ycEycuyceycayc , ycycuyceycaycyceycyc ) ycN Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycN) ycN Ia ycIyceycycnycyce.
cN, ycEycuyceycayc , ycycoycnycu ) end if if yaycaycuyaycuycuycuyceycaycyceycc.
cyciycuycayco , ycN) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cN, ycyciycuycayco ) end if end while Gambar 2.
Algoritma RRT*.
Nomor baris akan digunakan untuk menjelaskan library LabVIEW yang dibuat.
Algoritma perencanaan jalur RRT*-Connect diperlihatkan pada Gambar 3.
Algoritma ini adalah algoritma RRT* dengan dua pohon Berbeda dengan algoritma RRT dan RRT* yang hanya memiliki satu pohon pencarian yaitu ycN , maka pada algoritma RRT*-Connect memiliki dua pohon pencarian yaitu ycNya dan ycNyaA .
Pada Gambar 3 dapat terlihat bahwa proses dari algoritma RRT*-Connect ini mirip dengan proses pada algoritma RRT* yang ditunjukkan pada Gambar 2, kecuali terdapat dua pohon pencarian yang digunakan yaitu ycNya dan ycNyaA .
Algoritma Informed RRT* ditunjukkan pada Gambar 4.
Setelah memperoleh solusi pertama, algoritma ini melakukan pengampilan sample berdasarkan informasi pada area berbentuk elips yang dibentuk diantara node awal dan node akhir.
Proses informed sampling ini pertama-tama dilakukan dengan menghitung jarak terbaik antara node awal dengan node tujuan saat ini .
, yaitu disebut ycaycayceycyc .
Kemudian berdasarkan nilai ycaycayceycyc tersebut, akan dibuat suatu area elipsoid yang Algoritma 3: ycU ycayc IaRRT*-Connect.
cycnycuycnyc , ycyciycuycayco , ycoycayc.
% ========== Initialization ycNya Ia yaycuycnycycnycaycoycnycyceycNycyceyce() ycNyaA Ia yaycuycnycycnycaycoycnycyceycNycyceyce() ycNya Ia yaycuycyceycycycAycuyccyce(OI, ycycnycuycnyc , ycNya ) ycNyaA Ia yaycuycyceycycycAycuyccyce(OI, ycyciycuycayco , ycNyaA ) while ycyceycycoycnycuycaycycnycuycu ycaycuycuyccycnycycnycuycu ycuycuyc ycoyceyc do ycycycaycuycc Ia ycIycaycuyccycuycoycIycaycoycyycoyce.
ycEyeayeIyeCyee Ia ycAyceycayc.
cNya , ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycayc.
cycycaycuycc , ycEycuyceycayc , ycNya ) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycEyeayeIyeCyee Ia ycAyceycayc.
cNya , ycycuyceyc ) ycycoycnycu Ia yaEaycuycuycycEycycuyc.
cycuyceyc , ycEycuyceycayc , ycycuyceycaycyceycyc ) ycNya Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycNya ) ycNya Ia ycIyceycycnycyce.
cN, ycEycuyceycayc , ycycoycnycu ) if yaycaycuyaycuycuycuyceycaycyceycc.
cycuyceyc , ycNyaA ) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cNya , ycNyaA ) end if end if ycEyeayeIyeCyee Ia ycAyceycayc.
cNya , ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycayc.
cycycaycuycc , ycEycuyceycayc , ycNya ) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycEyeayeIyeCyee Ia ycAyceycayc.
cNyaA , ycycuyceyc ) ycycoycnycu Ia yaEaycuycuycycEycycuyc.
cycuyceyc , ycEycuyceycayc , ycycuyceycaycyceycyc ) ycNyaA Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycNyaA ) ycNyaA Ia ycIyceycycnycyce.
cN, ycEycuyceycayc , ycycoycnycu ) if yaycaycuyaycuycuycuyceycaycyceycc.
cycuyceyc , ycNya ) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cNya , ycNyaA ) end if end if 32: end while Gambar 3.
Algoritma RRT*-Connect.
Nomor baris akan digunakan untuk menjelaskan library LabVIEW yang dibuat.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Algorithm 4 : ycU ycayc IaInformed RRT*.
cycnycuycnyc , ycyciycuycayco , ycoycayc.
1: % ========== Initialization 2: ycN Ia yaycuycnycycnycaycoycnycyceycNycyceyce() 3: ycN Ia yaycuycyceycycycAycuyccyce(OI, ycycnycuycnyc , ycN) 4: while ycyceycycoycnycuycaycycnycuycu ycaycuycuyccycnycycnycuycu ycuycuyc ycoyceyc do ycaycayceycyc Ia yaycaycoycaycycoycaycyceycIEaycuycycyceycycycEycaycEayayceycuyciycEa.
cU ycayc ) ycycycaycuycc Ia yaycuyceycuycycoyceyccycIycaycoycyycoyce.
ycEyeayeIyeCyee Ia ycAyceycaycycAycuyccyceyc.
cN, ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycaycuyc.
cycycaycuycc , ycEycuyceycayc , ycN) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycEyeayeIyeCyee Ia ycAyceycayc.
cN, ycycuyceyc ) ycycoycnycu Ia yaEaycuycuycyceycEycycuyc.
cycuyceyc , ycEycuyceycayc , ycycuyceycaycyceycyc ) ycN Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycN) ycN Ia ycIyceycycnycyce.
cN, ycEycuyceycayc , ycycoycnycu ) end if if yaycaycuyaycuycuycuyceycaycyceycc.
cyciycuycayco , ycN) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cN, ycyciycuycayco ) ycyeeyenyeayeIycyeeyeIyeI.
cN) end if 20: end while Meskipun algoritma RRT* pada Gambar 2 mirip dengan yang dibahas oleh Karaman pada .
, perubahan telah dilakukan untuk memungkinkan setiap algoritma yang dibahas dalam bagian metode ini dapat dibandingkan dengan mudah.
Demikian pula, algoritma RRT*Connect pada Gambar 3, algoritma Informed RRT*-Connect pada Gambar 4, dan algoritma Informed RRT*-Connect pada Gambar 5 telah dimodifikasi dibandingkan dengan algoritma terkait yang dibahas oleh Klem .
Gammel .
,] dan Mashayekhi .
Nomor baris pada Gambar 1 - Gambar 5 akan digunakan untuk menjelaskan library LabVIEW yang dibuat pada Bab i.
Adapun algoritma RRT-ACS dapat dilihat pada paper Pohan .
Nomor barus yang digunakan pada algoritma RRT-ACS di paper Pohan akan digunakan untuk menjelaskan library LabVIEW yang dibuat pada Bab i.
Gambar 4.
Algoritma Informed RRT*.
Nomor baris akan digunakan untuk menjelaskan library LabVIEW yang dibuat.
Algoritma 5: ycU ycayc Ia Informed RRT*Connect.
cycnycuycnyc , ycyciycuycayco , ycoycayc.
1: % ========== Initialization 2: ycNya Ia yaycuycnycycnycaycoycnycyceycNycyceyce() 3: ycNyaA Ia yaycuycnycycnycaycoycnycyceycNycyceyce() 4: ycNya Ia yaycuycyceycycycAycuyccyce(OI, ycycnycuycnyc , ycNya ) 5: ycNyaA Ia yaycuycyceycycycAycuyccyce(OI, ycyciycuycayco , ycNyaA ) 6: while ycyceycycoycnycuycaycycnycuycu ycaycuycuyccycnycycnycuycu ycuycuyc ycoyceyc do ycaycayceycyc Ia yaycaycoycaycycoycaycyceycIEaycuycycyceycycycEycaycEayayceycuyciycEa.
cU ycayc ) ycycycaycuycc Ia yaycuyceycuycycoyceyccycIycaycoycyycoyce.
ycEyeayeIyeCyee Ia ycAyceycayc.
cNya , ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycayc.
cycycaycuycc , ycEycuyceycayc , ycNya ) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycEyeayeIyeCyee Ia ycAyceycayc.
cNya , ycycuyceyc ) ycycoycnycu Ia yaEaycuycuycycEycycuyc.
cycuyceyc , ycEycuyceycayc , ycycuyceycaycyceycyc ) ycNya Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycNya ) ycNya Ia ycIyceycycnycyce.
cN, ycEycuyceycayc , ycycoycnycu ) if yaycaycuyaycuycuycuyceycaycyceycc.
cycuyceyc , ycNyaA ) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cNya , ycNyaA ) ycyeeyenyeayeIycyeeyeIyeI.
cN) end if end if ycEyeayeIyeCyee Ia ycAyceycayc.
cNya , ycycycaycuycc ) ycycuyceycaycyceycyc Ia ycAyceycaycyceycycycAyceycnyciEaycayc.
cycycaycuycc , ycEycuyceycayc , ycNya ) ycycuyceyc Ia ycIycyceyceyc .
cycuyceycaycyceycyc , ycycycaycuycc .
OIy.
if ycCycaycycycaycaycoyceyceycyceyce.
cycuyceycaycyceycyc , ycycuyceyc ) then ycEyeayeIyeCyee Ia ycAyceycayc.
cNyaA , ycycuyceyc ) ycycoycnycu Ia yaEaycuycuycycEycycuyc.
cycuyceyc , ycEycuyceycayc , ycycuyceycaycyceycyc ) ycNyaA Ia yaycuycyceycycycAycuyccyce.
cycoycnycu, ycycuyceyc , ycNyaA ) ycNyaA Ia ycIyceycycnycyce.
cN, ycEycuyceycayc , ycycoycnycu ) if yaycaycuyaycuycuycuyceycaycyceycc.
cycuyceyc , ycNya ) then ycU ycayc Ia ycOycyyccycaycyceyaAyceycycycEycaycEa.
cNya , ycNyaA ) ycyeeyenyeayeIycyeeyeIyeI.
cN) end if end if 35: end while Gambar 5.
Algoritma Informed RRT*-Connect.
Nomor baris akan digunakan untuk menjelaskan library LabVIEW yang dibuat.
HASIL DAN DISKUSI
LabVIEW library untuk perencanaan jalur ini memiliki beberapa keunggulan, yaitu dapat memvisualisasikan setiap subproses, waktu komputasi yang cepat, tersedia tools untuk analisis, skenario pengujian dapat dibuat secara fleksibel, serta parameter algoritma dapat dengan mudah diubah untuk melihat bagaimana pengaruhnya terhadap kinerja keluaran algoritma.
Maka pembahasan selanjutnya adalah mengenai contoh pembuatan algoritma perencanaan jalur yang dijelaskan pada Bab II, serta mendemonstrasikan keunggulan dari Library ini.
Block Diagram LabVIEW Block diagram LabVIEW dari algoritma RRT yang dibuat dengan library ini ditunjukkan pada Gambar 6.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan pada Algoritma 1 Gambar 1.
Pada Gambar 6, terdapat beberapa sub-program yang digunakan pada library ini, yaitu:
AuData Initialization.
viAy .
omor 2, .
AuSampling.
viAy .
AuNearest List Index.
viAy .
AuSteer.
viAy .
omor 7, .
AuCheck Collision.
viAy .
AuInsert.
viAy .
omor 10, .
AuCheck Goal.
viAy .
AuMake Final Path.
viAy .
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Gambar 6.
Block diagram algoritma RRT yang dibuat dengan library ini.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan pada Algoritma 1 Gambar 1.
Gambar 7.
Block diagram algoritma RRT* yang dibuat dengan library ini.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan pada Algoritma 2 Gambar 2.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Gambar 8.
Sebagian block diagram algoritma RRT*-Connect yang dibuat dengan library ini.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan pada Algoritma 3 Gambar 3.
Gambar 9.
Block diagram algoritma Informed RRT* yang dibuat dengan library ini.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan pada Algoritma 4 Gambar 4.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Gambar 10.
Sebagian block diagram algoritma Informed RRT*-Connect yang dibuat dengan library ini.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan pada Algoritma 5 Gambar 5.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Gambar 11.
Sebagian block diagram algoritma RRT-ACS yang dibuat dengan library ini.
Nomor dalam kotak kuning menunjukkan proses yang dijelaskan makalah Pohan .
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Subprogram AuData Initialization.
viAy berfungsi untuk mengolah data environment yang akan di terapkan pada algoritma RRT.
Proses ini meniru algoritma RRT pada Gambar 1 baris 2 dan 3.
Subprogram AuSampling.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 baris 5.
Subprogram AuNearest List Index.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 Subprogram AuSteer.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 baris 7, 8.
Subprogram AuCheck Collision.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 baris 9.
Subprogram AuCheck Collision.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 baris 9.
Subprogram AuInsert.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 baris 10, 11.
Subprogram AuCheck Goal.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 baris 13.
Subprogram AuMake Final Path.
viAy melakukan perintah pada algoritma RRT pada Gambar 1 Adapun Gambar 7 menunjukkan Block diagram LabVIEW dari algoritma RRT* yang dibuat dengan library ini.
Gambar 8 menunjukkan Block diagram LabVIEW dari algoritma RRT*-Connect yang dibuat dengan library ini.
Gambar 9 menunjukkan Block diagram LabVIEW dari algoritma Informed RRT* yang dibuat dengan library ini.
Gambar 10 menunjukkan Block diagram LabVIEW dari algoritma Informed RRT*-Connect yang dibuat dengan library ini.
Sedangkan Gambar 11 menunjukkan Block diagram LabVIEW dari algoritma RRT-ACS yang dibuat dengan library Setiap nomor dengan kotak kuning pada Gambar 7 - 11, melakukan perintah pada algoritma bersangkutan pada Gambar 2 Ae 5.
Gambar 12.
Skenario lingkungan yang untuk pengujian algoritma RRT*, seperti yang diusulkan Karaman .
Saat program dijalankan, dapat diperoleh visualisasi pohon pencarian seperti Gambar 13.
Visualisasi ini memperlihatkan posisi node acak pada setiap iterasinya.
Posisi node acak ditunjukkan oleh kotak merah muda.
Cabang baru dari pohon pencarian akan menuju ke arah node Lingkaran berwarna merah adalah node Lingkaran berwarna biru adalah node Visualisasi Proses Perencanaan Jalur Salah satu keunggulan dari LabVIEW library memvisualisasikan setiap subproses.
Berikut ini adalah contoh visualisasi proses perencanaan jalur algoritma RRT* menggunakan skenario kasus yang diusulkan Karaman .
Gambar 12 Gambar 13.
Contoh Visualisasi dari pohon pencarian RRT*.
Cabang baru dari pohon pencarian menuju node acak berwarna pink Jika node baru dari pohon pencarian berada yang berdekatan dengan node tujuan, maka akan dibangun jalur lengkap yang menghubungkan node awal dan node tujuan.
Contoh dari suatu jalur lengkap ditunjukkan pada Gambar 14.
Selama iterasi berlangsung, algoritma RRT* dapat membangun jalur baru yang dapat menghubungkan node awal dan node akhir dengan TELEKONTRAN.
VOL.
NO.
APRIL 2022
jarak lebih pendek.
Jalur baru tersebut kemudian akan ditampilkan.
Gambar 16.
Visualisasi jalur lengkap yang diperoleh algoritma RRT*-Connect Gambar 14.
Garis berwarna merah tebal adalah contoh jalur lengkap dari node awal ke node tujuan.
Gambar 15 menyajikan hasil algoritma RRT* setelah iterasi ke-9721.
Gambar 14 dan Gambar 15 menunjukkan bahwa algoritma RRT* memiliki sifat optimal asimtotik.
Sifat ini berarti algoritma RRT* memiliki jaminan dapat menghasilkan solusi yang optimal jika dan hanya jika diberikan waktu yang cukup.
Karaman juga melaporkan sifat asimptotik optimal dari algoritma RRT* .
Gambar 17 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma Informed RRT*.
Pada Gambar 17 terlihat bahwa area pencarian difokuskan pada area ellipsoid yang ukurannya sebanding dengan rute terbaik saat ini.
Gambar 17.
Visualisasi contoh jalur lengkap dari algoritma RRT*Connect Gambar 15.
Contoh jalur lengkap dari algoritma RRT* setelah melakukan iterasi sebanyak 9721.
Sebagai contoh visualisasi dari algoritmaalgoritma lainnya yang ada di library ini, maka pada Gambar 16 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma RRT*Connect.
Garis biru pada Gambar 16 adalah pohon pencarian pertama, sedangkan garis hijau adalah pohon pencarian kedua.
Kedua pohon pencarian akan berusaha untuk saling terhubung.
Gambar 18 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma Informed RRT*-Connect.
Seperti pada algoritma RRT*-Connect.
Garis biru pada Gambar 18 adalah pohon pencarian pertama, sedangkan garis hijau adalah pohon pencarian kedua.
Kedua pohon pencarian akan berusaha untuk saling terhubung.
Dan seperti pada algoritma Informed RRT*.
Pada Gambar 18 terlihat bahwa area pencarian difokuskan pada area ellipsoid yang ukurannya sebanding dengan rute terbaik saat ini.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Gambar 18.
Visualisasi contoh jalur lengkap dari algoritma Informed RRT*-Connect Gambar 19 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma RRTACS.
Gambar 20 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma PRM.
Seperti yang ditunjukkan pada Gambar 20, algoritma PRM pertama-tama membangkitkan sample point .
otak merah mud.
Lalu algoritma PRM menggunakan Dijkstra untuk mencari rute terbaik yang menghubungkan node awal dengan tujuan melalui sample point tersebut.
Gambar 20.
Visualisasi contoh jalur lengkap dari algoritma PRM Gambar 21 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma A*.
Gambar 22 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma Dijkstra.
Kotak-kotak pada Gambar 21 dan Gambar 22 adalah hasil diskritisasi ruang pencarian, karena algoritma A* dan Dijkstra memerlukan proses diskritisasi ini.
Lingkaran hijau menunjukkan node-node yang telah diperiksa oleh algoritma A* dan Dijkstra.
Garis biru tebal adalah jalur terbaik yang dihasilkan oleh kedua algoritma tersebut.
Adapun Gambar 23 menunjukkan visualisasi proses dan hasil perencanaan jalur dari algoritma perencanaan jalur berbasis PSO.
Lingkaran biru yang ada pada Gambar 23 adalah partikelpartikel PSO yang bergerak sesuai peramaan umum PSO.
Gambar 19.
Visualisasi contoh jalur lengkap dari algoritma RRTACS Gambar 21.
Visualisasi contoh jalur lengkap dari algoritma algoritma A* TELEKONTRAN.
VOL.
NO.
APRIL 2022
Table I.
Perbandingan waktu komputasi beberapa library perencanaan jalur Gambar 22.
Visualisasi contoh jalur lengkap dari algoritma Dijkstra Bahasa Versi/ Compiler Python Matlab LabVIEW Pembuat .
Penulis Rata-rata Waktu Satu Iterasi Tabel I menunjukkan keunggulan dari LabVIEW library yang diusulkan ini dalam hal waktu komputasi.
Waktu komputasi dari LabVIEW library dapat diminimalkan dengan cara menjadikan semua subVI pada library ini sebagai subroutine .
Dengan menjadikan semua subVI sebagai subroutine, maka overhead subVI dapat diminimalkan.
Library ini juga hanya fungsi-fungsi .
ubVI) bawaan LabVIEW yang dapat diubah menjadi subroutine.
Perbandingan waktu komputasi jika suatu subVI dijadikan subroutine dan jika tidak dijadikan subroutine ditunjukkan pada Tabel II.
Table II.
Perbandingan waktu komputasi jika suatu subVI dijadikan subroutine dan jika tidak dijadikan subroutine Kondisi subVI subVI dijadikan sebagai subroutine subVI tidak dijadikan sebagai Waktu rata-rata algoritma untuk melakukan 20,000 iterasi 66,4 milidetik 95,8 milidetik Tools Untuk Analisis Gambar 23.
Visualisasi jalur lengkap yang diperoleh algoritma perencanaan jalur berbasis PSO Analisa Waktu Komputasi Untuk mendemonstrasikan keunggulan waktu komputasi dari library yang diusulkan, kami membandingkan waktu yang komputasi dari library ini dengan PythonRobotics yang dibuat oleh Sakai menggunakan python .
dan program RRT* yang dibuat oleh Vemprala menggunakan matlab .
Pengujian dilakukan menggunakan RRT*, tersebutlah yang ada pada setiap library yang akan Lamanya waktu yang dibutuhkan oleh algoritma RRT* untuk menyelesaikan satu iterasi Pengujian dilakukan sebanyak 50 kali untuk setiap library.
Tabel I menunjukkan hasil perbandingan ini.
LabVIEW library untuk perencanaan jalur ini, dibuat untuk membantu penelitian perencanaan Karena itu, library ini dilengkapi dengan berbagai tools yang dapat digunakan untuk menganalisis kinerja algoritma perencanaan jalur.
Menggunakan library ini, setiap pertumbuhan pohon pencarian dan jalur terbaik yang dihasilkan dapat disimpan otomatis selama iterasi.
Data-data dari proses perencanaan jalur juga dapat tersimpan dalam format file excel.
Data iterasi, jalur terbaik, dan waktu untuk mencapai iterasi semuanya disimpan dalam file excel tersebut.
Library ini juga dilengkapi tools untuk membuat grafik dari data performansi suatu perencanaan jalur, seperti yang ditunjukkan pada Gambar 24.
Gambar 24 menunjukkan grafik kecepatan konvergensi suatu algoritma untuk mencapai nilai optimal.
TELEKONTRAN.
VOL.
NO.
APRIL 2022
Gambar 24.
Tools untuk analisis i: performansi dari suatu algoritma dapat divisualisasikan dalam bentuk grafik kecepatan Peta Skenario Pengujian Salah satu kekurangan dari PythonRobotics yang dibuat oleh Sakai .
adalah hanya bisa diaplikasikan pada lingkungan dengan obstacle berbentuk lingkaran saja.
LabVIEW library ini dapat diaplikasikan pada lingkungan dengan berbagai bentuk obstacle.
Bahkan library ini dapat diaplikasikan pada lingkungan dengan obstacle berbentuk kurva, seperti yang ditunjukkan pada Gambar 25.
Parameter Algoritma Pada library ini, pengubahan parameterparameter dari suatu algoritma dapat dilakukan dengan mudah.
Dengan mengubah-ubah parameter ini, maka dapat diamati bagaimana pengaruhnya terhadap performansi dari algoritma perencanaan jalur tersebut.
Contoh front panel yang disediakan untuk mengubah parameter algoritma RRT* ditunjukkan pada Gambar 26.
Gambar 26.
Contoh front panel LabVIEW yang disediakan untuk mengubah parameter dari algoritma RRT*.
Contoh Implementasi pada LabVIEW Robotics Simulator.
LabVIEW library untuk perencanaan jalur ini telah diuji pada LabVIEW Robotic Simulator seperti terlihat pada Gambar 27.
Pertama-tama, robot memindai rintangan untuk membuat peta Berdasarkan peta lingkungan tersebut, lalu algoritma perencanaan jalur Robot kemudian digerakkan untuk mengikuti jalur yang telah dibuat.
Gambar 27.
Contoh implementasi pada LabVIEW Robotic Simulator Beberapa Pengembangan yang Dapat Dilakukan Gambar 25.
Algoritma perencanaan jalur yang dibuat menggunakan library ini, bahkan dapat diimplementasikan pada lingkungan dengan obstacle berbentuk kurva Dengan menggunakan LabVIEW library untuk perencanaan jalur diharapkan dapat membantu pengguna dalam mengembangkan algoritma perencanaan jalur.
Terdapat beberapa topik pengembangan perencanaan jalur yang potensial untuk dikembangkan menggunakan library ini.
Yang pertama adalah pengembangan proses sampling dari algoritma RRT.
Veras dkk.
dalam makalah mereka, telah membahas tinjauan literatur tentang metode pengambilan sampel dalam algoritma RRT.
Pembaca dapat TELEKONTRAN.
VOL.
NO.
APRIL 2022
mengembangkan metode pengambilan sampel algoritma RRT.
Sopa dkk.
serta Pakaya dan Pohan .
, dalam makalah mereka, telah mengembangkan metode pengambilan sampel dari algoritma RRT* menggunakan library ini.
Yang kedua adalah melakukan hibridisasi algoritma RRT dengan algoritma lainnya.
Hibridisasi adalah menggabungkan dua algoritma berbeda untuk membuat algoritma baru yang dapat mencapai hasil yang lebih baik .
Pohan .
, dalam papernya telah melakukan hibridisasi algoritma RRT dengan ACS, dan menamakannya sebagai RRT-ACS.
Pohan melaporkan bahwa performansi RRT-ACS lebih unggul daripada algoritma RRT maupun RRT*.
IV.
KESIMPULAN
Dari penelitian ini telah dipresentasikan library LabVIEW.
Menggunakan library ini, dapat dibuat beberapa algoritma perencanaan jalur algoritma RRT.
RRT*.
RRT*-Connect.
Informed RRT*.
Informed RRT*-Connect.
RRT-ACS.
PRM.
A*.
Dijkstra, dan PSO.
Telah ditunjukkan beberapa keunggulan dari library ini, yaitu: dapat memvisualisasikan setiap subproses, waktu komputasi yang cepat, tersedia tools untuk analisis, skenario pengujian dapat dibuat secara fleksibel, serta parameter algoritma dapat dengan mudah diubah untuk melihat bagaimana pengaruhnya terhadap kinerja keluaran algoritma.
Paper ini juga membahas beberapa pengembangan potensial dari algoritma RRT yang dapat dilakukan menggunakan library Dengan menggunakan library ini, diharapkan mahasiswa dapat memperoleh pemahaman yang lebih baik mengenai algoritma perencanaan jalur serta membantu dalam melakukan penelitian terkait algoritma perencanaan jalur.
DAFTAR PUSTAKA