Optimal Supervisory Control of Automated Manufacturing Systems YuFeng Chen Xidian University, Xi’an, China ZhiWu Li Xidian University, Xi’an, China R $6&,(1&(38%/,6+(56%22. CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2012 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U. Government works Version Date: 20130321 International Standard Book Number-13: 978-1-4665-7754-1 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use.
The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information stor- age or retrieval system, without written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.com (http://www.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that pro- vides licenses and registration for a variety of users. For organizations that have been granted a pho- tocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.com and the CRC Press Web site at http://www.com Preface Discrete event systems (DESs) are an outcome of the development of computer and information technology, which in recent decades have become an integral part of our world. They encompass a wide variety of physical systems that arise from contemporary technology, such as urban transportation systems, logistic systems, database management systems, communication protocols, computer communication networks, distributed software systems, monitoring and control systems of large buildings, air and train traffic control systems, and highly integrated command, control, communication, and intelligence systems. As a typical example of DESs, automated manufacturing systems (AMSs), usually considered to be an innovative, agile, and quick response pattern of production, have received much attention in recent decades since the traditional mass production mode is challenged by the quick changes of market requirements.
Due to a high degree of resource sharing, there exist deadlocks in an AMS, which are an undesirable phenomenon since their occurrence usually gives rise to unnecessary productivity loss and even catastrophic results in highly automated systems such as semiconductor manufacturing and safety-critical distributed databases. Deadlock problems in AMSs have received more and more attention from both academic and industrial communities. Digraphs, automata, and Petri nets are three major mathematical tools to investigate deadlock problems in AMSs. Recent decades have seen that Petri nets are increasingly becoming an important, popular, and fully-fledged mathematical model to provide solutions to the issues.
There are three criteria to evaluate and design a liveness-enforcing Petri net supervisor for an AMS to be controlled, which takes the form of monitors, sometimes called control places, that can be regarded as the intervention from human beings or other external agencies. The criteria include behavioral permissiveness, computational complexity, and structural complexity. A maximally permissive supervisor implies that all legal states in the sense of deadlock control in a plant to be controlled are reachable in the controlled system, which, from the productivity point of view, usually leads to high utilization of system resources. A deadlock control algorithm with low computational complexity usually means that the calculation of its corresponding supervisor is tractable and that it can potentially be applied to the real-world systems.
Structural complexity of a liveness- enforcing supervisor is referred to as the number of monitors as well as related arcs in the supervisor. A supervisor with a small number of monitors can always decrease iv Preface the hardware and software costs in the stage of model checking and verification, and control validation and implementation. In general, it is difficult or even impossible, given a real-world system, to find a maximally permissive, yet computationally efficient, supervisor with a minimal number of monitors. A trade-off among behavioral permissiveness, structural complexity, and computational tractability is usually adopted.
For example, siphon- based deadlock prevention approaches that do not depend on a partial or complete state enumeration cannot in general lead to a maximally permissive supervisor. On the other hand, most deadlock prevention approaches, existing in the literature, that can derive maximally permissive liveness-enforcing supervisors expressed by a set of monitors depend on a complete marking enumeration except for some net subclasses at special initial markings. This monograph aims to present the state-of- the-art developments in the design of behaviorally and structurally optimal liveness- enforcing Petri net supervisors with computationally tractable approaches. The outline of this book is as follows: Chapter 1 introduces AMSs with focus on their deadlock control issues.
A brief review is provided of a variety of deadlock avoidance and prevention approaches in the literature. Chapter 2 recalls the basic concepts and definitions of Petri nets, including siphons, P-invariants, state equations, reachability sets, and reachability graphs. Also, binary decision diagrams (BDDs) are introduced as a powerful tool to analyze Petri nets. It offers fundamentals for readers to understand the essential contributions and makes the book self-contained.
Reachability graphs are the most powerful analysis technique of Petri nets, whose computation usually suffers from the state explosion problem. Chapter 3 formulates symbolic computation and analysis methods of bounded Petri nets, by using BDDs which are capable of representing large sets of markings with small data structures. The use of symbolic computation and analysis makes it possible to compute an optimal liveness-enforcing supervisor for large-sized systems. The theory of regions deals with the synthesis problem of Petri nets from automaton-based behavioral descriptions.
Chapter 4 proceeds to a deadlock prevention strategy by using the theory of regions, which can lead to a maximally permissive liveness-enforcing supervisor expressed by a set of monitors if, given a plant, such a supervisor exists. The major issue of this strategy is the computational complexity problem. Chapter 5 considers the design of a maximally permissive liveness-enforcing supervisor for manufacturing-oriented Petri net models existing in the literature. Once the reachability graph of a plant net model is computed, it is divided into two parts: a live-zone and a deadlock-zone.
By a vector covering approach, two sets of reachable and forbidden markings, a minimal covering set of legal markings and a minimal covered set of first-met bad markings, are defined. A maximally permissive liveness-enforcing supervisor is referred to as a set of monitors such that all elements in the minimal covering set of legal markings are reachable and no element in the minimal covered set of first-met bad markings is reachable. Motivated by the fact that a maximally permissive supervisor described by an automaton does not always admit a Petri net representation, Chapter 6 undertakes Preface v the most behaviorally permissive supervisor design problem. A liveness-enforcing Petri net supervisor is said to be the most permissive if there are no other pure Petri net supervisors more permissive than it.
The structural complexity of a liveness-enforcing Petri net supervisor is usually represented by the number of its monitors. Structurally simple supervisors imply the low computational overheads in model checking, validation, and system implementation. Chapter 7 considers the design of a maximally permissive liveness- enforcing supervisor with a compact supervisory structure by minimizing the number of monitors. Chapter 8 provides a well trade-off among the three criteria: behavioral permissiveness, structural complexity, and computational complexity.
An iterative approach is proposed to design a liveness-enforcing supervisor that is behaviorally optimal with a small number of control places. Meanwhile, the computational overhead is significantly reduced. Chapter 9 deals with the forbidden state problems that are a typical class of control specifications in supervisory control of DESs. The chapter provides a methodology to design a maximally permissive supervisor that prevents the reachability of a given set of forbidden states only, while the supervisor is structurally minimized.
As another typical class of control specifications, generalized mutual exclusion constraints (GMECs) are also considered in this chapter by presenting a maximally permissive supervisor with a minimal supervisory structure. In other words, by using a minimal number of monitors, all states satisfying the set of GMECs are reachable while the ones violating the constraints are forbidden. Finally, Chapter 10 concludes the book and offers a number of open technical problems and future research directions. Attached to the end of every chapter is a reference bibliography.
A glossary and a complete index are provided in the final part, which should facilitate readers in using this book. The monograph evolves from the recent research work in System Control & Automation Group, Xidian University, which is originally sparked by recognizing the technical faults of the theory of regions when, pioneered by Professor Murat Uzam, it is applied to the deadlock prevention problem for manufacturing systems. Readers are, on the whole, expected to come to understand the state-of-the- art developments of optimal supervisory control problems arising in automated production systems. The optimality of a supervisor that is expressed by a set of monitors implies that it is maximally permissive and structurally minimal with computationally reasonable overheads.
The readers can learn a methodology to achieve the optimality purposes of deadlock prevention via converting a variety of problems under consideration into integer linear programming models. The approaches reported in this book convince the readers of their significance in dealing with other supervisory control problems in DESs. YuFeng Chen September 2012 ZhiWu Li Acknowledgements We are very grateful to Professor MengChu Zhou, Department of Electrical and Computer Engineering, New Jersey Institute of Technology. Since 2002, we have been collaborating in supervisory control of automated manufacturing systems, particularly, in deadlock analysis and control issues.
In 2007, Professor Zhou was invited by Xidian University as a Lecture Professor sponsored by the Cheung Kong Scholars Programme, launched by the Ministry of Education, China, and Hong Kong Li KaShing Foundation. Professor Zhou’s affiliation to Xidian University leads to the birth of System Control & Automation Group, currently run by Professor ZhiWu Li, the co-author of this monograph. Our sincere thanks go to Professor Zhou since the appearance of this book is impossible without his valuable suggestions, critical comments and reviews, sweet encouragement, and kind support. We extend very special thanks to many people who directly or indirectly contribute in a variety of ways to the development of the material included in this book.
The continuing interaction and stimulating discussions with them have been a constant source of encouragement and inspiration. They include Professors M. Jeng, Taiwan Ocean University (China), Y. Huang, Taiwan ILan University (China), M.
Uzam, Niğde Üniversitesi, Y. Chao, National Chengchi University (Taiwan, China), M. Fanti, Polytechnic di Baris, J. Wang, University of Monmouth, F.
Lewis, University of Texas at Arlington, M. Mosbahi, University of Carthage, L. Feng, Royal Institute of Technology, F. Tricas, Universidad de Zaragoza, N.
Wu, GuangDong Institute of Technology, K. Xing, Xi’an Jiaotong University, W. Wu, ZheJiang University, L. Wang, Peking University, and S.
Wang, ZheJiang Gongshang University. We would like to express our sincere gratitude and appreciation to Professor W. Wonham, Department of Electrical and Computer Engineering, University of Toronto, Professor M. Shpitalni, Department of Mechanical Engineering, Israel Institute of Technology (Technion), Professor H.
Hanisch, Institute of Computer Science, Martin-Luther Universität, and Professor K.