авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --

На правах рукописи

КАПУСТЯН Сергей Григорьевич МЕТОДЫ И АЛГОРИТМЫ КОЛЛЕКТИВНОГО УПРАВЛЕНИЯ РОБОТАМИ ПРИ ИХ ГРУППОВОМ ПРИМЕНЕНИИ Специальность: 05.02.05 – Роботы, мехатроника и робототехнические системы

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Таганрог – 2008

Работа выполнена в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика А.В. Каляева Южного федерального уни верситета и на кафедре "Интеллектуальные и многопроцессорные системы" Технологического института Южного федерального университета в г. Таганроге НАУЧНЫЙ КОНСУЛЬТАНТ: член-корреспондент РАН, доктор технических наук, профессор Каляев Игорь Анатольевич ОФИЦИАЛЬНЫЕ ОПОНЕНТЫ: член-корреспондент РАН, доктор технических наук, профессор Теряев Евгений Дмитриевич доктор технических наук, профессор Паршин Дмитрий Яковлевич доктор технических наук, профессор Глебов Николай Алексеевич ВЕДУЩАЯ ОРГАНИЗАЦИЯ: Государственный научный центр Российской Федерации "ЦНИИ робототехники и технической кибернетики" (г. Санкт-Петербург)

Защита состоится "_"_2008 г. в на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете в зале заседаний Ученого совета Научно-исследовательского института многопроцессорных вычислительных систем имени академика А.В. Каляева Южного федерального университета по адресу 347928, г. Таганрог, ул. Чехова, 2, корп. И, комн. 347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу г. Ростов-на-Дону, ул. Пушкинская, 148.

Просим Вас выслать отзыв, заверенный печатью учреждения по адресу: Ростовская обл., г. Таганрог, ГСП-17А, 347928, пер. Некрасовский, 44, Таганрогский технологический институт Южного федерального университета, Ученому секретарю диссертационного совета Д 212.208.24 Кухаренко Анатолию Павловичу.

Автореферат разослан "" 2008 г.

Ученый секретарь диссертационного совета, канд. техн. наук доцент А.П. Кухаренко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Основные исследования в области управления группами роботов ведутся во многих индустриально развитых странах мира, прежде всего в интересах обороны.

Наиболее интенсивный характер этих работ применительно к направлению военной робототехники наблюдается в США по линии Управления перспективных исследова ний Министерства обороны США ДАРПА (DARPA – Defense Advanced Research Pro jects Agency). Здесь следует выделить программу "Распределенные робототехниче ские системы", которая финансировалась этим агентством и выполнялась рядом ве дущих университетов и научно-исследовательских организаций США.

В настоящее время разработке методов организации взаимодействия в группах роботов на основе децентрализованного способа управления посвящены исследова ния, проводимые под патронажем управления DARPA в рамках программ "Про граммное обеспечение для распределенных робототехнических систем" (Software for Distributed Robotics (SDR)), "Программное обеспечение автономных мобильных ро ботов" (Mobile Autonomous Robot Software (MARS)) и MARS–2020.



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

Решением проблемы группового управления занимались многие известные уче ные, в нашей стране – И.М. Макаров, Д.Е. Охоцимский, Е.П. Попов, Е.И. Юревич, И.А. Каляев, В.Е. Павловский, А.В. Тимофеев и др., за рубежом – Т. Фукуда, Т. Балч, Р. Аркин, М. Матарик, М. Диас, М. Велосо и др.

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

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

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

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

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

В соответствии с поставленной целью для решения сформулированной научной проблемы определены задачи диссертации:

- провести анализ существующих подходов к проблеме группового управления роботами;

- разработать метод коллективного управления роботами при их групповом взаи модействии и провести анализ его эффективности;

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

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

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

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

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

- провести экспериментальные исследования и анализ эффективности разрабо танных методов и алгоритмов;

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

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

Научная новизна полученных результатов заключается в следующем:

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

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

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

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

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

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

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

Наиболее существенные новые научные положения и результаты, выдви гаемые для защиты:

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

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

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

- алгоритмическая реализация метода коллективного управления при решении задач распределения заданий (целей) в группах роботов;

- метод и алгоритмы коллективного управления группами роботов при наличии противодействия со стороны противника;

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

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

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

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

Практическая ценность работы. Практическое использование научных ре зультатов позволяет:

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

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

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

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

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

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

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИОКР в НИИ МВС ТРТУ (НИИ МВС ЮФУ), научным руководите лем, ответственным исполнителем и непосредственным участником которых являлся автор диссертации. Результаты диссертационной работы внедрены в НИИ МВС ЮФУ (г. Таганрог), НИИ специального машиностроения МГТУ им. Н.Э. Баумана (г. Моск ва), ОАО "ВНИИ ТРАНСМАШ" (г. Санкт-Петербург), ОАО "СКБ "Точрадиомаш" (г. Майкоп), Секции прикладных проблем при Президиуме РАН, ГОУ ВПО "Москов ский государственный институт электронной техники (технический университет)", войсковой части 93603 (г. Москва).

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

Внедрение полученных в диссертационной работе результатов вносит значи тельный вклад в развитие экономики и обороноспособности страны.

Апробация работы. Основные результаты работы докладывались и обсужда лись на ряде научно-технических конференций, в том числе: на 14-и международных конференциях и с международным участием, на 7-и всесоюзных, всероссийских кон ференциях и молодежных научных школах, среди них: 14-th Workshop on Distributed Control Systems. - Seoul, Korea, July 1997;

VII, VIII и IХ научно-технических конфе ренциях "Экстремальная робототехника", С.-Петербург, 1996, 1997 и 1998 г.г.;

Все российской научно-технической конференции "Новые технологии управления робо тотехническими и автотранспортными объектами", г. Ставрополь, 1998 г.;

The 4-th ECPD Inter. Conference on Advanced Robotics Intelligent Automation and Active System Proceedings, Moscow, Russia, 1998;

Международной конференцией "Интеллектуаль ные многопроцессорные системы (ИМС'99)", Таганрог, 1999 г.;

IARP Int. Workshop on Micro Robots, Micro Mashines and Systems. Moscow, Russia, nov. 24-25, 1999;

Моло дежной научной школе "Интеллектуальные робототехнические системы", пос. Див номорское, Геленджик, 2001 г.;

Международной научно-технической конференции "СуперЭВМ и многопроцессорные вычислительные системы" (МВС'2002), г. Таган рог, 2002г.;

Первой научной молодежной школе "Интеллектуальные роботы" (ИР-2002), п. Кацивели, Крым, Украина, 2002г.;

Юбилейной Международной конфе ренции по нейрокибернетике "Проблемы нейрокибернетики", посвященной 90-летию со дня рождения профессора А.Б. Когана, г. Ростов-на-Дону, 2002 г.;

Международных конференциях "Интеллектуальные и многопроцессорные системы", пос. Дивномор ское, Геленджик, 2003 г. и 2005 г.;

Научной молодежной школе "Экстремальная робо тотехника – 2003", пос. Дивноморское, Геленджик, 2003 г.;

Первой Всероссийской конференцим с международным участием "Мехатроника, автоматизация, управле ние", г. Владимир, 2004 г.;

Международных научных конференциях "Искусственный интеллект. Интеллектуальные и многопроцессорные системы" (ИМС-2004 и ИМС 2006), п. Кацивели, Крым, Украина, 2004 г., 2006 г;

Международной научной моло дежной школе "Микросистемная техника", п. Кацивели, Крым, Украина, 2004 г.;

IX Международной конференции "Устойчивость, управление и динамика твердого тела", г. Донецк, Украина, 2005 г.;

Международной научно-технической выставке-конгрессе "Мехатроника и робототехника (МиР-2007)", г. Санкт- Петербург, 2007 г.;

Междуна родной научно-технической конференции "Мехатроника, автоматизация и управле ние – 2007 (МАУ-2007)", пос. Дивноморское, Геленджик, 2007 г.

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





Публикации. По теме диссертации опубликовано 80 печатных работ, в том чис ле 2 монографии, 18 статей в центральной печати, из них 12 – в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Феде рации", утвержденный ВАК.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и библиографического списка из 229 наименований. Диссертация содер жит 376 страниц текста, 2 таблицы, 92 рисунка, 71 страницу приложений.

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

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

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

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

Задача группового управления роботами формулируется в работе следующим образом.

Пусть некоторая группа, состоящая из N роботов R j ( j =1, N ), функционирует в некоторой среде Е. Состояние каждого робота Rj ( j =1, N ) в момент времени t описывается вектор-функцией R j (t ) = r j,1 (t ), r j, 2 (t ),...,r j,h (t ). Состояние группы робо тов задается вектором (t ) = R 1 (t ), R 2 (t ),...,R N (t ). Состояние среды вокруг j-го ро бота – E j в момент времени t описывается вектором E j = e1, j (t ), e2, j (t ),...,e w, j (t ). То гда состояние среды, в которой функционируют роботы рассматриваемой группы, при условии, что среда стационарна, в момент времени t описывается вектором E(t ) = E1 (t ), E 2 (t ),...,E N (t ).

Роботы и среда, взаимодействуя друг с другом, образуют систему "группа робо тов – среда", под состоянием которой в момент времени t понимается состояние, описываемое парой S c =,E. Множество различных состояний системы "группа роботов – среда" описывается точками N (h + w) -мерного пространства состояний {S c }. Под начальным и конечным (целевым) состояниями системы "группа роботов – среда" понимаются состояния S 0 = 0,E 0, S cf = f, E f, (1) c соответственно.

Состояние системы "группа роботов–среда" S tc = t,E t в текущий момент вре мени называется текущим.

Каждый робот R j ( j =1, N ) может выполнять действия, описываемые векто ром A j (t ) = a1, j (t ), a 2, j (t ),...,a m, j (t ), причем множество действий, которые может вы полнять робот R j, – {A} j. Множество действий, которые может выполнять группа роботов, есть объединение множеств действий отдельных роботов группы:

{A c } = {A}1 {A}2...{A} N.

Действия, выполняемые группой роботов в момент времени t, могут быть опи саны с помощью вектор-функции A c (t ) = [ A 1 (t ), A 2 (t ),...,A N (t )]T. Изменения состояния системы "группа роботов – среда" описываются системой дифференциальных урав нений вида & S c = f c (S c (t ), A c (t )). (2) При этом на ситуации, а также на действия роботов группы могут накладываться некоторые ограничения:

S c (t ){S cp (t )}{S c }, A c (t ){A cp (t )} {A c }, (3) где {S c (t )} – множество допустимых в момент времени t состояний системы "груп p па роботов – среда";

{A cp (t )} – множество допустимых в момент времени t действий группы роботов.

С учетом введенных выше обозначений задача группового управления роботами заключается в определении на интервале [t 0,t f ] таких оптимальных действий A j (t ) для каждого робота R j, которые переводят систему "группа роботов – среда" из начального состояния в конечное (целевое) и при которых удовлетворяются система связей (2), ограничения (3), а также обеспечивается экстремум функционала tf tf Yc = F(S c (t ), A c (t ), t )dt = F (R 1 (t ), R 2 (t ),...,R N (t ), E(t ), A 1 (t ), A 2 (t ),...,A N (t ),t )dt, (4) t0 t задающего цель функционирования группы роботов и оценивающего качество про цесса управления.

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

Для задач группового управления роботами, функционирующими в условиях динамических, недетерминированных сред, недостаточно существования оптималь ного управления. Необходимо еще, чтобы это управление было найдено в течение времени, за которое состояние S c (t ) системы "группа роботов – среда" существенным образов не изменится.

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

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

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

В общем случае СГУ состоит из подсистемы планирования групповых действий (ППГД), локальных бортовых систем управления (БСУj, j =1, N ) отдельных роботов группы, отвечающих за реализацию групповых действий и бортовых исполнительных устройств (БИУj, j =1, N ) отдельных роботов. Обобщенная структура системы груп пового управления роботами может иметь вид, представленный на рисунке 1.

Ключевую роль в данном слу ППГД чае играет организация ППГД. В ра боте рассмотрены различные спосо AN A A бы организации этих подсистем, в R2,E2 RN,EN R1,E частности – централизованные, рас R1 RN R2 … пределенные (децентрализованные) БСУ1 БСУ2 БСУN и смешанные, например, иерархиче БИУ1 БИУ2 БИУN ские централизованные и иерархи ческие распределенные.

E1 A2 E2 EN A1 AN Как показал анализ сущест Среда Е вующих систем группового управ ления, централизованная организа Рисунок 1 – Обобщенная структура системы ция ППГД имеет ряд существенных группового управления роботами недостатков, основными из которых являются, во-первых, низкая живучесть системы, так как выход из строя центрально го устройства управления (ЦУУ) или канала связи с роботами приводят к выходу из строя всей системы группового управления, а во-вторых, большие объемы информа ции, которой ЦУУ обменивается с роботами. При децентрализованной (распределен ной) организации ППГД данные недостатки отсутствуют, так как планирование, точ нее, выбор своих действий A j каждый робот осуществляет сам с помощью локальной подсистемы планирования действий.

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

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

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

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

Иерархические Централизованные централизованные ППГД Время ППГД группового решения Иерархические распределенные ППГД Треш Распределенные децентрализованные ППГД Количество N 1 N1 N3 N2 роботов в группе Рисунок 2 – Зависимости времени группового решения от способа организации подсистемы планирования групповых действий На основании проведенного анализа в диссертационной работе сделан вывод, что наиболее эффективными являются распределенные системы, реализующие стра тегию децентрализованного группового управления роботами, так как время приня тия решений о групповых действиях роботов в таких системах значительно меньше, чем при других способах организации. Также этот анализ позволяет сделать вывод об отсутствии в настоящее время эффективных подходов к решению проблемы группо вого управления, реализующих децентрализованную стратегию. Существующие ме тоды достаточно громоздки и могут использоваться при управлении группами робо тов, как правило, для решения частных задач.

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

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

Коллективным управлением называется управление, в выработке которого участвуют все члены коллектива.

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

- каждый член коллектива самостоятельно формирует управление (определяет свои действия) в текущей ситуации;

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

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

- допускается принятие компромиссных решений.

В общем случае процессы в системе "группа роботов – среда" непрерывны, но в реальности вектор-функции управления (действия) A c (t ) не являются непрерывными.

Это обусловлено такими факторами, как:

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

- разрешающая способность (по времени) сенсорных устройств;

- цикличность вычислений и т.д.

По этим причинам групповые действия роботов A c (t ) представляют собой раз рывную функцию времени, которая изменяется скачкообразно лишь в определенные моменты времени t t (t – дискретное время, т.е. t = 0,1, 2,... ).

Показано, что в дискретной постановке задача управления группой роботов сво дится к задаче выбора и выполнения в текущий момент времени роботами группы та ких групповых действий A c (t ), которые обеспечивают экстремум (максимум, если оцениваются выгоды от действий роботов группы, или минимум, если оцениваются затраты) целевого функционала t f Yc (t) = F((t ),E(t ),A c (t ),g(t ))t, (5) t =t где g(t ) – вектор противодействующих сил. Далее, для простоты рассмотрения мате риала, речь будет идти о максимуме целевого функционала.

В этом случае задача каждого робота группы R j ( j =1, N ) заключается в том, чтобы выполнять такие действия A j (t ) ( t = 0,1,2,...,t f 1 ), которые бы приводили к дос тижению цели, стоящей перед роботом R j, и при этом максимизировали функционал t f Y j (t) = F j (R j (t ),E j (t ),A j (t ),g j (t ))t Y jmax (Y jmin ), (6) t =t при начальных условиях R 0j = R j (t 0 ) = R j (t), E 0j = E j (t 0 ) = E j (t ), (7) A 0j = A j (t 0 ) = A j (t), g 0j = g j (t 0 ) = g j (t ), уравнениях связи S j (t +1) = f j (S j (t), A1 (t), A 2 (t),...,A j (t),...,A N (t), g j (t)), j =1, N, t = 0,t f 1.

(8) и ограничениях A j (t ){A p (t )}, R j (t ){R p (t )}, E j (t ){E p (t )}. (9) j j j Решение задачи (6) – (9) в работе предлагается осуществлять на основе сформу лированного выше метода коллективного управления путем отыскания для каждого робота R j вектор-функции действий A j (t) ( j =1, N ), при которой достигается экс тремальное приращение целевого функционала (5), то есть Yc = Yc (t +1) Yc (t) (10) при связях (8), начальных условиях (7), ограничениях (9) и фиксированных значениях R i (t 0 )= R i (t )= R 0, A i (t 0 )= A i (t )= A 0 и g i (t 0 )= g i (t )= g i0 (i =1, 2,..., j 1, j +1,..., N ) текущих со i i стояний, действий других роботов Ri (i =1, N, i j ) группы и помех, соответствен но. В качестве текущего действия A 0j робота R j ( j =1, N ) на интервале [t,t +1] прини мается действие, определяемое начальным значением вектор-функции A j (t ) на ин тервале [t,t f ], т.е. A 0j = A j (t ).

Предложен подход к решению дискретной задачи коллективного управления группой роботов, основанный на использовании итерационной процедуры, в рамках которой роботы последовательно выбирают свои очередные действия. Для того чтобы реализовать итерационную процедуру решения оптимизационной задачи (6) – (9), ро боты в группе должны быть определенным образом пронумерованы. Существо ите рационного метода решения оптимизационной задачи (6) – (9) заключается в сле дующем. Каждый робот R j группы выбирает свое очередное действие на основе ин формации о групповой цели, своем текущем состоянии, текущем состоянии среды, текущем значении помехи (если таковая имеет место) и выбранных до него действиях остальных роботов группы, т.е. в соответствии с итерационной формулой A kj +1 = f j (A1 +1,...,A kj 1, A kj, A kj +1,....,A k, R 0j,E 0j,g 0j ), j =1, N, + (11) k N где k = 0,1,2,3,... – номер итерации.

При этом, естественно, должны учитываться ограничения (9).

Следует отметить, что к допустимым в текущий момент времени действиям {A j } робота R j относятся лишь те действия из множества допустимых {A p }, при p j которых выполняется условие Yc 0.Это неравенство можно рассматривать как ус j ловие того, что действия отдельных роботов не наносят ущерб коллективу в целом.

Действие A kj +1 робота R j учитывается всеми остальными роботами группы при выборе своих новых текущих действий. Поэтому при выборе роботом R j своего но вого текущего действия A kj +1 путем решения дискретной задачи (6)-(9) все остальные роботы группы должны попытаться осуществить новый выбор своих оптимальных с точки зрения достижения групповой цели действий, поскольку старый выбор не учи тывал нового действия робота R j. Итерационные циклы оптимизации повторяются до тех пор, пока приращение (10) целевого функционала (5) не прекращается или значе ние этого приращения становится пренебрежимо малым.

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

Во второй главе Дана постановка задачи распределения заданий (целей) в груп пе роботов, и показано применение метода коллективного управления для ее реше ния.

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

Задача распределения целей в группе роботов ставится следующим образом.

Каждый робот R j ( j[1, N ] ) может решать mj целевых задач, на которые раз бивается общая для группы роботов целевая задача (цель) Tc. Достижение каждой из целей Tl Tc, l[1, m j ] дает приращение целевого функционала Yl, j ( l[1, m j ] ).

Задача состоит в том, чтобы в момент времени t распределить цели Tl Tc, l [1, m j ] между роботами группы таким образом, чтобы N mj Yc = Yl, j max, ], (12) j =1 l = при условии, что каждый робот группы может выбирать одну или несколько целей.

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

Решение задачи распределения целей (12) разбивается на два этапа.

На первом этапе решается задача формирования первоначального опорного пла на. Для этого каждый робот группы R j ( j[1, N ] ) сначала определяет для каждой цели Tl Tc, l [1, m j ] значение оценки эффективности d j,l = f (R j (t 0 ),E j (t 0 )), формируя таким образом одномерный массив D j =[d j,1,d j, 2,...,d j,l,...,d j, N ]. Затем с помощью ите рационной процедуры формируется первоначальный опорный план, для чего каждый робот определенным образом выбирает одну из целей Tl Tc ( l[1, N ] ) случайно, или с таким же номером, как и у самого робота или по максимуму оценки эффективности d j,l в массиве Dj.

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

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

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

Показано, что предложенные алгоритмы коллективного улучшения плана позво ляют снизить вычислительную сложность задачи, решаемой бортовой системой управления каждого отдельного робота группы, по сравнению с известными центра лизованными алгоритмами последовательного улучшения плана, реализуемыми ЦУУ группы роботов. Например, при исследовании парных обменов сложность уменьша ется в N / 2 раз, а при исследовании цепочек обменов – в N раз, где N – число робо тов в группе.

Для решения задачи коллективного распределения целей также предложено ис пользовать алгоритмы, направленные на отыскание ближайшего локального экстре мума целевого функционала на интервале времени [ t 0,t 0 +1 ]. В некоторых случаях этот локальный экстремум может совпадать с глобальным, естественно, на указанном интервале времени. Эти алгоритмы являются приближенными или ускоренными, по скольку за счет отказа от поиска глобального экстремума достигается быстрота реше ния задачи распределения целей, являющегося если не оптимальным в текущей си туации, то близкой к оптимальному.

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

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

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

Доказана сходимость этих алгоритмов.

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

Кол-во операций 50 55 0 5 10 15 20 25 30 35 40 Численность Обозначения: группы роботов Полный перебор Алгоритм последовательного улучшения плана Алгоритм коллективного улучшения плана Приближенный алгоритм последовательного выбора целей Приближенный алгоритм одновременного выбора целей Уточненный ускоренный алгоритм Рисунок 3 – Зависимость количества вычислительных операций от численности группы роботов В работе приведены примеры использования предложенных методов и алгорит мов для решения прикладных задач коллективного распределения целей, в частности, в группе боевых роботов, а также в группе космических роботов при дистанционном зондировании поверхности, или в группе роботов, решающих задачу картографиро вании местности.

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

Данные экспериментов подтверждают эффективность предлагаемых алгоритмов.

В качестве показателя эффективности применения той или иной стратегии при реше нии задачи картографирования в работе использовалось значение удельных затрат группы роботов на картографирование одной единицы площади L q=, (13) S K п где L – суммарный путь, пройденный роботами группы при картографировании поверхности;

S – площадь обработанной поверхности (число дискретных участков);

Kп – коэффициент покрытия поверхности.

Обобщенные результаты одного из экспериментов для группы из трех роботов приведены в таблице.

Путь, пройденный Суммар- Коэффициент Алгоритм роботом № q ный путь покрытия 1 2 Коллективный 195 195 185 575 0,98 0, Жадный 180 189 171 540 0,82 0, Случайный вы 273 246 262 781 0,92 0, бор Из таблицы видно, что алгоритм коллективного распределения целей требует наименьших удельных затрат, чем другие алгоритмы.

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

В третьей главе исследуются задачи управления группами роботов при органи зованном противодействии со стороны другой группы роботов. Исследование прове дено на модельных задачах игры роботов в футбол и при ведении группой роботов боевых действий.

Задача планирования групповых действий при игре в футбол формулируется следующим образом: каждому роботу-игроку B j ( j =1, N ) необходимо в текущий мо мент времени в качестве цели своего движения выбрать такой участок поля S i S ej, чтобы в результате этого выбора достигалось максимальное значение функционала N Y = d j,i, (14) j = где dj,i – оценка эффективности выбора игроком B j участка S i S ej в качестве цели своего движения. В свою очередь, оценка эффективности dj,i определяется некоторым функционалом d j,i = F ( 1i, j, 2, j,..., w, j ), i i (15) где li, j (l =1,w) – функции, зависящие от параметров положения участка S i S ej отно сительно мяча, относительно других роботов-игроков обеих команд, своих и чужих ворот и т.п.

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

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

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

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

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

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

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

Задача планирования групповых действий роботов в смешанном подразделении на поле боя формулируется следующим образом. Предположим, что в боевых дейст виях участвуют две группы: ={R B, j =1, N } (условно "наша"), содержащая N боевых j единиц, и группа роботов противника C ={RiC,i =1, M }, содержащая M боевых единиц.

Состояние каждой боевой единицы описывается некоторым вектором параметров R B = r1Bj, r2B j,...,rvBj j =1, N или R C = r1Ci, r2Ci,...,rvCi i =1, M, (16) j,,, i,,, таких как, например, скорость, боекомплект, подвижность, огневая мощь, дальнобой ность, координаты местоположения и т.п.

Задача, стоящая перед "нашей" группой боевых роботов состоит в определе нии таких действий A B (t ) ( j =1, N ), в результате выполнения которых с учетом связей j (8) и ограничений (9) достигается максимум целевого функционала Y = K1 P K 2 P, (17) B C N где P = PR – суммарный боевой потенциал группы ;

B B j j = M P C = PRiC – суммарный боевой потенциал группы C ;

i = K 1 и K 2 – стратегические коэффициенты.

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

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

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

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

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

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

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

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

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

Отличие задачи стайного управления заключается в отсутствии у каждого робо та прямой и достоверной информации о наличии и действиях других роботов группы, а также о возможных противодействиях со стороны внешних сил, в том числе и орга низованного противодействия со стороны других групп роботов. В то же время он располагает информацией о своих индивидуальных возможностях по трансформации своего состояния S i и окружающего его участка среды E i за счет своих индивиду альных действий, а также имеет возможность определять действующие на него в те кущий момент времени силы G i. Иными словами, каждый робот Ri, входящий в стаю, не имеет информации о действиях всех роботов стаи и состояния среды вокруг них, а может только определять изменения своего состояния, состояния участка ок ружающей среды в соответствии с выражениями:

E i = f i ' (R i, A i, E i,G i ), R i = f i (R i, A i, E i,G i ), & & (18) его с учетом ограничений i (R i,E,G ) 0, i (R i, A i, E,G ) 0, (19) которые описывают его исходное "представление" о возможностях его индивидуаль ного влияния на среду с учетом ограничений.

При этом робот R j адаптирует свою индивидуальную модель (18) и (19) к стай ному взаимодействию посредством анализа изменений состояния среды E i, произо шедших в результате действий всей стаи.

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

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

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

Четвертая глава посвящена решению проблемы управления большими группа ми роботов.

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

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

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

При этом общее время t КД решения задачи оптимизации коллективных действий в группе роботов будет составлять t КД = (t ПОКД + t ПИ ) N K, (20) где t ПОКД – время реализации процедуры оптимизации коллективных действий од ним роботом группы;

t ПИ – время реализации процедуры передачи информации о выбранном действии каким-либо роботом остальным роботам группы;

N – число роботов в группе;

K – число итерационных циклов.

С другой стороны, для того чтобы действия, выбранные роботами с использова нием метода коллективного управления, отвечали текущей ситуации (т.е. соблюдался режим реального времени), необходимо, чтобы выполнялось условие t КД p, (21) где p – время изменения ситуации в системе "группа роботов – среда" (т.е. время, за которые параметры состояния роботов и среды изменяются таким образом, что могут быть измерены сенсорными устройствами роботов и могут быть учтены при выборе очередных действий действия).

Будем считать, что группа роботов "управляема", если выполняется условие (21).

Из (20) и (21) следует, что допустимое число роботов в "управляемой" группе, которые могут принимать участие в итерационной процедуре оптимизации коллек тивных действий, должно быть ограничено величиной p N max =, (22) K (t ПОКД + t ПИ ) где N max – максимально допустимое число роботов в группе, при котором выполняет ся условие управляемости (21).

Таким образом, возникает проблема "управляемости" больших групп роботов в случае, когда N N max.

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

Одним из возможных подходов к решению проблемы управляемости большой группы роботов (или микророботов) является ее разбиение на некоторые подгруппы, численность которых не превышает граничного значения N max (22), при котором вы полняется условие управляемости (21) для этих подгрупп.

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

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

Одним из таких методов является иерархическая кластеризация.

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

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

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

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

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

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

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

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

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

Работоспособность и эффективность методов кластеризации при управлении большими группами роботов показана на модельных примерах.

В пятой главе анализируется комплекс задач, решаемых отдельным роботом при выполнении очередного действия в составе группы и предлагаются методы и ал горитмы их решения с использованием однородных нейроподобных структур (ОНС).

В результате реализации процедуры оптимизации коллективных действий для каждого робота группы определяется действие, направленное на достижение группо вой цели. Для его выполнения бортовая система управления (БСУ) каждого робота группы должна сформировать соответствующие управляющие воздействия на испол нительные механизмы робота.

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

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

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

Для этого множество различных состояний системы "робот-среда" описывается точками S i, i [1, n] n-мерного пространства состояний системы "робот–среда" ( n = h + w ), которое можно обозначать, как {S}. Предлагается выполнить ряд преобра зований, в результате которых исходная задача управления роботом сводится к задаче определения дискретной последовательности состояний системы "робот-среда" S 0, S1,...,S f, реализующих экстремум интегральной суммы k Y = F0* (S, S). (23) m = При этом определяется последовательность управлений, соответствующая полу чаемой последовательности состояний.

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

Также показано, каким образом сформулированная выше задача может быть представлена в графовой форме. Для этого пространство состояний {S} системы "ро бот-среда" покрывается однородным графом-решеткой G (Q, X), Каждая вершина q j Q этого графа соответствует некоторой дискретной точке S m пространства состоя ний {S}. Дуга x(q m, qm+1 ) X соединяет вершины q m и qm+1, соответствующие соседним дискретным точкам S m и S m +1, пространства состояний. Кроме того, каждой дуге, значение которого может определяться различными x(q m, qm+1 ) приписывается вес способами и быть равным, например, приращению интегральной суммы (23) при пре образовании ситуации S m в ситуацию S m +1. Также веса, характеризующие приоритеты тех или иных состояний могут быть приписаны и вершинам графа.

Кроме того, на графе G (Q, X) выделяется вершина q0, координаты которой в пространстве {S}n соответствуют координатам точки S 0, определяемой, в свою оче редь, параметрами текущего состояния S 0, а также подмножество вершин Q f Q, координаты которых удовлетворяют параметрам целевых (конечных) состояний {S} f.

Также на графе G (Q, X) выделяется множество допустимых вершин Q g Q, соответ ствующих допустимым состояниям системы "робот-среда", а также множество до пустимых дуг X g X, соответствующих допустимым действиям робота.

В результате этих построений задача определения последовательности состоя ний S 0, S1,...,S f, дающих экстремум интегральной сумме (23) и удовлетворяющей ус тановленным в главе 1 ограничениям, сводится к задаче построения пути на графе G (Q, X) между вершиной q0 и одной из вершин множества Q f, проходящего только через вершины множества Q g и дуги множества X g, и имеющего экстремальный суммарный вес принадлежащих ему дуг.

Рассмотрены различные варианты топологии графа G (Q, X) и способы его по строения.

Для аппаратной реализации процедуры поиска экстремального пути на графе предложена структура, топологически подобная графу G (Q, X). Так как данная струк тура реализует не численные вычисления, а волновую процедуру, моделирующую процесс поиска всех возможных путей на графе, то она может быть отнесена к классу однородных нейроподобных структур (ОНС).

Преимуществами ОНС являются: их высокая живучесть, так как выход из строя отдельных элементов (ячеек) не приводит к выходу из строя всей структуры, высокое быстродействие, достигаемое за счет параллельной аппаратной реализации процеду ры поиска и анализа всех возможных путей на графовой модели пространства состоя ний системы "робот-среда", регулярность структуры, позволяющая легко реализовать ОНС в виде СБИС, представленной на рисунке 5 или на базе ПЛИС, что позволяет значительно уменьшить массогабаритные характеристики бортовых систем управле ния роботов. Такие СБИС были разработаны при непосредственном участии автора.

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

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

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

Показана работа этого алгоритма на примере управления движением мобильного робота к цели. Рисунок 5 – СБИС однородной нейроподобной структуры Описаны способы получения значений весов дуг и вершин графа G (Q, X).

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

Рисунок 6 – Фрагменты полигонных испытаний макетных образцов систем управления на базе ОНС в составе прототипов роботов-планетоходов В заключении обобщаются основные результаты диссертационной работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- предложены технические решения ОНС, реализованные в виде СБИС и микро сборок.

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

Эффективность полученных теоретических и прикладных результатов подтвер ждена экспериментальными исследованиями, а также практической реализацией, вне дрением и использованием этих результатов на ряде предприятий, в частности, СПП РАН (г. Москва), НИИ СМ МГТУ им. Н.Э. Баумана (г. Москва), МИЭТ (г. Москва), ОАО "СКБ "Точрадиомаш" (г. Майкоп), ОАО "ВНИИТРАНСМАШ" (г. Санкт Петербург), НИИ МВС ЮФУ (г. Таганрог), войсковой части 93603 (г. Москва).

Основные публикации по теме диссертации 1 Капустян, С.Г. Распределенные системы планирования действий коллективов роботов [Текст]: монография / И.А. Каляев, А.Р. Гайдук, С.Г. Капустян.–М.: Янус-К, 2002.–292 с.

2 Капустян, С.Г. Основы построения распределенных систем управления кол лективами роботов [Текст] / И.А. Каляев, С.Г. Капустян, Л.Ж. Усачев // Информаци онные технологии.- 1998.-№ 5.- С. 13-18.

3 Капустян, С.Г. Метод оптимального распределения целей в коллективе робо тов [Текст] / С.Г. Капустян, Л.Ж. Усачев, С.В. Стоянов // Информационные техноло гии.- М.: Машиностроение.- 1998.-№4,.- С.29-34.

4 Капустян, С.Г. Децентрализованное планирование действий коллектива интел лектуальных роботов [Текст] / С.Г. Капустян //Интеллектуальные робототехнические системы – 2001: мат. молодежн. научн. школы.- Таганрог: Из-во ТРТУ, 2001.- С. 184-187.

5 Капустян, С.Г. Метод организации мультиагентного взаимодействия в распре деленных системах управления группой роботов при решении задачи покрытия пло щади [Текст] / С.Г. Капустян //Искусственный интеллект.- 2004.- №3.- С. 715-727.

6 Капустян, С.Г. Многоуровневая организация коллективного взаимодействия в группах интеллектуальных роботов [Текст] / С.Г. Капустян //Известия ТРТУ.- Таган рог: Изд-во ТРТУ.- 2004.- №9.- С.149-158.

7 Капустян, С.Г. Децентрализованный метод коллективного распределения це лей в группе роботов [Текст] / С.Г. Капустян // Известия высших учебных заведений, Электроника.- 2006.-№2.- С. 84-91.

8 Капустян, С.Г. Алгоритмы коллективного улучшения плана в задачах группо вого управления роботами [Текст] / С.Г. Капустян //Искусственный интеллект.- 2006. №3.- С. 409-420.

9 Капустян, С.Г. Алгоритм коллективного улучшения плана в задачах распреде ления ресурсов многопроцессорных информационно-управляющих систем [Текст] / В.А. Гандурин, С.Г. Капустян, Э.В. Мельник // Вестник компьютерных и информаци онных технологий.- 2007.- №12.- С. 40-50.



Pages:   || 2 |
 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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