Планирование маршрута на основе облачно-точечной карты и улучшенного муравьиного алгоритма

ОБРАБОТКА ИНФОРМАЦИИ В НАВИГАЦИОННЫХ, СПУТНИКОВЫХ И ИНТЕГРИРОВАННЫХ СИСТЕМАХ

УДК 004.021

ПЛАНИРОВАНИЕ МАРШРУТА НА ОСНОВЕ ОБЛАЧНО-ТОЧЕЧНОЙ КАРТЫ И УЛУЧШЕННОГО МУРАВЬИНОГО АЛГОРИТМА

H.A. Чулин, Кэ Кэ Гэн

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

Ключевые слова: планирование маршрута, муравьиный алгоритм, дорожная

карта.

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

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

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

Для решения этих проблем в настоящей работе предлагается новый метод планирования маршрута на основе дискретной облачно-точечной карты.

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

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

Карта поиска разбивается на несколько кольцевых безопасных и опасных зон в соответствии с положением и размерами препятствий с равномерным расположением точек сетки в опасных зонах, как показано на рис. 1, где: Бр В2>Вз - препятствия; Бр 82* 83 - безопасные зоны; Бр Б2 - опасные зоны; О - позиция робота; О - целевая точка; р  Р2  Р3  О - один из возможных маршрутов без столкновений.

Видим, что структура облачно-точечной карты определяется следующим образом: Карта = [0, О, В, Б, В, Р], где В - препятствия; 5 -

безопасные зоны; В - опасные зоны; Р- точки поиска возможных маршрутов.

Чтобы понять, как функционирует алгоритм, нужно рассмотреть поведение муравья, движущегося от муравейника в поисках пищи. Изначально муравей движется в случайном направлении. Если муравей находит пищу, то он возвращается к муравейнику, помечая пройденный путь специальным химическим веществом - феромоном. Следующий муравей с большей вероятностью последует по тропе, уже помеченной феромоном. Посредством феромона происходит связь между муравьями и поиском оптимального маршрута при отсутствии централизованного управления и

81

знаний обо всей сети, а феромонные тропы являются как бы «коллективной памятью» муравейника. Однако феромон как химическое вещество испаряется с течением времени, поэтому муравьи вынуждены осваивать новые маршруты и выбирать среди них оптимальный. Вероятность перехода муравья к из позиции / в позицию у запишется в виде [9]

4

ZOl

р-, /Е allowedje allowed^ • О, others,

о)

где Ту - количество феромона на дуге у ; а - параметр влияния на Ту или

«нюх» муравья; щ- =1/с!у = 1 - х^2 + (у; - у^ - величина, обратно

пропорциональная длине дуги у; р - параметр, влияющий на щ- или

«зрение» муравьев; а11ом?ес1к- множество позиций, которые может выбрать муравей к.

S3 Л

D2

Dl^A'

O

Рис. 1. Схема облачно-точечной карты

По завершении очередной итерации алгоритма (когда все муравьи достигли конечных точек) происходит испарение феромона:

Чу (/ +1) = (1 - р)тгу (0 + рАХу (0;

in

Jk t

Ату (0 = 2^(0,

где к - номер муравья из популяции; / - номер итерации; ре (0,1)- скорость испарения феромона; ДТу (0 - приращение феромона; т - величина популяции муравьев.

Обновление феромона можно представить в виде:

А4

J [ О, others, где Q- запас феромона; L^- длина пройденного пути; tabujc- множество дуг, пройденных муравьем k; (z, j)e tabu^ - прохождение муравья к через дугу ij.

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

Для улучшения традиционного муравьиного алгоритма необходимо построение новой функции вероятности перехода, позволяющей уменьшить рассматриваемое число путей:

* Лм

-, z Е allowedj Е allowed£ ;

4

Z- lij hg ij ij

О, others,

где r\jg = \/djg =1 /J(xj -Xg)2 +(yj ~ Уg)2 ~ величина, обратная длине дуги jg\ Qfj- величина, обратная углу Z/zg;

djj = 1/дj(xj - Xj)2 + (yj - у j)2 - величина, обратная длине дуги ij\ 7, г-

параметры влияния.

В новой функции вероятности перехода были добавлены два «вдохновляющих» фактора и их параметры влияния, позволяющие быстрее найти самый кратчайший путь (рис. 2).

На рис. 2 точка О - текущая точка; G - целевая точка; А, В,С -точки с возможностями проходов.

Для традиционного муравьиного алгоритма точки А, В,С имеют одинаковые вероятности перехода. Если в функцию вероятности перехода добавим «вдохновляющий» фактор, обратный величине угла 0(Bj < 62), то вероятность перехода от точки О к точкам А и С станет больше, чем вероятность перехода от точки О в точку В. Если в функцию вероятности перехода добавим «вдохновляющий» фактор, обратный длине дуги d(d()A < ^ос) > то вероятность перехода от точки О в точку А станет больше, чем вероятность перехода от точки О в точку С. Таким образом, можем найти точку с самой большой вероятностью перехода.

83

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

С

Рис. 2. Выбор маршрутов с разными вероятностями

Рис. 3. Поиск маршрута. Синий маршрут - традиционным алгоритмом; красный маршрут - улучшенным алгоритмом

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

'Qt = m х m;

k m

Qy = ii nj x(m - n), i=lj=l

где Qt , Qy - размеры матриц смежности традиционного и улучшенного алгоритмов; nj - количество проходимых точках j-го муравья в i-й итерации; k - количество итерации; m - количество муравьев.

В общем случае Qy << Qt , что позволяет ускорить вычисления.

Определим область (сферу) наблюдения перед препятствием и запрещенную область перехода для каждой точки:

obs - num obs - num

Scope _ Pj = I Pj _ scopei; Pj _ fob = I Pj _ fobi, (6) i=1 i=1 где obs - num - количество препятствий; Pj - точка маршрута.

Обозначим буквой O начальную точку, буквой G целевую.

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

- если вектор OG не в сфере наблюдения перед препятствием Scope _ O, то не следует создавать облачно-точечную карту, так как робот может двигаться непосредственно от текущей позиции в целевую точку, как показано на рис. 4, а;

- если вектор PjG входит в сферу Scope _ Pj, то робот движется от

текущей позиции в точку Pj+1, которая имеет наибольшую вероятность перехода и не находится в области Pj _ fob;

- если вектор PG входит в сферу Scope_P, то можно остановить поиск маршрута, то есть робот может двигаться непосредственно из текущей позиции в целевую точку, как показано на рис. 4, б для точки P2.

Рис. 4. Стратегия избегания препятствий

85

Работоспособность алгоритма проверялась моделированием планирования маршрута в среде Ма11аЬ. В области моделирования существуют четыре препятствия с разными радиусами; С- целевая точка; О - начальная точка. Чтобы проиллюстрировать преимущества предлагаемого улучшенного муравьиного алгоритма (УМА), сравним результаты планирования маршрута с традиционным муравьиным алгоритмом (ТМА). Результаты моделирования показаны на рис. 5.

024 6 8 10 02468 10

а б

О 2 4 6 8 10 О О 2 4 6 8 10

в г

Рис. 5. Результаты моделирования планирования маршрута: а - ТМА, Ь=2; б - ТМА, Ь=2; в - УМА, Ь=2; г - УМА, Ь=1

На рис. 5 точки со звездочками - точки поиска маршрута; рис. 5, а и в - результаты при расстоянии между кругами «сетки» Ь = 2 ; рис. 5, б и г - результаты при расстоянии между кругами «сетки» Ь = 1; жирные сплошные линии - результаты планирования маршрута при числе итераций N = 20; жирные пунктирные линии - результаты планирования маршрута при числе итераций N = 3. Количественные результаты приведены в таблице.

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

86

Сравнение результатов моделирования

Вид алгоритма Значения L и N Длина маршрута, М Число шагов поиска Время вычисления, С

ТМА L = 1; N = 3 14,023 12 3,215

L = 1; N = 20 12,265 11 3,852

L = 2; N = 3 13,576 5 2,758

L = 2; N = 20 12,598 5 3,035

УМА L = 1; N = 3 13,892 4 1,254

L = 1; N = 20 10,770 2 1,264

L = 2; N = 3 13,621 3 1,035

L = 2; N = 20 10,770 2 1,136

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

Список литературы

1. Barraquand J, Latombe J. C. Robot motion planning: A distributed representation approach // The International Journal of Robotics Research. 1991. No. 10(6). P. 628-649.

2. Bhattacharya P., Gavrilova M. L. Roadmap-based path planning-Using the Voronoi diagram for a clearance-based shortest path // Robotics & Automation Magazine, IEEE. 2008. No. 15(2). P. 58 - 66.

3. Гастилович Е.А., Дементьев В. А., Мшиенина К.А. Потенциальное поле и частоты колебаний молекулы антрахинона // Журнал физической химии. 1981. С. 55 - 73.

4. Лебедев О.Б., Лебедева Е.М., Пестов В.А. Алгоритмы планирования движения подводного аппарата // Известия Южного федерального университета. Технические науки. 2015. No. (165). С. 67 - 77.

5. Pan P. Improved Ant Colony Algorithm for Path Planning of Soccer Robot // Journal of Convergence Information Technolog. 2013. No. 8(7). P. 958 - 965.

6. Щербаков В.С., Корытов М.С. Оптимизация трассы автомобильной дороги на рельефе с препятствиями методом вероятностной дорожной карты // Вестник СибАДИ. 2012. N 2 (28). С. 88 - 93.

7. Welzl E. Constructing the visibility graph for n-line segments in O(n2) time // Information Processing Letters. 1985. N 20(4). P. 167 - 171.

8. Соловьев В.В., Шаповалов И.О., Шадрина В.В. Планирование траектории подвижного объекта с применением диаграммы Ворного // Известия Южного федерального университета. Технические науки. 2015. N 2 (163). С. 29 - 40.

9. Штовба С. Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. 2003. No. 4(4). С. 70 - 75.

Чулин Николай Александрович, канд. техн. наук, доц., nchulin@yandex.ru, Россия, Москва, Московский государственный технический университет имени Н.Э. Баумана,

Гэн Кэ Кэ, асп., jsgengke@126. com, Россия, Москва, Московский государственный технический университет имени Н. Э. Баумана

ROUTE PLANNING BASED ON CLOUD-POINTS MAPS AND IMPROVED

ANT-COLONY ALGORITHM

H.A. Chulin, Geng Ke Ke

Based on discrete cloud-points map and improved ant-colony algorithm we propose a method for optimizing the movement of navigation, allowing you to quickly solve the problem of global route planning. Built discrete cloud-points map with detected obstacles. Improved ant-colony algorithm: eliminated limiting of search length at each step; reduced the size of the adjacency matrix; added inspiration factors in the calculation of the transition probabilities, which allow increase computing speed and find a shorter and smooth route. The simulation results show the correctness and validity of the proposed method.

Key words: route planning, ant-colony algorithm, road map.

Chulin Nikolay Alexandrovich, candidate of technical sciences, docent, nchu-lin@yandex.ru, Russia, Moscow, BaumanMoscow State Technical University,

Geng Ke Ke, postgraduate, jsgengke@126. com, Russia, Moscow, Moscow Bauman State Technical University