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

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

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

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

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

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

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

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

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

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