Filter Partikel

Perlakuan yang lebih teknis dari posting blog ini awalnya diterbitkan di blog Udacity .

Robot menggunakan algoritme yang sangat sederhana namun kuat untuk mencari tahu di mana mereka berada di peta, masalah yang disebut lokalisasi oleh para insinyur. Algoritme yang dikenal sebagai penyaringan partikel terlihat sangat keren. Bagian pertama dari artikel dua bagian ini diterbitkan di sini . Dalam artikel pertama ini, kami akan menjelaskan matematika yang diperlukan untuk membuat filter partikel Anda sendiri.

Mobil self -driving dirancang untuk berperilaku seperti pengemudi manusia. Sistem mobil self-driving tipikal dibangun dari enam komponen. Masing-masing dari enam komponen memecahkan masalah kritis yang diperlukan untuk mengemudi, otonom atau lainnya. Komponen dapat dianggap melakukan fungsi yang meniru driver manusia, yaitu:

Lokalisasi : Di ​​mana kita?
Perencanaan rute : Bagaimana kita mencapai tujuan?
Persepsi : Apa lagi yang ada di sekitarnya?
Prediksi : Seperti apa lingkungannya nanti?
Perencanaan : Jalan apa yang akan kita ikuti dalam beberapa detik ke depan?
Kontrol : Bagaimana kita akan mengikuti jalur yang kita inginkan?

Lokalisasi bagi manusia cenderung sangat mudah. Kami biasanya mengingat dari ingatan di mana kami berada di dunia, sering kali dibantu oleh perangkat GPS seperti ponsel cerdas yang membantu kami mengidentifikasi lokasi kami dengan lebih tepat di peta. Kami juga menggunakan petunjuk visual seperti rambu navigasi, marka jalur, dan pemahaman kami tentang kendaraan lain, jalan, dan lingkungan sekitar untuk memastikan bahwa kami selalu berada di jalur yang benar, di jalan yang benar, dan menuju ke arah yang benar.

Dalam hal lokalisasi, mengemudi otonom juga membutuhkan posisi dan arah kendaraan bergerak, disebut juga heading. Namun, berbeda dengan manusia, tingkat presisi yang dibutuhkan oleh kendaraan otonom sangatlah tinggi. Tidak cukup hanya mengetahui bahwa sebuah kendaraan berada di jalur yang benar dan berjalan sejajar dengan jalur tersebut. Presisi tinggi diperlukan untuk perencanaan. Jika pelokalan meleset lebih dari beberapa sentimeter tentang posisi atau lebih dari beberapa derajat tentang heading, komponen perencanaan mungkin menghasilkan jalur bencana yang mengakibatkan tabrakan di antara banyak hasil yang tidak diinginkan lainnya.

Seperti manusia, kendaraan otonom mendapatkan perkiraan posisi dan tujuan pertama mereka dari GPS. Penerima GPS, bahkan yang kecil yang ditemukan di smartphone, cenderung cukup akurat. Namun, ketepatan informasi lokalisasi yang diterima dari GPS tidak memadai untuk berkendara otonom yang aman. Misalnya, posisi yang dilaporkan dapat meleset dari satu meter hingga beberapa meter atau dalam kasus terburuk bahkan lebih.

Ketepatannya sering berfluktuasi dan sangat bergantung pada faktor-faktor seperti jumlah satelit yang terlihat oleh penerima, pantulan pancaran satelit dari objek besar seperti bangunan, dan penyerapan oleh elemen atmosfer.

Jika itu tidak cukup buruk, kecepatan pembaruan GPS untuk informasi lokalisasi juga cukup lambat, berkisar antara 1–10Hz. Bahkan pada 10Hz, kendaraan yang bergerak dengan kecepatan lambat 20Kmph akan bergerak sekitar setengah meter di antara dua pembaruan GPS.

Untuk mengurangi ketidakpastian lokalisasi akibat pergerakan, kendaraan otonom menggunakan unit pengukuran inersia (IMU). IMU cepat dan akurat serta mengukur akselerasi dan laju belokan kendaraan. Informasi ini kemudian dapat digunakan untuk memastikan posisi mobil di antara dua pembaruan GPS yang berurutan. IMU cenderung mengakumulasi kesalahan perkiraan kecil dari waktu ke waktu, tetapi bukan itu masalah yang kita hadapi di sini.

Masalah inti yang perlu dihadapi oleh sistem pelokalan adalah pembaruan GPS pada dasarnya tidak akurat. Alih-alih melaporkan posisi yang tepat, misalnya, GPS melaporkan area kecil di tanah di mana kemungkinan besar ada kendaraan saat GPS memperbarui dirinya sendiri. Kami menyebut area ini sebagai titik GPS.

Masalah melakukan pelokalan yang tepat direduksi menjadi masalah pengurangan area titik GPS.

Salah satu teknik yang telah digunakan dalam robotika untuk pelokalan yang akurat, mulai dari yang kurang akurat dikenal dengan penyaringan partikel . Ini berguna ketika lingkungan memiliki sejumlah landmark, yaitu objek besar dan tidak bergerak yang tidak sering berubah lokasi, tampilan, dan ukurannya. Ini bisa berupa bangunan, menara telepon seluler, pilar jembatan, tiang listrik atau sinyal lalu lintas, dan papan nama.

Untuk memahami bagaimana penyaringan partikel kita akan menggunakan analogi. Misalkan Anda kembali ke kamar hotel dengan lelah, matikan lampu dan rebahkan diri di tempat tidur telungkup. Anda bangun di tengah malam dan ingin mencari tahu di mana Anda berada. Tentu saja, Anda ingat menabrak tempat tidur tetapi Anda ingin tahu ke arah mana Anda menghadap, di mana sakelar lampu dan di mana sandal Anda berada. Ini membutuhkan lebih banyak akurasi daripada ingatan samar berada di tempat tidur.

Untuk mengorientasikan diri Anda dengan cepat, Anda memanfaatkan lingkungan sekitar. Anda pertama kali membayangkan diri Anda berada di lokasi berbeda di tempat tidur. Kemudian Anda merasakan objek 'tengara' di sekitarnya dengan menyentuh dan mengidentifikasinya. Anda mungkin mendorong botol air dari meja terdekat atau membenturkan jari kaki Anda ke kursi. Pengamatan ini memberi Anda petunjuk penting tentang kemungkinan besar Anda berada di dunia ranjang hotel. Karena Anda ingat letak botol, meja, dan kursi relatif terhadap tempat tidur, Anda dapat menyimpulkan posisi Anda di tempat tidur dengan lebih akurat. Dengan setiap observasi baru, Anda dapat mengesampingkan lokasi tertentu di tempat tidur dan meningkatkan peluang Anda untuk berada di lokasi lain.

Inilah cara kerja penyaringan partikel untuk kendaraan otonom. Berbekal titik GPS awal, kendaraan mengetahui posisi kasarnya dan arahnya di peta. Posisi kasar ini kemudian dibagi menjadi sel-sel imajiner kecil. Kendaraan juga mengetahui landmark mana yang ada di sekitar lokasi kasar itu. Kendaraan kemudian menyelidiki jarak ke landmark ini menggunakan lidar onboard. Sistem lokalisasi kemudian menghitung pengukuran ini terhadap setiap sel imajiner. Karena semakin banyak landmark yang diperiksa, sebagian besar sel dikesampingkan dan hanya beberapa yang kemungkinan besar tetap sebagai lokasi yang memungkinkan.

Penyaringan partikel nama berasal dari fakta bahwa lokasi setiap sel imajiner direpresentasikan sebagai partikel di peta dan kami mengesampingkan partikel dengan memfilternya dengan menghitung jarak ke tengara dan membuang partikel yang tampaknya tidak berada pada jarak yang tepat dari landmark.

Animasi di bawah menunjukkan lokasi awal partikel yang membentang di area yang cukup luas, yang dapat tersebar di beberapa jalur, jalan, dan area terbuka. Penginderaan atau penyelidikan lingkungan ditunjukkan oleh sinar Biru. Titik hijau yang mewakili posisi yang paling mungkin awalnya melompat di sekitar peta tetapi mengendap dengan sangat cepat karena semakin banyak partikel yang dikesampingkan dengan merasakan lingkungan.

Pemfilteran partikel adalah algoritme yang sangat sederhana yang menggerakkan banyak robot dan mobil otonom. Nvidia Drive Labs telah merilis video singkat tentang bagaimana pelokalan dapat memperoleh manfaat dari peta yang kaya, dengan berbagai tempat terkenal. Uber ATG telah menerbitkan sebuah blog tentang bagaimana mereka meningkatkan akurasi GPS di sini .