# Dealing with Deadlocks in Industrial Multi Agent Systems
## 2 Preliminaries
### Methods for the Deadlock Prevention and Avoiding  
As already mentioned, two main streams of methods are represented by methods based on: (i) reachability trees and \(P\)-invariants of PN and (ii) PN siphons and traps. In the former case, it is necessary to mention the most principal contributions [6; 8; 9; 31; 32; 33] important for the evolution of the \(P\)-invariants-based methods. The origin of this method consists in the effort to deal with the problem of the forbidden state in DES. Namely, it was shown in the literature that if a set \(\mathcal{L}\) of legal PN markings is expressed by a set of \(s\) linear inequality constraints (so called General Mutual Exclusion Constraints (GMEC)) and if \(\mathcal{L}\) is controllable, then the PN-based solution exists and it is maximally permissive. The controllability of \(\mathcal{L}\) means that from any marking \(M\in\mathcal{L}\) no forbidden marking is reachable by firing a sequence containing only uncontrollable transitions. In the opposite case, a general forbidden marking constraint may be enforced by PN-based controller only if the Petri net model of the system is safe. Hence, PN \(P\)-invariants are used in order to compute the feedback controller that enforces GMEC. They perform transformations on the system's specifications to obtain constraints in the desired form. The controller is a set of control Petri net places. When the controller is added to the PN model of the plant, control places ensure a live and maximally permissive behavior of the closed loop system with respect to the forbidden states or markings. The controller design has a linear complexity in the number of system states. However, there are cases where such PN controller does not exist. Especially, when the set of legal markings \(\mathcal{L}\)_is not convex_, there does not exist any PN place that can forbid the reachability of bad markings when allowing all legal ones. The concept of PN \(P\)-invariants was extended also to PN with uncontrollable and unobservable transitions. However, in this case maximally permissiveness cannot be guaranteed. In the latter case, there are lots more such basal publications--[6; 7; 10; 28; 34; 35; 36; 37; 38; 39; 40; 41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57]. Siphons are tied to dead transitions whose existence leads to the loss of liveness of PN-based models of AMS. Siphon control is an effective way to prevent the occurrence of deadlocks. In a general case, particularly for models of AMS based on generalized PN, a siphon-based deadlock prevention policy cannot find an optimal (i.e., maximally permissive) supervisor. However, for PN models of AMS based on ordinary PN it is possible. Siphons in the PN model of a plant are divided into elementary and dependent ones. A monitor is added to the plant model for each elementary siphon, in such a way that the siphon will be _invariant-controlled_. The method guarantees that no further emptiable control-induced siphon is generated due to the addition of the monitors. When all elementary siphons are controlled, the controllability of a dependent siphon is ensured by properly setting the _control depth variables_ of its related elementary siphons. The explanation of the term invariant-controlled siphon, as well as the term control depth variable, will be explained and illustrated below in the Section 4.2. However, this is applicable only for S\({}^{3}\)PR paradigm of RAS. In case of S\({}^{4}\)PR paradigm (modeled by generalized PN), which uses multiple resource requirements and information about the weight of arcs, the concept of extended elementary siphons have to be used. Namely, due to the complicated utilization of resources, it is insufficient to represent the relationship between elementary and dependent siphons in generalized PN in such way as it is in case of ordinary PN. Extended elementary siphons are find by an iterative process--see, e.g., [58].