Васюк А.О. - ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В СИСТЕМАХ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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. Zbigniev Michailevich. Genetic Algoritms plus Data Structures equal Evolution Programs. –Springer, 1999. – 387c.

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

Планирование пути автономного робота в изменяющейся окружающей среде