3810

УДК 004.896

ПЕРСПЕКТИВЫ ПРИМЕНЕНИЯ,

ПРИНЦИПЫ ПОСТРОЕНИЯ И

ПРОБЛЕМЫ РАЗРАБОТКИ

МУЛЬТИАГЕНТНЫХ

РОБОТОТЕХНИЧЕСКИХ СИСТЕМ

В.М. Лохин

Московский государственный технический университет радиотехники, электроники и автоматики Россия, 119454, Москва, пр. Вернадского, 78 E-mail: [email protected] С.В. Манько Московский государственный технический университет радиотехники, электроники и автоматики Россия, 119454, Москва, пр. Вернадского, 78 E-mail: [email protected] М.П. Романов Московский государственный технический университет радиотехники, электроники и автоматики Россия, 119454, Москва, пр. Вернадского, E-mail: [email protected] С.А-К. Диане Московский государственный технический университет радиотехники, электроники и автоматики Россия, 119454, Москва, пр. Вернадского, E-mail: [email protected] Ключевые слова: автономные роботы, многоагентные робототехнические системы, планирование действий, распределение заданий, конечные автоматы, многокритериальный выбор Аннотация. Рассматриваются примеры и перспективы применения мультиагентных робототехнических систем различных типов и назначения. Развиваются принципы группового управления роботами, методы, алгоритмы и программное обеспечение для планирования их целесообразного поведения и координации действий, а также построения единой информационной модели мира на основе интеграции разнородных сенсорных данных при совместном решении общих прикладных задач. Приводятся результаты комплексного моделирования мультиагентных робототехнических систем.

1. Введение Ретроспективный взгляд на историю современной робототехники позволяет выделить основные этапы ее поступательного развития, связанные с появлением принципиально новых типов устройств и систем, наращивание функциональных возможностей которых от поколения к поколению определяется существенным усложнением решаемых прикладных задач, а также расширением областей применения: – от жестко проXII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ ВСПУ- Москва 16-19 июня 2014 г.

граммируемых манипуляторов для загрузки станков и оборудования (60-е гг. ХХ века), до адаптивных манипуляционных и мобильных роботов для автоматизации сложных технологических процессов в различных отраслях промышленного производства (70е гг. ХХ века) и, наконец, интеллектуальных робототехнических систем военного, специального и бытового назначения, ориентированных на работу в условиях неопределенности автономном режиме, в том числе в составе мультиагентных систем (90-е гг.

ХХ - начало ХХI века).

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

2. Примеры и перспективы прикладного применения мультиагентных робототехнических систем Акцентированное внимание, активно проявившееся со стороны мирового научнотехнического сообщества на рубеже ХХ-ХХI веков к проблематике мультиагентных робототехнических систем (МАРС), обусловлено чисто прагматическими соображениями о преимуществах их прикладного применеия:

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

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

возможность повышения надежности решения выполняемой задачи при отказе одного из исполнителей за счет перераспределения функций между оставшимися;

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

Перспективы применения МАРС охватывают широкий спектр прикладных областей, представленных на рис. 1.

Рис. 1. Области прикладного применения многоагентных робототехнических систем.

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

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

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

Кроме того, в зависимости от возможности согласования индивидуально принимаемых решений, стратегии децентрализованного управления делятся на коллективные (с непосредственным обменом информацией между всеми членами группировки) и стайные (с опосредованной связью на основе анализа изменений среды и обстановки при отсутствии взаимной передачи данных).Таким образом, структура децентрализованной системы коллективного управления (рис. 2 б)) должна предусматривать наличие каналов двусторонней связи между всеми членами группировки для координации выполняемых ими действий и обмена информацией о текущем состоянии среды. Главное достоинство подобного варианта построения системы заключается в сохранении ее работоспособности при выходе из строя одного или нескольких элементов. Основной недостаток децентрализованных систем управления связан со значительным объемом функций, возлагаемых на каждого члена группировки.

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

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

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

Решение последней проблемы связано с необходимостью интеграции преимуществ ряда различных стандартов и технологий беспроводной связи, с учетом разработки специализированных протоколов передачи данных, реализации принципов ретрансляции сообщений абонетскими узлами (по аналогии с mesh-сетями [4]) и т.д.

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

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

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

обеспечения автономности агентов и системы в целом.

Каждая из перечисленных проблем является крайне сложной и многогранной, затрагивая целый ряд взаимосвязанных вопросов.

Так, например, проблема организации целесообразных взаимодействий между активными элементами в составе МАРС охватывает две важнйших составляющих:

планирование координированных действий агентов (исходя из анализа поставленной прикладной задачи, процесса ее выполнения и имеющихся ресурсов) с последующим формированием и выдачей соответствующих заданий;

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

Рис. 3. Ключевые проблемы разработки и внедрения мультиагентных робототехнических систем.

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

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

В свою очередь, обеспечение автономности робота (как самостоятельного элемента МАРС, априорно ориентируемого на работу в условиях неопределенности) предполагает наличие интеллектуальной бортовой системы управления, имеющей иерархическую структуру и реализующей весь спектр необходимых функций на основе комплексного применения современных технологий обработки знаний [2, 3, 5] (рис. 4.).

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

Н.Э. Баумана, МИЭТ, ЦНИИРТК, МИРЭА и других организациях по созданию экспериментальных образцов автономных робототехнических систем и комплексов.

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

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

единство целей функционирования агентов;

адекватность интеллектуальных и функциональных возможностей агентов сложности решаемых задач;

единство информационного пространства системы;

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

взаимная информационно-логическая совместимость агентов.

Рис. 4. Принципы построения и обобщенная структура интеллектуальной системы управления автономным роботом.

Представленные принципы фактически предопределяют функциональную структуру МАРС (Рис..5), включающую в свой состав следующий набор основных модулей:

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

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

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

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

построения модели среды на основе интерпретации обобщенной информации, поступающей от агентов;

анализа модели среды для выявления особенностей текущей обстановки.

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

Рис. 5. Обобщенная функциональная структура МАРС.

5. Модели и алгоритмы планирования действий в мультиагентных робототехнических системах Планирование целесообразных действий является важнейшим вопросом в теории и практике многоагентных систем. Один из подходов к его решению, активно развиваемый усилиями научной школы члена-корреспондента РАН И.А. Каляева, основан на формировании некоторого функционала, экстремум которого соответствует успешному достижению цели функционирования системы, а многомерный аргумент – действиям агентов по выполнению общей прикладной задачи. Очевидно, что значения аргумента, обеспечивающие экстремум целевого функционала, и будут определять искомый план действий агентов, входящих в состав системы. Применение этого подхода, эффективность которого подтверждается примерами моделирования МАРС различных типов и назначения [6-8], в первую очередь охватывает множество прикладных задач с произвольным порядком выполнения необходимых операций.

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

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

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

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

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

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

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

Рис. 6. Выявление доступных для исполнения операций по мере очередности завершения предыдущих на основе контроля за выполнением поставленной прикладной задачи по установленному сценарию.

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

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

(1) ненных операций, предшествующих данной; u1 – входной сигнал об отсутствии невыO полненных операций предшествующих данной; u2 – входной сигнал о завершении данной конкретной операции; X O x0, x1, x2 – алфавит состояний;

«операция не выполнена»; x1 – состояние «операция передана на выполнение»; x2 – ходной сигнал, подтверждающий, что операция находится в состоянии «невыполнена»;

y1 – выходной сигнал, подтверждающий, что операция передана на выполнение; y2 – выходной сигнал, подтверждающий, что операция выполнена; f O, h O – функции переходов и выходов, задаваемые таблицей 1.

Диаграмма переходов конечного автомата (1), как типового элемента модели выполнения решаемой прикладной задачи по установленному сценарию, показана на рис.

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

Реализуемость предложенного подхода к планированию действий МАРС полностью подтверждается данными компьютерного моделирования.

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

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

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

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

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

(2) где F j – логическая переменная, характеризующая наличие или отсутствие у агента необходимой функциональной возможности для выполнения рассматриваемой технологической операции и принимающая значение соответственно 0 или 1; R – количественная оценка полезности агента с позиций имеющихся (остающихся) у него ресурсов для (после) выполнения рассматриваемой технологической операции.

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

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

(3) где ci – весовой коэффициент, характеризующий значимость соответствующего вида ресурса в составе обобщенной оценки; ri – количественная оценка запаса соответствующего вида ресурса, имеющегося в распоряжении агента.

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

Экспериментальные исследования на практике подтвердили эффективность применения алгоритмов оценки полезности исполнителей для решения задач распределения заданий в составе МАРС, комплексное моделирование которой проводилось с использованием средств трехмерной графики MOGRE и физической библиотеки Nvidia PhysX.

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

Рис. 8. Моделирование процессов планирования действий и распределения заданий в составе МАРС при решении задачи сборки кубиков в пирамиду: исходное состояние.

1. Каляев И.А., Гайдук А.Р., Капустян С.Г. Модели и алгоритмы коллективного управления в группах роботов. М.: Физматлит, 2009.

2. Макаров И.М., Лохин В.М., Манько С.В. и др. Интеллектуальные системы автоматического управления.

М.: Наука, 2001.

3. Макаров И.М., Лохин В.М., Манько С.В., Романов М.П. Искусственный интеллект и интеллектуальные системы управления. М.: Наука, 2006.

4. Осипов И.Е. Mesh-сети: технологии, приложения, оборудование // Технологии и средства связи. 2006. № 5. Интеллектуальные роботы: учебное пособие для ВУЗов / Под ред. Е.Ю. Юревича / И.А. Каляев, В.М.

Лохин, И.М. Макаров и др. М.: Машиностроение, 2007.

6. Каляев И.А. Метод коллективного управления группой объектов // Мехатроника, автоматизация, управление. 2003. № 3.

7. Капустян С.Г., Вьюшин А.А. Распределенная система управления группой роботов-штабелеров / Мехатроника, автоматизация, управление. 2003. № 3.

8. Каляев И.А., Капустян С.Г. Проблемы группового управления роботами // Мехатроника, автоматизация, управление. 2009. № 6.

9. Зенкевич С.Л. Принципы построения систем управления роботов // Робототехнические системы и автоматическое управление: Межвуз. сб. научн. тр. М.: МИРЭА, 1985.

10. Зенкевич С.Л., Клевалин А.В. Программирование сборочных адаптивных роботов // Управление в гибких производственных системах и робототехнических комплексах: Межвуз. сб. научн. тр. М.: МИРЭА, 1988.

11. Кузнецов О.П., Адельсон-Вельский Г.М.. Дискретная математика для инженера. М.: Энергоатомиздат, 12. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и 13. Мамиконов А.Г. Принятие решений и информация. М.: Наука, 1983.