# Dealing with Deadlocks in Industrial Multi Agent Systems
## 4 Siphon and Trap-Based Method of Prevention Deadlocks  
Such approaches are much more widespread than approaches based on P-invariants. There are many sources in literature. Let us mention at least some of them [7; 8; 12; 13; 16; 29]. Invariants, siphons, and traps are structural entities of PN. All of them can be computed, e.g., by the Matlab-based tool presented in [30]. The problem of deadlock prevention in a concurrent system represented by \(N\) is equivalent to the problem of avoidance of empty siphons in the ordinary PN model of \(N\). When at least one empty siphon occurs in ordinary PN \(N\), the net is totally deadlocked [5]. At the supervisor synthesis it is sufficient to consider only minimal siphons. It is necessary to ensure that the sum of the number of tokens in each minimal siphon \(S\) is never less than one, namely in any reachable marking \(M\). In such a case, the general condition \(\mathbf{S}_{i}.\mathbf{M}\geq b\) for \(i\)th siphon can be replaced by the condition in the form \(\mathbf{S}_{i}.\mathbf{M}\geq 1\). This can be derived as follows. Consider the following formal specification in \(N\)  
\[\mathbf{1}^{T}.\mathbf{M}\geq b \tag{24}\]  
where \(\mathbf{1}\) is a (\(n\times 1\))-dimensional vector, \(\mathbf{M}\) is a marking and \(b\) is a scalar; \(b\) and the entries of \(\mathbf{1}\) are integers. The relation (24) says that the weighted sum of the number of tokens in each place should be greater than or equal to a constant. In [6], it was proved that if a Petri net \(N=(P,T,F,W)\) with incidence matrix \(\mathbf{N}\) and initial state \(\mathbf{M}_{0}\) satisfies the following relation  
\[b-\mathbf{1}^{T}.\mathbf{M}_{0}\leq 0 \tag{25}\]  
then a control place \(p_{c}\) can be added, that enforces (24). Let \(\mathbf{N}_{c}:T\to\mathbb{Z}\) (\(\mathbb{Z}\) is the set of integers) denotes the weight vector of arcs connecting \(p_{c}\) with the transitions in the net \(N\); \(\mathbf{N}_{c}\) is obtained by \(\mathbf{N}_{c}=\mathbf{1}^{T}.\mathbf{N}\). In general, when there are more \(p_{c}\) than one, \(\mathbf{N}_{c}=\mathbf{1}^{T}.\mathbf{N}\) with \(\mathbf{L}\) being the matrix were rows represent particular \(\mathbf{1}^{T}\) appetizing to particular \(p_{c}\). The initial number of tokens in \(p_{c}\) is \(M_{0}(p_{c})=\mathbf{1}^{T}.\mathbf{M}_{0}-b\geq 0\) or, in general, \(\mathbf{M}_{0}^{0}=\mathbf{L}.\mathbf{M}_{0}-\mathbf{b}\geq 0\). The controlled Petri net is maximally permissive. The control process enforces _just enough control_ to avoid all illegal markings. This is the basis for deadlock prevention, i.e., for the synthesis of the control algorithm based on siphons. Thus, the place invariant guarantees that for any marking \(\mathbf{M}\) in the set of reachable markings of \(N\)  
\[\mathbf{1}^{T}.\mathbf{M}-M(p_{c})=b \tag{26}\]  
Here, as it was defined above, \(M(p_{c})\) is the number of tokens in the control place \(p_{c}\). Due to the fact that \(M(p_{c})\) is non-negative, the inequality in (24) is satisfied. Equation (25)  
Figure 3: The controlled PN model of the AMS. expresses the demand that (24) must be satisfied for \(\mathbf{M}_{0}\), otherwise no solution exists there. \(\mathbf{b}_{c}\) represents the row which extends the incidence matrix \(\mathbf{N}\) of the uncontrolled net \(N\) with respect to the control place \(p_{c}\). In general, for more additive places \(p_{1},\ldots,p_{s}\), it can be written  
\[\mathbf{L}.\mathbf{M}\geq\mathbf{b},\quad\text{or}\quad\mathbf{L}.\mathbf{M}- \mathbf{M}_{c}=\mathbf{b} \tag{27}\]  
where \(\mathbf{L}\) is (\(n_{s}\times n\)) matrix of positive integers greater than or equal to 0. \(\mathbf{L}\) has the weighted vectors \(\mathbf{I}_{i}^{T}\), \(i=1,\ldots,s\), as its rows. The vector \(\mathbf{b}\) is (\(n_{s}\times 1\)) vector of restrictions with entries being positive integers greater than or equal to 0; \(\mathbf{M}_{c}\) is (\(n_{s}\times 1\)) vector of slacks with entries being positive integers greater than or equal to 0.