ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 3, с. 163-173
^=РОБОТОТЕХНИКА
УДК 621.865.8;007:159.955
СИСТЕМА ПЛАНИРОВАНИЯ ДВИЖЕНИЯ ГРУППЫ МОБИЛЬНЫХ МИКРОРОБОТОВ НА ОСНОВЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ*
© 2007 г. О. В. Даринцев, А. Б. Мигранов
Уфа, Институт механики Уфимского научного центра РАН Поступила в редакцию 20.05.06 г.
Рассматривается генетический алгоритм планирования оптимальных маршрутов для группы микророботов в среде с препятствиями, позволяющий решать поставленную задачу в соответствии с наиболее часто задаваемыми критериями: минимальная длина маршрута, минимизация времени движения и т.д. Высокое быстродействие предлагаемого алгоритма позволяет находить решение в режиме реального времени, используя ресурсы только бортовых вычислительных устройств микророботов. Представлены результаты моделирования и оптимальные значения параметров, при которых достигается наилучшая балансировка алгоритма.
Введение. В настоящее время широкое распространение получают автономные подвижные системы самых различных классов и функциональных назначений. К ним относятся всевозможные транспортные средства (наземные, воздушные, надводные), включая промышленные мобильные роботы, предназначенные для выполнения разнообразных функций в автономном режиме без участия человека. Наряду с мобильными роботами "классических" размеров существуют также мини- и микророботы, одной из перспективных областей применения которых может стать реализация сборочных, отладочных и тестовых операций над микроэлектронными изделиями. К примеру, использование мобильных микросборочных роботов (микророботов) в составе специализированных технологических комплексов может стать одним из эффективных подходов для автоматизации сборки гибридных микроэлектромеханических систем [1].
Вместе с тем одной из проблем применения робототехники является планирование оптимальных маршрутов движения мобильных роботов, одновременно оперирующих в пределах единого рабочего пространства. Если рассматривать группу микросборочных роботов, то планирование должно осуществляться с учетом наиболее предпочтительного варианта обхода всех встречающихся неподвижных препятствий в эоне проведения технологических операций, при этом необходимо исключить столкновения микророботов между собой, а также их выход за границы рабочего пространства. Наиболее
часто используемые в настоящее время аппарат
*
Работа выполнена при финансовой поддержке РФФИ (грант < 05-01-97906), Фонда содействия отечественной науке (грант "Кандидаты наук РАН") Фонда содействия отечественной науке, в рамках программы №16 фундаментальных исследований ОЭММПУ РАН.
многопараметрической оптимизации и алгоритмы оптимального планирования мало пригодны для решения этой задачи в реальном времени бортовыми вычислительными устройствами микророботов, что объясняется их скромными вычислительными возможностями, а также высокой размерностью уравнений, описывающих группу микророботов как объект планирования и управления. Аналитическое решение задач оптимального управления в такой постановке задачи невозможно, а известные численные методы требуют непозволительно большого времени для получения приемлемого решения.
Другой причиной разработки быстросчетных алгоритмов планирования и управления микророботами служит одна из наиболее актуальных в последнее время задач - создание распределенной одноранговой системы управления большими коллективами роботов. Данная задача нетривиальна, так как наряду с требованиями компактности и быстродействия программных продуктов, реализуемых на бортовых вычислительных комплексах, накладываются существенно более жесткие требования к реализации режима реального времени и адаптивности алгоритмов к изменяющимся внешним условиям. Такие требования приводят к необходимости отказа от классических схем построения системы управления и планирования и перехода в интеллектуальный базис. Одним из подобных подходов, который позволяет достаточно эффективно управлять сложными техническими объектами в условиях дефицита машинных ресурсов и высокой размерности поискового пространства, являются генетические алгоритмы (ГА).
Впервые использовать ГА в задаче планирования оптимальных маршрутов было предложено в 90-х годах прошлого века [2-5]. Анализ этих работ показал, что они не могут быть впрямую использованы для планирования траекторий мик-
163
11*
ророботов. Общая черта известных методов планирования на основе ГА - двухмерное сеточное представление модели внешней среды путем разбиения рабочей области на конечное постоянное число прямоугольных элементарных участков. Главный недостаток этого подхода состоит в том, что поиск оптимального решения проводится не в пространственно-временном, а только в координатном базисе. Вместе с тем в условиях нестационарной внешней среды, когда наряду со статическими в пределах рабочей зоны имеются динамические препятствия, более предпочтительный вариант обеспечения бесконфликтного движения предполагает не только изменение маршрута движения, но и регулирование значения скорости движения каждого из роботов на определенных участках маршрута, что возможно только при пространственно-временном представлении модели рабочего пространства. Другим недостатком известных методов на базе ГА является слабая организация процессов управления разнообразием популяции, и как следствие, - низкая скорость сходимости ГА или же их преждевременная сходимость [4]. В предлагаемом алгоритме планирования в качестве модели внешней среды используется представление пространство-время, а высокая скорость сходимости ГА обеспечивается организацией процесса управления разнообразием популяции на базе операций скрещивания, мутации, спрямления и сглаживания.
1. Модель нестационарной рабочей среды, описание в базисе пространство-время. Рассмотрим задачу планирования траектории движения мобильного микроробота в некоторой области со стационарными и подвижными препятствиями. В качестве подвижных препятствий выступают другие микророботы из группы, имеющие более высокий приоритет работы и перемещающиеся с определенными скоростью и ускорением по известным законам, которые удовлетворяют граничным условиям. Будем считать, что расположение неподвижных препятствий на момент планирования фиксировано и остается неизменным во времени. Оптимальное решение должно обеспечивать бесконфликтное движение микроробота с возможностью изменения его скорости вдоль найденного маршрута.
В интересах решения этой задачи с помощью ГА формируется модель внешней среды. Для ее описания используется N сеточных представлений рабочего пространства в виде матриц размерностью Бх х Бу (рис. 1), элементы которых принимают логические значения, в зависимости от того свободна или занята препятствием соответствующая ячейка сетки. Величина N выбирается в зависимости от шага квантования по времени и характеризует период, в течение которого движение препятствий в рабочей области задано, определяя
максимальную глубину планирования по времени. Квантование необходимо для дискретизации состояния неподвижных объектов, определения ячеек сетки, соответствующих стартовым и конечным положениям микроробота, а также для фиксирования моментов изменения состояния нестационарной рабочей среды.
В качестве индивидуумов рассматриваются маршруты движения по ячейкам сеток, и хромосома представляет собой последовательность Np узлов, образующих траекторию движения. При этом каждый 7-й узел содержит гены, представляющие собой координаты x7 и y7 соответствующей ячейки, а также индекс (период) времени 1, в течение которого микроробот находится в данной ячейке (рис. 2). Гены, отвечающие индексам времени и расположенные в последовательных узлах хромосомы, отличаются на единицу. Также вводится понятие сегмента хромосомы, под которым понимается несколько последовательных узлов (участок маршрута). Первый узел является стартовой точкой маршрута, а последний - конечной. Число генов в хромосоме динамически изменяется от итерации к итерации, однако общее число промежуточных узлов Np не превышает величину N.
Будем называть начальной популяцией те траектории, что соединяют точки старта и цели. Очевидно, что начальных популяций, переводящих микроробота к точке цели, может быть произвольное число. Потенциальные решения в виде начальной популяции могут и отсутствовать. Это свидетельствует о том, что не существует траектории, соединяющей начальную и конечную точки, или о том, что время движения по этой траектории больше, чем время N определенности рабочей области. Ясно, что множество начальных популяций представляет собой подмножество множества безопасных траекторий.
Главным требованием при выборе оптимального решения на каждом этапе эволюции является его соответствие следующему неравенству:
Smax 7 > Smax 7 - Ь где Smax 7 и Smax 7 - 1 - максимальные
значения критериев выживания на 7-м и (7 - 1)-м эволюционных этапах. В качестве функции пригодности используется следующая:
5 5
S = X®kSk' X® = 1
k=1 k=1
где ®k = const e [0, 1] - весовые коэффициенты, Sk -нормированные значения функций соответствия, характеризующих степень близости потенциального решения по заданному k-му критерию к оптимальному маршруту.
ХЫ - 1, УN - 1, Ы, - 1
Ж "'ЙЗВ
N.
Уo, .о
Я
Рис. 1. Модель внешней среды: ^ - свободные области рабочего пространства, - статические препятствия,
^^^ - другие микророботы, - текущее положение.
Первая из них 51 представляет критерий оптимальности по длине траектории
Гыр -1
Sl =
^ „Д X, + 1 - X,)2 + (у, + 1 - у, )2
V г =0
Гыр -1
^ С(X,, X, + !, у,, у, + ! )
,=0
где С(х, + ь у, у, + 1) = 1 при перемещении в соседнюю ячейку по горизонтали и вертикали и С(х,,
узел
Л
ген
сегмент
А
Л
■о Уо .0 ■1 У1 .1 ХЫ - 2 УЫ - 2 Ы - 2 ХЫ - 1 УЫ - 1 Ы - 1
V N.
Рис. 2. Кодировка маршрута движения в хромосоме. ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ < 3 2007
Х1 + 1, Уг, Уг + 1) = - по диагонали. Вторая £2 отражает условие оптимальности по времени, затраченному на движение по маршруту
£2 = .
Функция соответствия £3 позволяет найти маршрут, проходящий на безопасном расстоян
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.