Методи планування шляху для автономних мобільних роботів!!!
Зміст
Введення
Мобільні роботи все частіше використовуються в багатьох автоматизованих середовищах. Програми для мобільних роботів включають в себе широкий діапазон сервісних роботів для людей похилого віку, автоматизовані транспортні засоби для переміщення товарів на заводі, роботів, що без допомоги людей знешкоджують безпілотні бомби, а також роботів, що вивчають планети, окрім цього, часто вони знаходять застосування в галузі підводної розвідки. У всіх цих програмах мобільні роботи виконують їхні навігаційні функції за алгоритмом зображеним на рисунку.
У всіх програмах для того, щоб мобільні роботи виконували свої завдання успішно - планування шляху без зіткнень є обов'язковою умовою.
Навігація мобільного робота передбачає сприйняття середовища, локалізацію та побудову карти, пізнання та планування шляху та управління рухом. Планування шляху відповідно до поставленого завдання із використанням пізнавальних рішень є важливою фазою, перш ніж фактично виконувати бажану траєкторію руху.
Окрім програм для автономних роботів, планування шляху знаходить використання при плануванні маршрутів на платах, отриманні ієрархічних маршрутів для бездротових мереж, плануючи шлях в комп'ютерній графіці та обчислювальній біології, щоб зрозуміти можливі шляхи складання білків.
Проблематика в плануванні руху робота
Планування руху для мобільних роботів дуже складне, оскільки воно складається із кількох завдань. Робот повинен визначити геометричний шлях до заданої цілі, враховуючи своє конкретне розташування та цілі. Проблема стає ще більш складною, якщо робот повинен знайти оптимальний шлях з заданими обмеженнями або об'єктивною функцією, як-от найкоротший шлях або мінімальний час, або навіть мінімізація енергії. Робот також може зіткнутися із кількома перешкодами, статичними або динамічними, тому уникнення перешкод є надзвичайно важливим для мобільних роботів. Уникнення перешкод стосується методологій формування шляху робота для подолання непередбачуваних перешкод.
Категорії алгоритмів шляхів планування
Планування шляху мобільного робота полягає у визначенні шляху без зіткнень від початкової точки до цільової точки, що оптимізує такі критерії продуктивності, як відстань, час, витрачену енергію, відстань є найбільш важливим критерієм. На підставі наявної інформації про середовище існує дві категорії алгоритмів планування шляху - планування локального шляху, або онлайн планування та глобального шляху, або офлайн планування. У глобальному плануванні шляху, середовище відоме заздалегідь, а місцевість статична або перешкоди відомі заздалегідь. Отже, алгоритм планування шляху здатний зробити повну карту середовища від початкової точки до мети ще до початку руху робота. Планування глобального шляху вимагає повністю відомих умов і статичного рельєфу. З іншого боку, при плануванні локального шляху середовище невідоме для мобільного робота, тобто середовище є динамічним і неструктурованим, або перешкоди невідомі заздалегідь. У такій ситуації робот повинен збирати інформацію про середовище в режимі реального часу та оновлювати свої закони про контроль, щоб досягти цього. Зазвичай інформація про середовище отримується у формі даних із датчиків.Підходи до планування руху також можна розділити на класичні та еволюційні методи.
Класичні методи
1.Техніка пошуку на графах
Базоване на графах представлення є одним із перших спробів планування руху. У цьому підході побудована чітко визначена, добре організована та повністю структурована карта світу агента з метою планування безпечної навігації. Після будівництва вільних та окупованих приміщень наступна спроба пов'язати наявні вільні простори поля (тобто місця, які не мають перешкод) через підключені мережі ліній. Траєкторія робота планується за такою мережею, і таким чином робот може виконувати безпечне, цільове орієнтування, без зіткнення. Таким чином, у цьому підході до планування шляху, скорочується підключення початкового та кінцевого положень робота до мережі шляхів і пошук серії шляхів з позиції вихідного робота до місця призначення. Існують два підходи до пошуку на графах, графік видимості та діаграма Вороного. На графіку видимості шлях рухомого робота дуже близький до перешкоди і виходить з мінімальних шляхів відстані шляху, тоді як на шляху діаграми Вороного мобільний робот залишається на відстані від перешкоди настільки наскільки це можливо.
1.1 Графік видимості
Графік видимості - це сукупність прямих у вільному просторі, що з'єднують функцію об'єкта з об'єктом іншої. У своїй основній формі ці ознаки є вершинами багатокутних перешкод, які можуть бачити один одного, включаючи вихідну точку і мету, а також вершини, як показано на рисунку нижче.
Ці безперешкодні вершини - найкоротша відстань. Метою планування шляху є пошук найкоротшого шляху вздовж цих прямих.
1.2 Діаграма Вороного Діаграма Вороного — це такий вид розбиття простору, що визначається відстанями до заданої множини точок цього простору. У найпростішому випадку, ми маємо множину точок площини, кожній вершині належить комірка, утворена з усіх точок ближчих множини, ніж до будь-якої іншої вершини. Границі на діаграмі являють собою всі точки на площині, які рівновіддалені від двох найближчих вершин.
