Pengantar Teknik Kontrol: Perencanaan Jalur — A*, Dijkstra, RRT, RRT*, dan PRM

Contents — find the section you need

Memindahkan robot dari titik awal ke tujuan jarang berarti menggambar garis lurus. Rencana yang dapat digunakan harus memperhitungkan dinding, lebar jalur, jejak robot, batas belok, ketidakpastian lokalisasi, peta usang, pergerakan orang, dan jarak berhenti. Perencanaan jalur memilih ke mana harus pergi; pembangkitan dan kontrol lintasan menentukan bagaimana mengikuti rute tersebut dalam dinamika. Tumpukan yang aman menjaga tanggung jawab tersebut tetap terpisah sambil berbagi batasannya.

Panduan ini membandingkan Dijkstra grid dan A dengan RRT ruang kontinu, RRT, dan PRM. Ini menjelaskan inflasi rintangan, heuristik, pengambilan sampel, kompleksitas, integrasi SLAM/Nav2, pemeriksaan implementasi, dan perilaku keselamatan independen. Lihat Panduan Visual SLAM, Panduan ROS 2, dan Panduan Penggabungan Sensor untuk lapisan yang berdekatan.

Kesimpulan Praktis

Dijkstra menjamin jalur terpendek pada graf berbobot non-negatif tetapi meluas ke arah yang tidak terkait dengan tujuan. A* mengarahkan perluasan dengan heuristik yang dapat diterima sambil mempertahankan optimalitas yang sama.
RRT cenderung menemukan jalur yang layak dengan cepat di ruang kontinu berdimensi tinggi. RRT* mendekati jalur optimal seiring bertambahnya sampel, dengan biaya tetangga dan pengkabelan ulang tambahan. PRM mengamortisasi konstruksi peta jalan di banyak kueri dalam ruang yang cukup statis.
Jalur terpendek melalui peta yang tidak diinflasi adalah jalur tabrakan untuk robot dengan radius, kesalahan lokalisasi, dan jarak berhenti.
Rute yang dikembalikan bukanlah bukti keamanan. Kesegaran peta, penginderaan lokal, kesalahan pelacakan, rintangan dinamis, latensi perencanaan ulang, dan penghentian darurat perlu ditangani secara independen.

Definisikan ruang bebas sebelum memilih algoritma

Misalkan ruang keadaan adalah $\mathcal X$ , ruang rintangan $\mathcal X_{obs}$ , dan ruang bebas $\mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs}$ . Jalur $\sigma:[0,1]\to\mathcal X_{free}$ menghubungkan $x_s$ ke $x_g$ , dengan $\sigma(0)=x_s,\sigma(1)=x_g$ . Robot titik dalam 2D menggunakan $x=(x,y)$ ; kendaraan menambahkan arah $\theta$ , kecepatan, dan kemudi; manipulator mencakup semua sudut sendi. Penyederhanaan keadaan mengurangi biaya pencarian tetapi dapat menghasilkan kurva yang tidak dapat direalisasikan oleh kendaraan hilir.

Inflasi rintangan mengubah robot terbatas menjadi pencarian titik dengan memperluas rintangan. Di sini $r_{loc}$ harus berupa istilah ketidakpastian yang dinyatakan, seperti radius yang dipilih untuk tingkat kepercayaan yang ditentukan, daripada kesalahan rata-rata yang tidak ditentukan. Minimum konseptual adalah

r_{inflate}=r_{robot}+r_{loc}+r_{safe}

di mana $r_{robot}$ adalah radius badan, ketidakpastian lokalisasi diwakili oleh istilah sebelumnya, dan $r_{safe}$ adalah margin pelacakan/penghentian. Pada kenyataannya, margin bervariasi tergantung pada resolusi peta, titik buta sensor, kecepatan objek yang mendekat, dan kemampuan pengereman. Margin yang terlalu kecil menyebabkan tabrakan; margin yang terlalu besar membuat jalur yang layak dilewati menjadi tidak mungkin.

Diagram: Duskcoil, konseptual dan bukan terukur. Ukuran sel dan inflasi harus diturunkan dari jejak robot nyata, ketidakpastian, dan amplop operasi.

Pencarian grid: Dijkstra dan A*

Untuk grafik $G=(V,E)$ dengan biaya tepi non-negatif $c(u,v)\ge0$ , Dijkstra berulang kali menyelesaikan simpul yang belum diselesaikan dengan biaya awal terendah yang diketahui $g(n)$ dan merelaksasi tetangga. Setelah diselesaikan, nilai $g$ adalah yang terpendek. Dengan biner Dalam algoritma heap, kompleksitas representatifnya adalah $O((|V|+|E|)\log|V|)$ . Algoritma ini menjamin jarak graf terpendek, tetapi tanpa pengetahuan tujuan, cenderung meluas secara luas.

A* mengurutkan node berdasarkan

f(n)=g(n)+h(n)

di mana $h(n)$ adalah batas bawah biaya yang tersisa. Heuristik yang dapat diterima tidak pernah melebih-lebihkan biaya yang tersisa; maka A* tetap optimal. Jarak Manhattan cocok untuk grid 4-terhubung, sedangkan jarak Euclidean atau Chebyshev mungkin cocok untuk pergerakan 8-terhubung. Heuristik yang konsisten juga memenuhi $h(n)\le c(n,n')+h(n')$ dan mengurangi perluasan ulang.

A* berbobot menskalakan heuristik dengan $w>1$ untuk mencari rute yang layak lebih cepat dengan mengorbankan optimalitas. Ini bisa menjadi pertukaran operasional yang baik jika dinyatakan secara eksplisit. Biaya tepi dapat mengkodekan tidak hanya panjang tetapi juga risiko hambatan yang meningkat, jarak bebas, belokan, energi, atau medan. Output kemudian didefinisikan minimum. Biaya, bukan panjang geometris minimum.

Ruang kontinu dan berdimensi tinggi: RRT, RRT*, PRM

Kisi-kisi halus meledak dalam ruang konfigurasi lengan enam sendi atau ruang posisi kendaraan. RRT mengambil sampel $x_{rand}$ dari ruang bebas, menemukan simpul pohon terdekat $x_{near}$ , mengarahkan jarak terbatas ke arahnya, memeriksa tabrakan, dan menambahkan $x_{new}$ . Ini lengkap secara probabilistik: dengan cukup banyak sampel, probabilitas menemukan rute yang layak mendekati satu jika ada. Ini tidak menjamin rute pertama yang pendek.

RRT* memilih induk dengan biaya terendah di antara simpul terdekat dan menghubungkan kembali tetangga melalui simpul baru jika lebih murah. Ini optimal secara asimtotik, bukan optimal dalam waktu terbatas; pencarian tetangga, pengujian tabrakan, dan penghubungan kembali mengkonsumsi komputasi. Ukur kualitas pada batas waktu operasional daripada menjanjikan "optimal."

PRM mengambil sampel konfigurasi bebas dan menghubungkan pasangan bebas tabrakan di dekatnya menjadi peta jalan yang dapat digunakan kembali. Ini menarik dalam pengaturan pabrik statis atau kueri lengan berulang karena pra-pemrosesan dapat diamortisasi. Hambatan dinamis membatalkan tepi. Lorong sempit sulit untuk pengambilan sampel seragam, sehingga sampel batas hambatan, bias jalur, atau informasi tugas mungkin diperlukan.

Diagram: Duskcoil, disederhanakan. Pengambilan sampel, pengecekan tabrakan, dan konektivitas bukanlah pengukuran kinerja atau rute produksi akhir.

Metode	Ruang / biaya representatif	Properti hasil	Kecocokan yang baik	Mode kegagalan utama
Dijkstra	graf, $O((V+E)\log V)$	jalur terpendek dengan biaya non-negatif	tanpa heuristik, bidang biaya penuh	meluas menjauh dari tujuan
A*	graf; kasus terburuk sebanding	jalur terpendek dengan $h$ yang dapat diterima	kueri grid tunggal	melebih-lebihkan $h$ , biaya buruk
RRT	kontinu; bergantung pada sampel	lengkap secara probabilistik	rute high-D yang cepat dan layak	jalur sempit, pemeriksaan tabrakan kasar
RRT*	kontinu; overhead pengkabelan ulang	optimal secara asimtotik	meningkatkan selagi waktu tersisa	tenggat waktu/waktu eksekusi
PRM	pra-pemrosesan plus kueri	lengkap secara probabilistik dengan kondisi pengambilan sampel	kueri berulang statis	tepi usang di ruang dinamis

SLAM, Nav2, dan perencanaan lokal

SLAM menyediakan peta dan estimasi posisi, tetapi perencana membutuhkan transformasi yang selaras dengan stempel waktu dan makna okupansi/biaya yang jelas. Penutupan loop atau relokalisasi dapat menggeser posisi bingkai peta; terus mengikuti rute lama dapat berbahaya. Masukkan ketidakpastian, pengaturan ulang lokalisasi, dan peristiwa pembaruan peta ke dalam aturan perencanaan ulang; lihat Panduan Visual SLAM.

Dalam arsitektur ROS 2 yang mirip Nav2, peta biaya global dan perencana memilih rute skala besar, sementara peta biaya lokal dan pengontrol menangani rintangan dan kecepatan di dekatnya. Algoritma A* global dapat memilih koridor; lapisan lokal harus mengalah, berhenti, atau berbelok di sekitar seseorang. Lapisan yang sepenuhnya lokal dapat terjebak di jalan buntu. Definisikan perencana, pengontrol, pemulihan, tingkat pembaruan peta, tenggat waktu, dan prioritas secara eksplisit. Transportasi ROS 2 yang dijelaskan dalam ROS 2 Primer bukanlah jaminan waktu nyata atau keamanan.

Sebelum penyebaran, ukur jejak termasuk muatan, bidang pandang sensor, kecepatan/perlambatan maksimum, kesalahan lokalisasi, dan resolusi peta. Uji jarak bebas aktual di lorong sempit. Periksa tabrakan jalur yang direncanakan terhadap gerakan kontinu dan kinematika: rute grid dapat berbelok antar sel dengan cara yang tidak dapat dilakukan oleh penggerak diferensial, mobil, atau lengan robot.

Untuk rintangan dinamis, ukur kesegaran deteksi, kecepatan relatif, jarak pengereman, dan waktu perencanaan ulang; jangan pernah terus bergerak karena perencana terlambat. Perlakukan orang yang tidak dikenal, lubang, rintangan transparan, dan kegagalan sensor sebagai kasus keamanan, bukan sel yang secara otomatis bebas. Perlambat, berhenti, atau serahkan kendali jika tidak ada rute, jalur lokal tidak aman, kovariansi terlalu besar, peta usang, atau kesalahan pelacakan melebihi batasnya. Penghentian darurat harus beroperasi secara independen dari keluaran perencana.

Daftar Periksa Implementasi dan Keamanan

Definisikan ruang keadaan, jejak, bingkai, resolusi peta, dan arti sel yang tidak dikenal.
Pastikan inflasi mencakup kesalahan lokalisasi, kecepatan, dan jarak berhenti; uji jalur sempit yang sebenarnya.
Verifikasi penerimaan heuristik atau dokumentasikan jaminan yang sengaja dilonggarkan.
Catat resolusi pemeriksaan tabrakan, benih acak, tenggat waktu, dan perilaku tanpa solusi untuk perencana pengambilan sampel.
Suntikkan relokalisasi, perubahan peta, hilangnya sensor, rintangan dinamis, dan penundaan komunikasi.
Verifikasi pemberhentian yang aman dan jalur log yang dapat didiagnosis untuk kejadian tanpa rute, peta usang, dan penyimpangan pelacakan.

Referensi

Periksa pemahaman Anda

Bisakah kendaraan mengikuti jalur bebas hambatan apa pun?

Jejak kendaraan dan batasan belok penting. Jalur untuk suatu titik belum tentu layak untuk kendaraan.

Try it in the browser

Lab Change the conditions in a browser experimentNav2 memiliki jalur tetapi tidak bergerak: alur kerja diagnostik.

Pengantar Teknik Kontrol: Perencanaan Jalur — A, Dijkstra, RRT, RRT, dan PRM