TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
DOI 10.
34010/telekontran.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
p-ISSN : 2303 Ae 2901 e-ISSN : 2654 Ae 7384 Algoritma Perencanaan Jalur Kendaraan Otonom di Lingkungan Perkotaan dari Sudut Pandang Filosofi Kuhn dan Filosofi Popper Path Planning Algorithm for Autonomous Urban Vehicles from the Viewpoint of KuhnAos Philosophy and PopperAos Philosophy Muhammad Aria Rajasa Pohan1,*.
Bambang Riyanto Trilaksono1.
Sigit Puji Santosa2.
Arief Syaichu Rohman1 Sekolah Teknik Elektro dan Informatika Sekolah Teknik Mesin dan Dirgantara Institut Teknologi Bandung Jl.
Ganesha No 10.
Bandung Email : muhammad.
aria@students.
Abstrak Ae Kendaraan otonom dapat bermanfaat untuk meningkatkan keselamatan, efisiensi, aksesibilitas dan kenyamanan transportasi.
Salah satu tugas penting yang harus dilakukan oleh kendaraan otonom adalah melakukan perencanaan jalur melalui lingkungan perkotaan yang dinamis dimana terdapat kendaraan lain dan pejalan kaki.
Menuruf filosofi Kuhn, sebuah keilmuan memiliki siklus hidupnya sendiri-sendiri.
Siklus hidup suatu keilmuan terdiri dari fase kelahiran, fase pembuktian dan fase diterimanya keilmuan baru tersebut menjadi apa yang disebut sebagai ilmu normal.
Demikian juga dengan perkembangan keilmuan perencaan jalur, algoritma perencanaan jalur untuk kendaraan otonom masih terus diteliti dan dikembangkan oleh berbagai peneliti.
Studi baru terus dilakukan dalam upaya menemukan teknik perencanaan jalur yang dapat diterima secara umum, sehingga algoritma tersebut akan menjadi ilmu normal.
Menutur filosofi Popper, setiap algoritma yang diusulkan harus dapat diuji menggunakan prinsip falsifikasi untuk menentukan apakah teknik yang diusulkan tersebut akhirnya bisa menjadi ilmu normal atau tidak.
Maka makalah ini bertujuan untuk memberikan gambaran mengenai siklus keilmuan perencanaan jalur kendaraan otonom.
Makalah ini juga bertujuan untuk membandingkan penelitian-penelitian terkini mengenai algoritma perencanaan jalur untuk kendaraan otonom di daerah perkotaan.
Dalam membandingkan algoritma-algoritma tersebut akan digunakan prinsip falsifikasi Popper.
Dari hasil pengujian, ditunjukkan bahwa algoritma perencanaan jalur dapat bertahan dari metode falsifikasi Popper.
Hasil falsifikasi terhadap algoritma perenanaan jalur ini menunjukkan penguatan nilai saintifik dari algoritma tersebut.
Kata Kunci : Kendaraan otonom, algoritma perencanaan jalur, lingkungan perkotaan, siklus keilmuan Khun, falsifikasi Popper Abstract - Autonomous vehicles can be useful to improve safety, efficiency, accessibility and convenience of One important task that must be carried out by autonomous vehicles is to do path planning through a dynamic urban environment where there are other vehicles and pedestrians.
According to Kuhn's philosophy, a science has its own life cycle.
The science life cycle consists of the birth phase, the proof phase and the acceptance phase of the new science into what is called normal science.
Likewise with the scientific development of path planning algorithms, path planning algorithms for autonomous vehicles are still being researched and developed by various researchers.
New studies continue to be conducted in an effort to find pathway planning techniques that can be generally accepted, so that the algorithm will become a normal According to Popper's philosophy, each proposed algorithm must be tested using the principle of falsification to determine whether the proposed technique can eventually become a normal science or not.
this paper aims to provide an overview of the scientific cycle of planning autonomous vehicle lanes.
This paper also aims to compare the latest research on path planning algorithms for autonomous vehicles in urban areas.
In comparing these algorithms, the principle of Popper's falsification will be used.
From the test results, it was shown that the path planning algorithm can survive the Popper falsification method.
The results of the falsification of the path planning algorithm indicate the strengthening of the scientific value of the algorithm.
Keywords : Autonomous vehicles, path planning algorithms, urban environment.
KhunAos scientific cycles.
PopperAos falsification TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
PENDAHULUAN
Kendaraan otonom .
utonomous vehicle atau self-driving ca.
adalah kendaraan yang mampu mengoperasikan dirinya sendiri, tanpa campur tangan manusia secara manual, untuk bergerak menuju tujuan yang telah ditentukan .
Agar kendaraan otonom dapat beroperasi tanpa campur tangan manusia, kendaraan otonom harus mampu mendeteksi kondisi lingkungan, memprediksi pergerakan objek di sekitarnya, dan membuat jalur ke tujuannya sambil menghindari rintangan statis maupun dinamis yang ada di sekitarnya .
] Kendaraan otonom dapat bermanfaat untuk meminimalkan ruang parkir, meningkatkan kenyamanan transportasi dan banyak manfaat lainnya .
Dengan adanya kemajuan dalam teknologi sensor dan komputasi, jumlah studi di bidang kendaraan otonom telah meningkat dalam tiga dekade terakhir .
Penelitian survei mengenai kendaraan otonom juga telah banyak dilakukan oleh pada peneliti.
Badue dkk telah melakukan penelitian survei mengenai mobil otonom yang dipublikasikan semenjak kompetisi DARPA Urban Challenge (DUC) serta memiliki sistem otomasi yang dapat dikategorikan oleh Society of Automotive Engineers (SAE) sebagai level 3 atau Makalah tersebut membahas arsitektur umum pada kendaraan otonom, sistem persepsi, sistem pengambilan keputusan, serta arsitektur sistem kendaraan otonom dari Universidade Federal do Espyrito Santo (UFES) .
Zhao dkk.
membahas empat teknologi utama yang digunakan pada kendaraan otonom.
Teknologiteknologi tersebut adalah sistem persepsi lingkungan, sistem perencanaan jalus, sistem navigasi kendaraan dan sistem kendali kendaraan.
Paper ini juga membahas prediksi arah perkembangan penelitian dari kendaraan otonom .
Adapun Bimbraw membahas tren teknologi kendaraan otonom dari masa lalu, saat ini dan prediksi di masa depan.
Dikarenakan saat ini telah banyak fitur semi-otonom yang diperkenalkan pada kendaraan modern .
eperti automatic braking, lane keeping, dan adaptive cruise contro.
, maka Bimbraw memprediksi bahwa dalam satu dekade lagi, sebagian besar perusahaan akan meluncurkan kendaraan otonom penuh .
Paden melakukan penelitian survei terkini mengenai algoritma perencanaan jalur dan kendali dari mobil otonom untuk lingkungan perkotaan.
Paden mendiskusikan kelebihan dan kekurangan dari setiap algoritma perencanaan jalur .
Marina dan Sandu melakukan penelitian survei mengenai pemanfaatan Deep Reinforcement Learning (DRL) untuk kendaraan otonom.
Paper tersebut membahas kelebihan dan kekurangan pemanfaatan DRL.
Marina dan Sandu juga menyajikan penelitian tentang simulasi algoritma DRL pada kendaraan otonom .
Sementara Katrakazas dkk.
melakukan perbandingan mengenai metode perencanaan jalur pada kendaraan otonom.
Proses perencanaan jalur terdiri dari tiga tahapan, yaitu membangun jalur, menemukan manuver yang paling aman, serta menentukan jalur yang paling layak.
Metode yang dikembangkan untuk masing-masing tahapan tersebut menunjukkan kompleksitas dan akurasi yang berbeda-beda.
Katrakazas melakukan evaluasi kritis mengenai masing-masing metode ditinjau dari sisi kelebihan dan kekurangannya .
Meskipun banyak penelitian yang telah melakukan survei mengenai kendaraan otonom, sejauh pengetahuan penulis, belum ada penelitian yang membandingkan algoritma perencanaan jalur kendaraan otonom ini ditinjau dari sudut pandang filosofi Thomas S.
Khun dan filosofi Karl Popper.
Tujuan dari penelitian ini adalah untuk melakukan survei literatur tentang algoritma perencanaan jalur kendaraan otonom di lingkungan perkotaan dari sudut pandang filosofi Thomas S.
Kuhn dan dari sudut padang filosofi Karl Popper.
Literatur yang dipilih adalah literatur yang mengembangkan kendaraan otonom yang memenuhi kategori minimal level 3 menurut SAE.
Selain menggunakan sumber-sumber dari publikasi ilmiah, penelitian ini juga melakukan penelusuran melalui situs web dari perusahaan yang mengembangkan kendaraan otonom serta melalui informasi dari berbagai media.
Hal ini dilakukan dikarenakan tidak semua perusahaan komersial mempublikasikan hasil penelitian mereka melalui publikasi ilmiah.
Artikel ini akan menyajikan siklus keilmuan dari algoritma perencanaan jalur berdasarkan filosofi Thomas S.
Khun, serta menyajikan pula kajian falsifikasi berdasarkan filosofi Karl Popper terhadap berbagai algoritma perencanaan jalur.
II.
METODE PENELITIAN
Penelitian ini menggunakan metode survei Literatur yang digunakan adalah literatur yang mempublikasikan penelitian mengenai dikategorikan oleh SAE sebagai level 3 atau lebih.
Tetapi tidak semua perusahaan komersial yang TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
menginformasikan kemajuan penelitian mereka dalam publikasi ilmiah.
Maka kami juga menggunakan situs perusahaan atau berita dari berbagai media yang membahas mengenai penelitian tentang kendaraan otonom.
Diskusi akan ditekankan mengenai siklus keilmuan dari algoritma perencanaan jalur kendaraan otonom berdasarkan pandangan filosofi Thomas S.
Khun, serta mengenai ketahanan berbagai algoritma perencanaan jalur kendaraan otonom terhadap berbagai macam pengujian, atau yang disebut sebagai falsifikasi berdasarkan pandangan filosofi Karl Popper.
Analisis yang dilakukan meliputi kualitas performansi algoritma perencanaan jalur dalam menyelesaikan berbagai macam pengujian yang dilakukan.
PERKEMBANGAN KEILMUAN
PERENCANAAN
JALUR
BERDASARKAN
SUDUT
PANDANG FILOSOFI THOMAS
KHUN.
Jika sebagian orang berpikir bahwa perkembangan sains adalah linear-akumulatif, maka Thomas S.
Kuhn dalam bukunya yang berjudul "The Structure of Scientific Revolution," memiliki pandangan lain.
Menurut Kuhn, sains memiliki siklus hidupnya sendiri.
Siklus hidup sains terdiri dari fase kelahiran, fase pembuktian dan fase penerimaan dari sains baru ke dalam apa yang disebut sains normal.
Siklus puncak suatu sains adalah dalam fase sains normal, yang kemudian usang karena digantikan oleh pengetahuan atau paradigma baru.
Paradigma baru akan mengancam paradigma lama yang sebelumnya juga menjadi paradigma baru.
Gambar 1 menunjukkan siklus hidup ilmu dalam filsafat Thomas S.
Kuhn .
Pandangan Kuhn mengenai siklus ilmu dapat dilihat melalui tahapan-tahapan sebagai berikut.
Pra-Science Pada tahap ini, kegiatan penelitian dilakukan secara terpisah dan tidak terorganisir.
Ini dikarenakan tidak adanya paradigma tunggal yang diterima oleh semua ilmuwan tentang suatu teori.
Ada beberapa ilmuwan yang mengusulkan paradigma baru.
Peristiwa ini berlangsung selama periode waktu tertentu, sampai suatu paradigma tunggal diterima oleh semua ilmuwan.
Ketika paradigma tunggal diterima, tahapan akan berlanjut menuju Normal Science.
Gambar 1.
Siklus perkembangan keilmuan dari sudut pandang filosofis Thomas S.
Khun .
iadaptasi dari .
) Normal Science Pada tahap ini, aktivitas pengembangan ilmu menjadi terorganisir dan terarah.
Pada tahap ini tidak ada perselisihan diantara para ilmuwan mengenai hal-hal mendasar dari paradigma tunggal tersebut.
Paradigma tunggal dapat bertahan dari berbagai proses pengujian dan Anomali dan krisis Tahap anomali terjadi ketika ada masalah yang tidak bisa diselesaikan oleh ilmu pengetahuan normal .
aradigma tunggal yang sudah diterima tersebu.
Jika semakin banyak anomali terjadi, dan berbagai kelompok ilmiah mempertanyakan kesempurnaan paradigma yang berlaku, maka sains telah memasuki tahap krisis sejak saat itu.
Karena krisis, mengembangkan paradigma baru untuk menyelesaikan krisis.
Revolusi sains, kembali ke ilmu normal, dan kembali terjadi krisis Revolusi sains adalah tahap di mana paradigma lama digantikan oleh paradigma baru yang berbeda.
Revolusi sains ini menunjukkan tahap perkembangan keilmuan yang non-kumulatif, tetapi terjadi secara Jika paradigma baru ini dapat diterima, maka paradigma baru ini akan menjadi ilmu normal baru, dan kemungkinan akan ditemukan anomali akan baru, krisis baru terjadi dan siklus keilmuan akan terus Algoritma perencanaan jalur untuk kendaraan otonom masih merupakan ilmu yang berkembang.
Oleh karena itu pada bagian ini akan dibahas perkembangan paradigma algoritma perencanaan jalur dari sudut pandang siklus perkembangan keilmuan Thomas S.
Kuhn.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Perkembangan Keilmuan Algoritma Perencanaan Jalur Secara Umum Algoritma perencanaan jalur telah melalui beberapa siklus paradigma.
Salah satu paradigma pertama dalam algoritma perencanaan jalur adalah metode diskritisasi ruang kerja.
Algoritma perencanaan jalur seperti Djikstra .
dan A* .
merancang jalur optimal dalam ruang graph yang terkonektivitas.
Adapun algoritma D* .
dana AD* .
digunakan dalam graph yang Tetapi penggunaan metode diskritisasi ini akan menyebabkan penurunan kinerja pada kasus berdimensi tinggi.
Metode-metode baru dikembangkan untuk menghindari proses diskritisasi ini.
Salah satu paradigma yang diusulkan adalah metode berdasarkan nature inspires artificial intelligence.
Metode-metode berbasis Logika Fuzzy .
Jaringan Saraf Tiruan .
Algoritma Genetik .
, .
Ant Colony Optimization .
dan Simulated Annealing .
telah dikembangkan untuk aplikasi perencanaan jalur.
Tetapi metodemetode ini dapat terjebak pada solusi yang bersifat minimal lokal, serta memiliki performasi yang buruk pada kasus lingkungan yang sempit.
Paradigma lainnya yang diusulkan adalah metode perencanaan reaktif berbasis sensor, seperti yang diusulkan oleh Borenstein dan Koren .
Simmons .
ataupun Belkhouche dan Bendjilali .
Tetapi perencanaan reaktif berbasis sensor ini tidak dapat dianggap sebagai perencanaan jalur global.
Adapun metode kontrol klasik memerlukan formulasi model yang akurat dari robot maupun lingkungan .
, .
Formulasi model ini dapat menjadi pekerjaan yang rumit.
Paradigma perencanaan jalur lain yang diusulkan adalah perencanaan berbasis sampel atau Sampling Based Planning (SBP).
SBP
memilki keunggulan dalam hal dapat memberikan solusi yang cepat pada masalah yang sulit .
Algoritma yang paling umum digunakan untuk SBP adalah Probabilistic Roadmap Method (PRM) .
dan Rapidly-exploring Random Tree (RRT) .
Keunggulan algoritma PRM adalah dapat memberikan solusi yang bersifat asimptotik optimal, tetapi memiliki waktu komputasi yang tinggi, sedangkan keunggulan algoritma RRT adalah waktu komputasi yang rendah, tetapi memiliki hanya dapat memberikan solusi yang bersifat sub-optimal .
Algoritma RRT kemudian dikembangkan menjadi RRT* .
, yang memberikan solusi asimptotik optimal .
Namun, waktu komputasi RRT* masih tinggi.
Saat ini ada banyak algoritma pengembangan dari RRT* ini.
Akgun dan Stilman mengajukan algoritma B-RRT* .
Metode ini meningkatkan optimasi jalur yang dihasilan dengan cara menggunakan pencarian dua arah dari algoritma RRT*.
Kumar et al.
mengusulkan algoritma GoalBias-RRT .
Gammell et al.
Informed RRT* .
, mengusulkan agar pengambilan sampel pada algoritma RRT hanya dilakukan pada daerah elips yang mengelilingi simpul awal dengan simpul Nasir et al.
memperkenalkan algoritma RRT*-Smart untuk mempercepat laju konvergensi .
RRT*-smart menggunakan dua fitur yang dinamakan intelligent sampling dan route Dari pembahasan diatas, dapat terlihat beberapa perubahan paradigma dalam algoritma perencanaan jalur.
Beberapa paradigma tersebut adalah metode diskritisasi, metode berdasarkan nature inspires artificial intelligence, metode berdasarkan perencanaan reaktif berbasis sensor, metode kontrol klasik dan metode berbasis Perkembangan Keilmuan Algoritma Perencanaan Jalur yang Digunakan pada Kendaraan Otonom Gagasan mengenai kendaraan otonom dimulai pada tahun 1939 di New York World Fair dalam presentasi GM Futurama.
Tetapi membutuhkan beberapa dekade untuk mewujudkan ide kendaraan otonom tersebut.
Antara tahun 1987 hingga 1994, di Eropa telah dilaksanakan proyek EUREKA-PROMETHEUS dimana berbagai kendaraan dari perusahaan yang bermitra dengan proyek tersebut diotomatisasi.
Sistem kontrol yang digunakan untuk mengikuti rute adalah metode Clothoid .
Pada 1997, program PATH bekerja sama kendaraan otonom yang berjalan beriringan dengan jarak 6 meter antara satu dengan lainnya .
Carnegie Mellon University (CMU) juga mendemonstrasikan kendaraan otonom tunggal menggunakan kendaraan Navlab .
Pada tahun Belanda operasional CTS.
CTS menyediakan layanan pengantaran door-to-door .
, .
Dalam sistemsistem yang dibahas diatas, teknik yang digunakan adalah kontrol reaktif dan kerjasama kendaraan.
Salah satu penelitian pertama yang menguji teknik perencanaan jalur adalah proyek ARGO dari VisLab .
Sistem perencanaan jalur yang digunakan adalah pylonomial splines.
Selanjutnya DARPA Challenge (Grand dan Urban Challeng.
telah mendorong perkembangan teknik navigasi TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
otomatis dan teknik perencanaan jalur untuk kendaraan .
, .
Pemenang pertama dari DUC adalah tim Tartan Racing dari CMU.
Tim Tartan Racing menggunakan berbagai variasi teknik untuk menghasilkan lintasan lokal di lingkungan terstruktur dan grafik kisi dalam ruang konfigurasi 4 dimensi .
ermasuk posisi, orientasi, dan kecepata.
bersama dengan algoritma Anytime D* untuk menemukan jalur bebas tabrakan di area parkir .
Pemenang kedua DUC adalah tim Stanford Racing.
Tim Stanford menggunakan strategi perencanaan jalur Hybrid A* .
Pemenang ketiga dari DUC adalah tim VictorTango Virginia Tech.
Tim VictorTango membangun diskritisasi grafik dari manuver yang memungkinkan dan mencari jalur menggunakan algoritma A* .
Tim yang berhasil menyelesaikan DUC di posisi keempat adalah tim dari Massachusetts Institute of Technology (MIT).
MIT menggunakan varian dari algoritma RRT yang disebut Closed-Loop RRT dengan sampling bias .
Aspek inovatif utama dari sistem yang digunakan oleh tim MIT, dibandingkan dengan banyak tim lainnya, adalah bahwa keputusan otonom telah dibuat berdasarkan data persepsi lokal.
Aspek inovatif lainnya adalah penggunaan algoritma perencanaan dan kontrol berbasis RRT yang mampu melakukan semua persyaratan mengemudi lajur, parkir dan bermanuver dengan pendekatan tunggal terpadu .
Kendaraan otonom pertama yang diproduksi Google adalah pada tahun 2009.
Kendaraan otonom Google telah berhasil menempuh total jarak hingga 700.
000 mil tanpa adanya kecelakaan yang disebabkan oleh sistem otomatisasi.
Tetapi tidak ada publikasi ilmiah tentang teknik kontrol ataupun teknik perencanaan gerak yang digunakan oleh kendaraan otonom Google.
Pada tahun 2010, diselenggarakan VisLab Intercontinental Autonomous Challenge (VIAC) .
, yaitu tantangan kendaraan otonom dari VisLab untuk menempuh perjalanan sejaug 000 km dari Parma.
Itali menuju Shanghai.
Cina.
Salah satu metode perencanaan jalur yang digunakan adalah metode clothoid .
Pada tahun 2010 dan 2012.
Hyundai Motor Group menyelenggarakan kompetisi kendaraan otomatis di Korea.
Tantangan pada tahun 2010 difokuskan pada penghindaran rintangan dan mengikuti jalur .
ath followin.
Pada tahun 2012, tantangan difokuskan pada pemahaman sistem otonom terhadap kondisi perkotaan dan mendeteksi sinyal lalu lintas .
Beberapa teknik perencanaan jalur yang digunakan adalah clothoids .
, .
, dan RRT .
Salah satu kendaraan otonom yang telah disosialisasikan kepada masyarakat adalah mobil taksi otonom nuTonomy.
Mobil nuTonomy SingaporeAos One-North technology business district.
Mobil nuTonomy ini menggunakan algoritma perencanaan jalur RRT* untuk mengevaluasi banyak alternatif jalur potensial berdasarkan data dari kamera maupun sensor lainnya .
Adapun Karaman dkk.
menguji implementasi algoritma RRT* pada kendaraan otonom berupa robot forklift .
Melihat dari perkembangan implementasi algoritma perencanaan jalur yang digunakan pada kendaraan otonom diatas, dapat terlihat bahwa salah satu algoritma yang cukup sering digunakan adalah algoritma RRT.
Maka selanjutnya akan ditinjau proses-proses pengujian yang pernah dilakukan pada algoritma RRT dan variasinya.
IV.
ALGORITMA PERENCANAAN
JALUR DARI SUDUT PANDANG
FALSIFIKASI KARL POPPER
Popper berpendapat bahwa suatu teori atau pengetahuan baru dapat dipandang bersifat ilmiah jika dapat diuji .
melalui berbagai percobaan yang sistematis untuk menyangkalnya .
Jika suatu teori dapat bertahan terhadap berbagai macam pengujian dan penyangkalan, maka kebenaran dari suatu teori (Popper menyebutnya sebagai corroboratio.
Jika semakin besar upaya untuk menguji dan menyangkal suatu teori dan teori tersebut mampu untuk bertahan, maka akan semakin kokoh keberadaan teori tersebut .
Popper juga menegaskan bahwa setiap teori ilmiah hanya bersifat dugaan sementara .
dan tidak akan pernah tercapai kebenaran final.
Setiap teori selalu memiliki kemungkinan untuk tergantikan oleh teori lain yang lebih tepat.
Berdasarkan pembahasan bab i, dapat terlihat bahwa salah satu algoritma perencanaan jalur yang sering digunakan pada kendaraan otonom adalah algoritma RRT.
Maka pada bab IV ini akan dibahas pengujian-pengujian yang pernah dilakukan terhadap algoritma RRT dan variasinya Kemampuan algoritma RRT untuk bertahan terhadap berbagai macam pengujian, menurut Karl Popper, akan menunjukkan kekokohan dari algoritma RRT ini.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Algoritma dasar dari RRT ditunjukkan pada Gambar 2.
Adapun algoritma RRT* ditunjukkan pada Gambar 3 Ae Gambar 5.
Ilustrasi dari prinsip operasi chooseparent dan rewire pada RRT* ditunjukkan pada Gambar 6.
Algorithm 1 :
Gambar 2.
Algoritma dasar RRT Algorithm 2 :
Gambar 3.
Algoritma RRT* .
iadaptasi dari .
) Algorithm 3 :
Gambar 6.
Ilustrasi dari prinsip kerja RRT* .
Node baru ditentukan berdasarkan , .
Dipilih node-node terdekat dari dan dinamakan , .
Ditentukan yaitu node dari yang akan memberikan jarak terdekat antara dan node awal, .
Node lainnya pada akan dilakukan operasi rewire terhadap jika dapat dihasilkan jarak lebih dekat menuju node awal Uji Completness Algoritma RRT Gambar 4.
Operasi chooseparent pada algoritma RRT* .
iadaptasi dari .
) Algorithm 4 :
Gambar 5.
Operasi rewire pada algoritma RRT* .
iadaptasi dari .
) Uji completeness bertujuan mengetahui apakah algoritma RRT dapat memberikan solusi jika solusi itu ada.
LaValle pada publikasinya menyebutkan bahwa salah satu keunggulan dari RRT probabilistically complete .
Berdasarkan LaValle perkembangan pohon pencarian RRT seperti pada Gambar 7.
Pohon pencarian RRT akan cenderung mengekplorasi daerah yang belum Maka jika waktu pencarian yang diberikan itu memungkinkan, maka algoritma RRT akan dapat selalu memberikan solusi atau algoritma RRT bersifat komplit secara TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 7.
Perkembangan pohon pencarian pada algoritma RRT akan cenderung mengeksplorasi daerah yang belum terjelajahi .
Uji Optimality Algoritma RRT dan RRT* Uji optimality bertujuan mengetahui apakah algoritma RRT dan RRT* dapat memberikan solusi yang optimal.
Karaman pada publikasinya menyebutkan baha algoritma RRT tidak bersifat optimal, sedangkan algoritma RRT* memiliki .
Melalui eksperimen.
Karaman menunjukkan perbandingan pengujian algoritma RRT dan RRT* pada area tanpa rintangan, seperti yang ditunjukkan pada Gambar 8 dan Gambar 9.
Pada Gambar 8 menunjukkan bahwa meskipun jumlah iterasi terus ditambah, algoritma RRT tidak cenderung menghasilkan jalur yang optimal .
alur optimal pada area tanpa rintangan adalah garis lurus yang menghubungkan node awal dengan node akhi.
Adapun pada Gambar 9 menunjukkan bahwa dengan menambahkan jumlah iterasi, algoritma RRT* dapat cenderung menghasilkan jalur yang optimal .
alur yang dihasilkan algoritma RRT*, menghasilkan garis lurus yang menghubungkan node awal dan node akhi.
Uji Konvergensi Algoritma RRT.
RRT*, dan Informed RRT* Uji konvergensi dari algoritma RRT dan RRT* telah dilakukan oleh LaValle .
Karaman .
, dan Guevara .
Karaman melakukan pengujian dengan cara kedua algoritma dijalankan 20.
iterasi sebanyak 500 kali.
Lalu total jarak dari jalur terbaik dirata-ratakan pada tiap iterasi.
Hasilnya ditunjukkan pada Gambar 10.
Dapat terlihat bahwa algoritma RRT hanya dapat mendekati dalam skala faktor dari solusi optimal (LaValle juga melaporkan hasil yang Adapun algoritma RRT* dapat konvergen menuju solusi optimal.
Gambar 8.
Pengujian algoritma RRT pada area tanpa hambatan.
250 cabang, .
500 cabang, .
2500 cabang, .
000 cabang dan .
000 cabang .
Mirip dengan yang dilaporkan oleh Karaman.
Guevara juga melakukan uji konvergensi algoritma RRT.
RRT* dan Informed RRT* pada kasus area yang memiliki jalur yang sempit .
arrow ga.
Hasilnya ditunjukkan pada Gambar 11.
Terlihat bahwa algoritma RRT tidak menunjukkan peningkatan kualitas jalur, adapun RRT* Informed RRT* menunjukkan peningkatan kualitas jalur.
Pada kasus tersebut, algoritma informed RRT* lebih dahulu berhasil melewati jalur yang sempit daripada algoritma RRT*.
Pengujian Algoritma RRT* dan Variasinya pada Lingkungan Khusus Terdapat beberapa lingkungan khusus, yang telah diuji oleh beberapa peneliti, yang menunjukkan bahwa variasi dari RRT* memiliki keunggulan dibandingkan RRT* pada lingkungan Beberapa lingkungan khusus yang perencanaan jalur adalah maze .
, narrow .
elah sempi.
, trap .
uangan dengan celah sempit untuk masuk atau kelua.
serta clutter .
ingkungan dengan banyak rintanga.
TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
Gambar 11.
Grafik total jarak terhadap iterasi dari algoritma RRT.
RRT*, dan informed RRT*.
Ketiga algoritma dijalankan 10.
iterasi sebanyak 100 kali, .
area tanpa rintangan, .
area dengan rintangan .
Gambar 9.
Pengujian algoritma RRT* pada area tanpa hambatan.
250 cabang, .
500 cabang, .
2500 cabang, .
000 cabang dan .
000 cabang .
Gambar 12.
Algoritma RRT mampu membangun jalur yang melewati celah sempit .
, .
jika beruntung maka algoritma RRT dapat cepat melewati celah sempit, .
tetapi algoritma RRT terkadang membutuhkan waktu cukup lama untuk melewati celah sempit .
Gambar 10.
Total jarak terbaik dari algoritma RRT .
aris merah ata.
dan algoritma RRT* .
aris biru bawa.
Jalur optimal ditunjukkan oleh garis hitam putus-putus .
Elbanhawi .
melaporkan bahwa algoritma dasar RRT tetap bisa menemukan jalur menuju titik tujuan pada kasus narrow, trap, maupun clutter seperti yang ditunjukkan pada Gambar 12 dan Gambar 13.
Memang ada faktor keberuntungan pada kasus-kasus tersebut.
Seperti yang dicontohkan pada Gambar 12, jika beruntung, maka algoritma RRT dapat cukup cepat untuk melalui celah sempit dan mencapai titik tujuan seperti yang ditunjukkan pada Gambar 12 .
Tetapi adakalanya algoritma RRT membutuhkan waktu cukup lama untuk dapat melalui celah sempit seperti yang ditunjukkan pada Gambar 12 .
Adapun Nasir .
melaporkan bahwa algoritma RRT* mampu membangun jalur pada kasus labirin .
Gambar 13.
Algoritma RRT mampu membangun jalur pada kasus trap maupun .
Walaupun algoritma RRT dan RRT* mampu membangun jalur pada kasus maze, labirin, narrow, dan clutter, beberapa peneliti melaporkan performansi yang lebih baik untuk menyelesaikan kasus-kasus tersebut, jika menggunakan algoritma variasi dari RRT dan RRT* ini.
Nasir .
melaporkan bahwa penggunaan algoritma RRT*Smart dapat menghasilkan jalur yang lebih pendek dibandingkan penggunaan algoritma TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
RRT* untuk kasus maze, labirin, narrow, dan Noreen .
juga melaporkan informasi yang sama, yaitu penggunaan algoritma RRTSmart dapat mengurangi waktu komputasi dari RRT* dan dapat menghasilkan jalur yang lebih pendek dari algoritma RRT*.
Gammel .
melaporkan bahwa penggunaan algoritma Informed RRT* dapat mempercepat waktu komputasi dibandingkan penggunaan algoritma RRT*, seperti yang ditunjukkan pada Gambar 14.
Klemm .
juga melaporkan bahwa penggunaan algoritma RRT*-Connect dapat mempercepat waktu komputasi dibandingkan algoritma RRT*.
Jika strategi yang diusulkan oleh algoritma informed-RRT* adalah membatasi daerah pengambilan sampel hanya pada daerah elips yang mengelilingi simpul awal dengan simpul akhir, maka strategi yang diusulkan oleh algoritma RRT*-Connect adalah menggunakan pencarian dua arah dari algoritma RRT*, yaitu pencarian dimulai secara bersamaan dari titik awal dan titik akhir.
Gambar 14.
Algoritma RRT* dapat mencapai solusi optimal dalam waktu 8,26 detik, .
algoritma Informed RRT* dapat mencapai solusi optimal dalam waktu 0,76 detik .
Pengujian Algoritma RRT* pada Perencanaan Jalur Kendaraan Otonom Kuwata .
telah melaporkan berbagai pengujian variasi algoritma RRT* yaitu algoritma Closed-Loop RRT* untuk impelementasi pada perencanaan jalur kendaraan otonom.
Untuk mengevaluasi apakah lintasan yang direncanakan tidak akan menabrak rintangan atau melanggar aturan jalan raya, maka digunakan peta drivabiliy.
Semua data persepsi dari sensor, termasuk hambatan statis, hambatan dinamis, batas-batas jalur dan bahaya yang ada dipermukaan jalan disajikan dalam peta drivability ini.
Gambar 15 menunjukkan tampilan dari peta drivability.
Wilayah berwarna merah mewakili wilayah yang tidak dapat dilalui .
arena keluar jalur, adanya hambatan, dll.
Wilayah hitam adalah wilayah yang dapat dilalui dengan aman.
Wilayah abuabu, atau putih berarti wilayah tersebut masih dapat dilalui tetapi akan mendapat penalti.
Wilayah putih berarti berpenalti tinggi.
Nilai penalti diskalakan dengan warna skala abu-abu.
Adapun wilayah biru dinamakan "terbatas", yaitu kendaraan dapat melaju tetapi tidak boleh Contoh penggunaan daerah terbatas ini adalah saat terdapat hambatan di jalan.
Kendaraan akan berhenti dengan jarak yang cukup ke hambatan, seperti yang ditunjukkan pada Gambar 15.
Saat jalur telah memungkinkan untuk dilewati, maka kendaraan akan melewati area terbatas tersebut dan melewati hambatan yang ada dijalur.
Gambar 15.
Peta drivabiliy dan penjelasannya .
Gambar 16 menunjukkan proses navigasi wilayah yang memiliki hambatan.
Garis oranye adalah masukan ke pengontrol.
Masukan tersebut dihasilkan oleh algoritma pengambilan sampel.
Garis hijau menunjukkan lintasan prediksi yang Warna ungu yaitu mencapai Warna coklat muda yaitu aman tetapi tidak mencapai target.
Warna merah yaitu tidak aman.
Terlihat bahwa beberapa jalur telah berhasil mencapai tujuan.
Dapat terlihat bahwa jalur yang dihasilkan oleh algoritma Closed-Loop RRT ini telah memberikan jalur yang halus.
Gambar 16.
Perencanaan jalur di area dengan hambatan.
Titik start adalah di bagian bawah, dan tujuannya ada di sudut kiri atas .
Gambar 17 menujukkan pengujian untuk melakukan putaran balik (U-tur.
Melakukan putaran balik ini merupakan manuver yang cukup Sistem membangun tiga proses jalur yang TELEKONTRAN.
VOL.
NO.
OKTOBER 2019
saling berhubungan.
Jalur pertama mengarahkan kendaraan untuk bergerak ke kiri-depan untuk memulai belokan.
Jalur kedua mengarahkan kendaraan untuk bergerak mundur ke kanan.
Jalur ketiga mengarahkan kendaraan untuk bergerak ke kiri depan untuk menyelesaikan perputaran.
Gambar 17.
Perencanaan jalur untuk melakukan manuver putar Gambar 17a, 17b, dan 17c menunjukkan tiga tahapan jalur yang dirancang untuk melakukan putaran balik .
KESIMPULAN Makalah ini membahas penelitian survey mengenai algoritma perencanaan jalur dari sudut pandang filsafat ilmu Thomas S.
Khun dan Karl Popper.
Berdasarkan sudut pandang filsafat Thomas S.
Khun, telah dibahas perkembangan paradigma perencanaan jalur secara umum maupun perkembangan paradigma perencanaan jalur yang digunakan pada kendaraan otonom.
Adapun berdasarkan sudut pandang Karl Popper, telah dibahas berbagai pengujian atau usaha falsifikasi yang pernah dilakukan pada algoritmaalgoritma perencanaan jalur yang ada.
Pengujian yang dibahas pada paper ini meliputi uji completeness, uji optimality dan uji konvergensi.
Algoritma perencanana jalur dapat menunjukkan bahwa algoritma tersebut memiliki sifat completeness, optimality dan konvergen menuju nilai optimal.
Hasil falsifikasi terhadap algoritma perenanaan jalur ini menunjukkan penguatan nilai saintifik dari algoritma tersebut.
DAFTAR PUSTAKA