Об одном подходе к моделированию распределенных алгоритмов управления мультиагентными системами

Размещено на http://www.allbest.ru/

Об одном подходе к моделированию распределенных алгоритмов управления мультиагентными системами

И.А. Ломазова

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

1. Сети Петри и моделирование алгоритмов управления

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

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

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

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

В частности, многие параллельные алгоритмы управления и процессы обработки информации естественно моделируются граф-схемами [Бандман и др.,90]. Граф-схема алгоритма представляет собой ориентированный граф G = <V,E>, где V - множество вершин, E - множество дуг.

Множество вершин состоит из вершин следующих трех видов:

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

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

Вспомогательные вершины, которые в свою очередь подразделяются на три группы:

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

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

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

Важным достоинством граф-схем является то, что граф-схема алгоритма может быть формально преобразована в сеть Петри специального вида - сеть Петри со свободным выбором. При этом обоснование корректности граф схемы алгоритма сводится к проверке живости и безопасности соответствующей сети Петри. В сетях Петри со свободным выбором каждая позиция (условие), обуславливающая срабатывание более чем одного перехода, является единственной обуславливающей эти переходы позицией. Структурные особенности сетей Петри со свободным выбором позволили разработать эффективные алгоритмы их семантического анализа непосредственно по структуре сети ([Hack,74], [Thiagarajan et al,86]).

Однако, моделирование алгоритмов управления граф-схемами алгоритмов (т.е., сетями Петри со свободным выбором) имеет ряд существенных недостатков. В граф-схеме структура алгоритма задана изначально и не допускает, в частности, динамического распараллеливания задачи. Также граф-схема алгоритма не обладает модульной структурой, что делает моделирование и анализ больших задач весьма затруднительными. Для устранения этого ограничения в докладе предлагается использовать для моделирования алгоритмов управления расширение стандартного формализма сетей Петри - вложенные сети Петри ([Ломазова,98], [Lomazova 99]).

2. Вложенные сети Петри

Во вложенных сетях Петри фишки, помечающие позиции, рассматриваются как объекты, имеющие самостоятельное поведение, которое в свою очередь описывается также некоторыми сетями Петри. Название "вложенные сети" указывает на то, что элементы сетей в них сами являются сетями, подобно тому, как в системе вложенных множеств элементами некоторого множества могут быть множества. Вложенные сети Петри являются удобным и мощным средством для моделирования и анализа иерархических мультиагентнтных распределенных систем. Они обладают естественным механизмом модульности. Модульные сети Петри ([Ломазова,98],[Lomazova,99]) можно рассматривать как специальный случай вложенных сетей. По сравнению с другими расширениями формализма сетей Петри за счет понятия и конструкции объекта ([Badouel,98], [Battiston et al,95] [Lakos,95], [Moldt et al,97], [Sibertin-Blanc,94], [Valk, 98]) вложенные сети Петри сохраняют такие важные свойства стандартных сетей Петри, как простота и выразительность модели, и разрешимость некоторых важных для верификации свойств.

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

Поведение вложенной сети Петри включает четыре типа шагов.

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

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

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

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

3.Вложенные сети Петри и моделирование мультиагентных систем

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

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

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

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

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

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

Доказано ([Lomazova et al,99]), что выразительность вложенных сетей Петри слабее машин Тьюринга и сильнее обыкновенных сетей Петри. При этом вложенные сети Петри сохраняют важные для возможности их семантического анализа свойства (в частности, являются хорошо структурированными системами переходов [Finkel et al,97]).

В частности, в [Lomazova et al,99] доказано, что свойство останова (завершаемости алгоритма) и свойство поддержания некоторого заданного состояния управления (соntrol-state maintainability) разрешимы для вложенных сетей Петри.

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

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

Л и т е р а т у р а