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

Реферат по теме выпускной работы

Содержание

Введение

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

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

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

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

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

1. Актуальность темы

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

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

2. Цель и задачи исследования, планируемые результаты

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

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

Предмет исследования: алгоритм эволюционного навигатора планирования пути автономного робота.

Основные задачи исследования:

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

3. Общая постановка задачи планирования пути мобильного робота

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

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

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

3.1 Применение эволюционных алгоритмов в задачах навигации

Эволюционный навигатор (далее EN) должен представлять собой систему генетических алгоритмов, объединяющее в себе как автономный режим так и режиме онлайн-планирования с простой картой высокой точности и эффективным алгоритмом планирования. Первая часть алгоритма (автономный планировщик) ищет оптимальный глобальный путь от начальной точки до пункта назначения, в то время как вторая часть (онлайн планировщик) отвечает за обработку возможных столкновений или обход ранее неизвестных объектов, заменив часть спланированного глобально-оптимального пути на вспомогательный путь [7]. Важно отметить, что обе части ЭН используют один и тот же эволюционный алгоритм, но с разными значениями различных параметров.

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

3.2 Выбор генетического алгоритма для реализации эволюционного навигатора

За основу создания эволюционного навигатора я выбираю эволюционный алгоритм, предложенный в статье Збигниева Михалевича «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.