Apa cara yang efisien untuk mengunjungi setiap ruang yang dapat dijangkau di grid dengan hambatan yang tidak diketahui?

Saya mencoba membuat peta hambatan dalam ruang grid 2D yang cukup kasar, menggunakan eksplorasi. Saya mendeteksi hambatan dengan mencoba bergerak dari satu ruang ke ruang yang berdekatan, dan jika itu gagal maka ada hambatan di ruang tujuan (tidak ada konsep sensor rangefinding dalam masalah ini).

contoh kisi http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif (misalnya)

Proses selesai ketika semua kotak yang dapat dijangkau telah dikunjungi. Dengan kata lain, beberapa ruang mungkin benar-benar tidak dapat dijangkau bahkan jika mereka tidak memiliki hambatan karena dikelilingi. Ini diharapkan.

Dalam kasus yang paling sederhana, saya bisa menggunakan algoritma DFS , tapi saya khawatir ini akan memakan waktu terlalu lama untuk diselesaikan - robot akan menghabiskan lebih banyak waktu mundur daripada menjelajahi wilayah baru. Saya berharap ini menjadi sangat bermasalah ketika mencoba untuk mencapai kotak yang tidak terjangkau, karena robot akan menghabiskan semua pilihan.

Dalam metode yang lebih canggih, yang harus dilakukan adalah dekomposisi sel Boustrophedon .

Namun, saya tidak bisa menemukan deskripsi yang baik dari algoritma dekomposisi sel Boustrophedon (yaitu, deskripsi lengkap dalam istilah sederhana). Ada sumber daya seperti ini , atau yang lebih umum ini pada dekomposisi sel vertikal tetapi mereka tidak menawarkan banyak wawasan tentang algoritma tingkat tinggi maupun struktur data tingkat rendah yang terlibat.

Bagaimana saya bisa mengunjungi (memetakan) grid ini secara efisien? Jika ada, saya ingin algoritma yang berkinerja lebih baik daripada $O(n^2)$ sehubungan dengan jumlah total kotak kuadrat ( yaitu lebih baik daripada $O(n^4)$ untuk $n*n$ grid).

Dekomposisi sel Boustrophedon adalah hanya membagi lingkungan menjadi daerah-daerah yang dapat secara efisien ditutupi oleh jalur boustrophedon. Dekomposisi trapesium akan dilakukan, dan dapat dilakukan dengan menggunakan algoritma garis-sapuan. Lihat [Choset 2000], situs web ini , atau (saya sarankan!) Buku yang luar biasa "Computational Geometry" oleh Mark de Berg, et. al, untuk deskripsi lengkap tentang struktur data dan algoritma yang diperlukan.

Choset, Howie. "Cakupan Ruang yang Diketahui: Dekomposisi Seluler Boustrophedon" Autonomous Robots , 2000.

Sebagai contoh, anggap set hambatan sebagai tepi dan simpul. Katakanlah lingkungan juga dibatasi oleh poligon khusus. Kami memiliki sesuatu seperti berikut ini. Untuk menguraikan ruang ini, kami cukup menambahkan tepi vertikal antara setiap dhuwur dan garis terdekat atau dhuwur.

Untuk mencapai ini dalam kode, Anda hanya perlu tes persimpangan garis-segmen, daftar tepi yang diurutkan, dan daftar simpul yang diurutkan.

1. $v_i$
2. $l_i$$v_i$
3. Di setiap persimpangan, buat simpul baru.

Ketika ini dilakukan, himpunan tepi dan simpul baru hanya mencakup trapesium. Tapi saya tekankan, Anda tidak bisa melakukan ini secara online (tanpa pengetahuan sebelumnya tentang hambatannya). Jika Anda ingin melakukan cakupan yang kuat tanpa sepengetahuan sebelumnya, Anda mungkin melihat "algoritma bug". Secara khusus, inilah algoritma sederhana, dengan asumsi lingkungan dibatasi.

1. Dari posisi awal, gerakkan ke atas dan ke kiri hingga Anda mencapai sudut kiri atas lingkungan. Jika Anda menemui hambatan terlebih dahulu, Anda harus berkeliling. Anda tahu ada sesuatu yang menjadi kendala jika bisa dielakkan (benjolan dan bergerak).

2. Dari kiri atas, bergerak ke kanan hingga Anda menemukan batas. Kemudian bergerak ke bawah dan ke kiri (Kami sedang melakukan boustrophedon dari seluruh ruang).

3. Ketika Anda berada di garis kiri-kanan dan menemui hambatan, Anda memiliki dua opsi. (i) Kita dapat mengelilingi sampai kita mencapai garis kiri-kanan yang ingin kita bahas, kemudian lanjutkan. (ii), Kita dapat berbalik dan menutupi garis kiri-kanan yang baru sampai kita menemukan jalan kita melewati rintangan atau berakhir dalam situasi ini lagi. Saya akan menggambarkan.

Di sebelah kiri, kami bergerak di sekitar penghalang sampai kami dapat kembali ke "garis" yang kami coba ikuti. Di sebelah kanan, kami terus menutupi area (lebih kecil) di satu sisi hambatan.

Keuntungan dari metode pertama adalah Anda selalu memetakan rintangan sepenuhnya sebelum Anda membuat keputusan tentang bagaimana cara mengatasinya, sehingga Anda dapat mengambil jalan yang lebih pendek. Keuntungan dari metode kedua adalah Anda tidak harus melewati rintangan sama sekali, Anda dapat melanjutkan untuk menutupi area Anda berada.

Perhatikan bahwa ini mendefinisikan dekomposisi boustrophedon Anda secara online : Anda menutupi area di antara rintangan atau di antara rintangan dan batas.

Namun, sejauh yang saya tahu, metode pertama lebih mudah dianalisis. Algoritma yang lebih rumit (seperti BFS, dll), dipilih baik karena lingkungan tidak terikat (Anda tidak ingin menghabiskan selamanya mencari batas), atau ada hambatan yang sangat buruk dalam cara yang pada dasarnya memecah lingkungan. Kenapa ini buruk? lihat contoh ini:

Bergerak kiri-kanan, kemudian berputar-putar setiap kendala menghasilkan cara terlalu banyak sampul bagian kecil antara setiap kendala. Bahkan, tanpa perencanaan jalur global, Anda dapat menjadikan ini seburuk resolusi grid Anda dengan menempatkan kolom ini selebar 1 px, setinggi seluruh lingkungan dan terpisah 1 px. Maka Anda harus bergerak di sekitar rintangan setiap kali Anda menabraknya.

Inilah sebabnya saya bertanya apakah Anda memiliki gagasan tentang di mana Anda berada di lingkungan atau dapat melakukan perencanaan jalur global. Tetapi diskusi online vs offline dan algoritma optimal untuk ini bukanlah yang Anda inginkan.

Pembaruan: Saya harus menghapus gambar (bukan https), dan akan memposting ini yang sering digunakan dalam aplikasi dunia nyata yang praktis. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf

Pada akhirnya, saya menemukan bahwa cara terbaik untuk melakukan ini adalah dengan menggunakan konsep yang sangat sederhana: Flood Fill . Saya menggunakan pendekatan iteratif berbasis stack alih-alih opsi rekursif, dan memodifikasinya untuk ruang fisik dengan menggunakan pencarian A * untuk menemukan jalur dari lokasi saat ini ke lokasi berikutnya di stack (hanya menggunakan kotak kotak yang sudah memiliki telah dikunjungi, karena saya dijamin memiliki jalur di antara mereka).

Efisiensi tampaknya cukup masuk akal.