Coalition decision support system designing

Full Text

Введение. Данная работа посвящена вопросам проектирования и разработки коалиционной системы поддержки принятия решений (СППР) с использованием методов мультиагентного моделирования. СППР могут использоваться в любой области человеческой деятельности, в том числе в промышленности. В настоящее время возникающие в крупном промышленном производстве задачи часто касаются взаимодействия существующих на рынке различных предприятий, исследования процессов принятия решений по совместным выполнениям крупных заказов, реализации комплексных производственных проектов одной организацией и т.д. Эти задачи с точки зрения системного анализа являются слабоструктурированными в связи с содержанием в них большого количества неопределенных параметров, которые возникают, в первую очередь, при принятии решений в процессе проектирования, распределения ресурсов и средств в производственных процессах, решении задач по контролю качества и т. д. Описание модели. Целью разработки коалиционной модели мультиагентного процесса преобразования ресурсов (МППР) является описание процессов взаимодействия агентов и формирования коалиций при решении вопросов коллективного использования ресурсов и средств в условиях параллельного выполнения МППР. Основой для создания коалиционной модели МППР является математическая модель, разработанная К. А. Аксеновым и Н. В. Гончаровой [1]. Для реализации коалиционной модели МППР необходимо дополнение модели [1] следующими объектами: коалиция (K), база знаний коалиции (KBK ), цель коалиции (GK ), общая база знаний мультиагентной системы (МАС) (GKB), действие агента (DA ) и коалиции (DK ), план действий агента (PA ) и коали 72 Разработка коалиционной системы поддержки принятия решений ции (PK ), жизненный цикл агента (LA ) и коалиции (LK ). В новой модели необходимо функционирование следующих механизмов: обмена сообщениями между агентами и коалициями, формирования коалиций, формирования планов действий агента и коалиции, проведения аукционов. В коалиционной модели МППР протекают процессы, представленные на рис. 1. Коалиционной модели мультиагентного процесса преобразования ресурсов M соответствует структура, включающая множество объектов {Obj1 , . . . , Objm }, ориентированных на взаимодействие коалиций и агентов [2]: M = N ameM , DescM , {Obj1 , . . . , Objm }, {Relation1 , . . . , Relationm }, self self {Attr1 , . . . , Attrk } , где N ameM — имя модели; DescM — описание модели; {Obj1 , . . . , Objn } — объекты (элементы модели): ресурсы, средства, сообщения, преобразователи, цели, агенты, коалиции, параметры; {Relation1 , . . . , Relationm } — связи; self self {Attr1 , . . . , Attrk } — собственные атрибуты системы. Для описания коалиционной модели МППР определены следующие основные понятия. Мультиагентная система в коалиционной модели МППР имеет следующую структуру [2]: M AS = {A1 , . . . , Ak }, {K1 , . . . , Ka }, GKB , где {A1 , . . . , Ak } — множество агентов в МАС; {K1 , . . . , Ka } — множество коалиций в МАС; GKB — общая база знаний МАС. Каждая коалиция Ki и каждый агент Aj имеют возможность обращаться к своим базам знаний KBKi и KBj , получая необходимую информацию. Хранилищем информации, доступным для всех коалиций и агентов МАС, является общая база знаний GKB (General Knowledge Base). В ней хранится описание параметров всех МППР, функционирующих в данной модели МАС; методы разрешения конфликтов {Q1 , . . . , Qs } между агентами и коалициями и алгоритмы стратегий поведения {Str1 , . . . , Strv } агентов и коалиций в МАС. Агенты в коалиционной модели МППР представлены в виде следующей структуры [2]: A = N ameA , {GA1 , . . . , GAn }, KBA , {StrA1 , . . . , StrAv } , где N ameA — имя агента; {GA1 , . . . , GAn } — цели агента; KB — база знаний агента (Knowledge Base); {StrA1 , . . . , StrAv } — множество допустимых стратегий взаимодействий агента. Каждый агент Ai в МАС имеет собственную базу знаний KBi , в кото1 v рой хранятся: текущие стратегии поведения {StrAi , . . . , StrAi } с конкретными агентами МАС, данные по использованию собственных ресурсов агента {Res1 , . . . , Resm } и собственных средств {M ech1 , . . . , M echk }, план действий i i i i агента P DAi , план выполнения работ агента P WAi . Каждый агент Ai в МАС имеет множество целей {G1 , . . . , Gn }, храняAi Ai щихся в его базе знаний KBi , включающих одну доминирующую цель GD Ai и множество второстепенных целей {G1 , . . . , Gh }. При достижении домиAi Ai нирующей цели GD агента Ai либо её изменении, связанном с изменением Ai 73 А. С. З р а е н к о, В. П. Ф е д о т о в, К. А. А к с е н о в Рис. 1. Схемы процессов в коалиционной модели МППР 74 Разработка коалиционной системы поддержки принятия решений состояния окружающей среды (освобождения или захвата другими агентами МАС {A1 , . . . , Aj } определённых ресурсов {Res1 , . . . , Resm } или средств 1 t {M ech1 , . . . , M echk }, действий других агентов {DA1 , . . . , DAj }, состояния процесса PR), новой доминирующей целью агента Ai становится цель из множества его второстепенных целей {G1 , . . . , Gh }. Ai Ai Aj Агент Ai выбирает стратегию взаимодействия StrAi (из множества допустимых стратегий {Str1 , . . . , Strv } с другим агентом Aj для достижения определенной цели из множества целей {G1 , . . . , Gh }. Разрешение конфликAi Ai тов между агентами происходит по определенным методам {Q1 , . . . , Qs }, основанным на использовании стратегий поведения агентов или организации аукционов. Каждый агент Ai в МАС управляет собственными ресурсами {Res1 , . . . , Resm } и собственными средствами {M ech1 , . . . , M echk }. Управлеi i i i ние организуется с помощью формирования плана действий P DAi агентом Ai в процессе его жизненного цикла LAi на основе использования информации из собственной базы знаний KBAi и общей базы знаний GKB. Жизненному циклу LA соответствует весь период активности агента в МАС от его определения до прекращения его функционирования. В процессе работы МАС агенты {A1 , . . . , Ak } могут взаимодействовать друг с другом, формировать коалиции {K1 , . . . , Ka } с целями организации взаимовыгодного сотрудничества, увеличения шансов получения необходимых ресурсов и средств при возникновении конфликтов. Коалиция агентов в МАС имеет следующую структуру [2]: K = N ameK , {A1 , . . . , Am }, GK , {Str1 , . . . , Strv }, KBK , где N ameK — имя коалиции; {A1 , . . . , Am } — множество агентов, входящих в коалицию; GK — цель коалиции; {Str1 , . . . , Strv } — множество допустимых стратегий поведения коалиции; KBK — база знаний коалиции. План выполнения работ P WK формируется коалицией K для достижения цели Gi и состоит из определенной последовательности работ {WK1 , . . . , WKt }. K Плану P WK соответствует следующая структура [2]: P WK = {WK1 , . . . , WKt }, Gi , KBK , GKB, {AD1 , . . . , ADh }, K {ResK1 , . . . , ResKm }, {M echK1 , . . . , M echKk } , где {WK1 , . . . , WKt } — работы плана; Gi — цель плана; {AD1 , . . . , ADh } — K множество агентов, участвующих в плане; {ResK1 , . . . , ResKm } — ресурсы, участвующие в плане; {M echK1 , . . . , M echKs } — средства, участвующие в плане. Алгоритм мультиагентного моделирования. Алгоритм мультиагентного моделирования, разработанный для практической реализации коалиционной модели МППР, представлен на рис. 2. В качестве основы данного алгоритма использован алгоритм [3], состоящий из следующих основных этапов: определение текущего момента времени; диагностирование возникших ситуаций, выработка команд управления, формирование очереди правил преобразования; выполнение правил преобразования и изменение состояния рабочей памяти (данных по загрузке ресурсов и средств). 75 А. С. З р а е н к о, В. П. Ф е д о т о в, К. А. А к с е н о в Рис. 2. Алгоритм мультиагентного моделирования 76 Разработка коалиционной системы поддержки принятия решений Данный алгоритм дополнен возможностью формирования коалиций, механизмом составления планов действий активных объектов (агентов и коалиций) и расширенными возможностями коммуникаций (для реализации взаимодействия активных объектов и формирования совместных решений агентов в коалиции). При выполнении 5-го и 9-го блоков алгоритма происходит формирование перечня правил и выполняемых действий над объектами рабочей памяти, а также состояния характеристик объектов. При выполнении 11-го блока выполняется расчет целей, производных и консолидированных показателей для объектов модели. Программный комплекс коалиционной СППР. Разработанная СППР обеспечивает возможности формирования сообществ агентов (коалиций), планирования действий агентов (и коалиций), применения различных сценариев взаимодействий (на основе использования стратегий поведения и проведения различного вида аукционов) и формирования решений агентов (на основе механизма согласования решений и организации досок с объявлениями) при моделировании. Графический интерфейс СППР показан на рис. 3 на примере модели по разработке индивидуальных тепловых пунктов (ИТП) на промышленном предприятии «Альтернативные энергосистемы» (www.aesm.ru) . Рис. 3. Модель по разработке ИТП Внедрение программного комплекса СППР. В модели предприятия «Альтернативные энергосистемы» на рис. 3 решаются задачи оптимизации распределения ресурсов между главными инженерами проектов (ГИП) с использованием различных механизмов взаимодействия и планирования действий по выполнению проекта. Цель проведения моделирования — исследование влияния стратегий взаимодействия агентов на финансовые показатели предприятия и выработка наиболее выгодной схемы производства ИТП. Для достижения данной цели необходимо решение следующих задач: 1) определение стратегии взаимодействия агентов — менеджеров проек77 A. S. Z r a e n k o, V. P. F e d o t o v, K. A. A k s e n o v тов, при которой предприятие выполняет наибольшее количество проектов за фиксированное время с наименьшими простоями ресурсов и средств; 2) изучение и сравнительный анализ возможных стратегий взаимодействия агентов; 3) исследование динамики использования ресурсов и средств агентами в зависимости от стратегий их взаимодействия. Цели агентов — менеджеров проектов (A1 , A2 ): – минимизация времени выполнения работ по заказу: tAi (Wi ) → min; – минимизация финансовых затрат по выполнению работ (т.е. максимизация прибыли агента): S Ai → max; – минимизация количества используемых «общих» ресурсов и средств в связи с вероятностью возникновения «параллельного» заказа: N Ai → min. В результате внедрения МСППР BPsim.KIT чистая прибыль предприятия от деятельности по производству ИТП выросла на 27%. Расчёт эффективности использования МСППР Bpsim.KIT показал, что её эффективность использования составляет 47%. Выводы. Разработанный программный комплекс коалиционной СППР позволяет: 1) вырабатывать эффективные управленческие решения на предприятиях и в организациях различного типа; 2) создавать модели процессов преобразования ресурсов с использованием возможности разработки сценариев поведения агентов и коалиций; 3) проводить имитационные эксперименты с использованием механизма составления планов действий агентов и коалиций.

About the authors

Alexey S Zraenko

Institute of Engineering Science, Ural Branch of RAS

Email: zraenko@yandex.ru
Postgraduate Student 34, Komsomolskaya st., Ekaterinburg, 620049, Russia

Vladimir P Fedotov

Institute of Engineering Science, Ural Branch of RAS

Email: fedotov@imach.uran.ru
(Dr. Sci. (Techn.)), Chief Researcher, Lab. of Applied Mechanics 34, Komsomolskaya st., Ekaterinburg, 620049, Russia

Konstantin A Aksenov

Ural Federal University named after the first President of Russia B. N. Yeltsin

Email: wiper99@mail.ru
(Ph. D. (Techn.)), Associate Professor, Dept. of Automated Control Systems 19, Mira st., Ekaterinburg, 620002, Russia

References

Supplementary files