Методи планування шляху для автономних мобільних роботів!!!

Введення

Мобільні роботи все частіше використовуються в багатьох автоматизованих середовищах. Програми для мобільних роботів включають в себе широкий діапазон сервісних роботів для людей похилого віку, автоматизовані транспортні засоби для переміщення товарів на заводі, роботів, що без допомоги людей знешкоджують безпілотні бомби, а також роботів, що вивчають планети, окрім цього, часто вони знаходять застосування в галузі підводної розвідки. У всіх цих програмах мобільні роботи виконують їхні навігаційні функції за алгоритмом зображеним на рисунку.

Алгоритм прийняття рішення, щодо свого руху роботом

У всіх програмах для того, щоб мобільні роботи виконували свої завдання успішно - планування шляху без зіткнень є обов'язковою умовою. Навігація мобільного робота передбачає сприйняття середовища, локалізацію та побудову карти, пізнання та планування шляху та управління рухом. Планування шляху відповідно до поставленого завдання із використанням пізнавальних рішень є важливою фазою, перш ніж фактично виконувати бажану траєкторію руху. Окрім програм для автономних роботів, планування шляху знаходить використання при плануванні маршрутів на платах, отриманні ієрархічних маршрутів для бездротових мереж, плануючи шлях в комп'ютерній графіці та обчислювальній біології, щоб зрозуміти можливі шляхи складання білків.

Проблематика в плануванні руху робота

Планування руху для мобільних роботів дуже складне, оскільки воно складається із кількох завдань. Робот повинен визначити геометричний шлях до заданої цілі, враховуючи своє конкретне розташування та цілі. Проблема стає ще більш складною, якщо робот повинен знайти оптимальний шлях з заданими обмеженнями або об'єктивною функцією, як-от найкоротший шлях або мінімальний час, або навіть мінімізація енергії. Робот також може зіткнутися із кількома перешкодами, статичними або динамічними, тому уникнення перешкод є надзвичайно важливим для мобільних роботів. Уникнення перешкод стосується методологій формування шляху робота для подолання непередбачуваних перешкод.

Категорії алгоритмів шляхів планування

Планування шляху мобільного робота полягає у визначенні шляху без зіткнень від початкової точки до цільової точки, що оптимізує такі критерії продуктивності, як відстань, час, витрачену енергію, відстань є найбільш важливим критерієм. На підставі наявної інформації про середовище існує дві категорії алгоритмів планування шляху - планування локального шляху, або онлайн планування та глобального шляху, або офлайн планування. У глобальному плануванні шляху, середовище відоме заздалегідь, а місцевість статична або перешкоди відомі заздалегідь. Отже, алгоритм планування шляху здатний зробити повну карту середовища від початкової точки до мети ще до початку руху робота. Планування глобального шляху вимагає повністю відомих умов і статичного рельєфу. З іншого боку, при плануванні локального шляху середовище невідоме для мобільного робота , тобто середовище є динамічним і неструктурованим, або перешкоди невідомі заздалегідь. У такій ситуації мобільний робот повинен збирати інформацію про середовище в режимі реального часу та оновлювати свої закони про контроль, щоб досягти цього. Зазвичай інформація про середовище отримується у формі даних із датчиків.Підходи до планування руху також можна розділити на класичні та еволюційні методи.

Класичні методи глобального шляху

Техніка пошуку на графах

Базоване на графах представлення є одним із перших спробів планування руху. У цьому підході побудована чітко визначена, добре організована та повністю структурована карта світу агента з метою планування безпечної навігації. Після будівництва вільних та окупованих приміщень наступна спроба пов'язати наявні вільні простори поля (тобто місця, які не мають перешкод) через підключені мережі ліній. Траєкторія робота планується за такою мережею, і таким чином робот може виконувати безпечне, цільове орієнтування, без зіткнення. Таким чином, у цьому підході до планування шляху, скорочується підключення початкового та кінцевого положень робота до мережі шляхів і пошук серії шляхів з позиції вихідного робота до місця призначення. Існують два підходи до пошуку на графах, графік видимості та діаграма Вороного. На графіку видимості шлях рухомого робота дуже близький до перешкоди і виходить з мінімальних шляхів відстані шляху, тоді як на шляху діаграми Вороного мобільний робот залишається на відстані від перешкоди настільки наскільки це можливо.

Графік видимості

Графік видимості - це сукупність прямих у вільному просторі, що з'єднують функцію об'єкта з об'єктом іншої. У своїй основній формі ці ознаки є вершинами багатокутних перешкод, які можуть бачити один одного, включаючи вихідну точку і мету, а також вершини, як показано на рисунку нижче.

Графік видимості

Ці безперешкодні вершини - найкоротша відстань. Метою планування шляху є пошук найкоротшого шляху вздовж цих прямих.

Діаграма Вороного

Діаграма Вороного — це такий вид розбиття простору, що визначається відстанями до заданої множини точок цього простору. У найпростішому випадку, ми маємо множину точок площини, кожній вершині належить комірка, утворена з усіх точок ближчих множини, ніж до будь-якої іншої вершини. Границі на діаграмі являють собою всі точки на площині, які рівновіддалені від двох найближчих вершин.

Діаграма Вороного

Класичні підходи, хоча є ефективними, займають більше часу при визначенні реального шляху без зіткнень.

Еволюційні методи глобального шляху

Генетичний алгоритм

Генетичний алгоритм - це стохастичний глобальний метод пошуку, що імітує процес природної еволюції. Генетичний алгоритм починається без знання правильного рішення і цілком залежить від відповідей його середовища та операторів еволюції (тобто відтворення та мутації), щоб досягти найкращого рішення. Починаючи з декількох незалежних точок і виконуючи паралельний пошук, алгоритм уникає локальних мінімумів та конвергенції до субоптимальних рішень. Генетичний алгоритм пошуку використовується для генерації проміжних точок після виявлення об'єктів за допомогою системи зору. Значення придатності створених шляхів оцінюється з точки зору безпеки від перешкод динамічних об'єктів та відстані до позиції цілі.

Метод рою частинок

Метод рою частинок - це еволюційна методика обчислення, натхненна соціальною поведінкою групування птахів та алгоритм заснований на вивченні поведінки риб. Багато років вивчення динаміки птахів та риб дозволило використати цю поведінку як інструмент оптимізації. У порівнянні з генетичним алгоритмом, переваги методу рою частинок полягають у тому, що метод рою частинок простіше реалізувати, а параметрів, що потребують коригування менше. Цей метод використовується разом із алгоритмом, який виявляє найкоротший шлях, використовуючи підхід пошуку на графах.

Мурашиний алгоритм

Мурашиний алгоритм є відносно недавнім підходом до задач оптимізації та базується на моделюванні колективної поведінки справжніх колоній мурашок, що проходять від гнізда до джерела їжі. Мурахи здатні знайти найкоротший шлях від джерела до їжі. Це можливо завдяки тому, що у кожного мураха є певне кількість феромонів, які потрібно скинути по шляху. Мурашки відстежують стежки феромонів, які раніше скинули мурашки гнізда, щоб досягти шляху між двома точками гнізда та їжею відповідно. У випадку будь-яких перешкод, що існують на їхньому шляху, мурахи рухаються вздовж контуру перешкоди з обох сторін і знаходять свій шлях до джерела їжі. Штучна мураха рухається на основі привабливості феромона. Оскільки концентрації феромонів знаходяться більше уздовж шляху, мурашки накопичують більше феромонів за певний проміжок часу уздовж коротшого шляху. Це було використано для вирішення мобільних задач навігації роботом.

Класичні підходи локального шляху

Штучні потенційні поля

Концепція полягає в тому, що штучні сили, що породжуються перешкодами та цілями, застосовуються до робота, щоб рухатися навколо безбар'єрного середовища. На перешкоди та цільові позиції призначаються відштовхувальні та допоміжні сили відповідно. Таким чином, потенційна функція може бути визначена над вільним простором як сума допоміжного потенціалу, що притягує робота до конфігурації цілі, а відштовхувальний потенціал відштовхує робота від перешкод, як показано на рисунку.

Рух робота в концепції штучних потенційних полів

Таким чином, робот рухається до мети і відштовхується від перешкод, які заздалегідь відомі. Якщо під час руху виникають нові перешкоди, потенційне поле може бути оновлено, щоб врахувати це. Основними недоліками методології потенційного поля є те, що існують ситуації, де пастки можуть виникати внаслідок наявності локальних мінімумів та обчислень.

Гістограма векторного поля

У кожну мить полярна гістограма створюється для відображення полярної щільності перешкод навколо робота. Керуючий напрямок робота вибирається на основі найменшої полярної щільності та близькості до цілі. У певному середовищі полярна гістограма повинна регулярно відновлюватися кожного моменту, і тому цей спосіб підходить для середовищ з рідкими рухомими перешкодами.

Концепція конусу колізії

Помилок робота можна запобігти, якщо відносна швидкість робота по відношенню до певної перешкоди виходить ззовні до конусу зіткнення. Підхід до перешкод, що нагадує наближення конічного зіткнення полягає у виборі маневрів із запобігання, щоб уникнути статичних та рухомих перешкод у просторі швидкості. Вони використовували базову евристичну стратегію для визначення пріоритетів таких завдань такі, як запобігання зіткненням, досягнення мети або досягнення траєкторій з кращими топологіями.

Динамічний підхід до перешкод

Динамічна перешкода містить можливі лінійні та кутові швидкості з урахуванням можливостей прискорення робота. Тоді швидкість наступного моменту оптимізується для уникнення перешкод, залежно від динаміки робота.

Еволюційні методи локального шляху

Інтелектуальні системи управління

Метод заснований на здатності людського мозку виконувати складні завдання шляхом міркування, адаптації та реагування на зміни середовища. Такі методи поведінкового навчання можуть бути використані для вирішення складних проблем управління, з якими автономні роботи стикаються в незнайомому реальному світі. Деякі методи інтелектуальної системи управління включають нейронні мережі, нечіткі логіки, генетичні алгоритми, мурашиний алгоритм та інші.

Нейронні мережі

Створення нейронної мережі було натхненне через визнання того, що людський мозок обчислює інакше, ніж звичайний цифровий комп'ютер. Мозок виступає як дуже складний, нелінійний і паралельний комп'ютер. Нейронна мережа - це масово паралельно розподілений процесор, що складається з простих блоків обробки, відомих як нейрони, що має схильність до зберігання та доступності експериментальних знань. Основною перевагою нейронних мереж є те, що можна навчити нейронну мережу виконувати певну функцію, коригуючи значення зв'язків (ваги) між елементами. Наприклад, якщо ми хочемо навчити нейронну модель для наближення конкретної функції, ваги, які множать кожен вхідний сигнал, будуть оновлюватися до тих пір, поки вихід з нейрону не буде аналогічним функції. Цей процес називається тренуванням. Коли така техніка використовується для планування руху робота, стан космічного простору нейронної мережі є конфігураційним простором робота, динамічно змінюється середовище представляє динамічний ланцюг активності нейронної мережі. Ціль - глобально залучити робота в усьому існуючому просторі, тоді як перешкода викидає робота геть. В результаті було розроблено штучну нейронну мережу для навігаційного управління мобільними роботами.

Нечітка логіка

Нечітка логіка створює формальну техніку, що представляє та здійснює евристичні знання та заходи сприйняття експертів людини. Нечіткі логіки та нечіткі мови також використовувалися в навігаційних алгоритмах для мобільних роботів . На нечіткому логічному контролері на основі навігації проблема полягає в більш простих завданнях, і кожна поведінка складається з безлічі нечіткої логіки правил висловлювання, призначених для досягнення чітко визначеного набору цілей. Широко деталізовано комплексне дослідження нечіткого логічного контролю для планування руху.

Гібридні методи

Комбінація класичних та інтелектуальних методів також використовується для вирішення проблеми планування шляху. Про інтеграцію нейронних та нечітких прийомів, потенційних полів та оптимізації колоній мурашок та деяких інших таких робіт було згадано вище.

Можливості вирішення проблем існуючих методів та створення нових

Якісно кращі шляхи можна досягнути, вирішуючи такі проблеми:

1) Можна розробити більш точні математичні моделі, що містять миттєву швидкість роботи, а також наближення перешкод для вирішення навіть проблем із рухомими перешкодами.

2) Вплив інших стримуючих перешкод під час уникання найближчих перешкод може дати загалом кращий результат. Тому математична модель повинна одночасно розглядати ефект стримуючих перешкод, які можуть спричинити подальше відхилення більше ніж уникаючи неминучої загрози.

3) Уникнення перешкоди роботом, коли така можливість існує. Потреба у відновленні перешкоди може бути усунена.

4) Будь-який алгоритм планування в режимі онлайн стає справді успішним, якщо наступна дія робота планується в межах кінематичних та динамічних обмежень робота. Отже, математичні моделі повинні включати верхню межу для динамічних обмежень у складних та в обмежених у часі середовищах.

У сфері планування шляху, еволюційні методи виявилися кращими, ніж чисті класичні підходи. Все ще існує можливість розробки більш ефективних алгоритмів планування шляху, які забезпечать вирішення деяких проблем у такий спосіб:

1) В первинному поколінні населення слід враховувати дійсні шляхи, які не контактують із перешкодами, що виключає використання оцінки штрафних функцій.

2) Методи оптимізації з реальними рядками є обчислювально дешевше, тому що до оцінки цільової функції деталі альтернативних шляхів не потрібно виражати в двійкових кодах.

3) Шлях із змінною кількістю сегментів може бути використаний для генерації популяцій з огляду на складність (кількість вершин) середовища.

---

Виконала: Підойма Марина

Developed by Інститут Програмних Систем