Васюк А.О. -ОПТИМИЗАЦИЯ АЛГОРИТМА ЭВОЛЮЦИОННОГО НАВИГАТОРА ДЛЯ ПЛАНИРОВАНИЯ ПУТИ АВТОНОМНОГО РОБОТА

Аннотация:

Васюк А.О., Бабаков Р.М Оптимизация алгоритма эволюционного навигатора для планирования пути автономного робота. Рассмотрена навигационная задача планирования пути автономного робота. Для реализации планирования пути автономного робота за основу выбран генетический алгоритм эволюционного навигатора. Предложены варианты оптимизации для обеспечения универсальности алгоритма навигации.

Введение

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

Объект исследования – алгоритм эволюционного навигатора планирования пути автономного робота.

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

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

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

1 Общая постановка задачи

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

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

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

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

Сейчас важно определить пути, которые должен генерировать ЭН [5]. Путь состоит из одного или нескольких прямолинейных отрезков, из исходного положения, цели, и возможно, места пересечения двух смежных сегментов – узла. Осуществимый путь состоит в возможных узлах; невозможен путь тот, который содержит хотя бы один невозможный узел.

Предположим, существует путь р = (m₁, m₂, ..., m_n) (n ≥ 2), где m₁ и m_n обозначают начальный и конечный узлы, соответственно. Узел (i = 1, ..., n-1) является недопустимым, если он не возможен, или не может быть соединен с последующим узлом m_i через препятствия, или он находится внутри (или слишком близко к) самой преграде. Мы предполагаем, что начальный и конечный узлы находятся за пределами препятствий, и не слишком близки к ним [6].

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

2 Описание алгоритма эволюционного навигатора

Возьмем за основу исследований алгоритм эволюционного навигатора,предложеного в статье Збигниева Михалевича «Path planning in a mobile robot environment» [7].

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

ЭН сначала считывает карту и получает начальное и целевое места нахождения. Затем автономный эволюционный алгоритм (ОЭА) генерирует близкий к оптимальному глобальный путь, это частично-прямолинейный путь, состоящий из допустимых узловых точек или узлов. Рисунок 1.2 показывает такой глобальный путь, порожденный ОЭА (Закрашенный круг обозначает работа).

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

Если робот перемещается слишком близко объекту окружающей объекта, ОЭА практически заставляет «расти» представление этого объекта на карте и отдаляет локальный путь от объекта, что происходит также прямолинейно, как и было задумано ранее при построении пути алгоритмом АЭА . Робот дальше успешно движется по текущему пути к следующему спланированному узлу.

Рисунок 1.1 Структура алгоритма ЭН

Рисунок 1.2 Ход робота по алгоритму ЭН

3 Перспективы дальнейших исследований

Не смотря на свою эффективность алгоритм ЭН имеет существенные недостатки. Ключевой проблемой данного алгоритма является определение узловых точек. Выбор нетривиального способа вычисления этих координат существенно изменит работу алгоритма генетического навигатора.

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

Изучая существующие методы уклонения роботов от столкновений все алгоритмы можно разделить на несколько классов:

– гипотеза – тест;

– штрафная функция;

– метод скелетирования;

– нечеткая логика.

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

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

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

Вывод

В связи с попытками создать автономное движущееся средство или подвижного агента возникает ряд проблем, объединенных общим названием – «навигационные задачи». Речь идет, в первую очередь, о движении по земной поверхности, хотя полученные в этой области результаты с успехом применяются при движении подводных аппаратов или наведении ракет, и уже имеют успех в разработке компьютерных игр.

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

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

Литература

1. Браян Стоут. Алгоритмы поиска пути [Електронний ресурс]/ Браян Стоут. – [Електронний ресурс]. Режим доступу: <http://pmg.org.ru/ai/м index.html>

2. Курейчик В.М. Генетические алгоритмы и их применение. Таганрог: ТРТУ, 2002.

3. Lozano-Perz T. An Algorithm of Planning Colisions Free Paths among Polyhedral Abstracts/ T. Lozano-Perz – ACM,1984. P560-570.

4. Курейчик В. М. Поисковая адаптация: теория и практика/ Курейчик В. М., Лебедев Б. К., Лебедев О. К. – М: Физматлит, 2006. – С. 272. С. 59.

5. Sharon Laubach. Sensor-based Autonomous Navigation for Mars Rover [Електронний ресурс]/ Sharon Laubach, Joel Burdick. Larry Matthies. – [Електронний ресурс] Режим доступу: <http://secretary.erc.caltech.edu/~burdick/research/sharon/ roveretailed.htm>

6. K.Samejima. Adaptive internal state space construction method for reinforcement learning of a real-world agent/ K.Samejima, T. Omori – Neural Networks, 1999.

7. Zbigniev Michailevich. Genetic Algoritms plus Data Structures equal Evolution Programs. –Springer, 1999. – 387c.

8. В.А. Плотников. Анализ эффективности существующих методов уклонения от столкновения для мобильного робота // Плотников В.А. – Донецк: Штучний інтелект – 2010.

9. А.И. Ольшевский. Решение задачи Штейна при помощи генетического алгоритма // Ольшевский А.И., Починский М.Ю. : Бионика интеллекта –2008.

10. Емельянов В.В. Теория и практика эволюционного моделирования/ В. В.Емельянов, В. В. Курейчик В. В., В. М. Курейчик. – М: Физматлит, 2003. – С. 432.