/>Введение
Роботы – это физическиеагенты, которые выполняют поставленные перед ними задачи, проводя манипуляции вфизическом мире. Для этой цели роботов оснащают исполнительными механизмами,такими как ноги, колеса, шарниры и захваты. Исполнительные механизмы имеютединственное назначение – прилагать физические усилия к среде. Кроме того, роботовоснащают датчиками, которые позволяют им воспринимать данные об окружающей ихсреде. В современных роботах применяются различные виды датчиков, включая те,что предназначены для измерения характеристик среды (например, видеокамеры иультразвуковые дальномеры), и те, которые измеряют характеристики движениясамого робота (например, гироскопы и акселерометры).
Большинство современныхроботов можно отнести к одной из трех основных категорий. Роботы-манипуляторы,или роботы-руки, физически привязаны к своему рабочему месту, например назаводском сборочном конвейере или на борту Международной космической станции. Вдвижении манипулятора обычно участвует вся цепочка управляемых шарниров, чтопозволяет таким роботам устанавливать свои исполнительные механизмы в любуюпозицию в пределах своего рабочего пространства. Манипуляторы относятся к типунаиболее распространенных промышленных роботов, поскольку во всем миреустановлено свыше миллиона таких устройств. Некоторые мобильные манипуляторыиспользуются в больницах в качестве ассистентов хирургов. Без робототехническихманипуляторов в наши дни не смогут продолжать свою производственную деятельностьбольшинство автомобильных заводов, а некоторые манипуляторы использовались дажедля создания оригинальных художественных произведений.
Ко второй категорииотносятся мобильные роботы.Роботы такого типа передвигаются в пределахсвоей среды с использованием колес, ног или аналогичных механизмов. Они нашлисвое применение при доставке обедов в больницах, при перемещении контейнеров вгрузовых доках, а также при выполнении аналогичных задач. Одним из примеровмобильного робота является автоматическое наземное транспортное средство (UnmannedLand Vehicle – ULV) NavLab, способное автономно передвигаться поавтомагистралям в режиме самовождения. К другим типам мобильных роботов можноотнести автоматическое воздушное транспортное средство(Unmanned AirVehicle – UAV), обычно используемое для воздушного наблюдения, химическойобработки земельных участков и военных операций, автономное подводное транспортноесредство(Autonomous Underwater Vehicle – AUV) для глубоководных морскихисследованиях, ипланетоход, такой как робот Sojourner, приведенныйна рис. 1.1, а.
/> />
а) б)
Рисунок. 1.1 – Фотографиишироко известных роботов: движущийся робот Sojourner агентства NASA, которыйисследовал поверхность Марса в июле 1997 года (а); роботы-гуманоиды РЗ и Asimoкомпании Honda (б)
К третьему типу относятсягибридные устройства – мобильные роботы, оборудованные манипуляторами. В ихчисло входят роботы-гуманоиды, которые по своей физическойконструкции напоминают человеческое тело. Два таких робота-гуманоида показанына рис. 1.1, б; оба они изготовлены в японской корпорации Honda. Гибридныероботы способны распространить действие своих исполнительных элементов на болееобширную рабочую область по сравнению с прикрепленными к одному местуманипуляторами, но вынуждены выполнять стоящие перед ними задачи с большимиусилиями, поскольку не имеют такой жесткой опоры, которую предоставляет узелкрепления манипулятора.
Реальным роботам обычноприходится действовать в условиях среды, которая является частично наблюдаемой,стохастической, динамической и непрерывной. Некоторые варианты среды обитанияроботов (но не все) являются также последовательными и мультиагентными.Частичная наблюдаемость и стохастичность обусловлены тем, что роботу приходитсясталкиваться с большим, сложным миром. Робот не может заглянуть за каждый угол,а команды на выполнение движений осуществляются не с полной определенностьюиз-за проскальзывания приводных механизмов, трения и т.д. Кроме того, реальныймир упорно отказывается действовать быстрее, чем в реальном времени. В моделируемойсреде предоставляется возможность использовать простые алгоритмы (такие какалгоритм Q-обучения),чтобы определить с помощью обучения необходимые параметры, осуществляя миллионыпопыток в течение всего лишь нескольких часов процессорного времени, а вреальной среде для выполнения всех этих попыток могут потребоваться годы. Крометого, реальные аварии, в отличие от моделируемых, действительно наносят ущерб.В применяемые на практике робототехнические системы необходимо вноситьаприорные знания о роботе, о его физической среде и задачах, которые он долженвыполнять для того, чтобы быстро пройти обучение и действовать безопасно.
/>1. Анализ технического задания/>1.1 Область применения и цельпостроения подсистемы
Разрабатываемаяподсистема, называемая «Подсистемой планирования действий интеллектуальногоробота» предназначена для планирования целенаправленных действийинтеллектуального мобильного робота в противодействующей, априорнонеопределенной среде функционирования. Цель разработки – информационноемоделирование функционирования интеллектуального робота на информационномуровне организации тактико-технического планирования информационно-двигательныхдействий (ИДД) мобильного робота. На этапе разработки подобная модель подсистемыотсутствовала и планирование не производилось, основываясь лишь на жесткомалгоритме отработки заданной траектории перемещения исполнительных подсистемробота. Отсутствие обратной связи с выполняемыми операциями указывает на малуюгибкость системы в целом, что значительно сокращает возможности применения ПР вреальных условиях автоматизированного производства. Непосредственная эксплуатациятакой системы сталкивается со следующими проблемами:
- необходимостьсоздания гибкой распределенной структуры гибких производственных модулей;
- решениезадач временного согласования работы нескольких роботов при выполнении единойзадачи;
- необходимостьизменения управляющей программы при переходе в новые не структурированныепроизводственные участки, где сказывается сложность ввода траектории отработкитехнологической операции роботом.
Основным недостаткомявляется жёсткое требование к точности задания эталонной траектории, нарушениекоторой в процессе работы ведёт к нарушению исполнения всего ТП, при этом такуюситуацию сложно автоматически скорректировать, – необходимо интеллектуальноепланирование действий./>1.2 Задачи, решаемые подсистемой
Задачи, решаемые подсистемой,заключаются в моделировании процесса синтеза информации о допустимых ИДД взависимости от текущего состояния робота и конфигурации противодействующихобъектов в среде функционирования, а также объектов, подлежащих обработке, –планирование выполняемых информационно-двигательных действий мобильного робота.Из всех задач, которые должны решаться подобной подсистемой следует выделить следующие:
- представлениекомплексной информации о рабочем пространстве робота, включая операциикартографирования и нанесения условных планов передвижений робота;
- автоматическоесогласование конфигурации робота и объектов среды;
- контрольплана действий в зависимости от динамических изменений в конфигурации объектовсреды;
- процедурноепостроение условных информационно-двигательных траекторий передвижения робота;
- обеспечениепостоянной обратной связи плана действий с потоком сенсорных данных;
- синтезкарты исследуемой среды./>1.3 Функциональные требования кподсистеме
Подсистема должна обеспечиватьследующие функциональные возможности:
- планированиетраекторий передвижения интеллектуального робота в априорно неопределеннойдинамической среде функционирования:
1) репрезентация противодействующихобъектов среды и функционально-исполнительных узлов мобильного робота сиспользованием нечеткого конфигурационного пространства;
2) формированиетраектории передвижения с фиксированным уровнем доверия;
3) обновление карты средыпри исследовании новых участков среды функционирования.
- режимработы планировщика в реальном времени;
- модульностьи наращиваемость подсистемы.
При наполнении базы знанийвыбор общих характеристик (наименование, код, и т.п.) известных объектоввозлагается на оператора. Параметры обхода объектов вводятся непосредственно изСУ ПР и записываются как дополнительные параметры объектов. Изменение траекториив базе знаний объектов производится только при помощи самой подсистемы,оператор не имеет возможности менять эти параметры вручную.
Подсистема обеспечивает обновлениеметодов принятия решений за счёт объектно-ориентированной структуры информационно-моделирующегокомплекса, т.е. перекомпоновки без изменения базовых связей между объектами моделирования.
/>/>2. Информационноемоделирование функционирования интеллектуального робота/>2.1 Обобщенная архитектура интеллектуального робота
С точки зрения построенияобобщенной архитектуры интеллектуального робота, актуально воспользоватьсяпонятием интеллектуального агента. В этом случае конструкция компонентовархитектуры агентов (датчиков, исполнительных механизмов и процессоров) ужеопределена и требуется лишь разрабатывать программы агента. Но успехи всоздании реальных роботов не в меньшей степени зависят от того, насколькоудачно будут спроектированы датчики и исполнительные механизмы, подходящие длявыполнения поставленной задачи.
Датчики – это не чтоиное, как интерфейс между роботами и той средой, в которой они действуют,обеспечивающий передачу результатов восприятия. Пассивные датчики, такиекак видеокамеры, в полном смысле этого слова выполняют функции наблюдателя засредой – они перехватывают сигналы, создаваемые другими источниками сигналов всреде. Активные датчики, такие как локаторы, посылают энергию в среду.Их действие основано на том, что часть излучаемой энергии отражается и сновапоступает в датчик. Как правило, активные датчики позволяют получить большеинформации, чем пассивные, но за счет увеличения потребления энергии отисточника питания; еще одним их недостатком является то, что при одновременномиспользовании многочисленных активных датчиков может возникнуть интерференция.В целом датчики (активные и пассивные) можно разбить на три типа, в зависимостиот того, регистрируют ли они расстояния до объектов, формируют изображениясреды или контролируют характеристики самого робота.
В большинстве мобильныхроботов используются дальномеры, которые представляют собойдатчики, измеряющие расстояние до ближайших объектов. Одним из широкоприменяемых типов таких датчиков является звуковой локатор, известныйтакже как ультразвуковой измерительный преобразователь. Звуковые локаторыизлучают направленные звуковые волны, которые отражаются от объектов, и частьэтого звука снова поступает в датчик. При этом время поступления иинтенсивность такого возвратного сигнала несут информацию о расстоянии доближайших объектов. Для автономных подводных аппаратов преимущественноиспользуется технология подводных гидролокаторов, а на земле звуковые локаторыв основном используются для предотвращения столкновений лишь в ближайшихокрестностях, поскольку эти датчики характеризуются ограниченным угловымразрешением. К числу других устройств, альтернативных по отношению к звуковымлокаторам, относятся радары (в основном применяемые на воздушных судах) илазеры. Лазерный дальномер показан на рис. 2.1.
/> />
а) б)
Рис. 2.1 – Типичныйпример датчика и его практического применения: лазерный дальномер (датчикрасстояния) SICK LMS – широко применяемый датчик для мобильных роботов (а);результаты измерения расстояний, полученные с помощью горизонтальноустановленного датчика расстояния, спроектированные на двухмерную карту среды(б)
Некоторые датчикирасстояния предназначены для измерения очень коротких или очень длинныхрасстояний. В число датчиков измерения коротких расстояний входят тактильныедатчики, такие как контактные усики, контактные панели и сенсорныепокрытия. На другом конце спектра находится глобальная системапозиционирования(Global Positioning System – GPS), которая измеряетрасстояние до спутников, излучающих импульсные сигналы. В настоящее время наорбите находятся свыше двух десятков спутников, каждый из которых передаетсигналы на двух разных частотах. Приемники GPS определяют расстояние до этихспутников, анализируя значения фазовых сдвигов. Затем, выполняя триангуляциюсигналов от нескольких спутников, приемники GPS определяют свои абсолютныекоординаты на Земле с точностью до нескольких метров. В дифференциальныхсистемах GPSприменяется второй наземный приемник с известнымикоординатами, благодаря чему при идеальных условиях обеспечивается точностьизмерения координат до миллиметра. К сожалению, системы GPS не работают внутрипомещения или под водой.
Вторым важным классомдатчиков являются датчики изображения– видеокамеры, позволяющиеполучать изображения окружающей среды, а также моделировать и определятьхарактеристики среды с использованием методов машинного зрения. В робототехникеособо важное значение имеет стереоскопическое зрение, поскольку оно позволяетполучать информацию о глубине; тем не менее, будущее этого направлениянаходится под угрозой, поскольку успешно осуществляется разработка новыхактивных технологий получения пространственных изображений.
К третьему важному классуотносятся проприоцептивные датчики, которые информируют робота оего собственном состоянии. Для измерения точной конфигурации робототехническогошарнира, приводящие его в действие электродвигатели часто оснащаются дешифраторамиугла поворота вала, которые позволяют определять даже небольшиеприращения угла поворота вала электродвигателя. В манипуляторах роботов дешифраторыугла поворота вала способны предоставить точную информацию за любой периодвремени. В мобильных роботах дешифраторы угла поворота вала, которые передаютданные о количестве оборотов колеса, могут использоваться для одометрии –измерения пройденного расстояния. К сожалению, колеса часто сдвигаются ипроскальзывают, поэтому результаты одометрии являются точными только для оченькоротких расстояний. Еще одной причиной ошибок при определении позиции являютсявнешние силы, такие как течения, воздействующие на автономные подводные аппараты,и ветры, сбивающие с курса автоматические воздушные транспортные средства.Улучшить эту ситуацию можно с использованием инерционных датчиков, такихкак гироскопы, но даже они, применяемые без других дополнительных средств, непозволяют исключить неизбежное накопление погрешности определения положенияробота.
Другие важные аспектысостояния робота контролируются с помощью датчиков усилия и датчиковвращающего момента.Без этих датчиков нельзя обойтись, если роботыпредназначены для работы с хрупкими объектами или объектами, точная форма иместонахождение которых неизвестны. Можно представить себе, что робототехническийманипулятор с максимальным усилием сжатия и одну тонну закручивает в патрон электрическуюлампочку. При этом очень трудно предотвратить такую ситуацию, что роботприложит слишком большое усилие и раздавит лампочку. Но датчики усилияпозволяют роботу ощутить, насколько крепко он держит лампочку, а датчикивращающего момента – определить, с каким усилием он ее поворачивает. Хорошиедатчики позволяют измерять усилия втрех направлениях переноса и трехнаправлениях вращения.
Исполнительные механизмыявляются теми средствами, с помощью которых роботы передвигаются и изменяютформу своего тела. Для того чтобы представить основные особенности конструкцииисполнительных механизмов, необходимо вначале рассмотреть абстрактные понятиядвижения и формы, используя концепцию степени свободы.Какстепень свободы мы будем рассматривать каждое независимое направление, в котороммогут передвигаться либо робот, либо один из его исполнительных механизмов.Например, твердотельный свободно движущийся робот, такой как автономныйподводный аппарат, имеет шесть степеней свободы; три из них, (х, у, z),определяют положение робота в пространстве, а три других – его угловуюориентацию по трем осям вращения, известную как качание (yaw), поворот (roll) инаклон (pitch). Эти шесть степеней свободы определяют кинематическоесостояниеили позуробота. Динамическое состояниеробота включает по одному дополнительному измерению для скорости изменениякаждого кинематического измерения.
/> />
/>а) б)
Рис. 2.2 –Особенности конструкции манипулятора робота: станфордский манипулятор (StanfordManipulator) – один из первых манипуляторов робота, в котором используются пятьповоротных шарниров (R) и одно призматическое сочленение (Р), что позволяетполучить в целом шесть степеней свободы (а); траектория движения неголономногочетырехколесного транспортного средства с рулевым управлением от передних колес(б).
Роботы, не являющиесятвердотельными, имеют дополнительные степени свободы внутри самих себя.Например, в руке человека локоть имеет одну степень свободы (может сгибаться водном направлении), а кисть имеет три степени свободы (может двигаться вверх ивниз, из стороны в сторону, а также вращаться). Каждый из шарниров робота такжеимеет 1, 2 или 3 степени свободы. Для перемещения любого объекта, такого какрука, в конкретную точку с конкретной ориентацией необходимо иметь шестьстепеней свободы. Рука, показанная на рис. 2.2, а, имеет точно шестьстепеней свободы, создаваемых с помощью пяти поворотных шарниров, которыеформируют вращательное движение, и одного призматического сочленения,который формирует скользящее движение. Чтобы убедиться в том, что рукачеловека в целом имеет больше шести степеней свободы, можно провести простойэксперимент: положите кисть на стол и убедитесь в том, что вы еще имеетевозможность поворачивать руку в локте, не меняя положения кисти на столе.Манипуляторами, имеющими больше степеней свободы, чем требуется для переводаконечного исполнительного механизма в целевое положение, проще управлять посравнению с роботами, имеющими лишь минимальное количество степеней свободы.
В мобильных роботахколичество степеней свободы не обязательно совпадает с количеством приводимых вдействие элементов. Рассмотрим, например, обычный автомобиль: он можетпередвигаться вперед или назад, а также поворачиваться, что соответствует двумстепеням свободы. В отличие от этого кинематическая конфигурация автомобиляявляется трехмерной – на открытой плоской поверхности можно легко перевестиавтомобиль в любую точку (х, у), с любой ориентацией (см. рис. 2.2,б). Таким образом, автомобиль имеет три эффективные степени свободы, нодве управляемые степени свободы.Робот называется неголономным,если он имеет больше эффективных степеней свободы, чем управляемых степенейсвободы, и голономным, если эти два значения совпадают. Голономныероботы проще в управлении (было бы намного легче припарковать автомобиль,способный двигаться не только вперед и назад, но и в стороны), однакоголономные роботы являются также механически более сложными. Большинствоманипуляторов роботов являются голономными, а большинство мобильных роботов –неголономными.
В мобильных роботахприменяется целый ряд механизмов для перемещения в пространстве, включаяколеса, гусеницы и ноги. Роботы с дифференциальным приводомоборудованырасположенными с двух сторон независимо активизируемыми колесами (илигусеницами, как в армейском танке). Если колеса, находящиеся с обеих сторон,вращаются с одинаковой скоростью, то робот движется по прямой. Если же онивращаются в противоположных направлениях, то робот поворачивается на месте.Альтернативный вариант состоит в использовании синхронного привода, вкотором каждое колесо может вращаться и поворачиваться вокруг вертикальной оси.Применение такой системы привода вполне могло бы привести к хаотическомуперемещению, если бы не использовалось такое ограничение, что все пары колесповорачиваются в одном направлении и вращаются с одинаковой скоростью. Идифференциальный, и синхронный приводы являются неголономными. В некоторыхболее дорогостоящих роботах используются голономные приводы, которые обычносостоят из трех или большего количества колес, способных поворачиваться ивращаться независимо друг от друга.
Ноги, в отличие от колес,могут использоваться для передвижения не по плоской поверхности, а поместности, характеризующейся очень грубым рельефом. Тем не менее, на плоскихповерхностях ноги как средства передвижения значительно уступают колесам, ктому же задача создания для них механической конструкции является оченьсложной. Исследователи в области робототехники предприняли попытки разработатьконструкции с самым разным количеством ног, начиная от одной ноги и заканчиваябуквально десятками. Были разработаны роботы, оборудованные ногами для ходьбы,бега и даже прыжков (как показано на примере шагающего робота на рис. 2.3,а). Этот робот является динамически устойчивым; это означает, чтоон может оставаться в вертикальном положении, только непрерывно двигаясь.Робот, способный оставаться в вертикальном положении, не двигая ногами,называется статически устойчивым.Робот является статическиустойчивым, если центр его тяжести находится над многоугольником, охваченнымего ногами.
В мобильных роботахдругих типов для передвижения используются иные, чрезвычайно разнообразныемеханизмы. В летательных аппаратах обычно применяются пропеллеры или турбины.Роботизированные дирижабли держатся в воздухе за счет тепловых эффектов. Вавтономных подводных транспортных средствах часто используются подруливающие устройства,подобные тем, которые устанавливаются на подводных лодках.
Для того чтобы робот могфункционировать, ему недостаточно быть оборудованным только датчиками иисполнительными механизмами. Полноценный робот должен также иметь источникэнергии для привода своих исполнительных механизмов. Для приведения в действиеманипулятора и для передвижения чаще всего используются электродвигатели;определенную область применения имеют также пневматические приводы, в которыхиспользуется сжатый газ, и гидравлические приводы, в которых используетсяжидкость под высоким давлением. Кроме того, в большинстве роботов имеютсянекоторые средства цифровой связи наподобие беспроводной сети. Наконец, роботдолжен иметь жесткий корпус, на который можно было бы навесить все этиустройства, а также, фигурально выражаясь, держать при себе паяльник, на тотслучай, что его оборудование перестанет работать.
/> />
а) б)
Рис. 2.3 – Примерыроботов, передвигающихся с помощью ног: один из шагающих роботов Марка Рэйберта(Marc Raibert) в движении (а); роботы AIBO компании Sony, играющие в футбол (©от 2001 года, федерация RoboCup) (б)
Таким образом,существенной задачей в построении интеллектуальных робототехнических системявляется информационное моделирование интеллектуального робота как некоторогоактивного агента среды. И, собственно, одной из задач проектированиярационального агента среды становится задача разработки модели планирования егоинформационно-двигательных действий.
2.2 Общий принциппостроения модели
В соответствиетрадиционной модели организации моделирования, корда информационными потокамиобмениваются исследователь-проектировщик и имитационная модель, обратная связьпо результатам моделирования совершает внешняя по отношению к системе имитационногомоделирования цепочка – человек с приобщением вспомогательных средств и методовпрограммного обеспечения [11]. При этом исследователь-проектировщик выполняет функциюпреобразования информации, которая состоит в интерпретации результатов ипринятия решений относительно управления экспериментами и обобщением информациик базе знаний интеллектуального робота. Автоматизация управления экспериментамипредполагает при этом создание замкнутого программно реализованного контурауправления имитационной моделью />
в рамках средстввнешнего программного обеспечения (рис. 2.4).
Целенаправленные серииэкспериментов в соответствии с заданной целью функционирования робота и учетомограничений конфигурационных параметров организуют модули, которые специальноотносят к составу внешнего программного обеспечения. В общем случае, эти модулидолжны задавать наборы начальных данных, инициировать прогоны модели в целом,обрабатывать результаты и принимать решения о дальнейшем развитии экспериментовсоответствие реализуемому алгоритмом управления моделированием. Такой алгоритм,направляя эксперименты, в области допустимых значений параметров производитпоиск такого их объединения, который бы обеспечивал оптимум заданногопоказателя качества, т.е. по существу решает задачу оптимизации:
/>, (2.1)
где f – целеваяфункция, представленная алгоритмически имитационная модель;
/> – вектор параметров объектамоделирования;
X – множество допустимыхзначений входных параметров.
Таким образом, совокупностьалгоритмических и программных средств, обеспечивающая процессавтоматизированного моделирования, образует систему автоматизации имитационногомоделирования (САИМ) [36]. Поскольку пользователь при этом не вводит каждыйнабор начальных данных для очередного прогона имитационной модели и толькоуказывает цель или критерий и область варьирования параметров, в то время как поискдопустимых решений задач моделирования выполняется при помощи САИМавтоматически, к последней можно применить определение интеллектуальной системымоделирования. Например, функции САИМ, в контуре управления гибкойпроизводственной системы, в целом, заключаются в анализе альтернативныхвариантов поведения роботов после принятия того или иного возможного решенияотносительно диспетчеризации и оперативного планированияинформационно-двигательных действий и т.п.
Эффективность реализацииэтих функций обусловлена заменой жест кой логики управления интеллектуальнымроботом, что предполагает использование в отдельных ситуациях заданных ификсированных эвристик, гибким и динамическим механизмом, который обеспечиваетпринятие решений не только на основе подобного анализа текущего состоянияробота, но и с учетом перспектив его развития. При этом объединяются высокаявероятность результатов и возможность автоматического принятия решений в режиме«жесткого» реального времени.
/>
Проблемаавтоматизации управления экспериментами и синтеза знаний и построения базы знанийможет быть представлена логической структурой поэтапного решения отдельныхзадач интеллектуального робота (рис. 2.5).
На первом этапеавтоматизации управления экспериментами решаются две задачи: исполняетсяструктурно-алгоритмическое построение собственно модуля управления; формируютсясодержательные основы и формальные требования к организации информационногообмена с имитационной моделью.
Задачаструктурно-алгоритмического построения модуля управления экспериментами исинтеза системы знаний решается в следующей последовательности: определяютсясостав и структура модуля (разрабатываются условия взаимодействия его компоненти положение в общей структуре САИМ).
При выполнении сериипрогонов имитационной модели происходит целенаправленное варьирование значенийпараметров, которое может влиять на значения целевой функции не толькопосредством прямого влияния на показатели функционирования объектамоделирования, но и побочно посредством других сопряженных элементов объекта(робота). Как следствие, изменяются стоимостные и другие показатели. Наряду стем, на значения некоторых параметров можно наложить ограничения, в частностичасть их фиксировать, т.е. задать декларативно. Это может отображаться приформировании наборов начальных данных и инициализации начальных состоянийпроцесса моделирования системы знаний.
Рассматривая имитационнуюмодель как средство целенаправленного преобразования информации в соответствиис некоторой системой предписаний, имеет смысл говорить про алгоритмимитационного моделирования. Тогда формальную интерпретацию рассмотренныхтребований можно записать следующим образом:
/> (2.2)
где S – входное слово алгоритмаимитационного моделирования;
Q – множество допустимыхнаборов значений параметров робота;
С – область определенияалгоритма имитационного моделирования.
Входное слово Sзадает набор начальных данных для конкретного набора данных, т.е. />, где каждая величина /> соответствует некоторомузначению определенного параметра объекта моделирования. Область С определяетсяпрограммной реализацией алгоритма имитационного моделирования, а образовать еевозможно множеством Dвх наборов входного алфавита. Все величины/>, имеющие разрешенную реализациюобъекта моделирования U.
Таким образом, выражения(2.2) соответственно определяют условия согласования S с имитационноймоделью и с алгоритмом. Задача состоит в разработке аппарата формальногоанализа непротиворечивости изменений семантически взаимосвязанных параметров дляобеспечения варьирования, что не нарушает условия (2.2) и не приводит к изменениямфиксированных параметров.
На втором этапепроизводитсяавтоматизация управления экспериментами и построения системы знаний решаютсяследующие этапы:
– разработка принципов, взаимодействиясистемы логического вывода и численных оптимизационных процедур;
– выбор (разработка) аппаратареализации логического вывода в комбинированных алгоритмов управленияэкспериментами;
– разработка на основепредложенного аппарата эффективных алгоритмов вывода с учетом спецификивзаимодействия с численными процедурами оптимизации.
На третьем этапе решаетсязадача разработки оптимизационных процедур, которые используются в планированииэкстремальных действий. При этом вопрос разработки алгоритмического обеспеченияможно рассматривать для специфических аспектов моделирования объекта, а именно:
– автоматизацииуправления экспериментами в условиях лингвистической неопределенностипараметров, например, «степень подобия / отличия…» не имеет естественногочисленного измерения;
– организацииэкстремальных экспериментов в задачах однопараметрической оптимизации присущественно неравномерном расположении точек в середине интервала, например,унимодальная функция отклика, и фиксирования соответствующих состояний в моделисистемы знаний;
– сокращение временипоиска при значительной продолжительности прогона имитационной модели, чтоявляется важным при многоитерационных алгоритмов поиска, полном переборевариантов и т.п.2.3 Алгоритмы планирования
Метод потенциалов взадаче выбора пути для мобильного робота был предложен А.К. Платоновым в1970 году.
При этом рассматриваетсяслучай, когда робот снабжен достаточно точной навигационной системой, чтобы ееошибками можно было пренебречь, и системе управления известны как координатыробота и измерительного устройства, так и ориентация сектора обзора инаправление производящихся измерений в некоторой абсолютной системе координат(АСК). Робот во всех случаях представляет собой точку с предписанным векторомориентации.
Суть метода заключается вследующем. Предположим, что цель имеет некоторый положительный заряд,препятствия заряжены отрицательно; местоположения цели и препятствийфиксированы. Пусть также имеется некоторая отрицательно заряженная точка,способная перемещаться. Поместим ее в исходную точку. Под действием силподвижная точка будет притягиваться к цели и отталкиваться от препятствий,причем законы движения могут задаваться, в принципе, различными способами.Логично предположить, что при некоторых ограничениях на структуру местности изаконы движения подвижной точки эта точка достигнет цели.
В зависимости от способазадания функций, можно получить трассы с обходом препятствий с той или инойстепенью «риска» (величины приближения к препятствиям). Рассматриваемые нижеалгоритмы гарантируют от зацикливания в случае, когда контуры препятствийвыпуклы. Метод может также использоваться для случая, когда препятствияразбиваются на группы, выпуклые оболочки которых не пересекаются.
За рубежом основные ссылки делаются на работы Брукса и Хатиба,которые вышли в свет в 1985 году [6, 7]. Следует отметить, что в Японииподобные разработки были выполнены сотрудниками фирмы Hitachi, Ltd. в 1984 году[9]. Подобные же алгоритмы использовались и при трассировке печатных плат в1967 году (см. [8], в которой дана ссылка на более раннюю работу 1948 года).Для того, чтобы проследить эволюцию архетипа основной идеи метода, нижеприводится историческая справка о разработках, имеющих отношение к методупотенциалов в задачи выбора пути.
В данной работе исследованы модификации алгоритма, изложенного в[1]. При этом рассмотрены следующие направления модификации исходного алгоритма:
1) Исследованыстепенная и показательная функции отталкивания от препятствий и влияние их нарезультирующий путь мобильного робота (МР). Для оценки эффективности путииспользовалась функция отклонения вектора направления движения от вектора направленияна цель.
2) Проанализированывозможности использования метода потенциалов для управления распределенноймобильной системой (РМС). Исследовано пять способов организации такогодвижения:
а) движениепо схеме «цепь». В этом случае сила притяжения цели действует на «лидера», икаждый МР «притягивается» к впереди идущему;
б) движениетипа «гонка за лидером». В этом случае все элементы РМС «притягиваются» к«лидеру», который, в свою очередь, «притягивается» к целевой точке;
в) движениетипа «расхождения». В этом случае на МР, расположенные компактной группой илицепью, начинает действовать сила отталкивания от «лидера». МР «разбегаются»,исследуя каждый свой участок;
г) движениетипа «схождение». В этом случае «лидер» собирает все элементы РМС в компактнуюгруппу;
д) организациядвижения типа «свободный поиск». В этом случае сила притяжения к целиотсутствует, и каждый элемент РМС движется в свободном от препятствийнаправлении.
Первые два режимаиспользуются для организации передвижения РМС, последние три – дляинформационного исследования среды.
Основное отличие нового алгоритма от изложенного в [1] состоит втом, что в [1] непосредственно вычислялось расстояние до каждого из препятствийri непосредственно,а в новом алгоритме используется имитатор дальномерной системы. Полученныймассив дальностей в некотором секторе в дальнейшем подвергается логическойфильтрации для построения оценок величин ri.
Наряду с указанным названием – метод потенциалов (Potential FieldApproach), он имеет следующие названия: способа «искусственных потенциальныхполей» (artificial potential fields), «полей виртуальных сил» (virtual forcefield – VFF), «гистограммы векторных сил» (vector field histogram-VFH) и др.Суть этого метода, напомним, заключается в том, что путь строится на основерешения специального «уравнения движения», в которое входят «сила притяжения кцели», «силы отталкивания от препятствий» и, возможно, некоторые другие «силы».При ссылке на этот метод в качестве пионерских упоминаются работы 1985–1986 гг.[6,7]. Вместе с тем работа фирмы Хитачи по управлению МР, в которойиспользованы идеи «силового поля», выпущена в 1984 г. [9]. В [1] опубликовалирезультаты подобного исследования в ИПМ АН СССР в 1974 г. Вместе с тем использованиеподобных физических аналогий при трассировке электронных плат уходит корнямивглубь 50‑х годов [8]. Правда, вычислительные аспекты при этом имеют своюспецифику.
Сам архетип идеи движения в поле «информационных» (виртуальных)сил восходит к работам 30-40-х годов одного из виднейших представителей гештальтпсихологии КуртаЛевина. Он выступил с идеей применения в психологии концепции физического полядля описания поведения и конфликтных ситуаций при взаимодействии индивида с окружающиммиром [3]. Современные психологи критикуют К. Левина за физикализмконцепции, акцент на динамический аспект в ущерб содержательному и многоедругое. Вместе с тем в указанных работах К. Левина можно почерпнуть немалоинтересного. Экспериментальный материал, подтверждающий разработаннуюконцепцию, был получен в основном при наблюдении за детьми разного возраста идокументирован посредством киносъемок.
Все они имеют аналоги при использовании метода потенциалов дляуправления МР.
На начальном этапе исследований в ИПМ рассматривались препятствияв виде окружностей. Подобное представление после результатов работ Koditschek ссоавторами [4, 5] можно считать основным. Сила притяжения к цели полагаласьпостоянной по модулю и направленной к точке цели. Сила отталкивания от i‑огопрепятствия fi зависела от аргумента Ri/ri, где Ri–радиус i‑ой окружности, ri-расстояниеот центра i‑ой окружности до движущейся точки. fiсчиталась направленной от центра окружности. Траектория («локомоция») получаласьв результате интегрирования уравнений движения второго порядка, так какускорение, действующее на движущуюся точку, определялось суммой указанных сил.В ходе исследований выяснилось, что инерционность, заложенная в указаннуюмодель, приводит к тому, что траектория движения становится малоприемлемой(препятствие «отбрасывает» движущуюся точку очень сильно и траекторияполучается чересчур «изрезанной». Для того, чтобы избавиться от этогонедостатка и сделать метод годным для случая аппроксимации контуров препятствийдругими способами, было предпринято следующее. Во-первых, стали использоватьсяуравнения движения первого порядка (т.е. действующие силы определяют скорость,по сути дела речь идет об аналоге простого градиентного спуска). Во-вторых,сила отталкивания стала определяться аргументом, равным расстоянию до препятствия.При этом форма контура препятствия произвольна, а для приведенного выше примераэто разность ri – Ri. Направлена этасила в сторону от ближайшей точки препятствия. В ходе исследований былопризнано рациональным в случае наличия нескольких препятствий использовать функцииот указанного аргумента x типа x-k или e-cx,которые быстро убывают с расстоянием. При этом коэффициенты k и cмогут быть варьируемыми параметрами.
Следует особо подчеркнуть, что, варьируя параметры k и cпри определении сил отталкивания, можно получать траектории для движения несколькихМР. Если ввести в этом процессе запаздывание, то можно получить режим «следованиядруг за другом».
Иногда среда, в которой расположено много препятствий, «хорошо организована»,например, препятствия разбиваются на группы, выпуклые оболочки которых непресекаются. В этом случае сила отталкивания может вычисляться сразу для всейгруппы.
Таким образом, метод потенциалов позволяет строить «размытые» моделисреды и получать решение без учета ненужных подробностей.
Анализируя разнообразие зарубежных работ по методу потенциалов, можновыделить два интересных направления.
Первое является попыткой ответить на вопрос: можно ли эффективнозадавать силовое поле так, чтобы отсутствовали устойчивые точки равновесия в принципе.Достаточно очевидно, что в общем случае ответ на этот вопрос положительный.Действительно, функция потенциала в точке x, равная минимальной длинедопустимого пути от x кg – точке цели, задает такое поле. Однакоэту функцию в общем случае считать весьма непросто. Koditschek с соавторами всерии работ [4,5] и др. предложили свой подход к этой проблеме, который хотя иотличается оригинальностью, в итоге, оказывается, вряд ли намного прощеспособа, указанного выше. Вначале рассматривается «Сферический мир». Дляплоскости это окружности-препятствия, окруженные окружностью-рамкой. В этоммире результирующая сила определяется не как сумма сил, действующих отразличных препятствий, а как произведение таких сил. Эти два положенияпозволяют избежать наличия точек равновесия силового поля, что зафиксированотеоретически.
Далее строится последовательность диффеоморфизмов. Поначалу между «сферическиммиром» и «звездным миром» – в котором препятствия представляют многоугольникиособого вида. Затем происходит переход от «звездного мира» ко все более иболее» общим мирам». При этом диффеоморфизм сохраняет «безособость» получающихсяпри поэтапных переходах от «сферического мира» силовых полей. Однако необходимоотметить, что демонстрируемые иллюстрации подобных полей для более общихпостановок, чем «сферический мир», позволяют утверждать, что для них весьмахарактерны «овражные эффекты». Следовательно, при фиксированном значении шагавозможны в лучшем случае эффекты типа «информационного дребезга», а такжезацикливание в ложном экстремуме. Возможно, что именно поэтому авторы недемонстрируют построение траекторий движения, а только картинки линий уровня.
Второе направление,берущее начало от работ исследователей Оксфордского университета, заключается вследующем. Сам МР представляется не точкой, а отрезком или прямоугольником. Этопозволяет рассчитывать не только результирующую силу, действующую на МР, но и моментсил, т.е. управлять ориентацией.
Ниже приводятся некоторые ранее непубликовавшиеся результаты исследования алгоритмов, основанных на методепотенциалов, полученные в ИПМ в 70 – 80 х гг. прошлого века.
Критическое отношениешага к радиусу обходимой окружности для появления информационного дребезга 0.1для степенной функции и 0.3 для экспоненты.
Подобным образомисследовалось влияние информационного дребезга для плавного контура (окружностьрадиуса 1) при обходе методом потенциалов.
В статье [9] описываетсямобильный робот (МР), разработанный фирмой Hitachi, Ltd. (Япония) в 1984 г.,в котором, в частности, для реализации управления автономным перемещением, былиспользован так называемый «метод потенциального наведения». Онпредусматривает оснащение робота дальномерами, измеряющими расстояние до объектовв рабочей зоне. Принцип этого метода схематически представлен на рис. 3,где обозначено: Xk – точка нахождения робота в текущиймомент времени; tk — направлениепередвижения робота до текущего момента времени; tk+1 –направление передвижения робота в текущий момент времени; XG– целевая точка; g – вектор, направленный к целевой точке; rmax– максимальный радиус; ri* — вектор, проведенный до объекта, находящегося в рабочей зоне робота.
Расчетнаправления передвижения робота непрерывно осуществляется на основаниирезультата сложения трех векторов с учетом соответствующих весовых функций:вектора, характеризующего направление, при котором в наилучшей степенипросматривается целевая точка; вектора, характеризующего направлениепередвижения без столкновений с препятствиями, и вектора, соответствующегонаправлению движения робота до настоящего времени. При этом система управленияроботом обеспечивает рациональный обход неизвестных препятствий. Управлениеосуществляется с использованием карты по алгоритму построения в квазиреальномвремени квазиоптимальной (по расстоянию) траектории. Применение ультразвуковогодальномера, установленного на роботе, обеспечивает обнаружение препятствий,причем процедура планирования траектории вновь повторяется для внесения необходимыхкоррекций.
В работе [10]рассматривается архитектура систем навигации реального времени, используемых втом числе для обхода препятствий мобильными роботами (МР). Подробно рассмотреныследующие результаты:
– видыархитектуры и технологии соответствующих датчиков (сенсоров);
– представлениеразличных моделей поведения с помощью сенсорно-управляемых алгоритмов;
– методискусственного потенциального поля – алгоритм реального времени,разработанный специально для навигации МР во процессе движения.
Врассматриваемой системе данные инфракрасных датчиков создают образ среды внекоторой окрестности МР, в соответствии с которым затем строится траекториядвижения. Отсюда возникают строгие ограничения на скорость движения МР,связанные со скоростью получения и обработки данных, скоростью работынавигационного алгоритма и временем реакции управляющей системы МР на изменениеобстановки.
Вданной реализации метода потенциалов МР представляется как точка начала отсчетав полярных координатах, из которой вращающимся сенсором осуществляетсянепрерывное циклическое сканирование местности с сектором обзора 360°.
Пустьугол g –угловой шаг сканирования, di– результат i‑го(относительно текущего направления движения МР) замера дальности от МР допрепятствия. В соответствие каждому diставитсявектор силы fi, вычисляемый с помощью уравнений дляискусственного потенциального поля:
/> (2.3)
где A– фиксированная константа. После обзора всего сектора (360°) определяютсяновые компоненты вектора скорости Vx и Vy:
/> (2.4)
где b, сфизической точки зрения, есть весовой множитель, используемый для того, чтобына компоненты скорости большее влияние оказывали силы, действующие с фронта МР,нежели сзади. Утверждается, что в общем случае bестьфункция g и di:
/> (2.5)
при этом bпересчитывается каждыйраз при нахождении нового вектора скорости.
Авторами статьи [11]предложен алгоритм планирования движения выпуклого многоугольного объекта всреде, содержащей многоугольные препятствия. Представлена эвристика,базирующаяся на рассмотрении моментов, что позволяет расширить алгоритми ввести в рассмотрение дополнительную степень свободы мобильного робота (МР) –угол поворота. Также представлены результаты построения трассы для МР, движущегосяпо коридору.
В работе используетсяследующая терминология. Пусть рабочая область пространства W, в которойдействует МР, является подмножеством Ân. Пусть O ÌW представляет собоймножество препятствий в рабочей области, тогда свободным пространством в Wбудет являться множество F = W / O; задача построения пути МР в такомслучае есть задача нахождения набора точек в F, определяющих траекториюдвижения МР из начальной точки в точку целевую.
Сначала рассматриваетсяпростой алгоритм, в котором многоугольный объект M, имеющий две степенисвободы, перемещается в рабочем пространстве W, в котором присутствуетконечное множество препятствий O. Текущее положение объекта Mзадается вектором x, начальное положение – вектором xs,а целевая точка – вектором xg. Тогда трасса строитсяпо следующему алгоритму:
x ¬ xs
repeat
Dmin ¬ min (D(M, o)) "o ÎO
Frepulse¬Dmin× 1 / |D|2
Fattract¬ xg – x
Fres¬ Fattract + a × Frepulse
x ¬ x + Fres
until (x = xg)or (|Fres| = 0)
Здесь D – вектор, доставляющийминимальное расстояние между M и препятствием o ÎO. Константа aуправляет влиянием препятствия на M в зависимости от расстояния. Прииспользовании подобной потенциальной функции столкновений с препятствиями непроисходит, однако, алгоритм может зацикливаться в случае достижения МРлокального минимума в потенциальном поле. Для борьбы с этим явлением могутприменяться различный методы, например, «барьер» из точек высокого потенциалавокруг точки локального минимума или метод Монте-Карло.
Далее для объекта Mвводится дополнительная степень свободы – угол поворота q, начальная конфигурацияобъекта в данном случае – (xs,qs). Предполагается, чтодвижется в коридоре минимального потенциала (КМП). Если он ориентирован так,что момент вращения МР в потенциальном поле минимален, то движение происходиттаким образом, что главная ось направлена по касательной к КМП.
Пусть c – центрмасс M, а P – множество векторов, описывающих положение некоторыхконтрольных точек, нормально распределенных по границе M относительно c.Предыдущий алгоритм модифицируется следующим образом:
x ¬ xs
q¬qs
repeat
Frepulse¬(0, 0)
moment ¬ 0
for each pÎP
Dmin ¬ min (D(c + p,o))"o ÎO
Frepulse¬ Frepulse + Dmin× 1 / |D|2
moment ¬ moment + (p ´ Dmin) × k
endfor
Fattract¬ xg – x
Fres¬ Fattract + a × Frepulse
x ¬ x + Fres
q ¬ q + b ´ moment
until (x = xg)or (|Fres| = 0)
Константа bуправляет величиной поворота и определяется эмпирически, посколькуматематическое решение нетривиально и зависит от многих факторов. Кроме того,при практической реализации алгоритма, выбор c может быть неоднозначен.В рассматриваемых примерах для трехколесного МР в качестве c браласьсередина оси между двумя задними колесами.
В работе [12] представленметод обхода препятствий мобильным роботом (МР), получивший название метода«гистограмм векторных полей» (VHF‑метод). Он позволяет обнаруживатьпрепятствия и обходить их во время движения. МР, управляемый данным алгоритмом,маневрирует быстро и без остановок даже среди большого количества неупорядоченныхпрепятствий.
VHF‑метод дляпредставления препятствий использует сетку на двумерной декартовой плоскости.Каждой ячейке сетки ставится в соответствие характерное значение,представляющее уровень «уверенности» алгоритма в присутствии препятствия вданной ячейке. Метод использует двухуровневую систему представления данных:
– напервом уровне – детальное описание среды, окружающей робота, с помощьюдекартовой сетки C;
– навтором уровне – полярная гистограмма H, которая строится по данным,содержащимся в C, вокруг центра масс МР как набор значений из C,соответствующий некоторым фиксированным секторам шириной a каждый. Каждому сектору kставится в соответствие величина hk, называемая полярнойплотностью препятствий в направлении k.
Выходными даннымиалгоритма являются сигналы управления МР.
Пусть C*,называемая активной областью, есть область сетки C размером ws´ws, построенная вокруг МР;ее элементами являются активные ячейки cij. Тогда Cпреобразуется в H следующим образом: строятся векторы препятствий, направлениекоторых относительно точки текущего положения МР определяется как:
/> (2.6)
а модуль вектора
/> (2.7)
где a, b =const > 0;
dij – расстояние междуактивной ячейкой и МР;
c*ij – среднее значение вактивной ячейке (i, j);
x, y– текущие координаты МР;
xi, yi – координаты активнойячейки (i, j).
Каждому из kсекторов ставится в соответствие угол из ряда 0, a, 2a,…, 360°-a. Тогда между k и c*ijсуществует следующее отношение:
/> (2.8)
Для каждого сектора khk вычисляется
/> (2.9)
Такимобразом, каждая из активных ячеек находится в одном из секторов. Однако, из-задискретности сетки, в результате такого распределения ячеек могут возникать«ступеньки» в секторах, что может привести к ошибкам в выборе направления. Длятого чтобы избежать искажения результата, используется сглаживающая функция:
/>(2.10)
Далее вычисляетсянаправление движения в полярных координатах, qfree, и соответствующий емусектор kfree в H. Алгоритм выбирает более«проходимое» направление и, вместе с тем, как можно более приближенное ктекущему направлению на цель qtarg.
Скорость движения МР вначальной точке устанавливается максимальной (Smax), азатем определяется на каждом шаге в соответствии с формулой:
/> (2.11)
где h``c = min (h`c, hm);
h`c – сглаженная полярнаяплотность препятствий в выбранном направлении движения;
hm – эмпирическиустановленная константа.
При этом отношение (*)гарантирует S` ³ 0 приh``c£ hm.
Статья [13] посвященаметоду построения гладких трасс движения мобильного робота (МР), основанному нафизической аналогии. Основными достоинствами метода являются устойчивое решениеи работа не только с двоичными (препятствие или свободное пространство), но и сразнородными средами, поверхность которых может иметь неравные коэффициентытрения или углы наклона на различных участках.
В основе метода лежатфизические принципы гидродинамики. Если предположить, что вся среда заполненажидкостью, то потоки жидкости позволяют добраться из начальной точки в целевую.В этом случае оптимальным путем будет поток, направленный вдоль градиентадавления, в котором достигается стационарное движение жидкости; локальный минимумне может быть достигнут, поскольку во всех точках потока удовлетворяетсяуравнение Лапласа. Для учета неоднородностей среды вводится внешняя сила,учитывающая силу трения и влияние проходимых препятствий, поэтому рассматриваютсяпотоки вязкой жидкости. Основным уравнением движения вязкой несжимаемойжидкости является уравнение Навье-Стокса:
/> (2.12)
где r – плотность жидкости;
v – вектор скоростидвижения жидкости;
t – время;
f – внешняя сила;
p – давление;
m – коэффициент вязкостижидкости.
Упрощенное уравнениевыглядит следующим образом:
/> (2.13)
Здесь неизвестнымиявляются вектор скорости v и абсолютная координата x.
Граничные условия:
/> (2.14)
где ¶W – границы препятствий, n– внешняя нормаль к границе препятствия.
Начальные условия:
/> (2.15)
где xS– начальная точка, xG – целевая точка.
Для решения уравнения вдвумерном пространстве методом конечных разностей уравнение представляетсяследующим образом:
/>(2.16)
где
/> (2.17)
Если число точек сетки N,то необходимо решить разреженную систему из 3N линейных уравнений.
Результатом работырассматриваемого алгоритма является множество так называемых «коридоров».Каждый коридор начинается в окрестности стартовой точки и заканчивается вокрестности целевой. Следование МР по осевой линии коридора гарантирует егобезопасность.
Далеерассматривается случай, когда внешняя сила не равна нулю, что позволяетучитывать разнородность среды.
Полная потенциальнаяэнергия частицы в потоке:
/> (2.18)
где S – начальнаяточка, G – целевая точка, T – вектор, касательный к траектории, pG– pS– разность давлений в xS и xG.
В случае присутствия силытрения F:
/> (2.19)
Механическая работа силытрения L×F зависит от длины траектории L. В случаедостаточно большой величины F:
/> (2.20)
Все траектории имеютограниченную длину
/> (2.21)
Практически, установкаочень большой величины F на границах препятствий эквивалентна условию v= 0. При использовании F = const длина потоков может быть ограничена,поэтому, увеличивая величину F, можно добиться отсеивания путей большейдлины, оставляя лишь пути, длины которых близки к оптимальным.
Для тестов данного методаиспользовался 4-х колесный МР на полигоне 60 м ´ 100 м спрепятствиями [13]. Внешняя сила f задавалась в виде:
/> (2.22)
где m – масса МР, q– угол наклона участкаповерхности в направлении движения, Kf– коэффициенттрения между колесами и поверхностью.
Следует отметить такженаправление, связанное с достаточно сложным по своей структуре заданиемпотенциальной функции, которая не имеет локальных минимумов [4, 5]. Однако приэтом задание подобной потенциальной функции может оказаться очень сложным.
/>/>3. Управлениемобильным роботом на основе конечно-автоматногоподхода3.1 Предпосылки создания алгоритма
Распределенные системы, втом числе робототехнические, в последнее время привлекают все большее вниманиеисследователей. Одна из причин этого состоит в том, что системы такого классавсе чаще используются как для промышленных, так и непромышленных приложений: действительно,объединение параллельно функционирующих подсистем позволяет выполнять такиезадания, которые не под силу каждой из компонент сложной системы. На рис. 3.1приведен пример такой многокомпонентной системы, включающей мобильные роботыразного назначения: погрузчики, исследователи и т.д. С другой стороны,управление системами такого класса представляет собой нетривиальную задачу:если управление каждой из подсистем, составляющих сложную систему, задача,вообще говоря, решенная (например, перевод манипулятора из точки в точку по заданнойтраектории), то управление согласованным поведением группы роботов,объединенных общей целью, является сложной проблемой. Заметим, что задачауправления существенно усложняется, если часть подсистем преследует конфликтующиецели.
/>
Рис. 3.1 –Многокомпонентная робототехническая система
В статьепредлагается подход к решению задачи координации взаимодействия подсистем,составляющих сложную систему, базирующийся на описании всех подсистем какконечных автоматов и использующий сеть специальным образом построенныхавтоматов для координации работы подсистем в процессе выполнения предварительносформированного задания. Кроме того, предложены способы планирования поведениясложной системы, использующие методы искусственного интеллекта.3.2 Многокомпонентность интеллектуального робота
Многокомпонентная система это система, включающаяв свой состав множество подсистем, объединенных общим заданием.
Можно дать ее болееточное определение.
Пусть задание Tможет быть представлено как множество подзаданий ti:
T = {t1, t2,…,tm} (3.1)
Введем отношениеследования F на T, так что tiFtjозначает, что задание ti может быть выполнено только, есливыполнено tj. Если такая структуризация задания Tпроведена, тогда можно построить описывающий T ориентированный граф:
G = (T, A), (3.2)
где T = {ti}– множество вершин графа G, A = {ai} Î T ´ T – множество направленныхдуг, при этом дуга a Î A соединяет ti с tjтогда и только тогда, когда tiFtj.
Пусть система S состоитиз подсистем si (далее называемых локальными системами или терминалами):
S = {s1, s2,…,sN}, (3.3)
при этом Ti Ì T – задание, выполняемоесистемой si.
Тогда систему:
CS = (S, T), (3.4)
будем называть T‑сложнойсистемой (далее – сложной системой), если выполнены следующие условия:
/> (3.5)
Условия C1, C2 можноинтерпретировать следующим образом:
C1: Сложная системапредставляет собой набор подсистем, которые в состоянии выполнить задание T.
С2: Действия всехподсистем, входящих в состав сложной системы, должны координироваться впроцессе выполнения задания. Под координацией здесь мы понимаем обмен данными(или командами) между подсистемами.
Если одна из подсистем siÎ S является роботом, то такую сложную систему будем называть многокомпонентнойробототехнической системой (МРС).3.3 Выбор способа организации управления робототехническойсистемой
Обсудим сначала следующийвопрос: «Что мы понимаем под управлением МРС?» В действительности, каждая изподсистем Si, входящая в состав МРС, обладает собственной системойуправления, способной обеспечить выполнение всех функций, свойственных этойподсистеме. Однако, возникающая для рассматриваемого класса системнеобходимость взаимодействовать в процессе исполнения задания, ставит задачуформирования для подсистемы именно того задания, выполнение которого диктуетсясложившейся обстановкой. Таким образом, задача управления распределеннымисистемами состоит в планировании действий подсистем до начала исполнения ипоследующей координации в процессе исполнения.
Организацияпроцедуры планирования и координации является чрезвычайно важной: она оказываетсущественное влияние на используемые методы управления.3.3.1 Централизованное управление
Этотметод организации предполагает наличие центральной системы управления, котораяпланирует действия всех подсистем и затем координирует их взаимодействие впроцессе исполнения (рис. 3.2) в соответствии с предварительноразработанным планом. Центральная система управления (ЦСУ) передает подсистемезадание, исполнение которого не требует какой-либо координации междуподсистемами. Результат исполнения возвращается в ЦСУ. В зависимости отприсланного результата ЦСУ посылает подсистеме следующее задание, и далеепроцесс повторяется. Заметим, что физически ЦСУ может быть реализована либо какотдельное устройство, либо на базе системы управления одной из компонент МРС.3.3.2 Распределенное управление
При таком способе организации управленияотсутствует центральная система, и процессы планирования заданий и координацияв процессе исполнения реализуются путем обмена сообщениями между подсистемами(рис. 3.3). На этапе планирования осуществляется переговорный процесс, результатомкоторого является согласованный план исполнения задания. Реализация этого планапроисходит на этапе исполнения и состоит в выполнении подзаданий и обменерезультатами их исполнения. Строго говоря, при такой организации нельзя говоритьоб управлении распределенной системой, поскольку, в отличие от централизованнойорганизации, отсутствует явно выраженный носитель управления, обеспечивающийтребуемое поведение системы: все подсистемы являются равноправными как на этапепланирования, так на этапе исполнения.
/>
Таким образом,централизованное управление реализует иерархический способ организации системы,состоящий в частности в том, что управление является многоуровневым с явнымподчинением нижних уровней (локальных систем управления) верхним (центральнойсистеме управления). Все обмены сообщениями между подсистемами происходит ненапрямую, а через верхний уровень. Распределенное управление реализуетгетерархический способ организации, когда все компоненты системы равноправны ипроцесс планирования осуществляется параллельно всеми подсистемами.3.3.3 Выбор архитектуры подсистем интеллектуальногоробота
Архитектура каждойкомпоненты МРС обусловлена тем набором функций, которые она должна выполнять, аименно:
F1 – иметь возможностьобмениваться данными либо с центральной системой управления (дляцентрализованного способа управления), либо с локальными подсистемами (дляраспределенного способа).
F2 – обеспечивать процесспринятия решения или планирования (для децентрализованного управления).
F3 – обеспечитькоординацию с другими подсистемами на этапе исполнения спланированного задания,
F4 – исполнятьсоответствующие подзадания, сформированные на этапе планирования.
Функция F1 является,вообще говоря, чисто технической и ее реализация состоит в поддержкесоответствующих сетевых протоколов. Обеспечение функции F2 состоит в требованиииметь в составе подсистемы базу знаний для принятия решений. Функция F3 требуетналичия механизма, приводящего в действие исполнение системой соответствующихподзаданий по сигналам, поступающим от других подсистем. При этом эти сигналыне должны требовать перепланирования задания в целом (например, неуспех привыполнении подзадания одной из подсистем). Выполнение функции F4 обеспечиваетсянижним уровнем локальной системы управления и аппаратными средствами подсистем.
Заметим, что еслилокальная система является сложной в смысле введенного в п. 2 определения,то процесс исполнения подзадания также может включать в себя этапы планированияи координации исполнения. Например, для мобильного робота, включающего в свойсостав шасси, манипулятор и систему технического зрения, подзадание в форме«переместить объект А в позицию В» может быть распланировано следующим образом:t1 – манипулятор, убрать; t2 – TV, найти А; t3 –манипулятор, сменить схват; t4 – манипулятор, взять А; t5 –манипулятор, положить в В; с соответствующей координацией между подсистемами«манипулятор» и «TV» в процессе исполнения.
Таким образом, подсистемадолжна включать по крайней мере следующие 4 функционально различные компоненты(рис. 3.4):
- коммуникатор (F1);
- планировщик (F2);
- координатор (F3);
- исполнитель (F4).
/>
/>/>4. Метод координации и планирования4.1 Координация исполнения
Воспользуемся подходом,состоящим в представлении этого уровня системы управления как сети специальнымобразом построенных конечных автоматов.
4.1.1 Сетевой автомат
Назовем сетевымавтоматом NA с p входами и q выходами следующий кортеж:
NA = (4.1)
где I = {i1, i2,…,ip} – множество входов;
O = {o1, o2,…,oq} – множество выходов;
U = {u1, u2,…,um} – входной алфавит;
X = {x1, x2,…,xn} – множество состояний;
Z = {z1, z2,…,zk} – выходной алфавит;
f: X´V®X – одношаговаяпереходная функция, где VÌU´I;
h: X´V®W – выходная функция, гдеWÌZ´O.
Элементы множеств V и Wбудем называть обобщенными входными и выходными алфавитами соответственно.
Введем дополнительноспециальный символ e, который является элементом и входного ивыходного алфавитов. Этот символ мы будем интерпретировать как пустой символ,который всегда присутствует на выделенном входе автомата, так что если вописании перехода из некоторого состояния присутствует входной символ e, тогда осуществляетсясоответствующий переход. Появление символа e в выходном каналеозначает, что на выход ничего не поступает. Здесь надо заметить, что полученныйв результате автомат не является автоматом Мили, поскольку он не сохраняетдлину отображения.
Далее при изображении графа сетевого автомата мыбудем использовать следующую нотацию: через i.u будем обозначать символвходного алфавита uÎU, пришедший по входному каналу i Î I; через z.o будем обозначатьсимвол выходного алфавита zÎZ, поступивший в выходной канал oÎO.
Введем теперь понятиесети автоматов как набора автоматов, объединенных своими входами и выходами ивзаимодействующих путем передачи / приема символов своих выходных /входных алфавитов.
Назовем сетьюавтоматовL связный мультиграф:
L = (E, C), (4.2)
где E = {e1,e2,…, en} – множество вершин графа;
C = {c1, c2,…,cm} – множество направленных дуг, ci = (ej, ek).
Вершина графаинтерпретируется как сетевой автомат, а дуга – как канал связи междуавтоматами, используемый для обмена элементами входных / выходныхалфавитов.
Работа сети заключается впараллельном функционировании всех составляющих ее автоматов, поведение каждогоиз которых, в свою очередь, определяется его текущим состоянием, а такжесостоянием входных каналов.
Пусть теперь L = (E, C) –сеть автоматов, и пусть распределенная система состоит из подсистем, каждая изкоторых описывается конечным автоматом, так что M = {Mi} – множествомоделей подсистем.
Тогда, если M Ì E, то
Lc = {Ec,Cc}, (4.3)
где Ec = E \M, будем называть управляющей структурой для распределенной системы, представленноймоделями {Mi}.
Ясно, что будучи соединенной с реальными подсистемами, управляющаяструктура обеспечит некоторое поведение подсистем, зависящее от топологииуправляющей структуры и атрибутов сетевых автоматов, входящих в ее состав.4.1.2 Управляющая структура как средство координации/> />
Рассмотрим простойпример. Пусть два робота Rb1 и Rb2 перекладывают деталииз накопителя S на два конвейера С1 и С2 (рис. 4.1).
В соответствии сизложенным выше, роботы Rb1, Rb2 будем описывать какконечные автоматы
Rbi= (Ii, Oi, Ui, Xi, Zi, fi,hi), i=1,2 (4.4)
со следующими атрибутами:
Ii ={i0}; Oi ={i0}; Ui ={g}; xi ={0, 1, 2}; Zi ={y, Y}, i = 1,2 (4.5)/> />
Функции fiи hi задаются диаграммой, представленной на рис. 4.2. Каждыйиз роботов Rbi воспринимает только одну команду «g», в результатекоторой он перемещается к накопителю S, захватывает деталь, переносит иустанавливает ее на конвейер Сi. Сигналы «y» и «Y» на выходе роботапоявляются тогда, когда он освобождает опасную зону и завершает выполнениеодного цикла соответственно. Будем строить управляющую структуру в виде трехавтоматов, два из которых (Reg1 и Reg2) являютсялогическими регуляторами роботов, а третий (Res) обеспечивает слежение заресурсом.
Рисунок 4.2 – Управляющая структура: а) топология; б) диаграмма регуляторов; в) диаграмма автомата, следящего за ресурсом На рис. 4.2представлена топология управляющей структуры, а также диаграммы всех входящих вее состав автоматов. Структура функционирует следующим образом. Регуляторкаждого робота посылает запрос на занятие опасной зоны автомату-ресурсу. Еслизона свободна, то этот запрос удовлетворяется, опасная зона переходит в состояние«занято» и регулятор посылает команду роботу начать транспортную операцию.После того, как робот выйдет из опасной зоны, он информирует об этом регулятор,который в свою очередь переводит опасную зону в состояние «свободно» и ждетокончания выполнения операции. Далее цикл повторяется.4.1.3 Анализ функционирования планировщика
Приведенный выше способкоординации является весьма эффективным средством для построения толькоцентрализованных систем управления. Действительно, если нижний уровеньуправляющей структуры представляет собой по сути дела логические регуляторы иможет быть без труда ассоциирован с локальными системами управления, то верхниеуровни обмениваются данными со всеми подсистемами, участвующими в выполнениизадания, и потому являются фрагментом центральной системы управления.
/>
Естественный способпреодоления этой трудности состоит в формировании одноуровневой управляющейструктуры, т.е. такой, у которой число автоматов совпадает с числом подсистем,разрешив этим автоматам обмениваться данными непосредственно между собой, а нес верхним уровнем. Это, с одной стороны, приводит к усложнению довольно простогологического регулятора, а с другой стороны позволяет обойтись без центральнойсистемы управления. На рис. 4.3 показана соответствующая архитектурасистемы управления (модули, не связанные с координацией, не показаны).
4.2 Планирование исполнения информационно-двигательных действий
Рассмотрим сначала методпланирования задания для централизованной системы. Суть подхода состоит ввыполнении двухшаговой процедуры:
Шаг 1. На основе методовискусственного интеллекта найти последовательность подзаданий, выполняемыхкаждой из подсистем и сформированных в терминах входных алфавитов подсистем.
Шаг 2. Преобразовать этипоследовательности в управляющую структуру, которая обеспечит координациюисполнения сформированного задания.
Обсудим более детальноэту процедуру. В качестве метода решения задачи планирования будем использоватьисчисление предикатов первого порядка. Входная информация, необходимая длярешения задачи планирования, состоит из следующих компонент, содержащихописание:
К1 – возможностей каждойиз подсистем,
К2 – начальногосостояния,
К3 – задания,
К4 – универсальныхсвойств.
Компонента К1 включаетнабор предложений (правил), отражающих возможности каждой подсистемы изменятьсостояние внешней среды (перемещение объектов, получение информации об объектахи т.д.). Отличительной особенностью этой компоненты является наличиесколемовской функции, относящейся к одной из подсистем. Множество К2 включаетфакты, описывающие начальное состояние системы. Компонента К3 представляетсобой формулировку задания. Множество К4 описывает универсальные свойства, независящие от подсистем, входящих в состав МРС (это множество может быть пусто).Элементы всех множеств представляют собой правильно построенные формулы (ППФ) висчислении предикатов 1‑го порядка.
Задача планирования состоит в получениипоследовательности операторов, обеспечивающих выполнение цели. При этом дляобеспечения максимально возможного распараллеливания процесса исполнения представиммножество К1 в виде:
/> (4.6)
где N – множествоподсистем.
Таким образом, каждоеподмножество К1i содержит только ППФ, отражающие возможности i‑ойподсистемы. После осуществления такого разбиения будем строить резолюции rij,и не-цели с элементами К1i настолько долго, насколько это возможно.Если этот процесс невозможно продолжить, оставаясь в К1i (этоозначает, что на этом этапе исполнения необходимо взаимодействие междуподсистемами), строим резолюции с соседними подмножествами. Такой процессобеспечит (в случае успеха) получение последовательности операторов,относящихся к каждой из подсистем, а также точек координации их взаимодействия.Далее полученные результаты используются для преобразования в управляющуюструктуру, обеспечивающую исполнение сформированного плана (рис. 4.4).
/>