Search

A large amount of research has shown the vitality of siphon enumeration in the analysis and control of deadlocks in various resource-allocation systems modeled by Petri nets (PNs). In this paper, we propose an algorithm for the enumeration of minimal siphons in PN based on problem decomposition. The proposed algorithm is an improved version of the global partitioning minimal-siphon enumeration (GPMSE) proposed by Cordone et al. (2005) in IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, which is widely used in the literature to compute minimal siphons. The experimental results show that the proposed algorithm consumes lower computational time and memory compared with GPMSE, which becomes more evident when the size of the handled net grows.

State space techniques are one of the main approaches deployed for the analysis of concurrent systems. However, state space construction is stalled by a common phenomenon called the state explosion problem which makes it a tough task or even impossible when the state space computation demands prohibitive cost (time and memory). We limit general resource allocation systems (RASs) to a certain class whose state space can be hierarchically constructed, yet it comprises various enough types of real-world discrete event systems, such as automated manufacturing systems. This paper focuses on a class of RASs modeled with Petri nets (PNs), where, through pure algebraic operations, a novel method to compute the state spaces is proposed, which is motivated by the superposition property. Given a PN model of a system and a target resource configuration, we first propose a special initial marking called the initial basis marking and compute the corresponding reachability graph. Then, we increase the capacity of the resource places in an incremental way and generate the reachability graphs by taking advantage of the PN structure and the previously computed reachability graph until the capacity function of resources reaches the target resource configuration. A complete enumeration of reachable states can be obtained by a recursive scheme. Experimental studies also demonstrate the efficiency of the proposed approach in terms of computational cost and its high-potential to cope with the state-explosion problem.

In order to cope with uncertainties in a platoon, this paper proposes a reconfigurable multi-agent architecture to address the platoon safety problem by handling two modes: the normal mode and the degraded mode. At this stage of research, the normal mode is characterized by the interaction between agents over a Vehicle-to-Vehicle (V2V) communication network while the degraded mode simply involves sensors for a local perception. The switching from the normal mode to the degraded one is triggered when the communication quality is considered not fully reliable. A PID (Proportional Integral Derivative) controller is proposed to regulate the inter-vehicle distance and orientation. Two models are proposed in this paper: in the first one, the management operations such as splitting and joining are set up while the second is mainly modeled to assess the implemented controller quality. In this paper, the safety of a platoon is represented by the quality of tracking and the inter-vehicle distance. The mentioned features are assessed for both modes through a formal verification using the Uppaal software. We prove the efficiency of the proposed platoon model for several situations such as merging, following or leaving the platoon by verifying different properties using the model checking. The evaluation of the second model, simulated by the Webots software, proves the impact of the number of vehicles on the platoon performance and the vehicle tracking quality. We conclude that when the platoon reaches a certain number of vehicles, the safety criterion is no more reliable.