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

005538410

НИКОЛАЕВ Дмитрий Александрович

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

МОДЕЛИРОВАНИЕ И УПРАВЛЕНИЕ МУЛЬТИАГЕНТНЫМИ СИСТЕМАМИ МЕТОДАМИ ИДЕМПОТЕНТНОЙ АЛГЕБРЫ

Специальность 0o.l3.lS - Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических паук

Воронеж - 2013

005538410

Работа выполнена в ФГБОУ ВПО «Липецкий государственный технический университет».

Научный руководитель: Блюмин Семен Львович, доктор

физико-математических паук, профессор, ФГБОУ ВПО «Липецкий государственный технический университет», профессор кафедры прикладной математики

Официальные оппоненты: Агранович Юрий Яковлевич, доктор физико-математических паук, профессор, ФГБОУ ВПО «Воронежский государственный технический университет», профессор кафедры автоматизированных и вычислительных систем

Васильев Олег Олегович, кандидат технических наук, ФГБУН «Институт проблем управления им. В.А. Трапезникова российской академии паук», старший научный сотрудник лаборатории N«7

Ведущая организация: ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Защита состоится «28» ноября 2013 г. в 131Ю часов в конференц-зале па заседании диссертационного совета Д 212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» но адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «28» октября 2013 г.

Ученый секретарь ^ / "

диссертационного совета /Чб/ Барабанов Владимир Федорові!1

" с//' /

п

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Идемпотентная алгебра представляет собой раздел прикладной математики, изучающий полукольца с идемпотентным сложением. Тесные взаимосвязи с булевой и нечеткой логикой, а также теорией оптимизации вьщвинули данный раздел на одну из центральных позиций в искусственном интеллекте, теории управления и математической экономике. Причиной увеличения'интереса к этой области при решении задач моделирования, анализа и управления сложными системами послужило обнаружение скрытой линейности, формулируемой в терминах идемпотентных полуколец, многих нелинейных в обычном смысле задач и динамических процессов.

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

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

Тематика работы соответствует научному направлению Липецкого государственного технического университета «Алгебраические методы прикладной математики и. информатики в моделировании и управлении сложными распределенными системами».

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

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

- проведение анализа существующих подходов к моделированию и управлению сложными техническими системами на основе классической и

идемпотентной математики;

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

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

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

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

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

Тематика работы соответствует п. 3. «Развитие качественных и приближенных аналитических методов исследования математических моделей», и. 4 «Разработка, обоснование и тестирование эффективных численных методов с применением ЭВМ», п. 5 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента» паспорта специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ».

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

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

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

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

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

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

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

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

Компоненты математического и программного обеспечения прошли государственную регистрацию в Отраслевом фонде алгоритмов и программ и ФГБУ «Федеральный институт промышленной собственности».

Реализация и внедрение результатов работы. Математические модели, методы и научно-практические рекомендации диссертационного исследования использованы для создания опытного образца системы управления роботом-манипулятором и проекта системы управления коллективом транспортных роботов на заводе холодильников «Indesit International». Эффект от внедрения заключается в обеспечении необходимой функциональности программных модулей и реализации их информационного обеспечения. Результаты диссертационной работы используются в учебном процессе ФГ-БОУ «Липецкий государственный технический университет» при подготовке инженеров-математиков по специальности «Прикладная математика».

Апробация работы. Основные результаты работы докладывались и обсуждались на: Международном форуме студенческой и учащейся молодежи «Первый шаг в науку» (Минск, 2010,2011), Третьей, Четвертой и Пятой традиционных всероссийских молодежных летних школах «Управление, информация и оптимизация» ИПУ им. В.А. Трапезникова РАН (Ярополец, Звенигород, Солнечногорск, 2011, 2012, 2013), Международной школе-ссминарс «Интеллектуальные компьютерные обучающие системы» (Воронеж, 2011), Всероссийской конференции с элементами научной школы для молодежи

«Математическое моделирование в технике и технологии» (Воронеж, 2011), Всероссийской научной школе «Информационно-телекоммуникационные системы и управление» (Воронеж, 2011), XI и XII международных научно-практических конференциях «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2011), XVII Международной открытой научной конференции «Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем» (Воронеж, 2012), Воронежской весенней математической школе «Понтрягинские чтения -XXIII» (Воронеж, 2012), IX Всероссийской школе-конференции молодых ученых «Управление большими системами» (Липецк, 2012), Международной конференции «Tropical and Idempotent Mathematics» (Москва, 2012), Воронежской зимней математической школе «Современные методы теории функций и смежные проблемы» (Воронеж, 2013). Работа была награждена дипломом II степени Областного фестиваля научно-технического творчества молодежи «НТТМ-2011» (Липецк, 2011), дипломом Конкурса научных работ молодых ученых по теории управления и ее приложениям ИПУ им. В.А. Трапезникова РАН (Москва, 2011) и дипломом фонда содействия развитию малых форм предприятий в научно-технической сфере по программе У.М.Н.И.К. (Липецк, 2013).

Связь с научными программами. Исследование проводилось в рамках инициативного научного проекта, поддержанного грантом РФФИ «Разработка математического и программного обеспечения для моделирования, прогнозирования, оптимизации и управления сложными системами на основе методов идемнотеитной математики и интервального анализа», проект JV2 11-07-00580-а.

Публикации. По результатам исследования опубликованы 22 научные работы без соавторов, в том числе 4 - в изданиях, рекомендованных ВАК РФ.

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

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

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

Приведены основные сведения из искусственного интеллекта и теории мультиагентных систем, непосредственно связанные с тематикой исследования. Искусственный интеллект понимается как наука о проектировании ра-

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

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

Определение 1. Тропическое полукольцо йппп есть множество яи { + оо} вместе с операциями сложения а ф Ь = тш(а, Ь) и умножения а О Ь = а + Ь, нулем 0 = +оо и единицей 1 = 0. Тропическое полукольцо Ятях есть множество /?и {-оо} вместе с операциями сложения афЬ = тах(а, Ъ) и умножения а О Ь = а + Ъ, нулем 0 = —оо и единицей 1 = 0.

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

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

искусственных полукольцевых нейронных сетей Хопфилда.

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

Определение 2. Поразрядный порядок <raj является обобщением лексикографического порядка <1еХ на случай слов произвольной длины и для любых а = с*\... Oik, Ь = ßi... ßi Ç: определяется по формуле

a <rad b О (|а| < |6|) V (а <icx 6),

где - множество слов произвольной длины, порожденных упорядоченным алфавитом из q € N символов.

Определение 3. Частично свободным субтропическим полукольцом Fq>m¡п будем называть фактор-множсство = SJ U {+w} вместо с операциями

сложения a©b = iiiin(a, b) и умножения aQb = соп(а, b), нулем 0 = и единицей 1 = е, где а ~ b (а = 6) V(ja| = |6| = +оо), Е* - множество конечных слов, порожденных упорядоченным алфавитом Е? из q G N символов, min - операция минимума в смысле поразрядного порядка, соп - операция конкатенации, £ - пустое слово, +ui - класс эквивалентности бесконечных слов. Двойственное полукольцо F4iшах вводится аналогично.

Развитие техники для работы с данным классом полуколец включает в себя введение регуляризованного оператора замыкания, оператора бинаризации, нелинейных функций popi И sliceij, которые будут использованы в составе искомых математических моделей. Теорема, устанавливающая соответствие между введенным классом частично свободных субтропических полуколец и известными аналогами формулируется следующим образом. Теорема 1 (О морфизмах полуколец).

Пусть определены тропические полукольца Rm¡п и i?majc, свободные субтропические полукольца без нуля Ф?)П1ш и Фд,тах, частично свободные субтропические полукольца Fqtmin и -F<,,max, свободные гиперполукольца H,h^ и H4i гомоморфизмы —> и изоморфизмы к* полуколец. Тогда существуют сюрьек-тивные отображения рг, Pr, PR и следующая диаграмма коммутативна:

„ У = РгЫ -

I

у = PR(x) ]

* У = Рг(х)

1 q, шах ^тах

т т т

\v\ = -N M = -N у = -х

\ 1 I

>дргМ У = М , д .

Определение 4. Под регуляризованным оператором замыкания * понимается обычный оператор замыкания, перенормированный с использованием функции Мёбиуса /¿(ж) и определяемый для матрицы А 6 -Р1,"*" с элементами е как матрица Л* € с элементами а*- € ^ по формуле р

аЬ = ф ф ■ ■ ■ аЧ-а)ап 1а»1»2 • • •

/с=0 1<11,...г1<п

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

Определение 5. Оператором бинаризации Ь : —>• {О, I}9 будем назы-

вать оператор, преобразующий произвольное слово а = а\... а^ в бинарный вектор размера с единицами на сц-м, ..., а/ь-м не обязательно различных местах и нулями на всех остальных.

Определение 6. Однопараметрическая функция popi : ^ \ {0} ^ \ {0} есть функция, выделяющая единственный символ из исходного слова а = а\... ак согласно формуле рорДа) = а/, где I = тах(1, тт(г, к)). Определение 7. Двупараметрическая функция бПсс.,^ : \ {0} -»• \ {0} есть функция, выделяющая набор символов согласно формуле вИсе^а) = сч-.-аз, где I = шах(1,шт(г,])) и 3 = тт(/с, тах(г,.?')). Считается, что запись эНсе* эквивалентна вПсе^. Теорема 2 (Об уравнениях движения одиночного жадного агента). Пусть в каждый момент времени г & N введены обозначения модифицированной матрицы смежности А € Я?*" рабочего пространства, входа иЩ 6 состояния хЩ £ выхода уЩ е цели дЩ <Е радиуса действия сЩ £ начального состояния х[0] € агента и состояния внешней среды вЩ € -Р1™ над частично свободным субтропическим полукольцом Тогда движение одиночного жадного агента в дискретной неограниченно неопределенной динамической полностью наблюдаемой внешней среде описывается динамической системой

хЩ = РоРасмСтМ ® 7М)©»МЬ

уЩ = 81!с4сИ(7М © 7М)©7М*И]> _ х[0] = х0, и[4] = вЩ, Ь е N.

где 7^] 6 - слово, представляющее минимальный в смысле поразрядного порядка путь, 7 - оператор отрицания, Т - оператор транспонирования, Ь

- оператор бинаризации, diag - оператор диагонализации, рор2ф] и зНсе2ф]

- введенные ранее функции с параметром 2ф], п - число вершин в графе рабочего пространства.

Теорема 3 (Об уравнениях движения коллектива жадных агентов). Пусть для каждого г £ N агента в каждый момент времени £6 N введены обозначения модифицированной матрицы смежности А £ рабочего пространства, входа и[г, £] е состояния х[г,£] € выхода у[г, £] € цели д[г,Ц 6 радиуса действия с[г, £] £ начальных состояний х[г, 0] 6 агентов и состояния внешней среды 6\г, £] € над частично свободным субтропическим полукольцом Рп. Тогда движение коллектива жадных агентов в дискретной неограниченно неопределенной динамической полностью наблюдаемой внешней среде описывается динамической системой

г—1 р

«К А = 0 У[а, «] © вЩ © 0 х[з, £-1],

8=1 а=г+1

7[г,£] = хт[г, £-1] (diag й[г, £] Л й[г, ,

х[г, г] = рор^.м (7[г, £] Ф 7[г, ¿])©7[г, ф:{г, £-1], у[г, £] = зПсе^фд] (7[г, £] ф 7[г, £])©7[г, %[г, £-1], ^ а;[г, 0] = х0[г], г 6 ЛГ, Ь € ЛГ,

где 7[г, £] £ Рп - слово, представляющее минимальный в смысле поразрядного порядка путь, 7 - оператор отрицания, Т - оператор транспонирования, Ь

- оператор бинаризации, diag- оператор диагонализации, рор2ф.^ и зИсе2(;[Г)(]

- введенные ранее функции с параметром 2с[г, £], р - число агентов в коллективе, п - число вершин в графе рабочего пространства.

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

Теорема 4 (О классификации уравнений движения).

1. Уравнения динамики жадных одноагентных систем принадлежат к классу уравнений динамики искусственных полукольцевых нейронных сетей Хопфилда в обратном времени;

2. Уравнения динамики коллективов жадных агентов принадлежат к классу уравнений динамики набора согласованных полукольцевых нейронных сетей Хопфилда в обратном времени;

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

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

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

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

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

Алгоритм Greedy Agent, sControl( A, c[r, t],g[r, t],xo[t],0[t}) fori = l,...,Tdo —— for r = 1,... ,p do u[r,t]<^e{t] for s = 1,..., p do if s < r then

u[r,t) <- u[r,t] ®y\s,t] else if s > r then

u[r,t] <- u[r,t} ®i[s,i- 1] end if end for

Preconditioning(diagw[r, t] A diag й[г, t],~f[r,t], g{r, i]) for к = 0,..., n-1 do for i = L,..., n-L do for i = L,..., n-L do

end for end for end for

7[r, t\ <- A*y\r, t) if 7[r, t] ф 0 then

x\r,t] pop2rM(7k,<]) y[r,t] <- зНсегф^тМ]) else

x[r,t] <-x[r,t-1] y[r,t] x[r,t-l\ end if end for

end for______

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

Программный комплекс объединяет в себе библиотеку абстрактной алгебры, подсистему ввода-вывода и подсистему визуализации и вычислений, а также содержит средства для управления сложными робототехническими системами. Структура программного комплекса показана на рис. 1. Предусмот-

Подсистема визуализации и вычислений

Модуль визуализации одноагентных систем Модуль визуализации мультиагентпых систем Модуль матричных вычислений Модуль визуализации графов

Библиотека абстрактной алгебры

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

Подсистема ввода-вывода

Модуль преобразования форматов Модуль связи с программируемым логическим контроллером

Рис. 1. Структура программного комплекса

рена возможность управления декартовым роботом-манипулятором, оснащенным программируемым логическим контроллером Siemens Simantic S7 и соединенным с компьютером через СОМ-порт. Графический интерфейс спроектирован с использованием библиотеки Qt 4.7, взаимодействие программного комплекса с аппаратным обеспечением робота-манипулятора реализуется библиотекой Libnodave 0.8.4.5.

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

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

Рис. 2. Схема системы интеллектуального управления

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

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

Приводятся примеры вычислений состояний и выходов жадных аген-

тов согласно уравнениям динамики, полученных во второй главе, которые соответствуют решению задачи субоптимального управления агентами. Для сокращения занимаемого места в примерах используются оператор бинаризации b и оператор векторизации и. Пусть имеется коллектив изр = 4 жадных агентов, заданы начальные состояния х[1,0] = 5Ь, х[2,0] = 19ь, х[3,0] = 16ь, х[4,0] = Р и цели агентов g[l,0] = 21ь, д[2,0] = д{3,0] = Ю1', #[4,0] = 2АЬ. Состояние природы в{г, í] = (2171221)ь и радиус действия агентов c[r, l\ = 1 полагаются фиксированными для любых г G N и t £ N. Тогда вход, слово, представляющее минимальный в смысле поразрядного порядка путь, состояние и выход первого агента на первой итерации определяются по формулам:

ы[1,1] = 0[1] ф х[1, 0] © х\2, 0] Ф х[3, 0] =

10 0 1 110 0 0 0 0 0 0 0 0 1

0 0 0 0 0

7[1,1] = x[l,0](diagü[l, 1] ^diagü[l, 1])*<?[1, 1] = б^З^З2^2^'^1, х[1,1] = рор>(7[1,1] ф 7[1,1])©7[1,1]х[1, 0] = рор^(7[1,1]) =

"0 0 0 0 о!"

= рор^(51423282132122172221)=

0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

у[ 1,1] = Slic4(7[l, i] Ф 7[1.1])®7[1,1]аг[1,0] = slice* (7[1,1]) =

"о о о о о'

= slice^51423282132122172221) =

0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Разработана и реализована структура программного комплекса управления сложными робототехническими системами, использующая предложенный класс численных методов, для проведения вычислительных экспериментов. Результаты работы использованы в учебном процессе ФГ БОУ «Липецкий государственный технический университет» при подготовке инженеров-математиков по специальности «Прикладная математика».

Основные результаты диссертации опубликованы в следующих

работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Николаев Д.А. Моделирование координированного движения мультиагентных систем методами идемпотентной алгебры // Вести высших учебных заведений Черноземья, №1, 2012. С. 32-36.

2. Николаев Д.А. Динамические системы с двумерным параметром над идемпотентными полукольцами для моделирования движения мультиагентных систем // Системы управления и информационные технологии, №2(48), 2012. С. 22-26.

3. Николаев Д.А. Аналитическое описание дискретной динамики робота-манипулятора в неопределенной внешней среде методами идемпотентной математики // Автоматика и телемеханика, № 11, 2012. С. 114-128.

4. Николаев Д.А. Моделирование и управление движением агента в неопределенной внешней среде методами идемпотентной алгебры // Управление большими системами, № 40, 2012. С. 311-328.

Статьи и материалы конференций

5. Николаев Д.А. Адаптивное управление промышленным роботом на основе методов интервального анализа // Сборник материалов международного форума студенческой и учащейся молодежи «Первый шаг в науку -2010». - Минск: Беларуская навука, 2010. С. 458-460.

6. Николаев Д.А. Применение обобщенного программирования для реализации универсальных алгоритмов идемгютентной математики // Сборник материалов международного форума студенческой и учащейся молодежи «Первый шаг в науку - 2011». - Минск: Беларуская навука, 2011. С. 574-575.

7. Николаев Д.А. Алгебраический подход к моделированию и управлению движением агента в неопределенной внешней среде // Информационные технологии моделирования и управления, № 7(72). - Воронеж: Изд-во «Научная книга», 2011. С. 799-806.

8. Николаев Д.А. Разработка библиотеки обобщенных алгоритмов и концепций идемпотентной математики // Интеллектуальные компьютерные обучающие системы: материалы Международной школы-семинара. - Воронеж: ИПЦ «Научная книга», 2011. С. 164-166.

9. Николаев Д.А. Стационарные полукольцевые нейронные сети Хопфилда и их приложения в робототехнике // Материалы Всероссийской конференции с элементами научной школы для молодежи «Математическое моделирование в технике и технологии». - Воронеж: ИПЦ «Научная книга», 2011. С. 36-38.

10. Николаев Д.А. Гиперграфовая интерпретация решений уравнения Беллмана над идемпотентными ^¡оп-полукольцами // Всероссийская научная школа «Информационно-телекоммуникационные системы и управление». - Воронеж: ИПЦ «Научная книга», 2011. С. 164-167.

11. Николаев Д.А. Применение нестационарных полукольцевых нейронных сетей Хопфилда для траекторного управления промышленными роботами в динамической среде с препятствиями // Сборник статей XI международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности». - СПб: Изд-во Политехи, университета, 2011. С. 93-98.

12. Николаев Д.А. Алгебраическая модель движения агента в неопределенной внешней среде // Сборник статей XII международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности». - СПб: Изд-во Политехи, университета, 2011. С. 126-131.

13. Николаев Д.А. Алгоритм управления промышленными роботами в изменяющейся внешней среде на основе методов интервального и идемпо-тентпого анализа // Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем: Сб. трудов. Вып. 17. - Воронеж: Изд-во «Научная книга», 2012. С. 308-310.

14. Николаев Д.А. Алгебраическая модель движения коллектива агентов в неопределенной внешней среде // Сборник статей XII международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности». - СПб: Изд-во Политехи, университета, 2011. С. 131-138.

15. Николаев Д.А. Динамические системы над идемпотентными полукольцами как модели движения одиночного агента // Управление большими системами: материалы IX Всероссийской школы-конференции молодых ученых. Том 1 / ЛГТУ. - Тамбов-Липецк: Изд-во Першипа Р.В., 2012. С. 66-69.

16. Николаев Д.А. Методы идемпотентной алгебры для моделирования и управления мультиагентными системами // "Управление большими системами: материалы IX Всероссийской школы-конференции молодых ученых. Том 1 / ЛГТУ. - Тамбов-Липецк: Изд-во Першина Р.В., 2012. С. 69-71.

17. Николаев Д.А. Нелинейные динамические системы над идемпотентными полукольцами для моделирования и управления мультиагентными системами // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения» - Воронеж: ИПЦ ВГУ, 2012. - С. 162.

18. Николаев Д.А. О новом классе нелинейных окрестностных динамических систем как моделей движения коллективов интеллектуальных агентов // Современные методы теории функций и смежные проблемы: материалы Воронежской зимней математической школы. - Воронеж: ИПЦ ВГУ, 2013. -С. 162.

19. Nikolayev D.A. Nonlinear dynamical systems over idempotent semirings for modelling of single agent, motion in uncertain environment // G.L. Litvinov, V.P. Maslov, A.G. Kushner, S.N. Sergeev (Eds.) Tropical and idempotent mathematics. - Moscow: 2012. P. 185-192.

20. Nikolayev D.A. Idempotent algebra methods for modelling of hierarchical multiagent systems motion // G.L. Litvinov, V.P. Maslov, A.G. Kushner, S.N. Sergeev (Eds.) Tropical and idempotent mathematics. - Moscow: 2012. - P. 193-197.

21. Николаев Д.А. Программный комплекс «PathFinder» / Николаев Д.А., Федоркова Г.О. М.: ОФАП, 2010. Госрегистрация № 50201000887 от 10.06.2010.

22. Николаев Д.А. Программный комплекс «Моделирование и управление мультиагентными системами методами идемпотентной алгебры» / Николаев Д.А., Блюмип С.Л. М.: ФГБУ ФИПС, 2013. Госрегистрация № 2013618418 от 9.09.2013.

Подписано к печати 25.10.13. Формат60x84 '/16. Бумага офсетная. Гарнитура Гаймс. Печать цифровая. Печ. л. 1,00. Тираж 100 экз. Заказ 5896.

Отпечатано в Отделе операпшюй полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

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

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

Николаев Дмитрий Александрович

04201 452739

МОДЕЛИРОВАНИЕ И УПРАВЛЕНИЕ МУЛЬТИАГЕНТНЫМИ СИСТЕМАМИ МЕТОДАМИ ИДЕМПОТЕНТНОЙ АЛГЕБРЫ

Специальность 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор Блюмин С.Л.

Воронеж - 2013

ОГЛАВЛЕНИЕ

Введение......................................................................................4

Глава 1. Анализ работ по моделированию сложных систем ............11

1.1. Введение................................................................................11

1.2. Место жадных мультиагентных систем в искусственном интеллекте ....................................................................................12

1.3. Основы идемпотентной алгебры..............................................17

1.4. Приложения идемпотентной алгебры......................................24

1.5. Цель работы и задачи исследования........................................31

Глава 2. Моделирование динамики мультиагентных систем методами идемпотентной алгебры............................................................32

2.1. Введение................................................................................32

2.2. Частично свободные субтропические полукольца ....................33

2.3. Построение математических моделей динамики мультиагентных систем............................................................................48

2.4. Исследование математических моделей динамики мультиагентных систем......................................................................55

2.5. Выводы ................................................................................60

Глава 3. Программные комплекс для моделирования и управления

мультиагентными системами ........................................................62

3.1. Введение..............................................................................62

3.2. Описание программы..............................................................63

3.2.1. Общие сведения..................................................................63

3.2.2. Функциональное назначение................................................64

3.2.3. Описание логической структуры..........................................65

3.2.4. Используемые технические средства......................................73

3.2.5. Установка и удаление программы..........................................74

3.2.6. Входные данные................................. 75

3.2.7. Выходные данные................................ 78

3.3. Руководство оператора............................. 78

3.3.1. Назначение программы............................ 78

3.3.2. Условия применения.............................. 79

3.3.3. Выполнение программы............................ 80

3.3.4. Сообщения об ошибках............................ 87

3.4. Выводы ........................................ 88

Глава 4. Управление сложными робототехническими системами методами идемпотентной алгебры .......................... 90

4.1. Введение........................................ 90

4.2. Система управления роботом-манипулятором............. 91

4.3. Система управления коллективом транспортных роботов .... 98

4.4. Выводы ........................................107

Заключение.........................................109

Библиографический список.............................110

ВВЕДЕНИЕ

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

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

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

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

Тематика работы соответствует научному направлению Липецкого государственного технического университета «Алгебраические методы прикладной математики и информатики в моделировании и управлении сложными распределенными системами».

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

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

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

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

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

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

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

ленных методов, для проведения вычислительных экспериментов

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

Тематика работы соответствует п. 3. «Развитие качественных и приближенных аналитических методов исследования математических моделей», п. 4 «Разработка, обоснование и тестирование эффективных численных методов с применением ЭВМ», п. 5 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента» паспорта специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ».

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

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

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

- введен и исследован новый класс математических моделей динамики жадных мультиагентных систем в виде динамических систем над

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

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

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

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

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

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

Компоненты математического и программного обеспечения прошли государственную регистрацию в Отраслевом фонде алгоритмов и программ и ФГБУ «Федеральный институт промышленной собственности».

Реализация и внедрение результатов работы. Математические модели, методы и научно-практические рекомендации диссертационного исследования использованы для создания опытного образца системы управления роботом-манипулятором и проекта системы управления коллективом транспортных роботов на заводе холодильников «Indesit International». Эффект от внедрения заключается в обеспечении необходимой функциональности программных модулей и реализации их информационного обеспечения. Результаты диссертационной работы используются в учебном процессе ФГБОУ «Липецкий государственный технический университет» при подготовке инженеров-математиков по специальности «Прикладная математика».

Апробация работы. Основные результаты работы докладывались и обсуждались на: Международном форуме студенческой и учащейся молодежи «Первый шаг в науку» (Минск, 2010, 2011), Третьей, Четвертой и Пятой традиционных всероссийских молодежных летних школах «Управление, информация и оптимизация» ИПУ им. В.А. Трапезникова РАН (Ярополец, Звенигород, Солнечногорск, 2011, 2012, 2013), Международной школе-семинаре «Интеллектуальные компьютерные обучающие системы» (Воронеж, 2011), Всероссийской конференции с элементами научной школы для молодежи «Математическое моделирование в технике и технологии» (Воронеж, 2011), Всероссийской научной школе «Информационно-телекоммуникационные системы и управление» (Воронеж, 2011), XI и XII международных научно-практических конференциях «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности» (Санкт-Петербург,

2011), XVII Международной открытой научной конференции «Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем» (Воронеж, 2012), Воронежской весенней математической школе «Понтрягинские чтения - XXIII» (Воронеж, 2012), IX Всероссийской школе-конференции молодых ученых «Управление большими системами» (Липецк, 2012), Международной конференции «Tropical and Idempotent Mathematics» (Москва,

2012), Воронежской зимней математической школе «Современные методы теории функций и смежные проблемы» (Воронеж, 2013). Работа была награждена дипломом II степени Областного фестиваля научно-технического творчества молодежи «НТТМ-2011» (Липецк, 2011), дипломом Конкурса научных работ молодых ученых по теории управления и ее приложениям ИПУ им. В.А. Трапезникова РАН (Москва, 2011) и дипломом фонда содействия развитию малых форм предприятий в научно-технической сфере по программе У.М.Н.И.К. (Липецк, 2013).

Связь с научными программами. Исследование проводилось в рамках инициативного научного проекта, поддержанного грантом РФФИ «Разработка математического и программного обеспечения для моделирования, прогнозирования, оптимизации и управления сложными системами на основе методов идемпотентной математики и интервального анализа», проект № 11-07-00580-а.

Публикации. По результатам исследования опубликованы 22 научные работы без соавторов, в том числе 4 - в изданиях, рекомендованных ВАК РФ.

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

Во введении обоснована актуальность исследования, сформиро-

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

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

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

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

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

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

ГЛАВА 1. АНАЛИЗ РАБОТ ПО МОДЕЛИРОВАНИЮ СЛОЖНЫХ

СИСТЕМ

1.1. Введение

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

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

Поэтому целью диссертационного исследования ставится развитие

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