Asynchronous Multi-Agent Systems with Petri nets

Federica Adobbati, Łukasz Mikulski · 2025

Read Asynchronous Multi-Agent Systems with Petri nets by Federica Adobbati, Łukasz Mikulski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00602.txt.

Introduction

Federica Adobbati and Łukasz Mikulski modeled groups of agents that act without a shared clock, in a 2025 paper built on Petri nets. Modeling how parts interact is the first step to checking that a multi-agent system behaves. Earlier work set out two meanings for such systems as state machines.

The pair give a way to build the nets for both meanings, one where agents sync on actions and one where they sync on data. They prove how the joined net matches the global state machine in each case. They also show how to switch a net from one meaning to the other. That switch lets analysts pick the model that fits the trait they want to check. The results tie two lines of theory into one toolkit.

Catalog record

CREATORFederica Adobbati, Łukasz Mikulski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-00602

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asynchronous Multi-Agent Systems with Petri nets Federica Adobbati, Łukasz Mikulski Abstract Modeling the interaction between components is crucial for many applications and serves as a fundamental step in analyzing and verifying properties in multi-agent systems. In this paper, we propose a method based on 1-safe Petri nets to model Asynchronous Multi-Agent Systems (AMAS), starting from two semantics defined on AMAS represented as transition systems. Specifically, we focus on two types of synchronization: synchronization on transitions and synchronization on data. For both, we define an operator that composes 1-safe Petri nets and demonstrate the relationships between the composed Petri net and the global transition systems as defined in the literature. Additionally, we analyze the relationships between the two semantics on Petri nets, proposing two constructions that enable switching between them. These transformations are particularly useful for system analysis, as they allow the selection of the most suitable model based on the property that needs to be verified. 1 Introduction Multi-agent systems (MAS) allow one to model and analyze the interactions between several components. Their formal study is relevant for several problems, such as, for example, the work on games, where the goal is to understand whether a set of agents is able to enforce certain properties on a global system on which they interact (e.g. [ 3 , 15 , 6 ] ). When modeling MAS, several studies (e.g. [ 14 , 11 , 26 , 25 ] ) consider synchronous systems, that is, they assume the existence of a global clock. At every instant, each agent selects its own action, and when the clock ticks, all the actions are executed together, determining the next global state of the system. In contrast, in an asynchronous system, agents can perform their actions whenever they become available, without following any predefined order. Asynchronous systems are convenient in many applications; however, their analysis presents some challenges. Although each agent may have a limited number of states, the global system obtained composing the agents together can be exponentially larger, especially in systems with a high level of concurrency. This is known as state explosion problem , and several works have been developed to address it. In [ 2 ] , the authors develop a modular control plane verification, where they decompose the global system into smaller components and verify properties on them; in [ 17 ] the authors propose an assume-guarantee scheme to verify strategic properties. Petri nets are formal models that can explicitly represent concurrency. They were introduced in the 60 by Carl Adam Petri [ 23 ] , and their use allows to efficiently represent distributed systems, and to study them with concurrent semantics rather than interleaving. Several classes of Petri nets have been developed in recent decades, allowing us to model different features of the systems. In this work, we focus on 1-safe nets with the addition of read arcs [ 19 ] . There is a strong relationship between Petri nets and transition systems. Given a Petri net, obtaining a transition system describing its behavior is always easy: each state of the transition system is a global state of the Petri net, and states are connected by arcs labeled as the transitions in the Petri net producing the change in the global state. The reverse process namely, given a transition system how to construct a Petri net with the same behavior, is known as the synthesis problem, and it is in general not always possible. In [ 4 ] the authors describe how to obtain a Petri net from a transition system for different classes of Petri nets. Multi-Agent systems can be described as Petri nets, and their composition is generally smaller than in the case of transition systems, due to the explicit representation of concurrency in Petri nets. The composition of Petri nets can be executed in several different ways, based on the kinds of interactions between components and properties that the composition needs to satisfy. Several works in the literature address the problem of composition: in [ 8 , 21 ] , the authors present a composition that preserves soundness between workflow nets; [ 5 ] presents a composition operation between open nets, i.e. Petri nets with a set of places that represent the interface of the net with the external environment; [ 10 ] introduces I/O Petri nets studying the properties of their channels. In [ 24 ] , a general framework to model composition is proposed, and, among other formalisms, its application to Petri nets is shown. In [ 9 ] the authors present an application of composition calculus to business process models. In our work, we propose a framework to study MAS based on Petri nets. We start from two semantics developed on transition systems, and we show how we can derive Petri net agents and their composition starting from each of them. We then prove that from the Petri net MAS in one of these semantics, we can always obtain an equivalent Petri net MAS in the other. The steps to reach this goal are described in Fig. 1 . We start from AMAS and open MAS. For both semantics, the transition system of each agent can be synthesized into a 1-safe Petri net. In AMAS, agents synchronize on common transitions, and the resulting global model is defined as canonical interleaved interpreted systems (IIS). In [ 1 ] we proved that composing Petri nets agents through fusion of transitions produces a Petri net with a marking graph isomorphic to the canonical IIS. When we consider open MAS, the translation into Petri nets require more steps. In an open MAS, the possibility to execute an action is conditioned on the value of some external variables. This concept is not explicitly present in Petri net semantics. For this reason, at agent level, we prove the equivalence between closed module, namely modules in which external dependencies have been explicitly added, and Petri net agents modified in order to explicitly add constraints derived from compositions. In addition, we prove the equivalence between the global closed MAS obtained through data synchronization and the global Petri net obtained by fusion of sequential components. Finally, we prove a relation between the two semantics. The paper is structured as follows. In Sec. 2 we formally define AMAS, open MAS, closed modules and their composition. In Sec. 3 we provide basic definitions on 1-safe Petri nets and their synthesis from transition systems. Sec. 4 presents our first contribution: we describe agent composition for the two models, proving the equivalence between the Petri net global models, and the canonical IIS or closed MAS. In Sec. 5 we discuss and prove the relations between the two semantics; Sec. 6 concludes the paper describing future developments of this work. AMAS open MAS (module) Tran. sys. 1-safe Petri net net with var. net with int. canonical IIS closed MAS global net (dyn. synch.) global net (stat. synch.) closed module net with ext. \equiv \equiv \equiv proj. synthesis refine refine synch. on transitions synch. on data tran. fusion place fusion add seq. comp. add ext. places fair randomness fair randomness seq. comp. fusion Figure 1: Schema of involved models. 2 MAS as transition systems: two semantics Transition systems are

Read the complete text