Введение

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

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

Ко второй категории относятся мобильные роботы. Роботы такого типа передвигаются в пределах своей среды с использованием колес, ног или аналогичных механизмов. Они нашли свое применение при доставке обедов в больницах, при перемещении контейнеров в грузовых доках, а также при выполнении аналогичных задач. Одним из примеров мобильного робота является автоматическое наземное транспортное средство (Unmanned Land Vehicle – ULV) NavLab, способное автономно передвигаться по автомагистралям в режиме самовождения. К другим типам мобильных роботов можно отнести автоматическое воздушное транспортное средство (Unmanned Air Vehicle – 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 – Особенности конструкции манипулятора робота: станфордский манипулятор (Stanford Manipulator) – один из первых манипуляторов робота, в котором используются пять поворотных шарниров (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. движение по схеме «цепь». В этом случае сила притяжения цели действует на «лидера», и каждый МР «притягивается» к впереди идущему;

2. движение типа «гонка за лидером». В этом случае все элементы РМС «притягиваются» к «лидеру», который, в свою очередь, «притягивается» к целевой точке;

3. движение типа «расхождения». В этом случае на МР, расположенные компактной группой или цепью, начинает действовать сила отталкивания от «лидера». МР «разбегаются», исследуя каждый свой участок;

4. движение типа «схождение». В этом случае «лидер» собирает все элементы РМС в компактную группу;

5. организация движения типа «свободный поиск». В этом случае сила притяжения к цели отсутствует, и каждый элемент РМС движется в свободном от препятствий направлении.

Первые два режима используются для организации передвижения РМС, последние три – для информационного исследования среды.

Основное отличие нового алгоритма от изложенного в [1] состоит в том, что в [1] непосредственно вычислялось расстояние до каждого из препятствий r_i непосредственно, а в новом алгоритме используется имитатор дальномерной системы. Полученный массив дальностей в некотором секторе в дальнейшем подвергается логической фильтрации для построения оценок величин r_i.

Наряду с указанным названием – метод потенциалов (Potential Field Approach), он имеет следующие названия: способа «искусственных потенциальных полей» (artificial potential fields), «полей виртуальных сил» (virtual force field – VFF), «гистограммы векторных сил» (vector field histogram-VFH) и др. Суть этого метода, напомним, заключается в том, что путь строится на основе решения специального «уравнения движения», в которое входят «сила притяжения к цели», «силы отталкивания от препятствий» и, возможно, некоторые другие «силы». При ссылке на этот метод в качестве пионерских упоминаются работы 1985–1986 гг. [6,7]. Вместе с тем работа фирмы Хитачи по управлению МР, в которой использованы идеи «силового поля», выпущена в 1984 г. [9]. В [1] опубликовали результаты подобного исследования в ИПМ АН СССР в 1974 г. Вместе с тем использование подобных физических аналогий при трассировке электронных плат уходит корнями вглубь 50 х годов [8]. Правда, вычислительные аспекты при этом имеют свою специфику.

Сам архетип идеи движения в поле «информационных» (виртуальных) сил восходит к работам 30-40-х годов одного из виднейших представителей гештальтпсихологии Курта Левина. Он выступил с идеей применения в психологии концепции физического поля для описания поведения и конфликтных ситуаций при взаимодействии индивида с окружающим миром [3]. Современные психологи критикуют К. Левина за физикализм концепции, акцент на динамический аспект в ущерб содержательному и многое другое. Вместе с тем в указанных работах К. Левина можно почерпнуть немало интересного. Экспериментальный материал, подтверждающий разработанную концепцию, был получен в основном при наблюдении за детьми разного возраста и документирован посредством киносъемок.

Все они имеют аналоги при использовании метода потенциалов для управления МР.

На начальном этапе исследований в ИПМ рассматривались препятствия в виде окружностей. Подобное представление после результатов работ Koditschek с соавторами [4, 5] можно считать основным. Сила притяжения к цели полагалась постоянной по модулю и направленной к точке цели. Сила отталкивания от i ого препятствия f_i зависела от аргумента R_i /r_i, где R_i – радиус i ой окружности, r_i -расстояние от центра i ой окружности до движущейся точки. f_i считалась направленной от центра окружности. Траектория («локомоция») получалась в результате интегрирования уравнений движения второго порядка, так как ускорение, действующее на движущуюся точку, определялось суммой указанных сил. В ходе исследований выяснилось, что инерционность, заложенная в указанную модель, приводит к тому, что траектория движения становится малоприемлемой (препятствие «отбрасывает» движущуюся точку очень сильно и траектория получается чересчур «изрезанной». Для того, чтобы избавиться от этого недостатка и сделать метод годным для случая аппроксимации контуров препятствий другими способами, было предпринято следующее. Во-первых, стали использоваться уравнения движения первого порядка (т.е. действующие силы определяют скорость, по сути дела речь идет об аналоге простого градиентного спуска). Во-вторых, сила отталкивания стала определяться аргументом, равным расстоянию до препятствия. При этом форма контура препятствия произвольна, а для приведенного выше примера это разность r_i – R_i. Направлена эта сила в сторону от ближайшей точки препятствия. В ходе исследований было признано рациональным в случае наличия нескольких препятствий использовать функции от указанного аргумента 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, где обозначено: X_k – точка нахождения робота в текущий момент времени; t_k - направление передвижения робота до текущего момента времени; t_k+1 – направление передвижения робота в текущий момент времени; X_G – целевая точка; g – вектор, направленный к целевой точке; r_max – максимальный радиус; r_i^* - вектор, проведенный до объекта, находящегося в рабочей зоне робота.

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

В работе [10] рассматривается архитектура систем навигации реального времени, используемых в том числе для обхода препятствий мобильными роботами (МР). Подробно рассмотрены следующие результаты:

• виды архитектуры и технологии соответствующих датчиков (сенсоров);

• представление различных моделей поведения с помощью сенсорно-управляемых алгоритмов;

• метод искусственного потенциального поля – алгоритм реального времени, разработанный специально для навигации МР во процессе движения.

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

В данной реализации метода потенциалов МР представляется как точка начала отсчета в полярных координатах, из которой вращающимся сенсором осуществляется непрерывное циклическое сканирование местности с сектором обзора 360°.

Пусть угол g – угловой шаг сканирования, d_i – результат i го (относительно текущего направления движения МР) замера дальности от МР до препятствия. В соответствие каждому d_i ставится вектор силы f_i, вычисляемый с помощью уравнений для искусственного потенциального поля:

(2.3)

где A – фиксированная константа. После обзора всего сектора (360°) определяются новые компоненты вектора скорости V_x и V_y:

(2.4)

где b, с физической точки зрения, есть весовой множитель, используемый для того, чтобы на компоненты скорости большее влияние оказывали силы, действующие с фронта МР, нежели сзади. Утверждается, что в общем случае b есть функция g и d_i:

(2.5)

при этом b пересчитывается каждый раз при нахождении нового вектора скорости.

Авторами статьи [11] предложен алгоритм планирования движения выпуклого многоугольного объекта в среде, содержащей многоугольные препятствия. Представлена эвристика, базирующаяся на рассмотрении моментов, что позволяет расширить алгоритм и ввести в рассмотрение дополнительную степень свободы мобильного робота (МР) – угол поворота. Также представлены результаты построения трассы для МР, движущегося по коридору.

В работе используется следующая терминология. Пусть рабочая область пространства W, в которой действует МР, является подмножеством Âⁿ. Пусть O Ì W представляет собой множество препятствий в рабочей области, тогда свободным пространством в W будет являться множество F = W / O; задача построения пути МР в таком случае есть задача нахождения набора точек в F, определяющих траекторию движения МР из начальной точки в точку целевую.

Сначала рассматривается простой алгоритм, в котором многоугольный объект M, имеющий две степени свободы, перемещается в рабочем пространстве W, в котором присутствует конечное множество препятствий O. Текущее положение объекта M задается вектором x, начальное положение – вектором x_s, а целевая точка – вектором x_g. Тогда трасса строится по следующему алгоритму:

x ¬ x_s

repeat

D_min ¬ min (D(M, o)) "o Î O

F_repulse ¬ D_min × 1 / |D|²

F_attract ¬ x_g – x

F_res ¬ F_attract + a × F_repulse

x ¬ x + F_res

until (x = x_g) or (|F_res| = 0)

Здесь D – вектор, доставляющий минимальное расстояние между M и препятствием o Î O. Константа a управляет влиянием препятствия на M в зависимости от расстояния. При использовании подобной потенциальной функции столкновений с препятствиями не происходит, однако, алгоритм может зацикливаться в случае достижения МР локального минимума в потенциальном поле. Для борьбы с этим явлением могут применяться различный методы, например, «барьер» из точек высокого потенциала вокруг точки локального минимума или метод Монте-Карло.

Далее для объекта M вводится дополнительная степень свободы – угол поворота q, начальная конфигурация объекта в данном случае – (x_s, q_s). Предполагается, что движется в коридоре минимального потенциала (КМП). Если он ориентирован так, что момент вращения МР в потенциальном поле минимален, то движение происходит таким образом, что главная ось направлена по касательной к КМП.

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

x ¬ x_s

q ¬ q_s

repeat

F_repulse ¬ (0, 0)

moment ¬ 0

for each p Î P

D_min ¬ min (D(c + p, o)) "o Î O

F_repulse ¬ F_repulse + D_min × 1 / |D|²

moment ¬ moment + (p ´ D_min) × k

endfor

F_attract ¬ x_g – x

F_res ¬ F_attract + a × F_repulse

x ¬ x + F_res

q ¬ q + b ´ moment

until (x = x_g) or (|F_res| = 0)

Константа b управляет величиной поворота и определяется эмпирически, поскольку математическое решение нетривиально и зависит от многих факторов. Кроме того, при практической реализации алгоритма, выбор c может быть неоднозначен. В рассматриваемых примерах для трехколесного МР в качестве c бралась середина оси между двумя задними колесами.

В работе [12] представлен метод обхода препятствий мобильным роботом (МР), получивший название метода «гистограмм векторных полей» (VHF метод). Он позволяет обнаруживать препятствия и обходить их во время движения. МР, управляемый данным алгоритмом, маневрирует быстро и без остановок даже среди большого количества неупорядоченных препятствий.

VHF метод для представления препятствий использует сетку на двумерной декартовой плоскости. Каждой ячейке сетки ставится в соответствие характерное значение, представляющее уровень «уверенности» алгоритма в присутствии препятствия в данной ячейке. Метод использует двухуровневую систему представления данных:

• на первом уровне – детальное описание среды, окружающей робота, с помощью декартовой сетки C;

• на втором уровне – полярная гистограмма H, которая строится по данным, содержащимся в C, вокруг центра масс МР как набор значений из C, соответствующий некоторым фиксированным секторам шириной a каждый. Каждому сектору k ставится в соответствие величина h_k, называемая полярной плотностью препятствий в направлении k.

Выходными данными алгоритма являются сигналы управления МР.

Пусть C^*, называемая активной областью, есть область сетки C размером w_s´w_s, построенная вокруг МР; ее элементами являются активные ячейки c_ij. Тогда C преобразуется в H следующим образом: строятся векторы препятствий, направление которых относительно точки текущего положения МР определяется как:

(2.6)

а модуль вектора

(2.7)

где a, b = const > 0;

d_ij – расстояние между активной ячейкой и МР;

c^*_ij – среднее значение в активной ячейке (i, j);

x₀, y₀ – текущие координаты МР;

x_i, y_i – координаты активной ячейки (i, j).

Каждому из k секторов ставится в соответствие угол из ряда 0, a, 2a,…, 360°-a. Тогда между k и c^*_ij существует следующее отношение:

(2.8)

Для каждого сектора k h_k вычисляется

(2.9)

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

(2.10)

Далее вычисляется направление движения в полярных координатах, q_free, и соответствующий ему сектор k_free в H. Алгоритм выбирает более «проходимое» направление и, вместе с тем, как можно более приближенное к текущему направлению на цель q_targ.

Скорость движения МР в начальной точке устанавливается максимальной (S_max), а затем определяется на каждом шаге в соответствии с формулой:

(2.11)

где h``_c = min (h`_c, h_m);

h`_c – сглаженная полярная плотность препятствий в выбранном направлении движения;

h_m – эмпирически установленная константа.

При этом отношение (*) гарантирует S` ³ 0 при h``_c £ h_m.

Статья [13] посвящена методу построения гладких трасс движения мобильного робота (МР), основанному на физической аналогии. Основными достоинствами метода являются устойчивое решение и работа не только с двоичными (препятствие или свободное пространство), но и с разнородными средами, поверхность которых может иметь неравные коэффициенты трения или углы наклона на различных участках.

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

(2.12)

где r – плотность жидкости;

v – вектор скорости движения жидкости;

t – время;

f – внешняя сила;

p – давление;

m – коэффициент вязкости жидкости.

Упрощенное уравнение выглядит следующим образом:

(2.13)

Здесь неизвестными являются вектор скорости v и абсолютная координата x.

Граничные условия:

(2.14)

где ¶W – границы препятствий, n – внешняя нормаль к границе препятствия.

Начальные условия:

(2.15)

где x_S – начальная точка, x_G – целевая точка.

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

(2.16)

где

(2.17)

Если число точек сетки N, то необходимо решить разреженную систему из 3N линейных уравнений.

Результатом работы рассматриваемого алгоритма является множество так называемых «коридоров». Каждый коридор начинается в окрестности стартовой точки и заканчивается в окрестности целевой. Следование МР по осевой линии коридора гарантирует его безопасность.

Далее рассматривается случай, когда внешняя сила не равна нулю, что позволяет учитывать разнородность среды.

Полная потенциальная энергия частицы в потоке:

(2.18)

где S – начальная точка, G – целевая точка, T – вектор, касательный к траектории, p_G – p_S – разность давлений в x_S и x_G.

В случае присутствия силы трения 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 – угол наклона участка поверхности в направлении движения, K_f – коэффициент трения между колесами и поверхностью.

Следует отметить также направление, связанное с достаточно сложным по своей структуре заданием потенциальной функции, которая не имеет локальных минимумов [4, 5]. Однако при этом задание подобной потенциальной функции может оказаться очень сложным.

3. Управление мобильным роботом на основе конечно-автоматного подхода

3.1 Предпосылки создания алгоритма

Распределенные системы, в том числе робототехнические, в последнее время привлекают все большее внимание исследователей. Одна из причин этого состоит в том, что системы такого класса все чаще используются как для промышленных, так и непромышленных приложений: действительно, объединение параллельно функционирующих подсистем позволяет выполнять такие задания, которые не под силу каждой из компонент сложной системы. На рис. 3.1 приведен пример такой многокомпонентной системы, включающей мобильные роботы разного назначения: погрузчики, исследователи и т.д. С другой стороны, управление системами такого класса представляет собой нетривиальную задачу: если управление каждой из подсистем, составляющих сложную систему, задача, вообще говоря, решенная (например, перевод манипулятора из точки в точку по заданной траектории), то управление согласованным поведением группы роботов, объединенных общей целью, является сложной проблемой. Заметим, что задача управления существенно усложняется, если часть подсистем преследует конфликтующие цели.

Рис. 3.1 – Многокомпонентная робототехническая система

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

3.2 Многокомпонентность интеллектуального робота

Многокомпонентная система это система, включающая в свой состав множество подсистем, объединенных общим заданием.

Можно дать ее более точное определение.

Пусть задание T может быть представлено как множество подзаданий t_i:

T = {t₁, t₂,…, t_m} (3.1)

Введем отношение следования F на T, так что t_iFt_j означает, что задание t_i может быть выполнено только, если выполнено t_j. Если такая структуризация задания T проведена, тогда можно построить описывающий T ориентированный граф:

G = (T, A), (3.2)

где T = {t_i} – множество вершин графа G, A = {a_i} Î T ´ T – множество направленных дуг, при этом дуга a Î A соединяет t_i с t_j тогда и только тогда, когда t_iFt_j.

Пусть система S состоит из подсистем s_i (далее называемых локальными системами или терминалами):

S = {s₁, s₂,…, s_N}, (3.3)

при этом T_i Ì T – задание, выполняемое системой s_i.

Тогда систему:

CS = (S, T), (3.4)

будем называть T сложной системой (далее – сложной системой), если выполнены следующие условия:

(3.5)

Условия C1, C2 можно интерпретировать следующим образом:

C1: Сложная система представляет собой набор подсистем, которые в состоянии выполнить задание T.

С2: Действия всех подсистем, входящих в состав сложной системы, должны координироваться в процессе выполнения задания. Под координацией здесь мы понимаем обмен данными (или командами) между подсистемами.

Если одна из подсистем s_i Î S является роботом, то такую сложную систему будем называть многокомпонентной робототехнической системой (МРС).

3.3 Выбор способа организации управления робототехнической системой

Обсудим сначала следующий вопрос: «Что мы понимаем под управлением МРС?» В действительности, каждая из подсистем S_i, входящая в состав МРС, обладает собственной системой управления, способной обеспечить выполнение всех функций, свойственных этой подсистеме. Однако, возникающая для рассматриваемого класса систем необходимость взаимодействовать в процессе исполнения задания, ставит задачу формирования для подсистемы именно того задания, выполнение которого диктуется сложившейся обстановкой. Таким образом, задача управления распределенными системами состоит в планировании действий подсистем до начала исполнения и последующей координации в процессе исполнения.

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

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 = <I, O, U, X, Z, f, h> (4.1)

где I = {i₁, i₂,…, i_p} – множество входов;

O = {o₁, o₂,…, o_q} – множество выходов;

U = {u₁, u₂,…, u_m} – входной алфавит;

X = {x₁, x₂,…, x_n} – множество состояний;

Z = {z₁, z₂,…, z_k} – выходной алфавит;

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 = {e₁, e₂,…, e_n} – множество вершин графа;

C = {c₁, c₂,…, c_m} – множество направленных дуг, c_i = (e_j, e_k).

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

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

Пусть теперь L = (E, C) – сеть автоматов, и пусть распределенная система состоит из подсистем, каждая из которых описывается конечным автоматом, так что M = {M_i} – множество моделей подсистем.

Тогда, если M Ì E, то

L^c = {E^c, C^c}, (4.3)

где E^c = E \ M, будем называть управляющей структурой для распределенной системы, представленной моделями {M_i}.

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

4.1.2 Управляющая структура как средство координации

Рассмотрим простой пример. Пусть два робота Rb₁ и Rb₂ перекладывают детали из накопителя S на два конвейера С₁ и С₂ (рис. 4.1).

В соответствии с изложенным выше, роботы Rb₁, Rb₂ будем описывать как конечные автоматы

Rb_i = (I_i, O_i, U_i, X_i, Z_i, f_i, h_i), i=1,2 (4.4)

со следующими атрибутами:

I_i ={i0}; O_i ={i0}; U_i ={g}; x_i ={0, 1, 2}; Z_i ={y, Y}, i = 1,2 (4.5)

Функции f_i и h_i задаются диаграммой, представленной на рис. 4.2. Каждый из роботов Rb_i воспринимает только одну команду «g», в результате которой он перемещается к накопителю S, захватывает деталь, переносит и устанавливает ее на конвейер С_i. Сигналы «y» и «Y» на выходе робота появляются тогда, когда он освобождает опасную зону и завершает выполнение одного цикла соответственно. Будем строить управляющую структуру в виде трех автоматов, два из которых (Reg₁ и Reg₂) являются логическими регуляторами роботов, а третий (Res) обеспечивает слежение за ресурсом.

На рис. 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 ой подсистемы. После осуществления такого разбиения будем строить резолюции r_ij, и не-цели с элементами К_1i настолько долго, насколько это возможно. Если этот процесс невозможно продолжить, оставаясь в К_1i (это означает, что на этом этапе исполнения необходимо взаимодействие между подсистемами), строим резолюции с соседними подмножествами. Такой процесс обеспечит (в случае успеха) получение последовательности операторов, относящихся к каждой из подсистем, а также точек координации их взаимодействия. Далее полученные результаты используются для преобразования в управляющую структуру, обеспечивающую исполнение сформированного плана (рис. 4.4).