# Dealing with Deadlocks in Industrial Multi Agent Systems
## 4 Siphon and Trap-Based Method of Prevention Deadlocks
### Invariant-Controlled Siphons and Setting the Marking of Monitors in the Siphon-Based Approach  
The control places \(p_{c}\) creating the supervisor are frequently named as monitors. Denote them as \(V_{\mathrm{S}_{i}}\), \(i=1,\ldots,n_{m}\) (\(n_{m}\) is a number of monitors). Now it is important to find a suitable marking of the monitors \(V_{\mathrm{S}_{i}}\). Namely, an inadequate setting of marking of monitors may cause other deadlocks in the controlled plant. In general, for setting the marking of monitors \(V_{\mathrm{S}_{i}}\), \(i=1,n_{m}\) are valid the following general rules.  
Let \(S=\{p_{i},p_{j},\ldots,p_{k}\}\) be a strict minimal siphon (SMS) of an original (uncontrolled) ordinary net system \((N_{0},M_{0})\), where \(N_{0}=(P_{0},T_{0},P_{0})\). Add a monitor \(V_{\mathrm{S}}\) to \(N_{0}\) to make the vector \(\mathbf{I}=(0,\ldots,1i,\ldots,1j,\ldots,1k,\ldots,0,-1)^{T}\) be a \(P\)-invariant of a new (controlled) net system \((N_{1},M_{1})\). Here, \(\forall p\in P_{0}\backslash S\), \(I(p)=0\), \(I(V_{\mathrm{S}})=-1\), \(\forall p\in P_{0}\), \(M_{1}(p)=M_{0}(p)\), and \(\mathbf{N}_{1}=[\mathbf{N}_{0}^{T}|\mathbf{I}_{V_{\mathrm{S}}}^{T}]^{T}\), where \(\mathbf{L}_{V_{\mathrm{S}}}\) is a row vector corresponding to adding the place \(V_{\mathrm{S}}\). Let \(M_{1}(V_{\mathrm{S}})=M_{0}(S)-\xi_{S}\), where \(1\leq\xi_{S}\leq M_{0}(S)\). Then \(S\) is an invariant-controlled SMS. Hence, it is always marked at any reachable marking of the net system \((N_{1},M_{1})\). Namely, \(\mathbf{I}\) is a \(P\)-invariant and \(\forall p\in(P_{0}\cup\{V_{\mathrm{S}}\})\backslash S,I(p)<0\). Note than \(\mathbf{I}^{T}.\mathbf{M}_{1}=\mathbf{I}^{T}.\mathbf{M}_{0}=M_{0}(S)-M_{1}(V_ {\mathrm{S}})=\xi_{S}>0\). Thus, \(S\) is an invariant-controlled siphon.  
A siphon \(S\) is controlled in a net \((N,M_{0})\)_iff_\(\forall M\in R(N,M_{0}),M(S)>0\). Thus, any siphon that contains a marked trap is controlled. Namely, the marked trap can never be emptied. In ordinary PN a controlled siphon does not cause any deadlock.  
A siphon \(S\) in an ordinary PN \((N,M_{0})\) is [7] invariant-controlled by \(P\)-invariant \(I\) under \(M_{0}\)_iff_\(\mathbf{I}^{T}.\mathbf{M}_{0}>0\) and \(\forall p\in P\backslash S,I(p)\leq 0\), or equivalently \(\mathbf{I}^{T}.\mathbf{M}_{0}>0\) and \(||I||^{+}=p\in P|I(p)\) is the positive support of \(I\).  
More succinctly said, a siphon \(S\) is controlled if it can never be emptied, and invariant-controlled by \(P\)-invariant \(I\) if \(\mathbf{I}^{T}.\mathbf{M}_{0}>0\) and \(||I||^{+}\subseteq S\).  
So that, to guarantee that a siphon \(S\) is always marked in a net system, it is necessary to keep at least one token being present at \(S\) at any reachable marking of the net system. Suppose that it was found such a control of a siphon \(S\) that \(S\) will never be emptied. Let \(\xi_{S}\) is the least number of tokens being present at \(S\). Such \(\xi_{S}\) is called the siphon control depth variable. It is clear that the larger \(\xi_{S}\) is, the more behavior of the modeled system will be restricted. However, it may means that more reachable states will be forbidden than it is necessary. Therefore, it is suitable when the siphon control depth variable is as small as possible, i.e., \(1\), if possible.  
Figure 4: The siphon \(S\) and trap \(T\) in the PN model.  
Setting the Marking of Monitors in Example 2  
It is easy to check from Figure 3 with taking into account Figure 4 that \(I=\{p_{2},\ p_{4},\ p_{5},\ p_{6}\}-V_{5}\) is \(P\)-invariant of \(N_{1}\). Clearly, \(S=\{p_{2},\ p_{4},\ p_{5},\ p_{6}\}\) is invariant-controlled by \(I\), since \(||I||^{+}=S\) and \(M_{0}(S)-M_{1}(V_{5})=4-2>0\). Here, \(||I||^{+}\), is the positive support of \(I\).