TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
DOI : 10.
34010/telekontran.
TELEKONTRAN,
VOL.
NO.
OKTOBER 2021
p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 Algoritma Informed-RRT* Menggunakan Hybrid Sampling Untuk Menemukan Solusi akhir jalur yang Cepat Informed-RRT* Using Hybrid Sampling to Finding Fast Final Path Solution Miftah Fauzi*.
Muhammad Aria Rajasa Pohan Program Studi Teknik Elektro.
Fakultas Teknik dan Ilmu Komputer Universitas Komputer Indonesia Jl.
Dipati ukur No 112.
Bandung Email : miftahfauzi39@mahasiswa.
Abstrak Ae Informed Rapidly-exploring Random Tree* (Informed-RRT*) merupakan hasil pengembangan dari algoritma Rapidly-exploring Random Tree (RRT) yang dapat menghasilkan solusi jalur yang bersifat asimptotik optimal tetapi waktu komputasi yang dibutuhkan menjadi lebih lama.
Pada awalnya algoritma Informed-RRT* masih menggunakan metode random sampling yang mana metode ini akan mengambil sampel acak pada ruang pencarian.
Pengambilan sampel acak inilah yang akan membuat waktu komputasi menjadi tidak optimal.
Penelitian ini bertujuan untuk merancang algoritma Informed-RRT* menggunakan metode hybrid sampling.
Metode hybrid sampling merupakan integrasi dari beberapa metode pengambilan sampel.
Pada pengujian ini, performansi metode random sampling akan dibandingkan dengan perfomansi metode hybrid sampling dalam hal waktu komputasi.
Pengujian metode hybrid sampling pada algoritma InformedRRT* ini berbasis simulasi dan dilakukan pada lingkungan narrow, clutter, trap.
Hasil yang didapatkan dari pengujian ini adalah penggunaan metode hybrid sampling pada algoritma Informed-RRT* mampu menghasilkan performansi waktu rata- rata komputasi yang lebih cepat 26,4 detik bila dibandingkan dengan metode random sampling pada lingkungan clutter.
Pada lingkungan narrow metode hybrid sampling menghasilkan waktu komputasi 24,52 detik lebih cepat bila dibandingkan dengan metode random sampling.
Pada lingkungan trap metode hybrid sampling menghasilkan waktu komputasi 5,25 detik lebih cepat dibandingkan dengan metode random sampling.
Dari data hasil pengujian, metode hybrid sampling ini dapat menjadi metode pangambilan sampel alternatif untuk digunakan pada algoritma Informed-RRT* Kata kunci : Boundary sampling, goal biaing sampling, hybrid sampling.
Informed-RRT*, random sampling Abstract - Informed Rapidly-exploring Random Tree* (Informed-RRT*) is the result of the development of the RRT algorithm which can produce an optimal asymptotic path solution but the computation time required is Initially, the Informed-RRT* algorithm was still using the random sampling method, where this method will take a random sample in the search space.
This random sampling will make the computation time not This study aims to design the Informed-RRT* algorithm using a hybrid sampling method.
The hybrid sampling method is an integration of several sampling methods.
In this test, the performance of the random sampling method will be compared with the performance of the hybrid sampling method in terms of computation time.
The test of the hybrid sampling method on the Informed-RRT* algorithm is based on simulation and is carried out in a narrow, clutter, trap environment.
The results obtained from this test are that the use of the hybrid sampling method on the Informed-RRT* algorithm is able to produce a faster average computation time performance of 26.
4 seconds when compared to the random sampling method in a cluttered In a narrow environment, the hybrid sampling method produces a computation time of 24.
seconds faster than the random sampling method.
In the trap environment, the hybrid sampling method produces a computation time of 5.
25 seconds faster than the random sampling method.
From the test data, this hybrid sampling method can be an alternative sampling method to be used in the Informed-RRT* algorithm.
Keywords : : Boundary sampling, goal biaing sampling, hybrid sampling.
Informed-RRT*, random sampling TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
PENDAHULUAN
Latar Belakang Perencanaan jalur merupakan salah satu proses yang terdapat di dalam pengendalian robot otonom.
Proses ini sangat penting untuk memastikan bahwa jalur yang akan dilewati oleh robot otonom tersebut bebas dari tabrakan dimulai dari posisi awal hingga ke posisi tujuan.
Perjalanan robot menuju ke titik tujuan tentu saja akan menemui berbagai macam Oleh karena itu algoritma perencanaan jalur sangat perlu dilakukan untuk menghasilkan jarak yang optimal.
Perencanaan jalur pada robot otonom memiliki banyak kegunaan seperti Autonomus Vacum Cleaner Robots .
Unmanned Aerial Vehicles (UAV) menjelajahi lingkungan yang belum diketahui .
, pada bidang medis perencanaan jalur digunakan untuk mendesain obat yang lebih baik .
, kursi roda elektronik otonom di rumah sakit .
Pada pengaplikasian perencanaan jalur, algoritma yang sering digunakan adalah Sampling Based Planning (SBP).
Algoritma SBP bekerja dengan mengambil sampel acak pada ruang pencarian .
, .
Contoh algoritma SBP yang sering digunakan yaitu Rapidly-exploring Random Tree (RRT) .
, .
dan Probabilistic Roadmap Method (PRM).
Algoritma RRT memiliki keunggulan dalam hal waktu komputasi yang rendah, tetapi solusi yang diberikan bersifat sub-optimal, sementara PRM memiliki waktu komputasi yang tinggi, tetapi menghasilkan solusi yang bersifat asimptotik optimal .
Karena kekurangan yang dimiliki oleh RRT, maka Karaman dan Frazzoli mengusulkan variasi dari algoritma RRT yaitu RRT* .
Algoritma RRT* ini menghasilkan solusi yang bersifat asimptotik optimal.
Pengembangan dari RRT* informed-RRT* oleh Gammel dkk .
yang mana algoritma informed-RRT* akan melakukan pengambilan sample pada area yang berbentuk elips yang melingkupi titik awal dan titik akhir untuk memberikan jarak yang paling optimal.
Hal yang tidak kalah penting dalam SBP yaitu strategi pengambilan sample yang mana pengambilan sample merupakan inti dari SBP .
Pada awalnya algoritma RRT dan PRM diusulkan menggunakan strategi random sampling .
, .
, .
yang mana strategi pengambilan sampel tersebut digunakan pada sebagian besar algoritma SBP termasuk algoritma Informed-RRT*.
Strategi sampling tersebut dianggap sebagai kelemahan karena tidak menangkap konektivitas lingkungan yang sebenarnya.
Hal ini dapat menyebabkan waktu komputasi dan kualitas jalur menjadi tidak optimal .
Tinjauan State of art Permasalahan waktu komputasi yang tidak optimal dapat diatasi dengan yaitu seperti yang pernah dilakukan oleh Reza .
yaitu pencarian solusi awal jalur dilakukan dengan menggunakan algoritma RRT karena menghasilkan waktu komputasi yang lebih rendah.
Setelah solusi awal jalur jalur tersebut ditemukan maka jalur tersebut dioptimalisasi dengan menggunakan algoritma Informed-RRT*.
Pada penelitian tersebut masih menggunakan metode random sampling sehingga waktu komputasi masih belum optimal.
Pada penelitian ini penulis menggunakan metode hybrid sampling pada algoritma informed-RRT* sebagai pengganti dari metode random sampling yang digunakan pada algoritma Informed-RRT*.
Tujuan Penelitian ini bertujuan untuk mengusulkan metode pengambilan sampel alternatif untuk digunakan pada algoritma Informed-RRT*.
Metode pengambilan sampel yang diusulkan yaitu metode hybrid sampling.
Pengujian metode hybrid sampling ini dilakukan pada lingkungan clutter, narrow, dan trap.
Performansi yang diukur dari pengujian ini adalah waktu komputasi.
Hasil pengukuran performansi ini akan dibandingkan dengan algoritma Informed-RRT* dengan metode random sampling.
Sistematika Pembahasan Sistematika pada penulisan ini terdiri dari beberapa bagian.
Pada bagian 2 akan menjelaskan perancangan metode hybrid sampling pada algoritma informed-RRT*.
Pada bagian 3 akan memaparkan hasil data yang didapat dari percobaan metode hybrid sampling, random sampling, boundary sampling, goal biasing sampling pada algoritma informed-RRT*.
Pada bagian 4 akan membahas kesimpulan yang didapat dari hasil percobaan.
II.
METODOLOGI
Proses pada metode hybrid sampling yaitu dengan memilih salah satu metode pengambilan sampel yang telah diintegrasikan sebelumnya.
Metode pengambilan sampel yang diintegrasikan TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
yaitu metode goal biasing sampling, metode boundary sampling, metode random sampling.
Besarnya peluang terpilihnya salah satu metode sampling adalah tergantung dari nilai persentase yang telah ditetapkan masing-masing metode sampling yang telah diintegrasikan.
Semakin besar nilai persentasenya maka peluang terpilihnya salah satu algoritma pada setiap iterasi akan semakin Semakin kecil nilai persentase yang diberikan pada metode-metode sampling maka akan semakin kecil pula peluang terpilihnya salah satu algoritma pada setiap iterasinya.
Algoritma metode hybrid sampling dapat dilihat pada Algoritma 1.
Algoritma 1: Hybrid Sampling .
0, g.
1 x1 Ia a random number.
between 0 and 100 2 if x1 > 0 & x1 O b0 then sample Ia BoundarySample 4 else if x1 > b0 & x1 O b0 g0 then sample Ia GoalBiasSample 6 else sample Ia UniformSample 8 end if 9 return sample.
Pada Algoritma 1 parameter g0 merupakan persentase dari metode goal biasing sampling.
Parameter b0 merupakan persentase dari metode boundary sampling.
Baris ke 1 yang terdapat pada Algoritma membangkitkan nilai acak .
antara 0 dan 100.
Proses pada baris ke-2 yaitu untuk menguji apabila kondisi .
1 > 0 & x1 O b.
terpenuhi maka boundary sampling akan digunakan.
Pada baris ke-4 apabila .
1 > b0 & x1 O b0 g.
terpenuhi maka goal biasing sampling akan digunakan.
Jika kondisi pada baris ke-2 dan baris ke-4 tidak terpenuhi maka random sampling yang akan digunakan.
Cara keja dari random sampling yaitu dengan mengambil nilai acak pada ruang pencarian.
Algoritma random sampling dapat dilihat pada Algoritma 2.
Algoritma 2: Random Sampling .
0, g.
qrand Ia a RandomConfig().
return qrand Proses pada goal biasing sampling yaitu dengan mengambil sampel langsung pada titik tujuan dengan frekuensi tertentu.
Algoritma goal biasing sampling dapat dilihat pada Algoritma 3.
Algoritma 3: GoalBiasSample () 1 rand Ia a random number.
between 0 - 100 2 if rand < k then qrand Ia qgoal 4 else qrand Ia RandomConfig().
6 end if 7 return qrand Parameter qgoal yang terdapat pada Algoritma 3 merupakan titik tujuan.
Pada Algoritma 3.
Terdapat parameter k yang mana parameter ini merupakan besarnya persentase peluang untuk mengambil titik sampel langsung menuju ke titik Besarnya nilai persentase yang direkomendasikan adalah 0 sampai 10%.
Variabel rand merupakan nilai acak yang dibangkitkan mulai dari 0 sampai 100.
qgoal merupakan titik Jika random number lebih kecil dari k, maka qrand akan bernilai qgoal, jika tidak maka nilai qrand akan bernilai titik acak pada ruang pencarian.
Pada perancangan ini penulis menggunakan persentase sebesar 10% yang juga digunakan oleh penelitian sebelumnya oleh Mohamed Elbanhawi .
Algoritma boundary nodes dapat dilihat pada Algoritma 4.
Algoritma 4: BoundaryNodes.
=0, c, x=false, arr[ ], .
1 rand qobs Ia random node in obstacle 2 c= qobs 3 while g O 360 then while x = false then if c CollisonFree arr [ ] =, c Ia add c to array x= true c =0,01 g =n x=false c= qobs return arr [ ] Pada Algoritma 4 proses pada baris ke-1 yaitu membentuk titik acak di dalam obstacle .
Proses pada baris ke-2 akan memeriksa apakah sudut g pada titik qobs lebih kecil sama dengan 360 Proses pada baris ke-4 akan memeriksa nilai x apakah bernilai true atau false.
Proses pada baris ke-5 akan memeriksa apakah c berada berada TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
diluar obstacle atau tidak.
Apabila nilai c berada di luar obstacle maka tambahkan nilai c ke dalam array .
dan x akan menjadi true.
Jika c masih berada di dalam obstacle maka nilai c akan ditambah dengan nilai 0,01 menjauhi titik qobs pada sudut g.
Penggunaan nilai 0,01 bertujuan agar pencarian batas obstacle menjadi lebih akurat.
Semakin kecil nilainya maka akan semakin akurat titik batas obstacle yang akan didapatkan.
Nilai n merupakan penentu banyaknya titik sampel yang akan diambil pada setiap permukaan obstacle.
Pada perancangan ini penulis mengambil titik sampel pada permukaan obstacle sebanyak 20 titik pada setiap obstacle.
Pengambilan titik sampel sebanyak 20 titik setiap obstacle bertujuan umtuk mempermudah pohon pencarian menuju titik satu menuju ke titik lainnya.
nilai n yang digunakan pada perancangan ini adalah n=18 yang di dapat dari perhitungan 360 derajat / 20 titik = 18.
Ilustrasi pada Algoritma 4 dapat dilihat pada Gambar 1.
Proses pada Algoritma 5 baris ke-1 yaitu membangkitkan angka acak .
dari 0 sampai Kemudian proses pada baris ke-2 yaitu menguji apabila rand < 10 maka ambil sampel acak pada ruang pencarian.
Proses pada baris ke-4 Apabila rand > 10 maka pilih salah satu titik sampel pada permukaan obstacle yang terdapat pada variabel arr [ ].
besarnya pemilihan titik sampel di permukaan obstacle pada perancangan ini yaitu 90% dan persentase pengambilan titik acak pada ruang pencarian yaitu 10%.
Besarnya persentase yang digunakan pada perancangan ini bertujuan agar proses pada Algoritma 5 tidak hanya memilih titik sampel pada permukaan obstacle saja, tetapi juga sesekali dapat mengambil titik sampel pada ruang bebas apabila ternyata titik tujuan berada di ruang pencarian bebas.
HASIL DAN PEMBAHASAN
Pengujian metode goal biasing sampling, boundary sampling, random sampling pada algoritma InformedRRT* Gambar 1 ilustrasi pencarian titik batas pada obstacle Titik warna biru pada Gambar 1 merupakan titik-titik pengujian untuk mencari batas dari Titik biru ini merupakan variabel c yang terdapat pada Algoritma 4.
Garis berwarna merah pada Gambar 1 merupakan garis untuk sudut 0 derajat pada titik qobs (Black do.
Titik warna hijau pada Gambar 1 merupakan titik sampel pada permukaan obstacle yang didapatkan setelah beberapa pengujian pada titik biru dilakukan.
Algoritma pemilihan titik sampel pada permukaan obstacle yang telah di simpan pada variabel arr [ ] pada Algoritma 4 dapat dilihat pada Algoritma 5.
Algoritma 5: BoundarySample.
rr [ ] ) rand Ia random number.
between 0 and 100 if rand O 10 then sample Ia a RandomConfig().
randarr Ia random number.
and arr length sample Ia arr .
return sample Agar analisa pada percobaan metode hybrid sampling semakin mudah dipahami, maka penulis melakukan percobaan untuk melihat kelebihan dari metode pengambilan sampel goal biasing sampling dan boundary sampling.
Metode Percobaan pertama dilakukan dengan mengambil data sebanyak 30 data.
Setiap data akan dilakukan sebanyak 1000 iterasi.
Percobaan pertama yaitu dengan menempatkan titik tujuan dekat dengan obstacle dan berhadapan langsung dengan titik Percobaan pertama dapat dilihat pada Gambar 2.
Kemudian percobaan kedua yaitu dengan menempatkan titik tujuan sedikit lebih jauh dari obstacle.
Percobaan kedua dapat dilihat pada Gambar 3.
Kemudian percobaan ketiga yaitu dilakukan hanya untuk menguji metode boundary sampling yaitu dengan menempatkan titik tujuan yang membelakangi obstacle.
Percobaan ketiga dapat dilihat pada Gambar 4.
Pada Gambar 2 pohon pencarian pada metode random sampling akan menyebar kesegala arah karena pengambilan titik sampel pada metode random sampling dilakukan secara acak pada ruang pencarian.
Hal ini menjadi penyebab waktu komputasi pada metode random sampling menjadi sangat lama.
Bentuk pohon pencarian pada metode goal biasing sampling hampir sama seperti bentuk pohon pencarian pada metode random sampling.
Perbedaannya terletak pada pengambilan titik sampel pada metode goal biasing sampling yang TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
sesekali mengarah langsung ke titik tujuan, sehingga mempercepat waktu komputasi.
Bentuk pohon pencarian pada metode boundary sampling akan mengarah langsung menuju obstacle karena pengambilan titik sampel diambil pada permukaan obstacle, sekaligus menemukan titik tujuan yang berada didekat obstacle.
Sifat dari boundary sampling ini sama seperti percobaan yang dilakukan oleh Nancy .
Hal ini menyebabkan waktu komputasi pada metode sampling boundary menjadi sangat cepat.
Pada Gambar 3 pohon pencarian pada metode random sampling berada menyebar ke semua ruang pencarian, karena metode tersebut akan mengambil titik sampel secara acak diruang Sehingga waktu komputasi pada metode random sampling menjadi lebih lama tetapi tidak lebih lama bila dibandingkan dengan metode boundary sampling.
pada metode goal biasing sampling pengambilan sampel sama seperti metode random sampling, hanya saja pada metode goal biasing sampling akan menempatkan titik sampelnya langsung pada titik tujuan.
Sehingga pohon pencarian pada metode goal biasing sampling dapat mengarah langsung ke titik tujuan.
Sifat dari goal biasing sampling ini sama seperti yang dilakukan oleh Mohamed Elbanhawi .
Pada metode boundary sampling pohon pencarian akan mengarah langsung menuju ke permukaan obstacle dan sesekali pohon pencarian mengarah acak pada ruang pencarian.
Hal ini menyebabkan pohon pencarian pada metode boundary sampling menjadi sulit menemukan titik tujuan bahkan gagal menemukan titik tujuannya.
Pada Gambar 4 Pengujian dilakukan sebanyak 1000 iterasi.
Kondisi tersebut merupakan kondisi di mana metode boundary sampling tidak dapat menemukan titik tujuannya.
Metode boundary sampling tetap akan mengambil sampel merata pada permukaan obstacle akan tetapi pohon pencarian tidak dapat langsung menuju kebagian sisi belakang yang berdekatan dengan titik tujuan karena terhalang oleh obstacle itu sendiri.
Pada metode boundary sampling ini juga melakukan sebagian kecil pengambilan titik sampel acak pada ruang pencarian tetapi tetap tidak mampu menemukan titik tujuannya karena sebagian besar pengambilan titik sampel diambil pada permukaan Tabel hasil perbadingan waktu komputasi dari metode goal biasing sampling, boundary sampling, dan random sampling pada kondisi titik tujuan dekat dan sedikit lebih jauh dari obstacle dapat dilihat pada Tabel I-II.
Tabel I merupakan perbandingan waktu komputasi dari metode goal biasing sampling, boundary sampling, dan random sampling pada kondisi titik tujuan dekat dari Tabel II merupakan perbandingan waktu komputasi dari metode metode goal biasing sampling, boundary sampling, dan random sampling pada kondisi titik tujuan sedikit lebih jauh dari obstacle.
Gambar 2.
Perbandingan pohon pencarian pada kondisi titik tujuan berada di dekat obstacle dan berhadapan langsung dengan titik awal: random sampling .
, goal biasing sampling .
, boundary sampling .
Gambar 3.
Perbandingan pohon pencarian pada kondisi titik tujuan berada sedikit lebih jauh dari obstacle dan berhadapan langsung dengan titik awal: random sampling .
, goal biasing sampling .
, boundary sampling .
TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
Gambar 4.
Pohon pencarian pada kondisi titik tujuan membelakangi obstacle menggunakan boundary sampling Pada Tabel II metode boundary sampling mengalami 14 kali kegagalan dari 30 data yang dalam pencarian untuk menemukan titik tujuan.
Hal ini disebabkan karena karena sebagian besar titik sampel yang diambil berada pada permukaan obstacle dan hanya sebagian kecil mengambil titik sampel acak pada ruang pencarian.
Grafik perbandingan metode randaom sampling, goal biasing sampling, dan boundary sampling saat titik tujuan berada dekat dengan obstacle dapat dilihat pada Gambar 5.
Grafik perbandingan metode random sampling, goal biasing sampling, dan boundary sampling saat titik tujuan berada sedikit lebih jauh dengan obstacle dapat dilihat pada Gambar 6.
Tabel I Perbandingan waktu komputasi dari metode goal biasing sampling, boundary sampling, dan random sampling pada kondisi titik tujuan dekat dari obstacle.
Minimum Maksimum Rata-rata STD Goal biasing Boundary Waktu .
9,93 148,33 55,53 35,53 Waktu .
6,42 16,05 8,99 Waktu .
3,91 4,81 4,27 0,21 Tabel II.
Perbandingan waktu komputasi dari metode metode goal biasing sampling, boundary sampling, dan random sampling pada kondisi titik tujuan sedikit lebih jauh dari obstacle.
Minimum Maksimum Rata-rata STD Goal biasing Boundary Waktu .
11,84 128,45 43,19 33,32 Waktu .
8,42 13,93 11,19 Waktu .
45,21 96,21 69,54 15,68 Gambar 5.
Perbandingan metode random sampling, goal biasing sampling, dan boundary sampling .
ekat obstacl.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
Gambar 6.
Perbandingan metode random sampling, goal biasing sampling, dan boundary sampling .
edikit lebih jauh dari obstacl.
Pengujian metode random sampling dan hybrid sampling pada algortima Informed-RRT* Pengujian ini dilakukan pada lingkungan yang umum digunakan yaitu clutter, narrow, dan trap.
Parameter yang akan dibandingkan adalah waktu Pada percobaan ini dilakukan pengambilan data sebanyak 30 data.
Setiap data dilakukan percobaan dengan iterasi sebanyak 1000 Waktu komputasi yang terdapat pada Tabel i-Vi merupakan waktu komputasi terpendek yang didapatkan dari masing-masing metode random sampling dan hybrid sampling setelah iterasi berakhir.
Lingkungan clutter, narrow, dan trap dapat dilihat pada Gambar 7-9.
Gambar 8.
Contoh lingkungan pengujian Narrow Gambar 9.
Contoh lingkungan pengujian Trap Gambar 7.
Contoh lingkungan pengujian clutter Pengujian metode hybrid sampling dan metode random sampling menggunakan algoritma Informed-RRT* ditunjukkan pada Gambar 10 - 11.
Pada Gambar 10 merupakan bentuk pohon pencarian pada metode random sampling.
Gambar 11 merupakan TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
bentuk pohon pencarian pada metode hybrid titik tujuan sehingga waktu komputasi pada metode hybrid sampling menjadi lebih cepat bila dibandingkan dengan metode random sampling.
Pengujian metode hybrid sampling dan metode random sampling menggunakan algoritma Informed-RRT* ditunjukkan pada Gambar 12-13.
Pada Gambar 12 merupakan bentuk pohon pencarian pada metode random sampling.
Gambar 13 merupakan bentuk pohon pencarian pada metode hybrid Gambar 10.
Bentuk pohon pencarian pada metode random sampling pada lingkungan clutter Pada Gambar 10 terlihat bahwa cabang pada pohon pencarian menyebar ke segala arah.
Hal ini disebabkan karena metode random sampling akan selalu mengambil sampel acak pada ruang pencarian sehingga beberapa cabang bergerak menjauhi titik tujuan.
Hal ini menyebabkan waktu komputasi menjadi lebih lama.
Gambar 12.
Bentuk pohon pencarian pada metode random sampling pada lingkungan narrow Pada Gambar 12 pohon pencarian pada metode random sampling sebelum melewati celah sempit akan mengarahkan cabang pohon pencarian ke segala arah.
Setelah berhasil melewati celah, cabang pohon pencarian pada random sampling akan tetap menuju ke segala arah bahkan sebagian cabang bergerak menjauhi titik tujuan.
Hal ini yang menyebabkan waktu komputasi menjadi lebih Gambar 11.
Bentuk pohon pencarian pada metode hybrid sampling pada lingkungan clutter Bentuk pohon pencarian pada metode hybrid samping Pada Gambar 11, pohon pencarian akan langsung menuju ke arah obstacle hal itu disebabkan karena pengaruh dari metode boundary sampling yang mengambil titik sampel pada permukaan obstacle.
Goal biasing sampling dan boundary sampling pada lingkungan clutter membuat pohon pencarian lebih terarah menuju Gambar 13 Bentuk pohon pencarian pada metode hybrid sampling pada lingkungan narrow TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
Pada Gambar 13 cabang pohon pencarian sebelum melawati celah sempit terlihat lebih sedikit bila dibandingkan dengan metode random sampling pada Gambar 12.
Hal ini disebabkan karena sebagian cabang pohon pencarian yang dilakukan pada metode hybrid sampling akan menuju langsung ke permukaan obstacle yang menyebabkan peluang untuk dapat melewati celah sempit menjadi lebih besar.
Cabang pohon pencarian setelah melewati celah sempit akan cenderung mengarah langsung ke titik tujuan sehingga waktu komputasi menjadi lebih cepat bila dibandingkan dengan metode random sampling.
Pengujian metode hybrid sampling dan metode random sampling menggunakan algoritma Informed-RRT* pada lingkungan trap ditunjukkan pada Gambar 14-15.
Pada Gambar 14 merupakan bentuk pohon pencarian pada metode random Gambar 15 merupakan bentuk pohon pencarian pada metode hybrid sampling.
Gambar 14.
Bentuk pohon pencarian pada metode random sampling pada lingkungan trap Pada Gambar 14 cabang pohon pencarian pada metode random sampling memiliki peluang yang besar untuk keluar dari obstacle trap.
Karena pengambilan titik sampel pada metode tersebut diambil secara acak di seluruh ruang pencarian.
Setelah cabang pada pohon pencarian tersebut berhasil keluar dari obstacle trap, maka cabang pohon pencarian tersebut cenderung mengarah ke segala arah pada ruang pencarian.
Hal ini menyebabkan beberapa cabang yang tidak mengarah ke titik tujuan menjadi tidak berguna.
Gambar 15 bentuk pohon pencarian pada metode hybrid sampling dilingkungan trap Pada Gambar 15 cabang pohon pencarian pada metode hybrid sampling memiliki peluang yang lebih kecil untuk keluar dari celah sempit bila dibandingkan dengan metode random sampling.
Hal ini disebabkan karena beberapa pengambilan titik sampel pada metode ini berada pada permukaan obstacle yang menyebabkan waktu komputasi menjadi lebih lama.
Setelah cabang pada pohon pencarian berhasil keluar dari celah sempit maka cabang pohon pencarian cenderung menuju ke titik tujuan.
Pada kasus pengujian dilingkungan trap ini metode boundary sampling tidak terlalu dibutuhkan pada proses pencarian jalur karena pohon pencarian menjadi sulit menemukan jalan keluar dari dalam trap.
Tabel perbandingan waktu komputasi menggunakan metode random sampling dan hybrid sampling pada lingkungan clutter, narrow, dan trap ditunjukkan pada Tabel i-V.
Tabel i.
Perbandingan waktu komputasi pada lingkungan Data Minimum Maksimum Rata-rata STD Random Waktu .
13,01 108,81 39,00 21,17 Hybrid sampling .
oal biasing 50%, boundary 30%, random 20%) Waktu .
10,15 21,23 14,03 3,02 TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
Tabel IV.
Perbandingan waktu komputasi pada lingkungan Data Minimum Maksimum Rata-rata STD Hybrid sampling .
oal biasing 50%, boundary 30%, random 20%) Waktu .
10,11 47,55 21,46 10,54 Random Waktu .
23,53 53,50 40,34 7,97 Tabel VII merupakan perbandingan waktu komputasi dari dua kombinasi hybrid sampling yang dilakukan pada lingkungan narrow.
Tabel Vi merupakan perbandingan waktu komputasi dari dua kombinasi hybrid sampling yang dilakukan pada lingkungan trap.
Tabel VII.
Perbandingan waktu komputasi dari dua kombinasi hybrid sampling yang dilakukan pada lingkungan narrow.
Data Tabel V.
Perbandingan waktu komputasi pada lingkungan trap Data Minimum Maksimum Rata-rata STD Random Sampling Waktu .
15,25 42,15 23,20 6,24 Hybrid sampling .
oal biasing 50%, boundary 30%, random 20%) Waktu .
8,23 35,76 19,45 5,38 Pada Tabel i-V menunjukkan bahwa penggunaan metode hybrid sampling pada algoritma Informed-RRT* dapat memberikan waktu komputasi yang lebih cepat bila dibandingkan metode random sampling pada algoritma Informed-RRT*.
Penulis mencoba melakukan beberapa percobaan dengan mengubah nilai persentase pada metode hybrid sampling untuk mengetahui apakah waktu komputasi metode hybrid sampling pada algoritma informed-RRT* dapat menjadi lebih baik atau lebih buruk.
Perbandingan waktu komputasi dari kombinasi hybrid sampling pada lingkungan clutter, narrow, dan trap dapat dilihat pada Tabel VI-Vi.
Tabel VI merupakan perbandingan waktu komputasi dari dua kombinasi hybrid sampling yang dilakukan pada lingkungan clutter.
Tabel VI.
perbandingan waktu komputasi dari dua kombinasi hybrid sampling yang dilakukan pada lingkungan clutter.
Hybrid sampling .
oal biasing 70%, boundary 10%, random 20%) Hybrid sampling .
oal biasing 90%, boundary 5%, random 5%) Minimum Maksimum Rata-rata Waktu .
9,73 25,44 13,04 Waktu .
9,28 STD
3,07
Data Minimum Maksimum Rata-rata STD Hybrid sampling .
oal biasing 70%, boundary 10%, random Hybrid sampling .
oal biasing 90%, boundary 5%, random 5%) Waktu .
10,17 34,78 16,84 Waktu .
9,31 41,32 15,82 7,45 Tabel Vi.
Perbandingan waktu komputasi dari dua kombinasi hybrid sampling yang dilakukan pada lingkungan trap.
Data Minimum Maksimum Rata-rata STD Hybrid sampling .
oal biasing 70%, boundary 10%, random Hybrid sampling .
oal biasing 90%, boundary 5%, random 5%) Waktu .
40,55 6,14 Waktu .
9,34 24,64 3,03 Hal yang menarik dari hasil persentase kombinasi metode hybrid sampling percobaan yang dilakukan pada Tabel i-Vi yaitu semakin besar persentase goal biasing sampling maka waktu komputasi yang dihasilkan akan semakin Persentase kombinasi metode hybrid sampling yang menghasilkan waktu komputasi paling cepat yaitu goal biasing sampling 90% boundary sampling 5% random sampling 5%.
Grafik perbandingan metode hybrid sampling dapat dilihat pada Gambar 16-18.
Pada Gambar 16 merupakan grafik perbandingan metode hybrid sampling dan random sampling pada lingkungan Pada Gambar 17 merupakan grafik perbandingan metode hybrid sampling dan random sampling pada lingkungan narrow.
Pada Gambar 18 merupakan grafik perbandingan metode hybrid sampling dan random sampling pada lingkungan TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
Gambar 16.
Grafik perbandingan metode hybrid sampling dan random sampling pada lingkungan clutter Gambar 17.
Grafik perbandingan metode hybrid sampling pada lingkungan narrow Gambar 18.
Grafik perbandingan metode hybrid sampling pada lingkungan narrow TELEKONTRAN.
VOL.
NO.
OKTOBER 2021
IV.
KESIMPULAN
DAFTAR PUSTAKA