Apa cara terbaik untuk menavigasi dan menghindari rintangan untuk robot servis?
Robot adalah sistem mekanis dan perangkat lunak yang berinteraksi dengan dunia nyata. Untuk robot layanan, sangat penting untuk memahami posisi Anda saat ini di ruang angkasa, posisi target dan kemampuan untuk membangun rute ke target dengan melewati kemungkinan rintangan. Kami sedang mengembangkan
robot untuk mengumpulkan bola golf di driving range . Kami mempertimbangkan berbagai opsi untuk membangun rute untuk menemukan yang terbaik untuk kami, mungkin informasi ini akan menarik bagi seseorang.
Cara termudah untuk membuat robot melakukan rute ke tujuan utamanya dalam ruang dua dimensi. Penjelajah itu sendiri di sini adalah titik kecil di depan yang tidak ada hambatan. Oleh karena itu, robot dalam situasi ini bergerak dalam garis lurus, dan ketika mencapai tujuan ia berhenti.
Metode ini cocok jika hanya ada robot di dunia dan tujuan yang harus dicapai. Direct akan memungkinkan Anda mencapai konfigurasi akhir secepat mungkin.
Tetapi algoritma ini tidak dapat diterapkan jika suatu hambatan tiba-tiba muncul di depan robot. Bergerak dalam garis lurus, bajak tidak akan bisa mengelilinginya atau melewatinya. Dalam hubungan ini, ia hanya berhenti di depan rintangan dan tidak bergerak.
Bagaimana cara mengatasi kendala? Cara termudah untuk menyelesaikan masalah adalah opsi perilaku yang disebut "Penghindaran Hambatan". Dalam praktiknya, ini diwakili oleh berbagai algoritma.
Walk To Algorithm
Jika tujuannya tidak tercapai:
- Bergerak menuju tujuan.
- Kalau tidak: berhenti.
Metode ini cocok jika hanya ada robot di dunia dan tujuan yang harus dicapai. Direct akan memungkinkan Anda mencapai konfigurasi akhir secepat mungkin. Tetapi algoritma apa yang harus diterapkan jika hambatan muncul di depan target di depan robot?
Rintangan tidak memungkinkan robot untuk mencapai tujuannya dalam garis lurus, penjelajah dalam situasi ini hanya berhenti di depannya. Dalam hal ini, Anda juga dapat menggunakan algoritme "Berjalan Ke", tetapi perlu ditambah.
Algoritma Bug
Dalam kehidupan sehari-hari, seseorang, ketika ia berpindah dari satu titik ke titik yang lain menuju tujuan dan menjumpai sebuah rintangan, cukup melewatinya. Perilaku ini disebut "menghindari rintangan." Ini akan berubah diterapkan untuk mencapai tujuan oleh robot. Cara termudah untuk menerapkan algoritma kumbang.
Algoritma Bug disebut oleh para ahli dengan cara ini mengingat fakta bahwa perilaku kumbang diambil di sini sebagai dasar - jika ia melihat rintangan, ia memintasinya.
Langkah-langkah yang diambil robot saat bergerak menuju target (termasuk ketika berjalan di sekitar rintangan) disebut lintasan.
Algoritma bug berfungsi sebagai dasar untuk konsep yang digunakan dalam membangun rute dari tipe yang lebih kompleks. Ini termasuk:
Konsep lintasan. Ini adalah urutan sederhana dari gerakan robot, yang ia lakukan untuk mencapai tujuan akhir. Algoritma kumbang juga merupakan "Perencana Trajektori." Setelah menerima koordinat titik di mana robot dan targetnya berada, algoritma mengembangkan lintasan pergerakan yang sesuai.
Konsep kebijakan . Jika menggunakan algoritma kumbang instruksi tertentu untuk pergerakan ditransmisikan ke robot, maka cara membangun rute ini disebut "Kebijakan Manajemen".
Konsep heuristik. Ini adalah nama aturan yang digunakan untuk menginformasikan robot tentang tahap selanjutnya dari algoritma. Dalam situasi ini, heuristik adalah garis di mana objek bergerak. Saat membuat jalur, Anda perlu menentukan heuristik dengan benar. Jika ini dilakukan secara tidak benar, maka rute yang dibangun tidak akan beroperasi.
Namun, algoritma semacam itu membatasi pengembang, karena dengan bantuannya akan dimungkinkan untuk membangun rute yang ukurannya terbatas. Ketika menggunakan algoritme seperti itu untuk membangun jalur, perlu bahwa semua hambatan mengambil bentuk poligon cembung.
Algoritma Bug juga memiliki batasan:
- rintangan harus berada pada jarak tertentu dari satu sama lain, tidak mungkin mereka memiliki kesamaan;
- batas-batas rintangan adalah kurva tertutup, sementara mereka harus sedemikian rupa sehingga garis lurus di mana robot bergerak memotong masing-masing untuk waktu yang terbatas;
- robot adalah titik kecil yang tidak proporsional, sehingga dapat bergerak di antara rintangan terlepas dari bagian di antara mereka.
Beberapa keterbatasan ini dapat diatasi dengan menggunakan algoritma DH-Bug canggih. Fiturnya adalah bahwa dengan bantuannya robot akan dapat mengatasi hambatan bergerak. Selain itu, algoritma semacam itu terdiri dari dua lapisan. Yang pertama adalah penasehat. Ini memungkinkan Anda untuk melakukan pra-evaluasi rute tanpa menggunakan informasi tambahan. Lapisan kedua adalah adaptif. Berkat dia, robot tepat waktu merespons kendala yang tidak ditetapkan dalam program pada awalnya.
Algoritma CBUG
Algoritme CBUG adalah versi pembangunan rute sedemikian rupa yang memperhitungkan semua detail. Selama pengembangannya, spesialis memperhitungkan ukuran robot, dan juga menyelesaikan masalah yang terkait dengan optimalisasi jalur yang dibuat. Fitur khusus dari algoritma yang ditingkatkan tersebut adalah untuk menghasilkan rute, perlu bahwa titik awal selalu tetap dalam memori objek. Biasanya untuk algoritma CBUG, hanya untuk aplikasinya perlu jumlah memori yang tetap.
Algoritma Dijkstra
Algoritma yang digunakan pada grafik dibuat oleh E. Dijkstroy pada paruh kedua abad terakhir. Dengan bantuannya, akan dimungkinkan untuk menentukan jalur terpendek dari salah satu simpul grafik ke yang lain. Algoritma seperti itu berakhir ketika robot telah mengunjungi semua puncak. Jika mereka yang belum dia kunjungi belum naik, puncak dengan tanda minimum dipilih.
Keuntungan dari algoritma Deister meliputi:- memperhatikan panjang jalan dan biayanya;
- node diperbarui jika yang lebih optimal ditemukan.
Kerugian dari metode ini membangun rute adalah bahwa itu hanya cocok untuk grafik di mana tidak ada tepi bobot negatif. Sangat tidak nyaman bahwa ia kurang berorientasi ketika mencari lebar.
Algoritma Bellman-Ford
Namun seringkali timbul situasi di mana perlu untuk membangun rute di mana ada tulang rusuk dengan bobot negatif. Algoritma Bellman-Ford akan membantu menyelesaikan masalah seperti itu. Jika, sebagai akibatnya, jumlah dari bobot tepi jalan akhir mengambil nilai negatif, maka itu disebut siklus negatif.
Algoritma Johnson
Algoritma ini diperkenalkan oleh DB Johnson untuk mengidentifikasi semua rute terpendek dari satu puncak ke puncak lainnya. Dalam hal ini, metode ini dapat digunakan untuk tepi dengan bobot positif dan negatif. Satu-satunya kelemahan dari algoritma ini adalah tidak ada siklus negatif.
Algoritma A *
Untuk menemukan cara paling optimal menggunakan grafik, Anda perlu menerapkan algoritma A *. Ini memungkinkan Anda untuk menentukan rute terbaik dari robot ke target dengan kecocokan pertama pada grafik. Dasar dari algoritma ini adalah rumus heuristik, yaitu sebagai berikut:
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .Algoritma ini memungkinkan Anda menemukan jalur terpendek ke tujuan hingga h (n) mengambil nilai maksimum yang diizinkan. Fitur dari algoritma A * adalah fleksibilitasnya. Paling sering, negara adalah sel atau lokasi robot. Tetapi bisa juga berupa kecepatan atau orientasi.
Pada saat yang sama, keadaan terdekat bervariasi tergantung pada kasus tertentu.
Fleksibilitas dari algoritma ini juga dimanifestasikan dalam kenyataan bahwa tujuan yang perlu dicapai robot dapat terdiri dari beberapa posisi sekaligus. Dalam situasi seperti itu, perkiraan heuristik h (n) harus segera valid untuk semua tujuan yang tersedia.
Seberapa baik algoritma A * akan bekerja tergantung pada eksponen h (n). Semakin baik kualitas perkiraan heuristik, semakin tinggi efisiensinya. Juga, jumlah memori bebas dan waktu prosesor mempengaruhi pengoperasian algoritma.
Algoritma Pelacakan Gelombang
Juga, algoritma gelombang sering digunakan untuk menggambar rute pada grafik. Saat membuat jalur dengan cara ini, metode pencarian lebar digunakan.
Algoritme itu sendiri mencakup langkah-langkah berikut:- inisialisasi
- bangunan ombak;
- pemulihan rute.
Pada tahap awal, gambar banyak sel dibuat, yang masing-masing menjadi bisa dilewati atau dilewati untuk robot.
Robot, bergerak dari satu sel ke sel lain, secara berurutan menentukan apakah mungkin untuk melewatinya dan jika dia belum menandainya sebelumnya.
Setelah itu, jalur terpendek dari sel awal ke sel terakhir dibuat oleh brute force, yang pencapaiannya adalah tujuan bajak.
Diskritkan Algoritma Antariksa
- Ruang konfigurasi memiliki ukuran konstan di semua dimensi.
- Diskritkan semua pengukuran sehingga memiliki jumlah sel yang konstan.
- Semua sel yang terletak di ruang konfigurasi di dalam penghalang harus ditandai sebagai tidak bisa dilewati.
- Akibatnya, semua sel yang bisa dilewati berubah menjadi node.
- Setiap node terhubung ke semua tetangga dalam grafik.
Pencari Jalur Acak
Aspek yang paling sulit ketika merencanakan rute adalah menghitung ruang konfigurasi dan menentukan jalur yang paling nyaman ketika melewati ruang ini. Berkat peta jalan, dimungkinkan untuk menyelesaikan masalah ini. Inti dari metode ini adalah membagi ruang menjadi kotak yang identik, menghubungkan semua simpul terdekat. Ulangi semua jalur Urutkan semua jalur untuk menemukan jalur dengan nilai terkecil.
Algoritma Peta Jalan Probabilistik
- 1. Buat grafik kosong G.
- 2. Tambahkan ke grafik G node robot dan tujuan akhirnya.
- 3. Untuk jumlah integrasi ke-N:
- Temukan sampel acak yang seragam dari ruang konfigurasi dan berikan nama R.
- Jika robot bertentangan dengan konfigurasi R, maka Anda dapat melanjutkan.
- Kalau tidak: tambahkan R ke kolom G.
- 4. Identifikasi semua node dalam grafik yang terletak di dalam titik d dan R.
- 5. Untuk semua N node yang sesuai dengan parameter ini:
Mengeksplorasi Algoritma Pohon Secara Acak
Terkadang Anda perlu membangun jalur tanpa menerapkan kueri perencanaan sebelumnya. Dalam situasi seperti itu, Anda harus menggunakan metode berikut:
- Buat pohon T. kosong
- Tambahkan ke T konfigurasi awal robot.
- Sampai tujuan tercapai:
- Ambil simpul R.
- Tentukan dalam T node yang terletak paling dekat dengan R. Beri dia nama K.
- Pindahkan robot dari K ke R hingga kondisi berikut terpenuhi:
- Jika terjadi tabrakan, lanjutkan ke definisi sampel acak.
- Jika tidak: tambahkan simpul baru ke T dalam konfigurasi ini.
- Jika jarak maksimum antara d dan K tercapai, mulailah mengerjakan pengambilan sampel acak lagi.
- Solusi diperoleh jika simpul rantai terletak dalam jarak d dari simpul T.
Kesimpulan
Bagi kami, optimal untuk memisahkan masalah pembangunan rute menjadi global dan lokal. Rute global adalah daftar titik target untuk melewati bidang atau tujuan untuk kembali ke pangkalan. Rute lokal dimulai ketika sensor ultrasonik atau bemper mendeteksi hambatan.
Karena dalam spesifikasi kami semua hambatan adalah cembung, kami menggunakan algoritma BUG paling sederhana, dan bahkan lebih sederhana. Metode navigasi "kekanak-kanakan" tertentu. Ketika USG mendeteksi hambatan, rover berputar searah jarum jam 90 derajat, melewati 1 m, berbalik 90 berlawanan arah jarum jam. Jika kendala terdeteksi oleh bumper, sebelum memutar robot 0,5 meter ke belakang.
Paket
Selama awal proyek pada musim panas 2018. Sejumlah besar peristiwa terjadi. Kami sedang menyiapkan pos pada pengembangan proyek kami. Terima kasih atas perhatian anda!
Referensi