# Dealing with Deadlocks in Industrial Multi Agent Systems
## 1 Introduction  
Recent decades represent a huge evolution of Automated Manufacturing Systems (AMS), previously named Flexible Manufacturing Systems (FMS). We can even talk about the new industrial revolution. According to [1], this evolution is realized mainly by the development in four axes, namely products, technology, business strategies, and production paradigms. The edited book [2] offers a wide perspective on modern design and operation of production networks. The evolution of the manufacturing system in the future is presented in [3].  
The operation of AMS often has a similar character to Discrete-Event Systems (DES), where the next state depends only on both the current state and the occurrence of discrete events. Petri nets (PN) [4; 5] are frequently used for modeling and control of DES. The family of AMS is a typical representative of DES where many devices cooperate together--robots, machine tools, transport belts, automatically guided vehicles (AGV), etc. They are frequently called to be resources. They are shared by multiple production lines, robotized working cells, etc. These devices and their aggregates, in the form of lines and cells, can also be considered industrial agents and the whole AMS as a multi-agent system. The adequate resource allocation is very important in AMS in order to avoid deadlocks. A deadlock in general is a state in which two or more processes are each waiting for the other one to execute, but neither can go on. Hence, deadlock is undesirable and bad phenomenon. Due to deadlocks, either the entire plant or some of its parts remain stagnate. Thus, the primal intention of the production cannot be achieved. For a design of deadlock-free AMS discrete mathematics is necessary. PN-based discrete mathematical models of AMS yield a suitable background for this.  
There exists a large number of publications interested in this topic. From the older ones, the following works should be mentioned in particular [6; 7; 8; 9; 10], as well as the UML (Unified Modeling Language)-based work [11] applied in software engineering. While in [6; 9] foundations of the \(P\)-invariant-based method were laid, in [7; 8] the method based on siphons and traps was elaborated. A generalized view on deadlocks in multi-agent systems is presented in [10]. Among the more recent works should be mentioned [12; 13; 14; 15], as well as the author's survey article [16]. While in [12] a comprehensive survey of Petrinet siphons were presented, in [13; 15] unreliable resources are investigated and the robust control for AMS containing such resources is designed. In [14], deadlocks in mobile agent systems are detected and resolved.  
In relation to the elimination of deadlocks, in [16; 17; 18; 19; 20; 21] three categories of strategies are distinguished: (i) deadlock detection and recovery--which is used in cases where deadlocks are infrequent and their consequences are not too serious; (ii) deadlock prevention--it imposes restrictions on the interactions among resources and their users to prevent resource requests that may lead to deadlocks; and (iii) deadlock avoidance--it grants a resource to a user only if the resulting state is not a deadlock.  
Consequently, it is impossible to address to such a broad issue in one paper. In this paper, only two methods of deadlock prevention in AMS by means of PN-based models are introduced and compared. Both methods add monitors (additional places) into the original PN model of AMS in order to remove deadlocks. One method enumerates monitors and their interconnections with the original PN model using P-invariants and the other using siphons and traps.