ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

Поки основною проблемою усіх нині існуючих мобільних апаратів, що переміщаються самостійно, без управління з боку людини, залишається навігація[1]. У зв'язку зі спробами створити автономний засіб або рухомого агента виникає ряд проблем, об'єднаних загальною назвою – «навігаційні задачі». Навігація – наука про управління ходом мобільного робота (іншими словами автономного об'єкта) в навколишньому середовищі. Для успішної навігації в просторі бортова система робота повинна вміти будувати маршрут, управляти параметрами руху (задавати кут повороту коліс і швидкість їх обертання), правильно інтерпретувати відомості про навколишній світ, одержані від датчиків, і постійно відстежувати власні координати.

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

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

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

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

1. Актуальність теми

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

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

2. Мета і задачі дослідження та заплановані результати

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

Об'єкт дослідження: застосування генетичних алгоритмів для вирішення задачі планування шляху автономного робота

Предмет дослідження: алгоритм еволюційного навігатора планування шляху автономного робота

Основні задачі дослідження:

  1. Для розробки системи генетичного навігатора необхідно дослідити:
    • способи планування шляху мобільного роботу;
    • алгоритми обходу перешкод;
    • вспособи представлення довколишнього середовища.
  2. Вирішити ключові проблеми обраного алгоритму, такі як вібор вуздлвих точок.
  3. Для оптимізації вибраного генетичного алгоритму потрібно :
    • модифікувати його оператори;
    • порівняти показники роботи;
    • вибрати найефективніший варіант генетичного алгоритму.

3.Загальна постановка задачі планування шляху мобільного робота в навколишньому середовищі

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

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

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

3.1 Застосування еволюційних алгоритмів для задач навігації

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

В останні роки інші дослідники експериментували з еволюційним методам обчислень для завдання планування шляху [8]. Так,наприулад, Давідор використовує динамічні структури хромосом і зміну оператора кросовер оптимізації деяких процесів в реальному світі (у тому числі розробки додатків планування шляхів) [9]. У інших роботах описаний генетичний алгоритм для задачі планування шляху, представлений генетичний алгоритм для розробки в режимі реального часу мульти-евристичної стратегії пошуку. Обидва підходи передбачають використання певної карти, що складається з вузлових точок[10-11]. Інші дослідники використовували класифікатор систем або парадигму генетичного програмування підходячи до проблеми планування шляху. Вибраний підхід є унікальним в тому сенсі, що еволюційний навігатор працює на всьому вільному просторі і не робить жодних апріорних припущень про допустимі вузлові точки шляху, і він поєднує в собі разом автономний режим і в режим онлайн планування[12-13].

3.2 Вибір генетичного алгоритму для реалізації еволюційного навігатора

За основу створення еволюційного навігатора (далі EН) я обираю еволюційний алгоритм, запропонований Збигнієвим Міхайлевичем в статті «Path planning in a mobile robot environment», описаний далі [14]. Обраний підхід є унікальним в тому сенсі, що еволюційний навігатор працює на всьому вільному просторі і не робить ніяких апріорних припущень про допустимі вузлових точок шляху, і він поєднує в собі разом автономний режим і в режим онлайн планування .

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

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

Припустимо, існує шлях р = (m1, m2, ..., mn) (n ? 2), де m1 і mn позначають початковий і кінцевий вузли, відповідно. Вузол (i = 1, ..., n-1) є неприпустимим, якщо він не можливий, або не може бути з'єднаний з наступним вузлом mi через перешкоди, або він знаходиться всередині (або занадто близько до) самої перешкоді. Ми припускаємо, що початковий і кінцевий вузли знаходяться за межами перешкод, і не дуже близькі до них [16]. Однак слід відзначити, що початковий вузол не обов'язково повинен бути можливим (якщо не можливо пройти до наступного вузла), тоді як цільовий вузол (пункт) завжди можливий. Відзначимо також, що різні шляхи можуть мати різну кількість вузлів.

3.3 Опис алгоритму еволюційного навігатора

Еволюційний алгоритм, який буде описаний тут, є еволюційним навігатором , що об'єднує в собі автономний режим і режим онлайн планування з простою карти високої точності і ефективний алгоритм планування[17]. .

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

ЕН спочатку зчитує карту і отримує початковий і цільове місця знаходження. Потім автономний еволюційний алгоритм (ОЕА) генерує близький до оптимального глобальний шлях, це частково-прямолінійний шлях, що складається з допустимих вузлових точок або вузлів. Рисунок 1 показує роботу генетичних алгоритмів єволюційного навігатора.

Навигатор

Рисунок 1 – Візуалізація роботи еволюційного навігатора

(анимація:12 кадрів, 10 циклів, 30кб)

Якщо робот переміщується дуже близько об'єкту навколишнього об'єкта, ОЕА практично змушує «рости» подання цього об'єкта на карті і віддаляє локальний шлях від об'єкта, що відбувається також прямолінійно, як і було задумано раніше при побудові шляху алгоритмом АЕА. Робот далі успішно рухається по поточному шляху до наступного спланованим вузлу.

4. Перспективи подальших досліджень

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

Вивчаючи існуючі методи ухилення роботів від зіткнень всі алгоритми можна розділити на декілька класів:

Далі необхідно детально проаналізувати методи обходу перешкод для вибору вузлових точок при плануванні шляху.

Алгоритм, подібний еволюційному навігатора, детально рассматівалісь при вирішенні задачі Штейна в дослідженнях А.І. Ольшевського і М.Ю. Почінского [19]. Наведені дослідження показують, що для зменшення часу обчислень доцільно виділяти області вихідних даних для створення початкових популяцій при вирішенні задачі планування шляху за допомогою генетичного алгоритму.

Слід відмінити, що на етапі програмної реалізації модифікованого ЕН до його основних компонентів будуть підбиратися параметри для ефективної роботи навігаційної системи в будь-яких умовах [20]. Однак оцінити ефективність оптимізації неможливо без проведення експериментальних досліджень.

Висновки

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

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

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

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2012 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Перелік посилань

  1. Лысенко О. Использование лазерных сканеров SICK AG для навигации мобильных роботов /Олег Лысенко / материалы из журнала «Компоненты и технологии» № 1 '2008 [Электронный ресурс]. – Режим доступа:http://www.kit-e.ru/articles/sensor/2008_01_56.php
  2. Черноножкин В.А. Система локальной навигации для наземных мобильных роботов/ Черноножкин В.А., Половко С.А./ Центральный научно-исследовательский и опытно-конструкторский институт робототехники и технической кибернетики – Режим доступа к материалам: http://144.206.159.178/ft/9344/538978/11790042.pdf
  3. Бобровский С.Навигация мобильных роботов/Сергей Бобровский/ PC Week/RE («Компьютерная неделя») / [Электронный ресурс]. – Режим доступа: http://www.pcweek.ru/themes/detail.php?ID=66917
  4. Стоут Б.. Алгоритмы поиска пути/ Браян Стоут[Электронный ресурс].– Режим доступа: http://pmg.org.ru/ai/index.html
  5. Sharon Laubach. Sensor-based Autonomous Navigation for Mars Rover/ Sharon Laubach, Joel Burdick. Larry Matthies[Электронный ресурс]. – Режим доступа: http://robotics.caltech.edu/~jwb/ERC/rover/rover_detailed.html
  6. Latombe J. C. Robot Motion Planning/J-C Latombe.– Kluwer Academic Publishers: 1991.
  7. Jean-Yves Bouguet. Visual Navigation using a single camera. – [Електронний ресурс]/ Jean-Yves Bouguet, Pietro Perona. – Режим доступа:http://www.vision.caltech.edu/bouguetj/
  8. Lozano-Perz T. An Algorithm of Planning Colisions Free Paths among Polyhedral Abstracts/ T. Lozano-Perz. – ACM,1984. p 560-570.
  9. Davidor Y. Genetic Algoritms and Robotics./ Y. Davidor. – World Scientific, 1991
  10. Sibata T. Robot Motion Planning by Genetic Algoritms with Fuzzy Logics/ T. Sibata, T. Fukuda. – ISIC, 1993.
  11. Shing M.T. Genetic Algoritms for the Development of Real-Time Multi-Historic Search Strategies/ M.T Shing, G.B. Parker. – 1993. 570 p.
  12. Zhou H.H. Learning by Analogy in Genetic Classifier Systems/Zhou H.H. – CA, 1994. 550 p.
  13. Handly S. The Genetic Planner/ S. Handly. – ISIC,1993.
  14. Zbigniev Michailevich. Genetic Algoritms plus Data Structures equal Evolution Programs/ Zbigniev Michailevich.– Springer, 1999. – 387 c.
  15. Курейчик В. М. Поисковая адаптация: теория и практика/ Курейчик В. М., Лебедев Б. К., Лебедев О. К. – М: Физматлит, 2006. – 272 c.
  16. Samejima K. Adaptive internal state space construction method for reinforcement learning of a real-world agent/ K.Samejima, T. Omori. – Neural Networks, 1999
  17. Курейчик В.М. Генетические алгоритмы и их применение/В.М.Курейчик .– Таганрог: ТРТУ, 2002
  18. Плотников В.А. Анализ эффективности существующих методов уклонения от столкновения для мобильного робота / Плотников В.А. – Донецк: Штучний інтелект – 2010.
  19. Ольшевский А.И. Решение задачи Штейна при помощи генетического алгоритма /Ольшевский А.И., Починский М.Ю. : Бионика интеллекта –2008.
  20. Емельянов В.В. Теория и практика эволюционного моделирования/ В. В.Емельянов, В. В. Курейчик В. В., В. М. Курейчик. – М: Физматлит, 2003. – 432 c.