Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,441

СИНТЕЗ ГИБРИДНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ АЛГОРИТМОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ

Даринцев О.В. 1 Мигранов А.Б. 1
1 ФГБУН «Институт механики им. Р.Р. Мавлютова» УНЦ РАН
Рассматриваются вопросы построения интеллектуальной гибридной системы планирования траекторий мобильных роботов. Гибридная архитектура системы позволяет формировать оптимальную траекторию в двух приближениях: грубом и точном. На этапе грубого планирования формируется модель внешней среды для поиска траектории с использованием генетических алгоритмов. Полученное на этом этапе решение является приближенным, и окончательный вид траектории формируется уже подсистемой точного планирования, реализованной на базе нечетких алгоритмов. Предложенный подход может использоваться для решения задачи планирования в условиях, когда вычислительные возможности бортовых электронных устройств ограничены габаритными размерами робота, а высокая степень изменчивости и неопределенности рабочей среды требует от системы управления интеллектуальных способностей при принятии решений. Представлены результаты планирования, проведен сравнительный анализ и выделены основные особенности использования разработанного подхода.
планирование
мобильный робот
гибридный алгоритм
генетический алгоритм
нечеткая логика
1. Даринцев О.В., Мигранов А.Б. Области применения приближенных и интеллектуальных методов планирования траекторий для групп мобильных роботов // Современные проблемы науки и образования. – 2014. – № 6; URL: www.science – education.ru/120-16542.
2. Даринцев О.В., Мигранов А.Б. Различные подходы управления движением мобильных роботов на основе технологий мягких вычислений // Искусственный интеллект. – 2012. – № 3 IПШI МОН i НАН Укра ни “Наука i Освiта”. – С. 339–347.
3. Даринцев О.В., Мигранов А.Б. Разработка архитектуры гибридной интеллектуальной системы планирования траекторий мобильных роботов // Материалы 8-й Всероссийской мультиконференции по проблемам управления. Т.2. – Ростов-на-Дону: Изд-во Южного федерального университета, 2015. – С. 124–126.
4. Даринцев О.В., Мигранов А.Б. Система планирования движения группы мобильных микророботов на основе генетических алгоритмов // Известия РАН. Теория и системы управления. – 2007. – № 3. – С. 163–173.
5. Garcia M., Montiel O. Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation // Appl Soft Comput, 2009, ISSN 1568-4946, 9(3): 1102–1110.
6. Tuncer A., Yildirim M. Dynamic path planning of mobile robots with improved genetic algorithm // Comput Electr Eng, 2012, ISSN 0045-7906, 38: 1564–1572.
7. Xiao J., Huang Y., Cheng Z., He J., Niu Y. A hybrid membrane evolutionary algorithm for solving constrained optimization problems // Optik, 2014, ISSN 0030-4026,
125(2): 897–902.

В последнее время значительная часть исследований в робототехнике посвящена вопросам применения мобильных роботов: показывается перспективность их использования в задачах автоматизации технологических процессов, мониторинга, исследования окружающей местности и многих других приложениях. В этой связи особый интерес представляет взаимодействие агентов в группах мобильных роботов, так как использование мобильных роботов в составе группы позволяет увеличить надежность в целом, сократить время выполнения поставленной задачи и гарантировать ее выполнение даже при выходе из строя отдельных роботов. Поэтому не теряет актуальности одна из фундаментальных проблем робототехники: планирование оптимальных маршрутов движения мобильных роботов, одновременно функционирующих в пределах единого рабочего пространства. Сложность решения проблемы определяется недетерминированностью окружающей обстановки; повышенными требованиями к бортовой системе управления: необходимо принятие решений в реальном масштабе времени при наличии дефицита ресурсов. Поэтому известные системы планирования группами роботов часто строятся с использованием различных методов искусственного интеллекта [5–7].

Как показывают результаты сравнительного анализа эффективности интеллектуальных алгоритмов, используемых для решения рассматриваемой задачи, результаты их работы в большей мере зависят от требуемого уровня детализации маршрута, количества роботов в группе, наличия и объема сенсорной информации [1]. Также большое влияние на результат работы имеют некоторые специфические особенности применяемых методов: генетические алгоритмы (ГА) позволяют избежать появления локальных экстремумов; нейросети могут быть реализованы с использованием нейроускорителей, а также обладают способностью быстрой адаптации с организацией пере- или дообучения в реальном времени, нечеткие алгоритмы (НА) нетребовательны к аппаратным ресурсам при достаточно высокой скорости обработки.

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

Гибридная архитектура системы планирования

Гибридная система будет эффективна в условиях, когда возможности систем технического зрения (СТЗ) не позволяют в полной мере обеспечить расчет безопасных траекторий, что связано с малыми габаритами объектов в рабочем пространстве или в больших по площади рабочих зонах [3]. Когда разрешающей способности СТЗ недостаточно для синтеза безопасных траекторий движения, выполняемое при этом планирование движений может быть отнесено к грубому планированию. Благодаря низкому уровню детализации алгоритмы грубого планирования отличаются быстросчетностью и позволяют легко решать оптимизационную задачу в соответствии с одновременно задаваемыми критериями: минимальной длиной маршрута, минимизацией времени перемещения и т.д. Однако это не снимает необходимости и в точном планировании траекторий: для исключения столкновений в рабочей зоне, обеспечения безопасных расстояний относительно препятствий и других роботов. Недостаточная разрешающая способность СТЗ в этом случае компенсируется бортовыми сенсорными системами роботов (ближняя локация). При одновременном использовании этих методов система планирования будет иметь гибридную архитектуру (рис. 1).

pic_22.tif

Рис. 1. Архитектура гибридной интеллектуальной системы планирования траекторий мобильных роботов

Подсистема грубого планирования

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

? изменены используемые критерии качества;

? изменен набор генетических операторов;

? увеличен шаг дискретизации.

Это позволяет сократить наиболее затратные в вычислительном плане математические операции и увеличить общее быстродействие алгоритма. Получаемое при этом некоторое снижение качества траектории компенсируется подсистемой точного планирования.

Как и в базовом методе, для описания модели внешней среды используются матрицы размерностью Sx?Sy, элементы которых принимают логические значения «0» или «1» в зависимости от того, свободна или занята препятствием соответствующая ячейка сетки. Количество матриц N выбирается в зависимости от шага квантования по времени и характеризует период, в течение которого движение препятствий (других роботов) в рабочей области задано, определяя максимальную глубину планирования по времени. В качестве индивидуумов рассматриваются маршруты движения по ячейкам сеток, а хромосома представляет собой последовательность N узлов, образующих траекторию движения. Первый узел является стартовой точкой маршрута, а последний узел – конечной. В качестве функции пригодности служит следующий функционал:

darints01.wmf darints02.wmf

где ?k = const ? [0, 1] – весовые коэффициенты; Sk – нормированные значения функций соответствия, вычисляемых для проверки степени близости потенциального решения по заданному k-му критерию к оптимальному маршруту.

Функция соответствия S1 характеризует критерий оптимальности по длине траектории:

darints03.wmf

где xi и yi – координаты текущей точки, xi + 1 и yi + 1 – координаты следующей точки, d(xi, xi + 1, yi, yi + 1) = 1 при перемещении в соседнюю ячейку по горизонтали и вертикали, и darints04.wmf – по диагонали.

Функция соответствия S2 характеризует критерий оптимальности по времени, затраченному на движение по маршруту:

darints05.wmf

где Np – длина хромосомы.

Использование двух функций S1 и S2 позволяет выбирать из популяции оптимальный маршрут независимо от скорости движения робота вдоль пути.

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

Подсистема точного планирования

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

Подсистема точного планирования основана на НА [2]. В качестве входных сигналов нечёткого регулятора используется следующая информация: A – свободные области рабочей зоны; b – угловое отклонение от цели.

Свободные области рабочей зоны A – это матрица, формируемая на основе информации, поступающей от датчиков, расположенных в каждом из восьми возможных направлений движения (рис. 2, а). Угловое отклонение от цели b – входная переменная, определяющая отклонение курса движения мобильного робота от целевого направления (рис. 2, б).

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

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

pic_23.wmf pic_24.tif

а б

Рис. 2. а – кодировка элементов матрицы; б – угловое отклонение от цели

Результаты планирования

Рассмотрим результаты планирования траектории для модели рабочего пространства 8?8 с использованием ГА (рис. 3, а), НА (рис. 3, б) и гибридного подхода (рис. 4). В качестве критерия оптимальности используется длина траектории, значение которой выражается в условных шагах (у.ш.). С целью упрощения оценки предполагается, что длина шага при движении по горизонтали и вертикали совпадает с длиной шага по диагонали, а также с уменьшением шага дискретизации длина условного шага не изменяется. С учетом вышесказанного длина траектории, найденной с помощью ГА, составляет 15 у.ш., НА – 20 у.ш. и гибридного подхода – 13 у.ш.

Как видно из рис. 3, а, особенности алгоритма и используемая модель рабочего пространства не позволяют ГА проложить траекторию между узловыми точками C и D, хотя габариты робота позволяют двигаться ему по прямой, соединяющей эти точки, поэтому робот вынужден двигаться в обход «препятствия».

Особенностью работы НА (рис. 3, б) является получение бортовыми системами управления информации о внешней среде только в ближней окрестности робота, но больший уровень детализации окружающей обстановки позволяет уменьшить шаг ее дискретизации. Отсутствие модели всего рабочего пространства не позволяет роботу пройти по более короткому маршруту, чем найденный ГА, но благодаря более точной информации в ближней окрестности и меньшему шагу дискретизации, его траектория проходит вдоль отрезка, соединяющего точки C и D.

Гибридный алгоритм включает достоинства каждого из методов, и сгенерированная гибридной системой траектория является оптимальной по длине (рис. 4). На отрезках AC и DB робот осуществляет движение по грубой траектории, на отрезке CD – по точной траектории. Условием выбора того или иного алгоритма являются неравенства

lAC > dAC, lCD < dCD, lDB > dDB,

где lij – длина маршрута между точками i и j вдоль точной траектории; dij – длина маршрута между точками i и j вдоль грубой траектории.

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

pic_25.wmf pic_26.wmf

а б

Рис. 3. Планирование траектории с использованием: а – генетического алгоритма; б – нечеткой логики

pic_27.wmf

Рис. 4. Планирование траектории с использованием гибридного алгоритма

Работы по данной тематике выполнялись в рамках Программы фундаментальных исследований Президиума РАН I.40П, проект «Актуальные проблемы робототехники».


Библиографическая ссылка

Даринцев О.В., Мигранов А.Б. СИНТЕЗ ГИБРИДНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ АЛГОРИТМОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ // Фундаментальные исследования. – 2015. – № 12-4. – С. 676-681;
URL: http://fundamental-research.ru/ru/article/view?id=39603 (дата обращения: 20.06.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074