Algoritma pencarian jalan untuk peta kontinu (misalnya poligon)
Saya mencoba untuk menyelidiki algoritma yang berbeda untuk jalur pendek antara dua titik dalam bidang dengan rintangan poligonal. Sebagian besar algoritma yang saya temukan menggunakan peta diskrit (Peta Kisi, grafik visibilitas, Peta Jalan Voronoi, dll.). Beberapa buku (seperti "Elements of Robotics" oleh Ben-Ari atau "Introduction to Autonomous Robots" oleh Nikolaus Correll) menyebutkan peta kontinu (misalnya data poligon mentah), tetapi tidak menjelaskan algoritme yang sesuai. Mereka mengklaim keunggulan memori atau efisiensi untuk sedikit dan rintangan sederhana, yang bisa sangat menarik bagi saya.
Saya percaya, harus ada pendekatan yang cerdas dengan menggunakan kalkulasi geometris (misalnya deteksi persimpangan) dan beberapa paradigma algoritmik (misalnya dengan biaya paling rendah pada cabang dan terikat), tetapi saya tidak ingin menemukan kembali roda dengan buruk.
Apakah ada sumber daya untuk beberapa algoritme jalur pendek (est) yang menggunakan peta berkelanjutan atau kata kunci yang berguna untuk dicari?
Seperti yang disarankan, saya mencoba menentukan beberapa istilah yang saya gunakan:
Peta kontinu (lihat Gambar. ) Mengacu pada penyimpanan nilai bilangan real (kontinu) dari bentuk geometris. Rintangan / Segitiga I. akan disimpan sebagai: A = (3,2), B = (7,5), C = (7,2).
Peta diskrit (lihat Gambar. ) Mengacu pada sub-divisi menjadi potongan-potongan (diskritisasi, misalnya seperti di peta grid). Obstacle / Triangle I. sekarang akan disimpan sebagai indeks sel: (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) pencarian jalan dalam peta diskrit sering kali dilakukan dengan algoritma berbasis grafik seperti Dijkstra atau A *.
Perhitungan geometris hanyalah istilah samar yang saya gunakan untuk operasi geometri komputasi yang saya harapkan dalam algoritma pencarian jalan untuk peta kontinu. (mis. Terjemahan, jarak tegak lurus, deteksi persimpangan)
Jawaban
Untuk "peta kontinu" seperti yang Anda sebut, cukup gunakan Dijkstra pada semua simpul Anda. Satu-satunya perbedaan adalah Anda harus memeriksa pemotongan saat menghitung jarak antar node.
Istilah lain yang lebih sering digunakan untuk masalah saya tampaknya adalah Jalur Terpendek Euclidean . Perbedaan antara algoritme untuk peta Kontinu dan peta Diskrit tampaknya agak ambigu bagi saya.
Namun, hal terdekat yang saya temukan pada algoritma untuk peta kontinu adalah Algoritma Mitchell untuk Masalah Dijkstra Berkelanjutan (atau metode Dijkstra berkelanjutan). Algoritma ini menggunakan wavelet yang menyebar secara merata dari titik awal. Dengan “difraksi” wavelet, mereka mencapai area yang tidak dapat dijangkau secara langsung. Ini membuat peta jalur terpendek yang dapat digunakan untuk mengidentifikasi jalur terpendek Euclidean ke titik mana pun dalam ruang konfigurasi berkelanjutan.
Untuk lebih lanjut lihat:
- "Jalur Terpendek Euclidean Tepat atau Algoritma Perkiraan" oleh F. Li dan R. Klette
- animasi yang bagus tapi agak buggy oleh Ivan Chen
- aplikasi oleh Anton Kovsharov
Orang mungkin berpendapat, bahwa peta jalur terpendek yang dibuat hanyalah diskritisasi lain dari ruang konfigurasi berkelanjutan. Namun, saya kira peta jalur terpendek hanyalah hasil yang dapat diperoleh, jika algoritme diterapkan ke seluruh ruang konfigurasi. Jika hanya jalur terpendek antara dua titik yang diinginkan, algoritme dapat berhenti setelah mencapai titik target. Saya tetap tidak yakin tentang klasifikasi algoritme ini tetapi ini harus menjawab pertanyaan saya.