Deadlock Avoidance Policies for Automated Manufacturing Systems Using Finite State Automata

This chapter considers the problem of deadlock avoidance in flexibly automated manufacturing systems, one of the most prevalent supervisory control problems that challenges the effective deployment of these environments. The problem is addressed through the modeling abstraction of the (sequential) resource allocation system (RAS), and the pursued analysis uses concepts and results from the formal modeling framework of finite state automata (FSA). A notion of optimality is defined through the notion of maximal permissiveness, but the computation of the optimal DAP is shown to be NP-Hard. Hence, the last part of the chapter discusses some approaches that have been developed by the relevant research community in its effort to deal with this negative complexity result.