Algoritma apa yang harus saya terapkan untuk memprogram robot pembersih kamar?

Untuk pertanyaan ini asumsikan bahwa hal-hal berikut tidak diketahui:

• Ukuran dan bentuk ruangan
• Lokasi robot
• Adanya kendala

Juga asumsikan bahwa hal-hal berikut ini konstan:

• Ukuran dan bentuk ruangan
• Jumlah, bentuk, dan lokasi dari semua (jika ada) hambatan

Dan asumsikan bahwa robot memiliki sifat-sifat berikut:

• Itu hanya dapat bergerak maju dalam penambahan unit absolut dan mengubah derajat. Juga operasi yang bergerak akan mengembalikan true jika berhasil atau salah jika gagal bergerak karena halangan
• Sumber tenaga yang tidak terbatas (katakanlah itu adalah robot bertenaga surya yang ditempatkan di stasiun ruang angkasa yang menghadap matahari setiap saat tanpa langit-langit)
• Setiap gerakan dan rotasi dilakukan dengan presisi absolut setiap saat (jangan khawatir tentang data yang tidak dapat diandalkan)

Akhirnya tolong pertimbangkan sifat-sifat lingkungan robot berikut:

• Berada di stasiun ruang angkasa tanpa langit-langit, ruangan ini aman dan jaraknya sangat dekat dengan komet yang lewat, sehingga debu (dan es) terus-menerus mengotori lingkungan.

Saya ditanya versi yang lebih sederhana dari pertanyaan ini (ruangan adalah persegi panjang dan tidak ada hambatan, bagaimana Anda akan pindah memastikan bahwa Anda bisa melewati setiap bagian setidaknya sekali) dan setelah saya mulai bertanya-tanya bagaimana Anda akan mendekati ini jika Anda tidak bisa tidak menjamin bentuk atau adanya hambatan. Saya sudah mulai melihat ini dengan algoritma Dijkstra , tetapi saya terpesona mendengar bagaimana orang lain mendekati ini (atau jika ada jawaban yang diterima dengan baik untuk ini? (Bagaimana Roomba melakukannya?)

Sejauh yang saya tahu, masalah ini belum "diselesaikan."

Secara formal, ini adalah masalah cakupan online. Cakupan, karena kita harus membahas setiap titik di lantai, dan online karena kita tidak memiliki akses offline ke peta. Jika Anda tertarik dengan hasil terbaru, saya sarankan Anda mencari " algoritma cakupan online robot ," mungkin di Google Cendekia (ada banyak dan banyak hasil bagus). Selain posting @ embedded.kyle yang sangat berwarna (kembali), saya akan menambahkan beberapa detail (saya juga akan mencoba dengan cepat menemukan beberapa hasil sederhana):

• Dijkstra's akan memberi Anda jalan, tetapi tidak harus cakupan. Misalnya, bagaimana Anda menentukan untuk Dijkstra bahwa Anda harus mengunjungi setiap titik dalam grafik, daripada mengunjungi satu titik secepat mungkin? Anda dapat menjalankan all-pair jalur terpendek, tetapi apa poinnya? Anda tidak memiliki peta.

• Algoritma online seperti ini sering disebut algoritma "bug" karena mereka cenderung terlihat seperti bug yang berkeliaran di suatu daerah, menabrak sesuatu, kemudian berkeliaran di sekitarnya sedikit.

• Tanpa ada penghalang, dan ruang persegi panjang, dan dengan asumsi Anda mulai pada batas boustrophedon sebuah (cara lembu) jalur optimal.

Lucu bahwa petani telah melakukan ini selamanya, bukan? http://en.wikipedia.org/wiki/Boustrophedon . Ini dapat diperluas ke kamar dengan rintangan dengan menemukan area persegi panjang yang bebas hambatan. Howie Choset mengerjakan ini sedikit .

• Untuk menutupi area dengan batas tidak diketahui, dan dengan asumsi Anda tidak memulai pada batas, apa strategi optimal? Nah, bayangkan Anda jatuh ke dunia, dan tidak bisa melihat batasnya. Anda dapat berjalan dalam garis lurus hingga mencapai perimeter, lalu melakukan boustrophedon, bukan? Kecuali sekarang Anda "membuang" waktu yang dihabiskan untuk menemukan perimeter, karena Anda akan membahas bagian itu dua kali. Inilah sebabnya robot cenderung spiral: Pada saat Anda mencapai batas, Anda telah menutupi banyak area ( mana adalah jarak ke batas terdekat , kan?). Ini sangat membantu: sekarang Anda dijamin menemukan batas terdekat, dan dapat melacaknya.$\pi*d^2$$d$
• Ini adalah area yang sangat luas dan mempesona. Maaf saya tidak bisa memberikan ringkasan yang lebih baik!

Masalah terbesar adalah Anda tidak memiliki peta. Tanpa peta, Anda terbatas pada tindakan sederhana seperti mengikuti perimeter, dan bergerak di sepanjang jalan (seperti yang disebutkan dalam spiral). Jadi, ada beberapa robot yang benar-benar membangun peta saat membersihkan, menguraikan area yang dipetakan menjadi bentuk, lalu menutupi setiap bentuk untuk memastikan cakupan. Lihat: http://mintcleaner.com/

Roomba dimulai dalam bentuk spiral hingga menyentuh sesuatu, kemudian melakukan sapuan perimeter. Kemudian hanya memantul. Roomba menjadi standar de facto dalam pembersih vaksin robot rumah tangga, saya kira Anda bisa menyebutnya "solusi yang diterima". Tetapi dari pengalaman pribadi (saya memiliki dua), pasti ada ruang untuk perbaikan.

Dari Cara Kerja :

Dari wawancara dengan Nancy Dussault Smith, Wakil Presiden Komunikasi Pemasaran di iRobot:

Ketika mulai, Anda akan melihat pola spiral, itu akan melingkar ke area yang lebih besar dan lebih besar sampai menyentuh suatu objek. Ketika ia menemukan objek, ia akan mengikuti sepanjang tepi objek itu untuk jangka waktu tertentu, dan kemudian ia akan mulai melewati persimpangan, mencoba untuk mencari tahu jarak terbesar yang bisa ia tempuh tanpa mengenai objek lain, dan itu membantunya mencari tahu mengetahui seberapa besar ruang itu, tetapi jika itu berlangsung terlalu lama tanpa menabrak dinding, itu akan mulai berputar lagi, karena angka itu berada di ruang terbuka yang luas, dan itu terus-menerus menghitung dan mencari tahu.

Ini mirip dengan sensor tanah di bawahnya, ketika salah satu sensor tersandung itu mengubah perilakunya untuk menutupi area itu. Ini kemudian akan pergi mencari daerah kotor lain di jalur lurus. Cara pola-pola yang berbeda ini bertumpuk satu sama lain saat kita berjalan, kita tahu bahwa itu adalah cara paling efektif untuk menutupi ruangan.

Pola yang kami pilih dan bagaimana algoritma awalnya dikembangkan didasarkan dari algoritma berbasis perilaku yang lahir dari MIT yang mempelajari hewan dan bagaimana mereka mencari daerah untuk makanan. Ketika Anda melihat bagaimana semut dan lebah keluar dan mereka mencari area, cakupan seperti ini dan mencari tahu semua itu berasal dari penelitian itu. Ini tidak tepat, jelas, saya tidak mengatakan kita adalah lebah madu, tetapi pemahaman tentang bagaimana mencari area di alam yang menjadi dasar di balik bagaimana teknologi adaptif kita dikembangkan.

Beberapa foto paparan lama Roombas dengan LED di atasnya menggambarkan cara kerjanya dalam praktik:

Neato menggunakan pendekatan terorganisir. Menggunakan SLAM dan bumper, ini memetakan ruang 'saat ini', perimeter terlebih dahulu, kemudian menerapkan beberapa algoritma untuk membersihkan seefisien mungkin. Saya tidak pernah memiliki Roomba, tetapi mengingat apa yang saya baca tentang algoritme itu, saya tidak akan pernah beralih dari neato.

Laser Range Finder di neato sering dapat dinisasi untuk robotika, karena merupakan sensor yang hemat biaya untuk algoritma SLAM.

Jika saya diberi tugas, Pertama saya akan menemukan implementasi SLAM yang cocok , berdasarkan perangkat keras yang saya miliki.

Kemudian saya akan menggunakan algoritma perencanaan gerak ISLAND CNC . Pengalaman saya adalah mereka cenderung sangat efisien dalam mencakup area yang sewenang-wenang dengan jumlah gerakan paling sedikit.

Hal pertama yang perlu Anda tetapkan adalah tujuan robot - tidak cukup jelas dari pertanyaan Anda. Ada dua tugas utama yang harus diselesaikan robot Anda: menemukan bentuk area yang dapat dibersihkan, lalu membersihkannya.

Tetapi apakah jumlah kotorannya konstan? Apakah kotoran ditambahkan terus menerus? Apakah tujuan Anda untuk meminimalkan waktu rata-rata agar kotoran tetap menempel di lantai, atau waktu rata-rata? Apakah tujuannya menjaga lantai tetap bersih? Atau hanya membersihkan sekali, secepat mungkin? Apakah ada pola akumulasi kotoran yang dapat Anda ukur dan gunakan untuk keuntungan Anda dalam mencapai tujuan Anda?

Jawaban atas pertanyaan-pertanyaan ini akan membantu memandu algoritma apa yang Anda pilih. Dalam kasus robot Roomba, mungkin tidak ada gunanya mempelajari tata letak ruangan yang tepat karena furnitur (seperti kursi di sekitar meja), orang, dan penghalang lainnya sering bergerak. Namun, dalam kasus Anda, mungkin lebih baik untuk menjelajahi ruang untuk membangun peta lengkap (beberapa kombinasi dari pola mesin pemotong rumput dengan menemukan tepi), kemudian menggunakan peta itu untuk menghitung jalur terpendek melalui ruang (istilahnya adalah "cakupan", dan ada beberapa cara untuk melakukannya misalnya spanning tree algorithm ).

Satu hal lagi yang perlu Anda khawatirkan adalah bagaimana mendiskritasikan ruang tempat Anda berada. Karena Anda dapat bergerak ke segala arah - bahkan dengan jumlah derajat integer dan unit integer jarak - posisi X dan Y Anda dapat memiliki pecahan nilai-nilai. Anda harus memutuskan bagaimana merepresentasikan hambatan pada peta itu tanpa membuatnya tumbuh hingga jumlah titik data yang tak terbatas.

Saya tidak yakin apakah Anda masih membutuhkannya, tetapi bagi mereka yang kebetulan menggunakan google untuk utas ini, saya telah membuat satu versi sederhana dari algoritma ini.

Pada dasarnya, ia mencoba untuk membangun peta area saat ia membersihkan, dan ia menggunakan peta untuk menemukan simpul terdekat yang tidak ada bantuan (bagian dari ruangan). Ketika tidak dapat menemukan apapun, itu berarti ruangan dibersihkan (atau bagian yang tidak bersih tidak dapat diakses oleh robot).

Mungkin lebih lambat dari algoritma lain, tetapi dapat menjamin cakupan terlepas dari posisi awal, arah dan hambatan.

https://github.com/dungba88/cleaner_robot

UPDATE: Saya telah membuat demo di sini dan membandingkannya dengan DFS backtracking. Jadi meskipun algoritma saya adalah O (N ^ 2), itu jauh lebih dioptimalkan dalam hal jumlah gerakan dan belokan.

http://jenova.dungba.org/cleaner/showdown

Melihat masalah sederhana yang Anda tanyakan - sebuah ruangan persegi panjang, tanpa hambatan dan membersihkan setiap bagian setidaknya sekali.

Solusinya adalah menemukan sudut ruangan, dan menemukan sudut tidak akan menjadi masalah besar. Setelah itu tercapai, maka ikuti saja jalur spiral ke tengah ruangan.