Pemetaan dan lokalisasi serentak

Pemetaan dan lokalisasi serentak ( PDLS ) adalah masalah komputasi dalam membangun atau memperbarui peta lingkungan yang tidak diketahui sekaligus melacak lokasi agen di dalamnya. Meskipun awalnya masalah ini tampak seperti masalah ayam atau telur, ada beberapa algoritme yang diketahui dapat menyelesaikannya, setidaknya dalam waktu kira-kira, dalam waktu yang dapat disesuaikan untuk lingkungan tertentu. Metode solusi perkiraan yang populer mencakup filter partikel, filter Kalman yang diperluas, persimpangan kovarians, dan GraphSLAM. Algoritme PDLS didasarkan pada konsep geometri komputasi dan visi komputer, dan digunakan dalam navigasi robot, pemetaan robot, dan odometri untuk realitas virtual atau realitas tertambah .

Pemenang DARPA Grand Challenge 2005 Stanley melakukan PDLS sebagai bagian dari sistem penggerak otonomnya.

Peta yang dihasilkan oleh Robot PDLS

Deskripsi matematis dari masalah tersebut

Diberikan serangkaian kontrol $u_{t}$ dan pengamatan sensor $o_{t}$ melalui langkah waktu diskrit $t$, masalah PDLS adalah menghitung perkiraan status agen $x_{t}$ dan peta lingkungan $m_{t}$ . Semua besaran biasanya bersifat probabilistik, jadi tujuannya adalah untuk menghitung

$P(m_{t+1},x_{t+1}|o_{1:t+1},u_{1:t})$

Penerapan aturan Bayes memberikan kerangka kerja untuk memperbarui posterior lokasi secara berurutan, dengan adanya peta dan fungsi transisi $P(x_{t}|x_{t-1})$ ,

$P(x_{t}|o_{1:t},u_{1:t},m_{t})=\sum _{m_{t-1}}P(o_{t}|x_{t},m_{t},u_{1:t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1},u_{1:t})/Z$

Demikian pula peta dapat diperbarui secara berurutan

$P(m_{t}|x_{t},o_{1:t},u_{1:t})=\sum _{x_{t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t},u_{1:t})P(m_{t-1},x_{t}|o_{1:t-1},m_{t-1},u_{1:t})$

Seperti banyak masalah inferensi, solusi untuk menyimpulkan dua variabel bersama-sama dapat ditemukan, hingga mencapai solusi optimal lokal, dengan memperbarui dua keyakinan secara bergantian dalam bentuk algoritma ekspektasi-maksimalisasi .

Algoritma

Teknik statistik yang digunakan untuk memperkirakan persamaan di atas mencakup filter Kalman dan filter partikel (algoritme di balik Lokalisasi Monte Carlo). Mereka memberikan perkiraan distribusi probabilitas posterior untuk pose robot dan parameter peta. Metode yang secara konservatif memperkirakan model di atas menggunakan persimpangan kovarians dapat menghindari ketergantungan pada asumsi independensi statistik untuk mengurangi kompleksitas algoritmik untuk aplikasi skala besar. Metode perkiraan lainnya mencapai peningkatan efisiensi komputasi dengan menggunakan representasi ketidakpastian wilayah terbatas yang sederhana.

Teknik keanggotaan himpunan terutama didasarkan pada propagasi batasan interval . Mereka menyediakan satu set yang mencakup pose robot dan satu set perkiraan peta. Penyesuaian bundel, dan lebih umum lagi estimasi maksimum a posteriori (MAP), adalah teknik populer lainnya untuk PDLS menggunakan data gambar, yang secara bersama-sama memperkirakan pose dan posisi landmark, meningkatkan fidelitas peta, dan digunakan dalam sistem PDLS yang dikomersialkan seperti ARCore Google yang menggantikannya. Anjungan komputasi realitas berimbuh sebelumnya bernama Tango, sebelumnya Project Tango . Penaksir PDLS menghitung penjelasan yang paling mungkin dari pose robot dan peta berdasarkan data sensor, daripada mencoba memperkirakan keseluruhan probabilitas posterior.

Algoritme PDLS baru tetap menjadi area penelitian aktif, dan sering kali didorong oleh perbedaan persyaratan dan asumsi tentang jenis peta, sensor, dan model seperti yang dijelaskan di bawah. Banyak sistem PDLS yang dapat dipandang sebagai kombinasi pilihan dari masing-masing aspek ini.

Pemetaan

Peta topologi adalah metode representasi lingkungan yang menangkap konektivitas (yaitu topologi) lingkungan daripada membuat peta yang akurat secara geometris. Pendekatan PDLS topologi telah digunakan untuk menegakkan konsistensi global dalam algoritma PDLS metrik.

Sebaliknya, peta rajah menggunakan larik (biasanya persegi atau heksagonal) sel yang didiskritisasi untuk mewakili dunia topologi, dan membuat kesimpulan tentang sel mana yang ditempati. Biasanya sel diasumsikan independen secara statistik untuk menyederhanakan perhitungan. Dengan asumsi seperti itu, $P(m_{t}|x_{t},m_{t-1},o_{t})$ disetel ke 1 jika sel peta baru konsisten dengan pengamatan $o_{t}$ di lokasi $x_{t}$ dan 0 jika tidak konsisten.

Mobil swakendara modern kebanyakan menyederhanakan masalah pemetaan menjadi hampir tidak ada, dengan memanfaatkan secara ekstensif data peta yang sangat rinci yang dikumpulkan sebelumnya. Hal ini dapat mencakup anotasi peta hingga tingkat penandaan lokasi setiap segmen garis putih dan tepi jalan di jalan. Data visual yang diberi tag lokasi seperti Google StreetView juga dapat digunakan sebagai bagian dari peta. Pada dasarnya sistem seperti itu menyederhanakan masalah PDLS menjadi tugas lokalisasi yang lebih sederhana, mungkin memungkinkan objek bergerak seperti mobil dan orang hanya diperbarui di peta pada saat waktu berjalan.

Pengindraan

PDLS akan selalu menggunakan beberapa jenis sensor yang berbeda, dan kekuatan serta batasan berbagai jenis sensor telah menjadi pendorong utama algoritma baru. Independensi statistik adalah persyaratan wajib untuk mengatasi bias metrik dan gangguan dalam pengukuran. Jenis sensor yang berbeda menimbulkan algoritma PDLS yang berbeda yang asumsinya paling sesuai untuk sensor tersebut. Pada satu sisi ekstrem, pemindaian laser atau fitur visual memberikan detail banyak titik dalam suatu area, terkadang menjadikan inferensi PDLS tidak diperlukan karena bentuk di awan titik ini dapat dengan mudah dan jelas diselaraskan pada setiap langkah melalui registrasi gambar . Sebaliknya, sensor taktil sangat jarang karena hanya berisi informasi tentang titik yang sangat dekat dengan agen, sehingga memerlukan model sebelumnya yang kuat untuk mengimbanginya dalam PDLS taktil murni. Sebagian besar tugas PDLS praktis berada di antara ekstrem visual dan sentuhan ini.

Model sensor terbagi menjadi pendekatan berbasis landmark dan data mentah. Bangunan terkenal adalah objek yang dapat diidentifikasi secara unik di dunia yang lokasinya dapat diperkirakan menggunakan sensor, misalnya titik akses Wi-Fi atau suar radio. Pendekatan data mentah tidak membuat asumsi bahwa tengara dapat diidentifikasi, melainkan membuat model $P(o_{t}|x_{t})$ secara langsung sebagai fungsi lokasi.

Sensor optik dapat berupa pengukur jarak laser satu dimensi (sinar tunggal) atau 2D (menyapu), deteksi dan jangkauan cahaya definisi tinggi 3D ( lidar ), denyar lidar 3D, sensor sonar 2D atau 3D, dan satu atau lebih kamera 2D. Sejak tahun 2005, terdapat penelitian intensif terhadap PDLS visual (PDLSV) yang terutama menggunakan sensor visual (kamera), karena semakin banyaknya kamera yang ada di mana-mana seperti yang ada di perangkat seluler. Sensor visual dan lidar cukup informatif untuk memungkinkan ekstraksi landmark dalam banyak kasus. Bentuk PDLS terbaru lainnya termasuk PDLS taktil (penginderaan hanya dengan sentuhan lokal), PDLS radar, PDLS akustik, dan Wi-Fi-SLAM (penginderaan berdasarkan kekuatan titik akses Wi-Fi terdekat). Pendekatan terbaru menerapkan jangkauan nirkabel kuasi-optik untuk multi-laterasi ( sistem lokasi waktu nyata (RTLS)) atau multi-angulasi dalam hubungannya dengan PDLS sebagai penghormatan terhadap tindakan nirkabel yang tidak menentu. Semacam PDLS untuk pejalan kaki manusia menggunakan unit pengukuran inersia yang dipasang di sepatu sebagai sensor utama dan mengandalkan fakta bahwa pejalan kaki dapat menghindari dinding untuk secara otomatis membuat denah lantai bangunan melalui sistem penentuan posisi dalam ruangan .

Untuk beberapa aplikasi luar ruangan, kebutuhan akan PDLS hampir seluruhnya dihilangkan karena sensor SPG diferensial presisi tinggi. Dari perspektif PDLS, ini dapat dipandang sebagai sensor lokasi yang kemungkinannya sangat tajam sehingga mendominasi inferensi sepenuhnya. Namun, sensor PDLS kadang-kadang dapat menurun atau mati seluruhnya, misalnya pada saat konflik militer, yang merupakan hal yang menarik bagi beberapa aplikasi robotika.

Pemodelan kinematika

Itu $P(x_{t}|x_{t-1})$ istilah ini mewakili kinematika model, yang biasanya mencakup informasi tentang perintah tindakan yang diberikan kepada robot. Sebagai bagian dari model, kinematika robot disertakan, untuk meningkatkan perkiraan penginderaan dalam kondisi kebisingan bawaan dan kebisingan sekitar. Model dinamis menyeimbangkan kontribusi dari berbagai sensor, berbagai model kesalahan parsial, dan akhirnya terdiri dari penggambaran virtual yang tajam sebagai peta dengan lokasi dan arah robot sebagai awan peluang. Pemetaan adalah penggambaran akhir dari model tersebut, peta adalah penggambaran tersebut atau istilah abstrak untuk model tersebut.

Memindahkan benda

Lingkungan non-statis, seperti lingkungan yang berisi kendaraan lain atau pejalan kaki, terus menghadirkan tantangan penelitian. PDLS dengan DATMO adalah model yang melacak objek bergerak dengan cara yang mirip dengan agen itu sendiri.

Gelung tutupan

Gelung tutupan adalah masalah dalam mengenali lokasi yang dikunjungi sebelumnya dan memperbarui keyakinan yang sesuai. Hal ini dapat menjadi masalah karena kesalahan model atau algoritme dapat menetapkan prioritas rendah pada suatu lokasi. Metode Gelung tutupan yang umum menerapkan algoritma kedua untuk menghitung beberapa jenis sensor yang mengukur kesamaan, dan mengatur ulang lokasi sebelumnya ketika kecocokan terdeteksi. Misalnya, hal ini dapat dilakukan dengan menyimpan dan membandingkan fitur transformasi fitur invarian skala (SIFT) vektor kumpulan kata dari setiap lokasi yang dikunjungi sebelumnya.