Автор : Збигниев Михайлечичз
Автор перевода: Анна Олеговна Васюк
Источник: Збигниев Михайлечичз. Генетические алгоритмы + структуры данных = эволюционная программа/ Збигниев Михайлечичз.– Спрингер,1999
Навигация наука (или искусство) об управлении ходом мобильного робота при прохождении окружающей среды. Основой любой системы навигации является желание достичь пункта назначения, не заблудиться или врезаться в любые объекты.
Часто путь для робота планируется автономно, что может привести робота в пункт назначения при условии, что окружающая среда прекрасно известна и стационарна, и робот может ее отлично чувствовать. Раннее планирование пути было автономным применялось только для таких автономных агентов (например, [1,2]). Тем не менее, ограниченность автономного планирования привело исследователей к изучению онлайн-планирования, которое опирается на знания, полученные от зондирования местной окружающей среды [3] для обработки неизвестных препятствий, в то время как робот проходит в окружающей среде.
Эволюционные программы, которые мы описываем здесь, то есть эволюционный навигациитор (ЭН), объединяющей в автономном режиме и режиме он-лайн планирования с простой картой высокой точности и эффективный алгоритм планирования [4,5]. В первой части алгоритма (автономный планировщик) ищет оптимальные пути глобального с самого начала до пункта назначения, а вторая часть (он-лайн планировщик) отвечает за обработку возможных столкновений или ранее неизвестных объектов, заменив части оригинального глобального пути на оптимальный субпуть. Важно отметить, что обе части ЭН используют тот же эволюционный алгоритм, но с разными значениями различных параметров.
За последние пять лет другие исследователи экспериментировали с эволюционным методам вычислений для задачи планирования пути. Davidor [6] использовал динамические структуры хромосом и изменение кроссовер оператора, чтобы оптимизировать некоторые реальные мировые процессы (в том числе приложения путей робота). В работе [7] генетический алгоритм для задачи планирования путь описан, а в [8] представлен генетический алгоритм для развития в реальном времени нескольких эвристических стратегий поиска. Оба подхода предполагают предопределенные карту, состоящую из узловых точек. Другие исследователи использовали системы классификаторов [9] или генетическую программную парадигму [10], чтобы подойти к решению проблемы путем планирования. Наш подход является уникальным в том смысле, что эволюционная Navigator (1) работает на всем свободном пространстве и не дает никаких априорных предположений о возможности узловых точек в пути, и (2) соединяет вместе с он-лайн и он-лайн планирует алгоритмов.
Прежде чем объяснить алгоритм подробно, давайте сначала объясним структу карту. В целях поддержки поиска пути во всем пространстве положим, что оно непрерывное и свободное, вершинные графы используются для представления объектов в окружающей среде. В настоящее время мы ограничиваем окружающую среду, испаользуем только двумерное представление объектов и движений робота считаем поступательным. Таким образом, робот может быть представлен в виде в точки, а объекты в окружающей среды «расти» соответственно [11]. Мобильный робот оснащен ультразвуковыми датчиками (например, Деннинг робот) предполагается на EN. Известный объекты представляются упорядоченным списоком своих вершин(по часовой стрелке). Он-лайн встречаются неизвестные препятствия и моделируются куски «стена», где каждая часть «стена» является прямолинейным и представлена списоком из двух конечных точек. Это представление согласуется с представлением известных объектов, а также вмещает частичную информацию о неизвестных препятствиях, которые могут быть получены из зондирования в определенном месте. И, наконец, вся среда определяется как прямоугольная область.
Сейчас важно определить пути, которые генерирует эволюционный навигатор. Путь состоит из одного или нескольких прямолинейных отрезков, с начального положения, цели места, и (возможно) пересечение местах двух смежных сегментов – узлов. Возможный путь состоит возможных узлов; невозможным путь содержит хотя бы один узел невозможным. Предположим, что существует путь path p = (mi, m2,..., mn) (n > 2), где mi и mn обозначают начало и цель узлов, соответственно. Узел (i = 1,..., n—1) является недопустимым, если оно либо не подключаться к следующему узлу rrii+i в связи с препятствиями, или он находится внутри (или слишком близко к) препятствие сома. Мы предполагаем, , что начальный и целевой узлы находятся за пределами препятствий, и не слишком близко к ним. Однако следует отметить, что в начале узла не обязательно должно быть возможно (он может не подключается к следующему узлу), в то время как цель не всегда возможный. Отметим также, что разные пути могут иметь разное число узлов. Теперь мы готовы пройти через процедуру эволюционного навигатора Рисунок 1.
Рисунок 1 – Визуализация работы эволюционного навигатора
Эволюционный навигатор сначала считывает карту и получает начальное и целевое заданое положение. Затем офф-лайн эволюционный алгоритм (FEG) генерирует близкий к оптимальному глобальный путь, кусочно-прямолинейный путь, состоящий из допустимых точек или узлов. Рисунок 2 показывает такой глобальный путь порожденных FEG. (Заполненный круг имитирует робота).
Рисунок 2 – глобальный путь порожденных FEG
Как робот начнет следовать по пути, чтобы двигаться к цели, он чувствует окружающую среду и его близость к объектам, а также он-лайн эволюционный алгоритм (NEG) используется для создания местных путей для решения неожиданных столкновений и объектов. Для имитации эффекта неизвестных объектов в окружающей среде, дополнительно, были созданы файлы данных, чтобы представлять такие препятствия (например, куски «стены», как описано ранее). Мы экспериментировали с пятью различными наборами неизвестных объектов, рисунок 3. ad представляет действия робота на одном из этих множеств.
Рисунок 3 – Движение робота по алгоритму ЭН
Когда робот перемещается слишком близко к нижнему левому углу соседнего объекта, NEG практически «выросли» «А» на месте и затсаляет локальный путь держаться в стороне от «А», которая также была частью прямолинейного пути.Робот затем следуют текущий путь успешно дойти до «а» пункта. В то время как робот перемещается от «а» до «b», он обнаружил неизвестноого или нового объекта «B». Теперь EN обновил карту, и снова, NEG вызвала локальный путь с узлом точки «D» (рис. 11.3a ). Как робот перемещается от «d» к «b», он стал слишком близко к объекту «B»: следовательно, создан другой локальный путь в лице узел точка «Е» (рис. 3b).Робот затем переехал с «D» на , наконец, достигли подцель «B». Следующим шагом был переход от «B» для достижения цели, как показано на рисунке 3c, отрезке пути было слишком близко к нижнему правому углу объекта «С». Таким образом, еще один локальный путь был создан в лице узеловой точки T, а затем в «цель». Рисунок 3d показывает оригинальный глобальный путь и фактический путь, пройденный. Обратите внимание, что процесс навигация прекращается, когда робот приходит на цель или в неисправном состоянии, как сообщается, т. е. если эволюционный навигатор не может найти возможный путь в определенный период времени (т.е. в течение определенного количества поколений NEG).
Как мы уже упоминали, эволюционный навигатор сочетает в себе с автономное и онлайн-планирование с той же структурой данных и тот же алгоритм планирования. То есть, единственное различие между FEG и NEG в параметрах которые они используют: численность населения, число поколений, максимальная длина хромосомы, и т.д. Заметим, что оба алгоритма FEG и NEG делают глобальное планирование, даже если NEG обычно создает локальный путь, он работает на обновленной глобальной карте. Более того, если объект не первоначально известная в окружающей среде, или нет изначально известных объектов между местом старта и цели, то FEG создаст прямолинейный путь только с двумя узлами:начала и цели местах. Это будет исключительно зависеть от NEG ка вести робота к цели, избегая при этом неизвестне препятствия.