Содержание к диссертации
Введение
1 STRONG Разработка методов поддержки процессов принятия решений в открытых сетевых
организациях STRONG 17
1.1 Анализ процессов управления современными предприятиями 17
1.1.1 Особенности перехода к новому информационному обществу 17
1.1.2 Глобализация экономической деятельности 20
1.1.3 Холистический подход к управлению предприятиями 23
1.1.4 Пример построения холистической структуры предприятия 27
1.2 Мультиагентные технологии как основа для управления предприятиями 30
1.2.1 Краткий обзор мультиагентных систем 30
1.2.2 Общая характеристика интеллектуальных агентов 32
1.3 Сети потребностей и возможностей (ПВ-сети) 35
1.3.1 Понятие ПВ-сети для управления предприятиями 35
1.3.2 Формализованная модель ПВ-сети 40
1.4 Методы взаимодействия агентов в ПВ-сети 44
1.4.1 Метод «скользящего» принятия решений 44
1.4.2 Метод компенсаций 46
1.4.3 Метод виртуального «круглого стола» 49
1.4.4 Метод взаимного обучения агентов 53
1.5 Примеры применения 57
1.5.1 Пример применения метода компенсаций в транспортной логистике 57
1.5.2 Пример применения метода компенсаций для е-коммерции 61
1.5.3 Пример применения метода компенсаций для управления проектами 63
Выводы 65
2 Разработка архитектуры ОМАС для поддержки процессов принятия решений на основе ПВ-сетей 66
2.1 Обзор архитектуры современных MAC 66
2.1.1 Основные направления развития MAC 66
2.1.2 Виртуальные организации 67
2.1.3 «Интеллект роя» как пример виртуальной организации 71
2.1.4 Примеры архитектур MAC 74
2.1.5 Недостатки существующих MAC 80
2.2 Основные компоненты архитектуры ОМАС ППР на основе ПВ-сетей 81
2.3 Методы и средства построения онтологии 83
2.3.1 Определение понятия онтология 83
2.3.2 Критерии построения онтологии 84
2.3.3 Базис для создания онтологии 85
2.3.4 Формализованное представление знаний 86
2.3.5 Интеграция знаний от различных экспертов 88
2.3.6 Языки представления онтологии 90
2.3.7 Программные средства конструирования онтологии 92
2.3.8 Примеры успешных применений 95
2.4 Разработка онтологии для ОМАС ППР 98
2.4.1 Общая характеристика корпоративных знаний 98
2.4.2 Категориальный анализ деятельности предприятия 101
2.4.3 Развитие системы деятельности предприятия 104
2.4.4 Миры деятельности предприятий 108
2.4.5 Мир ПВ-сетей для поддержки принятия решений 110
2.5 Конструкция программных агентов ОМАС ППР 112
2.5.1 Базовые компоненты агентов для работы в ПВ-сетях 112
2.5.2 Конструкция интеллектуальных агентов 113
2.5.3 Конструкция агента как комбинации физических и ментальных тел 115
2.5.4 Многоуровневые агенты 117
Выводы 118
3 STRONG Разработка инструментальной среды для построения ОМАС ППР в сетевых
организациях STRONG 119
3.1 Обзор методов и средств проектирования MAC 119
3.1.1 Общие подходы к проектированию MAC 119
3.1.2 Языки программирования агентов 122
3.1.3 Среды проектирования MAC 130
3.2 Основные компоненты среды для построения ОМАС ППР 132
3.2.1 Общее описание инструментальной среды 132
3.2.2 Особенности реализации исполняющей системы RC Engine 134
3.2.3 Конструктор онтологии для RC Engine 146
3.2.4 Интегратор корпоративных знаний и данных 151
3.2.5 Система извлечения знаний 154
3.2.6 Система понимания текстов 159
3.3 Построение прикладных ОМАС ППР на основе ПВ-сетей 166
3.4 Исследование реализационных характеристик разработанных средств 169
3.5 Перспективы развития подхода: на пути к эмерджентному интеллекту 171
Выводы 173
4 Разработка и применение интегрированной ОМАС ППР управления предприятиями 174
4.1 Общая характеристика системы 174
4.1.1 Краткий обзор традиционных систем управления предприятием 174
4.1.2 Структура и функции системы (первая очередь) 179
4.2 ОМАС ППР для решения задач логистики 182
4.2.1 Базовая ОМАС ППР для моделирования логистики 182
4.2.2 Прикладные ОМАС ППР для АО «АвтоВАЗ» 188
4.3 ОМАС ППР для решения задач электронной коммерции 192
4.3.1 Базовая ОМАС ППР для электронной коммерции 192
4.3.2 Интернет-портал «Оптик-сити» для производителей оптики 194
4.3.3 Продажа бытовой электроники 201
4.3.4 Работа пищевого предприятия 204
4.4 ОМАС ППР для решения задач управления проектами 212
4.4.1 Базовая ОМАС ППР для управления проектами 212
4.4.2 Прикладная система для моделирования рисков по проектам 216
4.4.3 Планирование работ в компании по разработке программ 218
4.5 ОМАС ППР для других приложений 219
Выводы 221
5 Применение ОМАС ППР при разработке проектов систем управления социально-производственными комплексами (СПК) 222
5.1 Структура и функции системы управления СПК.. 222
5.1.1 Задачи реформирования управления СПК 222
5.1.2 Предлагаемый подход к реформированию управления 225
5.1.3 Общая архитектура ОМАС ППР для управления регионом 231
5.2 Интегрированная ОМАС ППР администрации СПК 234
5.2.1 ОМАС ППР «Регламент госслужбы» 234
5.2.2 ОМАС ППР «Гибкое планирование и контроль» 235
5.2.3 ОМАС ППР «Бюджетирование» 236
5.2.4 ОМАС ППР «Развитие персонала» 237
5.3 ОМАС ППР для моделирования процессов адресного взаимодействия населения и органов исполнительной власти СПК 238
5.3.1 Постановка задачи разработки 238
5.3.2 Предлагаемый подход к разработке 240
5.3.3 Описание разработанной системы 243
5.4 ОМАС ППР для управления здравоохранением СПК 251
5.4.1 Назначение системы 251
5.4.2 Предлагаемый подход 252
5.4.3 Структура и функции системы 252
5.4.4 Принципы работы системы 264
5.5 ОМАС ППР для развития социокультурных ресурсов СПК 267
5.5.1 Назначение и применение 267
5.5.2 Общее описание 270
5.5.3 Структура содержания 272
5.5.4 Онтология культуры 272
5.5.5 Функции агентов 276
5.5.6 Другие возможности 281
Выводы 282
Заключение 283
Литература 285
- Общая характеристика интеллектуальных агентов
- Интеграция знаний от различных экспертов
- Особенности реализации исполняющей системы RC Engine
- Прикладные ОМАС ППР для АО «АвтоВАЗ»
Введение к работе
Открытый характер современного информационного общества и глобальной рыночной экономики приводит к ускорению научно-технического прогресса и обострению конкуренции на рынках, что заставляет предприятия искать новые методы и средства организации и управления, направленные на более качественное и эффективное удовлетворение индивидуальных запросов потребителей.
Один из новых подходов к управлению предприятиями связан с построением сетевых организаций (Networking Organizations), подразделения которых могут рассматриваться как автономные предприятия. В отличие от традиционных предприятий, сетевая организация по своему устройству является открытой, поскольку входящие в ее состав предприятия могут напрямую взаимодействовать с другими организациями, которые также могут интегрироваться в ее структуру или, наоборот, выходить из нее в зависимости от ситуации на рынке. Превалирующими процессами в открытых организациях становятся обучение, развитие и адаптация, создающие условия для наиболее эффективного функционирования организации, но и требующие взамен более согласованного, гибкого и оперативного принятия решения, в частности, по обновлению номенклатуры продукции, установлению партнерских связей, внедрению новых технологий и т.д.
Вместе с тем, для таких открытых организаций, отличающихся распределенным сетевым характером, высокой динамикой изменений и априорной неопределенностью условий функционирования, традиционные программные системы по управлению ресурсами предприятий (Enterprise Resource Planning), разработанные такими компаниями, как SAP, BAAN, Navision и другие, оказываются не достаточно эффективными. Ключевой проблемой этих систем становится отсутствие средств своевременной идентификации новых потребностей и возможностей в среде, позволяющих предприятию оперативно принимать эффективные решения по реконфигурации производственных, кадровых, финансовых и других ресурсов.
Типичными примерами событий, вызывающих необходимость заново идентифицировать потребности и возможности, являются: появление нового выгодного заказа, для исполнения которого недостаточно собственных ресурсов предприятия; возникновение на рынке новых ресурсов, обладающих большей эффективностью для предприятия; неожиданный отзьш принятого ранее и запущенного в производство заказа; выход из строя части имеющихся ресурсов; а также изменение критериев принятия решений. Чем выше неопределенность, чем более распределенный характер имеют процессы принятия решения и чем чаще случаются незапланированные события, - тем ниже эффективность существующих систем, не
способных самостоятельно принимать решения и автоматически перестраиваться под изменения в среде. Кроме того, любая модификация схем принятия решений в традиционных системах представляет собой весьма сложный и трудоемкий процесс и требует высокой квалификации исполнителей, что делает разработку и эксплуатацию рассматриваемых систем крайне дорогостоящими.
Для решения этой проблемы рядом компаний (таких как iLog, Valdero и др.) начаты разработки нового класса так называемых SCEM систем (Supply Chain Event Management), призванных обеспечить более оперативную реакцию на незапланированные события в цепочках поставок. Однако и эти системы, оставаясь классическими по своему устройству, не обеспечивают своевременную идентификацию потребностей и возможностей, оказываются не достаточно гибкими и оперативными в работе, являются трудоемкими в настройке и адаптации, и потому дорогостоящими для широкого применения, а также не позволяют реализовать индивидуальный подход к решению задач каждого конкретного пользователя.
Новый подход к решению задачи оперативной обработки информации в процессах принятия решений связывается с применением мультиагентных технологий, получивших интенсивное развитие в последнее десятилетие, на стыке методов искусственного интеллекта, объектно-ориентированного программирования, параллельных вычислений и телекоммуникаций. В основе этой технологии лежит понятие «агента», программного объекта, способного воспринимать ситуацию, принимать решения и коммуницировать с себе подобными. Эти возможности кардинально отличают мультиагентные системы (МАС) от существующих «жестко» организованных систем, обеспечивая им такое принципиально важное свойство как способность к самоорганизации. При этом агенты могут действовать от имени и по поручению лиц, принимающих решения, и на основе данных им полномочий в автоматическом режиме вести переговоры, находить варианты решений и согласовывать свои решения друг с другом.
Различные классы агентов и методы их взаимодействия рассматривались в работах Д.Кеннеди и Р.Эберхарта, Р.Марча и Т.Джонса, Д.Фербера, В.Бреннера, Н. Гуарино, В.Хорошевского, В.Городецкого, В.Тарасова и ряда других авторов. Вместе с тем, в этих работах методам коллективного и согласованного взаимодействия агентов в открытых системах уделялось недостаточно внимания, а существующие применения охватывали сферы е-коммерции, информационного поиска и некоторые другие.
В настоящей работе в качестве методической основы для создания открытых мультиагентных систем оперативной обработки информации для поддержки процессов
принятия решений (ОМАС ППР) предлагается модель сети потребностей и возможностей (ПВ-сеть). Эта модель базируется на холистическом подходе, в рамках которого предприятие декомпозируется до уровня сети отдельных автономных «физических сущностей» (станки, транспортные средства, детали, материалы и т.д.), каждая из которых получает своих агентов потребностей и возможностей. Указанные агенты, функционирующие как отдельные автономные компании (с собственным расчетным счетом) на виртуальном рынке предприятия, способны взаимодействовать между собой, идентифицируя нужные потребности и возможности и устанавливая временные связи (отношения), обеспечивающие бронирование ресурсов под поступающие заказы. При этом агенты возможностей стремятся найти для себя наилучшее применение, а агенты потребностей - максимально удовлетворить своим требованиям в пределах заданных ограничений. В результате две эти сущности ведут себя как две противоположности, временно связывающиеся в относительно устойчивые комбинации (например, представляющие собой расписания перевозок в логистике, структуру кластеров при обработке данных и т.д.), или распадающиеся на свои составные части, рекомбинирующие с другими компонентами на более выгодных для них условиях. В такой открытой системе агенты потребностей и возможностей должны быть постоянно в готовности к установлению или расторжению связей и реагировать на любые изменения в среде, а текущая конфигурация ПВ-сети, задаваемая набором связей между ними, отражает лишь временный баланс интересов участников этого взаимодействия.
На основе такого подхода агенты потребностей и возможностей ресурсов транспортных средств в логистике могут договориться о том, какой маршрут выбрать для перевозки того или иного конкретного груза и какое расписание могло бы устроить как заказчика, так и перевозчика. Агенты ресурсов товаров и экранных форм в е-коммерции могут договориться о том, какие товары предлагать конкретному покупателю, пришедшему на сайт, с учетом интересов других товаров. Агенты ресурсов исполнителей при появлении нового проекта договорятся о распределении работ с учетом знаний и опыта, а также предпочтений каждого из разработчиков и т.д.
Вместе с тем, одной из наиболее сложных задач разработки ОМАС ППР становится задача построения моделей переговоров агентов, на основе которых строится согласованное принятие решений. Наиболее известными примерами моделей переговоров являются аукционные схемы (прямые и обратные), договорные сети Смита-Сандхольма, метод монотонных минимальных уступок по Розеншайну и Злоткину и некоторые другие. В более сложных моделях коллективного взаимодействия агентов, представленных, например, в работах М.Тамбе, Шехори и Крауса, решаются задачи формирования коалиций и
распределения задач между партнерами по коалиции, в работах П.Коэна, П.Стоуна и М.Велозо, Д.Киннея и других авторов - задачи планирования и координации работ в группе и т.д. Эти модели существенно развивают возможности взаимодействия агентов в MAC, однако они ориентированы на решение поставленных задач в условиях определенности, когда состав участников взаимодействия фиксирован и не требуется пересмотра принятых ранее решений при появлении новых возможностей или потребностей, что является характерным для рассматриваемых открытых систем.
В этой связи в настоящей работе предлагаются новые методы взаимодействия агентов, позволяющие динамически создавать ПВ-сети и реконфигурировать их под действием изменений в среде. Главной особенностью этих методов является возможность построения состояний ПВ-сети как состояний временного равновесия, отражающего баланс интересов всех участников взаимодействия, и согласованного пересмотра принятых ранее решений по мере поступления (или отзыва) заказов или возникновения (исчезновения) ресурсов в среде. Так, в задачах логистики приходящий новый заказ может изменить схему распределения ресурсов и выполнения принятых ранее заказов и даже привести к обращению к одному из заказчиков с предложением продлить срок исполнения его заказа в обмен на дополнительную скидку; в задачах управления проектами потеря одного из исполнителей не вызовет отказа от проекта, а приведет лишь к перераспределению задач между ресурсами исполнителей и т.д.
При этом в ряде случаях для принятия решений в рассматриваемых системах могут использоваться и классические методы, например, если ситуация является хорошо определенной, имеется адекватная математическая модель рассматриваемых процессов и у системы достаточно времени на получение строгого решения.
В то же время в ходе исследований было выяснено, что предлагаемые подходы к построению ПВ-сетей и разработанные методы взаимодействия агентов возможностей и потребностей применимы не только к миру «физических вещей», но и миру «абстрактных сущностей» - например, системам извлечения знаний, где может решаться задача перераспределения записей между кластерами по мере поступления новых записей, или системам понимания текста, где вновь пришедшее предложение может полностью изменить распределение смыслов слов во всех предыдущих предложениях.
Все это позволяет сделать вывод о том, что разработанный подход к созданию ОМАС ППР развивает новую теорию сложных социо-технических систем, постепенно складывающуюся на основе фундаментальных работ К.Николиса и И.Пригожина в области диссипативных структур в физике, М.Минского - в области психологии интеллекта и
А.Кестлера - в области биологических систем. Большой вклад в формирование этой новой теории внесли работы Международного Института Санта Фе (США), объединяющего исследователей из разных стран, работы Т. Саати и К. Кернса по принятию решений в условиях неопределенности, Г.Кёперса по самоорганизации в сложных социо-технических системах, Г.А. Ржевского по сложным адаптивным системам, работающим на границе хаоса, В.А.Виттиха по принципам построения холистических систем и ряда других отечественных и зарубежных ученых. Важнейшим результатом этой теории является осознание необходимости построения сложных систем с использованием моделей живых организмов, обладающих способностью к самоорганизации и эволюции.
Наконец, нельзя не отметить, что рассматриваемый подход оказывается весьма перспективным для построения систем так называемого «эмерджентного интеллекта» (по М. Минскому), возникающего спонтанно и самопроизвольно из динамического взаимодействия более простых элементов - как возникает «коллективный интеллект» роя пчел или колонии муравьев из поведения отдельных особей.
В результате, предлагаемый подход открывает возможности для построения широкого класса качественно новых систем, обладающих способностью к самоорганизации, универсальностью для различных применений, технологичностью построения, оперативностью, гибкостью и эффективностью, повышенной живучестью, а также индивидуальным подходом к каждому пользователю. Эти системы могут быть использованы как в различных задачах управления предприятиями, так и для проектирования сложных технических объектов, проведения научных исследований и обучения, реализации социальных программ и во многих других областях, требующих коллективного взаимодействия специалистов и согласованного принятия решений.
Таким образом, следует признать актуальной задачу разработки открытых MAC оперативной обработки информации в процессах принятия решений.
Исследования выполнялись в соответствии с основными заданиями комплексных программ фундаментальных исследований проблем машиностроения, механики и процессов управления РАН 1996-2000 гг. (п. 3.1.2) и 2000-2003 гг. (раздел III «Управление и автоматизация», тема «Разработка основ теории управления сложными открытыми системами с применением компьютерного представления и обработки знаний», гос. per. № 01200110152), программы фундаментальных исследований РАН «Повышение надежности систем "машина-человек-среда"» 1988-1995 гг., а также в процессе выполнения совместной Программы Института проблем управления сложными системами РАН и АО «АВТОВАЗ»
по созданию системы интеграции знаний для согласованной инженерной деятельности при проектировании и производстве автомобилей в 1995-2000 гг.
Предмет исследования составляют процессы обработки информации, связанные с поддержкой принятия решений в открытых системах.
Цель исследования состоит в разработке теоретических основ и инструментальных программных средств для построения открытых MAC оперативной обработки информации в процессах принятия решений (ОМАС ППР).
Принятый подход к достижению поставленных целей требует решения следующих задач:
• разработки принципов построения ОМАС ППР, обеспечивающих оперативную идентификацию потребностей и возможностей при принятии решений;
• разработки формализованных моделей ПВ-сетей и методов взаимодействия агентов в этих сетях, позволяющих создавать и реконфигурировать ПВ-сети под действием изменений в среде;
• разработки базовой архитектуры ОМАС ППР для построения ПВ-сетей;
• создания инструментальных средств для реализации ОМАС ППР, обеспечивающих построение ПВ-сетей в различных предметных областях;
• исследования характеристик разработанных методов и средств взаимодействия агентов;
• создания на основе разработанных средств базовых подсистем для управления предприятиями как открытыми социо-техническими системами;
• применения разработанных методов и средств для решения практических задач управления сложными системами.
Методы исследования базировались на использовании системного анализа, алгебры и логики, методов искусственного интеллекта, теории графов, методов параллельных вычислений, теории формальных грамматик и языков, методов имитационного моделирования.
Научная новизна
1. Предложены принципы построения открытых мультиагентных систем, обеспечивающих оперативную обработку информации в процессах принятия решений в условиях неопределенности, распределенного взаимодействия и высокой динамики изменений в среде.
2. Введено понятие и разработана формализованная модель ПВ-сети, применяемой для идентификации потребностей и возможностей в открытой системе и обеспечивающей оперативную, гибкую и эффективную реконфигурацию ресурсов системы.
3. Предложены методы взаимодействия агентов ПВ-сети в открытых системах, позволяющие обеспечить поддержку процессов согласованного принятия решений по реорганизации ресурсов при возникновении непредусмотренных событий внутри системы или во внешней среде.
4. Разработана архитектура открытой мультиагентной системы, реализующей предлагаемые методы взаимодействия агентов ПВ-сети и включающей виртуальную машину для исполнения параллельных процессов, подсистему сообщений, матчинговый процессор, машину принятия решений, потоковый вычислитель, а также интерфейсную компоненту.
5. Разработаны инструментальные средства для построения открытых мультиагентных систем для реализации ПВ-сетей в различных приложениях, включающие средства для конструирования и использования онтологии, а также создания расширений исполняющей системы.
6. Исследованы характеристики разработанных методов и средств, показывающие возможности оперативной обработки информации при принятии решений в различных применениях.
Практическая ценность
Для создания ОМАС ППР, базирующихся на концепции ПВ-сетей и предложенных методах взаимодействия агентов, разработаны инструментальные средства, обеспечивающие построение рассматриваемых систем в двух наиболее распространенных средах объектно-ориентированного программирования Object Pascal и C++. Важной особенностью рассматриваемых систем является наличие развитых средств конструирования онтологии предметной области, позволяющих отделить предметные знания от программного кода системы и обеспечить агентам возможность применять эти знания в процессе принятия решений.
Разработанная инструментальная среда MagentA Engine RC, реализованная на базе языка Object Pascal и имеющая развитый графический интерфейс, ориентирована на моделирование процессов принятия решений и применение в локальных сетях предприятий. Эта система обеспечивает возможность построения до 500 тысяч простых агентов на персональном компьютере стандартной конфигурации, способных взаимодействовать со скоростью 40 тысяч сообщений в секунду. Инструментальная среда MagentA Engine SB,
реализованная на языке C++, ориентирована на создание Интернет-приложении, предназначенных для поддержки процессов коллективного принятия решений в реальном времени. Исполняющая часть этой подсистемы является мультипользовательской и способна обрабатывать до 10 одновременных запросов в секунду.
Разработанные инструментальные среды помимо исполняющей подсистемы включают средства для построения онтологии, а также могут быть дополнены средствами для извлечения знаний, поддержки диалога с пользователем на естественном языке и интеграции корпоративных знаний. Разработанные системы обеспечивают возможности управления приложениями, защиты информации, интеграции с другими пакетами, включая СОМ-интерфейс, поддержку XML и т.д.
На основе созданных инструментальных систем была разработана интегрированная открытая мультиагентная система для поддержки процессов принятия решений при управлении предприятиями, основные виды деятельности которых реализуются в сети Интернет (ИОМАС ППР «е-Предприятие»). Эта система включает модули управления продажами (модуль «е-Коммерция»), управления логистикой (модуль «е-Логистика»), управления проектами («е-Проекты») и т.п.
Разработанные средства нашли применение при создании логистической сети и моделировании процессов принятия решений в воздушной доставке крупнотоннажных грузов, в морской транспортировке сырой нефти и контейнерных перевозках, при моделировании процессов производства, хранения, транспортировки и сборки частей автомобилей, оперативном планировании экспериментального производства автомобилей, при продаже товаров через Интернет, включая продажу бытовой электроники, продуктов питания и авиабилетов, в формировании меню для предприятий пищевой промышленности, при составлении железнодорожных расписаний, оперативной обработке данных о продаже товаров, дистанционном обучении и т.д.
Проведенные разработки показали высокую гибкость и оперативность рассматриваемых систем, а также возможность индивидуального подхода в работе с каждым пользователем. Наличие инструментария и технологичность построения разрабатываемых систем позволили существенно сократить сроки создания новых приложений, а также затраты по их разработке, поддержке и развитию. Ряд приложений показал также высокую надежность и живучесть разрабатываемых систем, способных продолжать работу в условиях потери или выхода из строя части ресурсов.
Кроме того, разработанные методы и средства нашли применение при разработке проекта первой очереди интегрированной системы управления регионом, призванной
обеспечить оперативную поддержку процессов открытого, адресного и эффективного взаимодействия населения и органов исполнительной власти Самарской области, который стал одним из победителей во Всероссийском конкурсе Федеральной целевой программы «Электронная Россия» в 2002 году.
Результаты диссертации использовались в Дирекции технического развития АО «АвтоВАЗ» для моделирования процессов принятия решений в задачах логистики и оперативного планирования производства экспериментальных образцов автомобилей; в научно-производственной компании (НПК) «Маджента Девелопмент» при разработке инструментальных средств MagentA Engine и основных модулей ОМАС ППР «е-Предприятие», а также их применения для решения задач воздушной, морской и железнодорожной логистики, электронной коммерции и управления проектами, извлечения знаний и понимания текстов; в НПК «Генезис знаний» для разработки первой очереди интегрированной системы управления Самарской областью; в Самарском филиале Физического института РАН для создания Интернет-портала «Оптик-сити» и системы дистанционного обучения «Дифракция», в Департаменте социальной защиты Администрации Самарской области для разработки социального паспорта жителя Самарской области и моделирования процессов адресного взаимодействия населения и органов исполнительной власти, в Департаменте культуры - для создания Интернет-портала развития социокультурных ресурсов региона.
По результатам разработок подготовлен учебный курс «Мультиагентные системы», включающий цикл методических пособий и лабораторных работ, внедренный в учебный процесс в Самарском государственном аэрокосмическом университете и Поволжской государственной академии информатики и телекоммуникаций.
Основные положения, выносимые на защиту
1. Для поддержки принятия решений в открытых системах целесообразно применение мультиагентных технологий, позволяющих программным агентам воспринимать изменения ситуации, принимать решения и коммуницировать друг с другом для согласования этих решений.
2. Открытые мультиагентные системы для оперативной обработки информации в процессе принятия решений следует создавать на основе ПВ-сетей, обеспечивающих непрерывную идентификацию потребностей и возможностей в среде.
3. Для динамической реконфигурации ПВ-сетей в открытых системах следует применять разработанные методы взаимодействия агентов, включая метод скользящего
принятия решений, метод компенсаций, метод виртуального «круглого стола» и метод взаимного обучения агентов.
4. Для промышленного применения разработанных методов и средств необходима разработка инструментальных средств, позволяющих автоматизировать процесс разработки и сократить трудоемкость, сроки создания и стоимость разработки и эксплуатации прикладных систем.
5. Разработанные методы и средства обеспечивают высокую эффективность в решении задач оперативной обработки информации в процессах принятия решений в открытых системах, отличающихся условиями неопределенности, распределенным характером взаимодействия и высокой динамикой изменений в среде.
Апробация работы
Основные результаты работы докладывались и обсуждались на международных и национальных конференциях и семинарах, в том числе: на XIII Международной конференции по применению искусственного интеллекта в технике (Ирландия, Гэлвей, 1998), VI и VII Национальных конференциях по искусственному интеллекту (Пущино, 1998 и Переславль-Залесский, 2000), VI Международном семинаре по распределенной обработке информации (Новосибирск, 1998), XVI Всемирном конгрессе IMACS по прикладной математике и моделированию (Швейцария, Лозанна, 2000), 1-4-ой Международных конференциях по проблемам управления и моделирования сложных систем (Самара, 1999 -2002), 3-м Международном семинаре по новым информационным технологиям (Уфа, 2001), Международном семинаре «Новые модели бизнеса: Организационные аспекты и современные технологии» (Санкт-Петербург, 2001), Международном конгрессе «Искусственный интеллект - 2001» (пос. Дивноморское, 2001), Международной конференции «Интеллектуальные многомашинные системы» (Таганрог, 2001), 6-ой Международной конференции по систематике, кибернетике и информатике (США, Орландо, 2002), Международной конференции по развитию инфраструктуры электронного бизнеса, науки, образования и медицины в Интернет (Италия, Аквила, 2002).
Публикации. Основные положения диссертации изложены в 40 печатных работах.
Структура и объем работы. Диссертация состоит из введения, пяти разделов, заключения, девяти приложений. Общий объем работы 284 страниц, включая 120 рисунков и 8 таблиц, объем приложений 115 страниц, список использованных источников из 160 наименований, всего 419 страниц сквозной нумерации.
Раздел 1 посвящен анализу и формализации процессов управления в сетевых предприятиях и разработке принципов построения ПВ-сетей на основе мультиагентных
технологии, а также методов взаимодействия агентов для поддержки процессов согласованного принятия решений.
Раздел 2 содержит описание предлагаемой архитектуры ОМАС ППР для построения ПВ-сетей и реализации рассмотренных методов взаимодействия агентов. Рассматриваются особенности представления знаний и конструкции агентов для организации взаимодействия в ПВ-сетях, связанные с матчингом потребностей и возможностей, поддержкой принятия решений об установлении и разрыве связей, использованием онтологии и организации потоковых вычислений.
В Разделе 3 дается описание инструментальной среды для построения ОМАС ППР и сравниваются характеристики исполняющих систем, реализованных в среде Object Pascal и C++. Рассматриваются основные принципы реализации систем и проводится исследование реализационных характеристик разработанных методов и средств на примерах из логистики.
В Разделе 4 излагаются принципы построения, основные модули и приложения ИОМАС ППР «е-Предприятие», разработанной с использованием предлагаемых методов и средств.
Раздел 5 посвящен разработке проектов систем управления сложными социально-производственными комплексами.
В приложения вынесены вспомогательные материалы, описания разработанных инструментальных и прикладных систем, а также акты об использовании результатов исследований.
Общая характеристика интеллектуальных агентов
Холистический подход приводит к появлению предприятий, которые оказываются построены как сеть других более простых предприятий, действующих автономно и независимо как на внутреннем рынке породившей «материнской» компании, так и во внешней по отношению к исходному предприятию среде. Продолжая этот процесс можно «расщепить» предприятие до уровня отдельных независимых ресурсов (человек, компьютер, готовая деталь и т.д.), каждый из которых сам по себе может быть некоторой автономной бизнес-единицей (холоном). В таком подходе /20/ не только группы людей или даже один человек, но и неживые физические или даже абстрактные объекты знаний могут являться независимыми "компаниями" (например, компьютер за каждый час времени может получать условную арендную плату, которая может идти на ремонт его частей, осуществление профилактики и т.д.).
Такое предприятие (здесь мы будем в основном рассматривать предприятия, работающие над проектами - так называемые «project-based companies") может рассматриваться как набор некоторых ресурсов (рисунок 1.3). Ресурсы призваны перерабатывать разного рода заказы, формируемые как составные части проектов. Заказы и ресурсы при реализации проекта могут быть динамически связаны между собой, образуя в каждый момент времени некоторую внутреннюю сеть предприятия, например, ресурс некоторого исполнителя для реализации некоторого заказа может быть временно связан с ресурсом оборудования, ресурсом помещения, ресурсом времени, ресурсом знаний и т.д.
Возникновение непредусмотренных изменений во внешней среде (появление нового большого проекта или наоборот, останов уже начатого проекта, появление нового исполнителя или более производительного пакета программ, поломка компьютера, пересмотр целей или критериев работы предприятия и т.д.), должно немедленно вызывать цепочки пересмотра принятых ранее решений по распределению ресурсов предприятия по принятым ранее заказам и наоборот, а также возможно привлечению новых ресурсов или выведению из работы некоторых других неэффективных ресурсов.
Все заказы и ресурсы предприятия взаимодействуют, вступая в связи между собой, на основе своих возможностей и потребностей. В этом контексте можно считать, что каждый ресурс или заказ раздваивается на две противоположности (рисунок 1.4): возможности и потребности. Например, определенный исполнитель может иметь возможность, например, писать программы на языке C++ в заданные сроки, но при этом имеет потребность в компьютере. Если же заказ слишком сложен, у него появится «потребность» найти для себя со-исполнителей, способных выполнять данную работу, с соответствующими знаниями и умениями, причем они должны быть свободны в заданный момент времени, быть согласными на оплату не выше заданной и т.д.
В результате «характеры» заказов и ресурсов также оказываются прямо противоположными: ресурсы более консервативны и должны стремиться быть максимально использованными и просуществовать как можно больший срок (для чего необходимо осуществлять специальный регламент, такой как отдых для человека или профилактика для компьютера), а заказы, наоборот, более активные и стремятся как можно быстрее реализоваться с наилучшими характеристиками, в частности, как можно меньше использовать ресурсы, чтобы меньше потратить денег на расчеты с ними. Возможности Потребности Рисунок 1.3 - Возможности и потребности ресурса Таким образом, заказы и ресурсы, возможности и потребности становятся новыми базовыми элементами устройства предприятия, состоящими в диалектических отношениях между собой. Единство и борьба этих противоположностей реализуется через постоянный поиск соответствия между ними (далее - «матчинг» потребностей и возможностей), обусловленный заданными индивидуальными критериями для каждой из сторон (качество, деньги, время и т.д.). Как следствие, два ресурса могут бороться между собой и конкурировать за один заказ или, наоборот, кооперироваться, когда работа не по силам каждому из них в одиночку. Если же заказ «нашел» свой ресурс и ресурс также «нашел» свой заказ (т.е. обе стороны согласны на сотрудничество) - устанавливается связь и образуется относительно устойчивая «пара», выражающая временное «единство» рассмотренных противоположностей, которые, заметим, на следующем шаге могут легко и «расстаться». В результате рассмотренные элементы оказываются подобными известным частицам «инь и янь» (как монадам Лейбница) - как две постоянно противодействующие сущности, находящиеся в единстве и борьбе противоположностей.
В результате в работе такого предприятия важнейшим процессом становится процесс принятия и пересмотра решений о распределении ресурсов (возможностей по потребностям), в основе которого лежит указанная выше операция «матчинга» - поиска взаимного соответствия между возможностями и потребностями (рисунок 1.5). Суть этой операции для каждой из сущностей состоит в том, чтобы обнаружить все имеющиеся на внутреннем рынке предприятия альтернативные возможности или потребности и принять решение об установлении связи, которая отвечает улучшению заданного критерия или набора критериев, при условии, что и противоположный партнер (ресурс или заказ) согласен на установление такой связи. В результате установления связи противоположности временно перестают конкурировать и приходят в «единство» - до тех пор заказ не будет выполнен и не появится новая материальная сущность (ресурс) со своими возможностями и потребностями. Однако если в ходе работы по проекту выясняется необходимость и возможность поменять исполнителя или компьютер - потребности и возможности должны договориться о разрыве одних и установлении других связей.
Интеграция знаний от различных экспертов
При интеграции знаний от различных экспертов в рамках единой онтологии возникает новая проблема, связанная с индивидуальной природой знаний у экспертов и неравномерностью распределения знания между группой географически удаленных экспертов. В /67/ для решения этой проблемы предлагается использовать технику репертуарных решеток Дж. Келли в рамках теории персональных конструктов. В рамках этой теории считается, что в основе нашего знания о мире лежат базовые категории, которые всегда помогают нам упрощать его восприятие, укладывать знания в определенную, понятную нам систему. Отдельные категории, как прутья, складываются в индивидуальные, групповые и профессиональные структуры (которые могут иметь разные названия -иерархии категорий и ценностей, когнитивные модели, и т.п.), всегда имеющие утилитарные значения, которые и позволяют их называть решетками. Метафора решетки очень удобна, т.к. она позволяет говорить об отдельных элементах, из которых состоит решетка. Описать модель - значит выявить ту решетку, на которой «приготавливается продукт». Использование техники персональных конструктов позволяет расширить границы когнитивного пространства, в рамках которого живут и эксперт, продуцирующий знания, и рядовой пользователь это знания.
Интеграция знаний призвана помогать в организации и координации работы в современных «распределенных» компаниях. В таких случаях при создании онтологии ориентируются в первую очередь не на структуру объектов предметной области, а на структуру производственных и бизнес-процессов.
Для описания процессов и координации выполнения производственных операций все чаще используется методология WorkFlow (в буквальном переводе - поток работ) /68/. В основе методологии WorkFlow лежат следующие понятия: объект - информационный, материальный или финансовый объект, используемый в бизнес-процессе; событие -внешнее действие, произошедшее с объектом; операция - элементарное действие, выполняемое в рамках рассматриваемого бизнес-процесса; исполнитель. В рамках этой модели процесс состоит из операций и других процессов. Операция адресуется исполнителям, которые, в свою очередь, отвечают за выполнение одной или нескольких операций бизнес-процесса. Объекты участвуют в выполнении операции. События могут влиять на выполнение операций, например, изменяя результат операций или последовательность их выполнения. Операции обрабатывают события, являясь реакцией системы на внешние действия. Жизненный цикл объекта связан с внешними событиями и операциями, выполняемыми в составе процесса.
Заметим, что для описания такого рода онтологии могут быть использованы и классические сети Петри и алгебры процессов /69/. Сети Петри - это класс формализмов, основанных на представлении системы сетями с вершинами двух видов: позициями для представления локальных состояний системы и переходами, соответствующими атомарным действиям. Алгебры процессов - это также класс формализмов для описания и анализа параллельных систем, при этом процесс описывается с помощью алгебраического выражения над атомарными действиями.
Однако, несмотря на многочисленные теоретические исследования в области формализованного представления знаний, продукций, семантических сетей и фреймов, до сих пор на практике не сложился унифицированный стандарт и готовые для применения библиотеки онтологии, которые бы могли значительно помочь в создании прикладных систем примерно так же как стандартные библиотеки математических функций.
Особенности реализации исполняющей системы RC Engine
Исполняющая система включает в себя подсистему параллельного исполнения агентов, Подсистему коммуникаций агентов, подсистему поддержки онтологии, подсистему формирования интерфейса, сервисную подсистему.
Рассмотрим более подробно две основные подсистемы: подсистему параллельного Исполнения агентов и подсистему коммуникации агентов.
Подсистема параллельного исполнения агентов по своей сути представляет собой Диспетчер процессов, связанных с каждым агентом в сцене (рисунок 3.6).
Рисунок 3.6 - Внутреннее представление сцены мира При этом каждому процессу сцены в данной подсистеме последовательно выделяется некоторый квант времени для исполнения. Длительность этого кванта переменная и зависит от того, где находится в программе агента пользователя следующий системный вызов, т.е. от вызова - до вызова любой функции подсистемы. Пользователь может также принудительно разбить свою программу на блоки (размещая там специальные вызовы), которые будут обеспечивать прерывание работы программы и передачу управления на другие параллельные процессы. Процесс может и явно передавать управление другими процессам, что гарантирует агентам возможность взаимодействия как по прерыванию, так и по времени.
Все процессы внутри одного агента в целом работают параллельно и синхронизируются передачей сообщений. При этом в каждый момент времени у одного агента исполняется только один процесс (иначе его общий атрибут одновременно мог бы быть изменен несколькими процессами). Все получаемые на агента сообщения передаются процессам агента. Разделение сообщений между процессами происходит по типу сообщений, явно указываемом в фильтре в каждом процессе. При этом сообщения играют роль важных событий, запускающих процессы. Порядок же исполнения процессов внутри одного агента определяется приоритетами процессов: процессы с более низкими приоритетами никогда не исполняются, пока активен процесс с более высоким приоритетом. Если существуют несколько процессов с одинаковыми приоритетами, то они исполняются по очереди.
В расчете на последующее реальное многомашинное взаимодействие разработанный диспетчер создан не централизованным, а полностью распределенным. Фактически, для каждого агента создается своя копия полнофункционального диспетчера, который занимается его процессами. В результате диспетчеры образуют дерево процессов, в котором имеются "корень", "узлы" и "листья". Здесь "листья" сопоставляются с процессами, т.к. процесс не может содержать в себе другие процессы, "узлы" сопоставляются с агентами, а агент мира сопоставляется с "корнем" дерева, привязываемым к операционной системе (что собственно и отличает агента мира от других агентов).
В настоящий момент в MA DAE поддерживается три типа «листьев» (процессов): основанные на системном объекте fiber, основанные на раздельных процедурах обработки и основанные на интерпретаторе языка Pascal. Очевидно, что каждый из описанных типов процессов достаточно специфичен и создает для себя свой тип "листа", обеспечивая возможность согласованной работы столь различных компонент. В результате, процессы могут быть построены как компилированные процедуры, дающие наибольшую скорость работы, так и интерпретируемый набор инструкций.
"Корень" дерева процессов является точкой сопряжения с механизмами диспетчерезации ОС и с системой управления, через которую пользователь контролирует исполнение (запуск, останов, пошаговая работа и пр.). Именно от этого "корня" начинается работа системы исполнения и каждого агента/процесса. В случае ОС Windows в корне находится пул нитей Windows и система балансировки нагрузки на нити.
Важной особенностью подсистемы является то, что "дерево", за исключением своего "корня" и некоторых типов "листьев" (fiber-based процессы), является независимым от структуры ОС. Поэтому процесс портирования под другие ОС (в случае наличия соответствующего компилятора) состоит из замены "корня" и переработки или удаления ОС-специфичных "листьев".
Подсистема коммуникации агентов обеспечивает возможность идентификации агентов и обмена сообщениями в ситуациях, присущих открытым системам. Рассмотрение этой системы начнем с вопроса взаимной идентификации агентов. Дело в том, что чуть выше была рассмотрена система исполнения, главной задачей которой ставилось независимость работы одного агента от другого. Но применение такого подхода заставляет спросить, а как же быть с взаимодействием агентов? Например, агент А1 получил от А2 сообщение, запомнил идентификатор (ссылку) на А2, но в этот момент А2 был уничтожен, и любое обращение А1 по имеющейся у него ссылке на А2 будет некорректным.
Среди способов, используемых для решения подобной проблемы, наиболее часто встречаются следующие два: а) отложенное уничтожение А1, т.е. А1 будет уничтожен только, когда на него будут уничтожены все ссылки и б) сквозная нумерация агентов и использование для ссылок идентификаторов. При этом первый способ не соответствует принципам работы агента, т.к. агент перестает контролировать одну из собственных функций - уничтожение. Второй же весьма неудобен для конечного разработчика и в зависимости от способа реализации может заметно снижать производительность при увеличении количества агентов.
Для решения этой проблемы был выбран подход, применяемый в распределенных системах, который состоит в том, что на самого агента не может быть прямых ссылок, для этого существует специальный объект-связь AgentNexus, который в себе несет ссылку на агента. Ссылки на AgentNexus выполнены на основе СОМ интерфейса IAgentNexus, таким образом в каждый момент времени известно, используется ли этот объект кем-то еще. AgentNexus агрегируется агентом (т.е. возвращает IUnknown агента). При этом, все интерфейсы, принадлежащие самому агенту являются блокирующими уничтожение, но их использование строго ограничено. В случае уничтожения агента, объект AgentNexus не уничтожается, если на него существуют ссылки, но перестает быть агрегированным, т.е. самостоятельно обслуживает IUnknown.
Дополнительная польза такого подхода состоит в том, что через интерфейсы не доступен реализующий их агент, т.о. в принудительном порядке поддерживается правило о том, что сообщения являются единственным способом взаимодействия агентов, и именно интерфейс IAgentNexus является адресом агента или системы сообщений. Кроме того, если взаимодействие с агентом всегда происходит через посредника AgentNexus, то для другого агента безразлично, где реально находится собеседник, таким образом, подобная организация ссылок без существенных затрат позволяет сделать распределенную мультиагентную систему.
В первой версии инструмента подсистема коммуникаций обеспечивает взаимодействие агентов только посредством передачи сообщений (в последующем будет создана система органов чувств агентов). В сообщениях, как было отмечено выше, идентификаторами агентов выступают объекты связи агентов, а не сами агенты. На основе этого достигается не только корректная обработки доставки сообщений уже "умершим" агентам, но так же и взаимодействие агентов на разных машинах. Если агент существует на одной машине, но взаимодействует с агентами на других машинах, то там создаются его объекты-связки, с информацией, о том, куда же в действительности пересылать ответные сообщения.
Прикладные ОМАС ППР для АО «АвтоВАЗ»
В этом разделе рассматривается применение разработанных методов и средств для моделирования процессов принятия решений в логистике опытно-экспериментального (ОЭП) производства АО «АвтоВАЗ» /146/.
Фрагмент онтологии этой системы представлен на рисунке 4.2.
При этом автомобили, их узлы и образующие их детали, а также транспортные средства, складские мощности, производственные станки и материалы получают агентов ПВ-сети, которые отслеживают график производства и помогают специалистам принимать решения по сборке готовых экспериментальных образцов автомобилей точно в срок. В такой системе поломка станка или пропажа детали не вызывают останова производства, а лишь инициируют новые переговоры между агентами и пересогласование их планов методом компенсаций, позволяя решить проблему без нарушения ритма производства и больших издержек.
На рисунке 4.3 приведен экран исполняющей системы, отражающий пример работы макета-прототипа ОМАС ППР логистики при перепланировании производства. В нижней части этого экрана представлен протокол переговоров, которые ведут между собой агенты заказов на производство прототипов, агенты деталей, склада, производственной линии при решении задач оперативного изменения планов производства.
Рисунок 4.3 - Экран исполняющей системы для моделирования логистики производства
Еще один пример, подробно рассматриваемый в работе /146/, связан с решением задачи разработки системы для формирования годового плана опытно-экспериментального производства АО «АвтоВАЗ», призванной функционировать в реальном времени в сети Интернет. В этой системе каждый специалисты может иметь своего агента для согласования принимаемых решений за постоянно действующим виртуальным «круглым столом», инициируемом при возникновении срочных работ (например, сборки автомобиля для поставки на выставку), что позволяет принимать продуманные и согласованные решения, обеспечивающие точность исполнения, минимальные затраты и кратчайшие сроки исполнения заказов.
Еще одной рассматриваемой задачей является применение разработанных методов и средств для формирования годового плана опытно-экспериментального производства АО «АвтоВАЗ». В данном случае рассматривается система реального времени, функционирующая в сети Интернет, где каждый специалист предприятия имеет своего агента для согласования принимаемых решений за постоянно действующим виртуальным «круглым столом». Возникающие проблемы (например, необходимость срочной сборки автомобиля для испытаний на ледовой дорожке или поставке на выставку) инициируют переговоры за виртуальным «круглым столом», позволяющие принимать продуманные и согласованные решения, обеспечивающие точность исполнения, минимальные затраты и кратчайшие сроки исполнения заказов.
Рисунок 4.4 - Конструкция виртуального Рисунок 4.5 - Фрагмент онтологии рулевого "круглого стола" управления На рисунке 4.4 показана конструкция виртуального "круглого стола", используемого в реализованной системе, а на рисунке 4.5 - фрагмент онтологии вариантов рулевого управления.
Предположим, что конструктор автомобиля заказал в экспериментальном производстве прототип машины, атрибуты которой показаны на рисунке 4.6. В результате взаимодействия и переговоров участников "круглого стола" выявляются следующие варианты:
1. Заказ можно удовлетворить, но требуется запланировать внеочередную командировку менеджера по снабжению в Германию для поставки по импорту рулевого управления с переменным шагом зубьев рейки рулевого механизма (нестандартный вариант) и "линия поведения" его агента требует согласовать это решение с человеком. Также требуется согласование с экономистом из-за того, что используется импортный модуль и необходима дополнительная заграничная командировка. Окно соответствующего согласования появляется перед экономистом (рисунок 4.7).
2. Снабженец выполняет поставку по ранее намеченному графику (у него запланирована командировка), поэтому в согласованиях с ним нет необходимости, но сроки завершения испытаний будут сдвинуты и это потребует согласования с конструктором.
3. Используется стандартное рулевое управление. При этом никаких дополнительных согласований не требуется.
Если конструктор соглашается на первый вариант, то менеджеру по снабжению по электронной почте уйдет письмо с просьбой подтвердить перенос командировки на более ранний срок (см. рисунок 4.8). Предположим, что снабженец согласится и тогда аналогичное письмо пойдет финансисту с просьбой подтвердить требуемое увеличение финансирования. Если теперь финансист откажется, то заново стартуют переговоры с новыми условиями и конструктору будет послано письмо с альтернативными вариантами и объяснениями причины отказа.
Данный подход фактически полностью воспроизводит схему переговоров реальных специалистов предприятия. Но в данном случае в компьютерной сети предприятия будет постоянно функционировать виртуальный "круглый стол" агентов, реагирующий на каждое изменение в ситуации на производстве. Этот круглый стол будет отличаться от реального только тем, что будет работать 24 часа в сутки и 7 дней в неделю, инициируя привлечение людей для принятия решений лишь в случае действительной необходимости.
В Приложении Е приведены примеры других успешных применений разработанной системы в логистике, включая производство деревянных частей для оформления салонов автомобилей класса люкс, воздушные перевозки крупногабаритных грузов, планирование железнодорожных расписаний и ряд других /126/.
