# Dealing with Deadlocks in Industrial Multi Agent Systems
## 3 \(P\)-Invariant-Based Method of Prevention Deadlocks  
\(P\)-invariants are vectors \(\mathbf{I}\) with the important property. The multiplication of such vectors with any marking (state) vector \(\mathbf{M}\) reachable from a given initial marking \(\mathbf{M}_{0}\) yields the same result. It is the relation of the state conservation, as follows  
\[\mathbf{I}^{T}.\mathbf{M}=\mathbf{I}^{T}.\mathbf{M}_{0} \tag{2}\]  
Taking into account the consecutive states obtained by firing of only one transition, we have for each transition \(t\)  
\[\mathbf{I}^{T}.\vec{col}_{t}(\mathbf{N})=0, \tag{3}\]  
where, \(\vec{col}_{t}(\mathbf{N})\) is the column of the incidence matrix \(\mathbf{N}\) corresponding to the transition \(t\). These vectors are solutions of the following equation  
\[\mathbf{I}^{T}.\mathbf{N}=\mathbf{0}^{T} \tag{4}\]  
what corresponds with the original Definition 2 of \(P\)-invariants introduced in the Section 2. Consider the inequality representing linear combinations restricting behavior of marking \(\mathbf{M}\)  
\[\mathbf{L}.\mathbf{M}\leq\mathbf{b} \tag{5}\]  
Here, \(\mathbf{L}\) is a matrix of integers, \(\mathbf{b}\) is an integer vector. An efficient help at creating \(\mathbf{L}\) yields the reachability tree (RT) of the net \(N\). After removing inequality by adding slack variables, we have  
\[\mathbf{L}.\mathbf{M}+\mathbf{s}=\mathbf{b}, \tag{6}\]  
where entries of the \((n_{s}\times 1)\) vector \(\mathbf{s}\) represents slack variables. Just the Equation (4) represents the base of the method for the supervisor synthesis. Namely, when we force there \([\mathbf{L}|\mathbf{I}_{s}]\) instead of \(\mathbf{I}^{T}\), we obtain (7) and some additional PN places (slacks) can be added to \(N\). Thus, the extended (augmented) PN \(N_{1}=N\circ N_{s}\) (where the symbol \(\circ\) expresses a composition) will arise. \(N_{s}\) is the PN which will (after finding its interconnections with \(N\)) ultimately create the supervisor. Then, slacks will create the places of the supervisor, frequently called monitors. In \(N_{1}\) we have the following structure of (4) in the form  
\[\left[\mathbf{L}\left|\mathbf{I}_{s}\right]\right[ \begin{array}{c}\mathbf{N} \\ \mathbf{N}_{s}\end{array} ]=\mathbf{0}, \tag{7}\]  
where \(\mathbf{I}_{s}\) is \((n_{s}\times n_{s})\)-dimensional _identity matrix_, \(n_{s}\) is the number of slacks; \(\mathbf{L}\) is a \((n_{s}\times n)\)-dimensional matrix which in a suitable form expresses the conditions imposed on marking (state) vectors of the original PN \(N\), and \(\mathbf{N}_{s}\) is the \((n_{s}\times m)\)-dimensional matrix. After finding \(\mathbf{N}_{s}\) from (7) by computing, we have the structure of the PN-based model of the supervisor--i.e., interconnecting arcs between \(N\) and \(N_{s}\). Consequently, in general,  
\[\mathbf{L}\mathbf{N}+\mathbf{N}_{s} = \mathbf{0} \tag{8}\] \[\mathbf{N}_{s} = -\mathbf{L}\mathbf{N}\] (9) \[\mathbf{N}_{s} = \mathbf{N}_{s}^{+}-\mathbf{N}_{s}^{-}, \tag{10}\]  
where \(\mathbf{N}_{s}^{+}\) is \(\mathbf{Post}_{s}\) and \(\mathbf{N}_{s}^{-}\) is \(\mathbf{Pre}_{s}\) of \(\mathbf{N}_{s}\). The marking \(\mathbf{M}_{a}\) of the supervised system \(N_{1}\) consists of the state vector \(\mathbf{M}\) of the \(N\) augmented with the state vector \(\mathbf{M}_{s}\) of the supervisor \(N_{s}\). Analogically, the incidence matrix \(\mathbf{N}_{a}\) of the net \(N_{1}\) consists of the incidence matrix \(\mathbf{N}\) of \(N\) augmented with the incidence matrix \(\mathbf{N}_{s}\) of the net \(N_{s}\). The marking and the incidence matrix of the net \(N_{1}\) are as follows  
\[\mathbf{M}_{a}=\left( \begin{array}{c}\mathbf{M}\\ \mathbf{M}_{s}\end{array} \right) \tag{11}\]  
\[\mathbf{N}_{a}^{-}=\left( \begin{array}{c}\mathbf{N}^{-}\\ \mathbf{N}_{s}^{-}\end{array} \right) \tag{12}\]  
\[\mathbf{N}_{a}^{+}=\left( \begin{array}{c}\mathbf{N}^{+}\\ \mathbf{N}_{s}^{+}\end{array}