# Dealing with Deadlocks in Industrial Multi Agent Systems
## 3 \(P\)-Invariant-Based Method of Prevention Deadlocks
\right), \tag{13}\]  
Here, \(\mathbf{N}_{a}\), \(\mathbf{N}\) and \(\mathbf{N}_{s}\) are expressed by sub-matrices \(\mathbf{N}_{a}^{+}\) and \(\mathbf{N}_{a}^{-}\), \(\mathbf{N}^{+}\) and \(\mathbf{N}^{-}\), and \(\mathbf{N}_{s}^{+}\) and \(\mathbf{N}_{s}^{-}\). Because of the prescribed conditions we have  
\[\left[\mathbf{L}\left|\mathbf{I}_{s}\right]\right[ \begin{array}{c}\mathbf{M }_{0}\\ \mathbf{s}\mathbf{M}_{0}\end{array} ]=\mathbf{b}, \tag{14}\]  
where \(\mathbf{b}\) is the \((n_{s}\times 1)\))-dimensional vector (see (5) and (6)). Its integer entries represent the limits for number of tokens in (5). Sometimes \(\mathbf{b}=\mathbf{1}\) where \(\mathbf{1}\) is the vector with all its entries equal to 1. Because  
\[\mathbf{L}\mathbf{M}_{0}+{}^{s}\mathbf{M}_{0}=\mathbf{b} \tag{15}\]  
the initial state vector of the supervisor can be simply computed as follows  
\[{}^{s}\mathbf{M}_{0}=\mathbf{b}-\mathbf{L}\mathbf{M}_{0} \tag{16}\]  
Example 1: Consider the simple example of \(N\) modeling an AMS with two production lines \(\{p_{7},t_{1},p_{1},t_{2},p_{2},t_{3}\}\) and \(\{p_{8},t_{4},p_{3},t_{5},p_{4},t_{6}\}\) with two common resources \(p_{5}\) and \(p_{6}\), introduced in Figure 1. Places \(p_{7}\) and \(p_{8}\) are idle process places, \(p_{1}\), \(p_{2}\), \(p_{3}\), and \(p_{4}\) are active process places, and \(p_{5}\) and \(p_{6}\) are resource places. A token in an active process place models, e.g., a part being processed. In Figure 1, active process places are empty till firing \(t_{1}\) and/or \(t_{4}\). Tokens located in a resource place model, e.g., the available capacity of buffers. Tokens located in an idle place indicate the maximal number of concurrent activities that can occur in a process represented by the corresponding production line. Parameters of \(N\) are as follows  
\[\mathbf{N}^{-}=\left( \begin{array}{cccccccc}0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&0&1&0\\ 1&0&0&0&1&0\\ 0&1&0&1&0&0\\ 1&0&0&0&0&0\\ 0&0&0&1&0&0\end{array} \right)\quad\mathbf{N}^{+}=\left( \begin{array}{cccccccc} 1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0&1&0&0&0&1\\ 0&0&1&0&1&0\\ 0&0&1&0&0&0\\ 0&0&0&0&0&1\end{array} \right) \tag{17}\]  
This \(N\) has, at the given initial state \(M_{0}=(0,\,0,\,0,\,2,\,2,\,3,\,3)^{T}\), the fairly branched (patchous) reachability tree (RT) with 33 nodes (including \(M_{0}\)). All RT nodes, being the reachable markings \(M_{0}\),..., \(M_{32}\) are the columns of the following matrix (in the ascending order):  
\[\mathbf{X}_{r}=\left( \begin{array}{cccccccccccccccccccccccccccccccccccc}0&1&0 &2&0&1&0&0&1&2&0&1&1&0&2&0&1&2&0&1&0&0&1&0&1&0&0&1&0\\ 0&0&0&0&1&0&0&1&0&0&0&1&2&1&0&1&0&0&2&1&1&2&1\\ 0&0&1&0&0&1&2&0&0&1&1&2&0&1&0&0&1&2&0&1&0&1&0&0&1\\ 0&0&0&0&0&0&1&0&0&0&1&1&0&0&0&0&0&1&1&1&2&1&1&2&1&2\\ 2&1&2&0&2&1&2&1&1&0&2&1&0&1&0&2&1&0&1&0&1&0&0&1&0&0&0&0\\ 2&2&1&2&1&1&0&2&1&1&0&0&2&1&1&0&0&0&1&1&0&0&1&0&0&0\\ 3&2&3&1&2&2&3&3&1&1&2&2&2&3&0&1&1&1&2&2&3&3&0&0&1&2&2&3&1&1&2&0&2\\ 3&3&2&3&3&2&1&2&3&2&1&2&1&3&3&2&1&2&1&0&1&3&2&2&1&0&0&2&1&1&2&0\end{array} \right) \tag{18}\]  
Because RT is too big, it cannot be introduced here full. In Figure 2, at least its principal fragment is introduced. Figure 1: The PN model of an AMS. From the RT fragment we can find the solitary deadlock \(M_{17}=(2,\,0,\,2,\,0,\,0,\,0,\,1,\,1)^{T}\)--see (18), where it is separated.