Preface

This book is intended for graduate students, advanced undergraduates, and practicing engineers who are interested in the control problems of manufacturing, communication and computer networks, chemical process plants, and other high level control applications. The text is written from an engineering perspective, but it is also appropriate for students of computer science, applied mathematics, or economics. The book contains enough background material to stand alone as an introduction to supervisory control with Petri nets, but it may also be used as a supplemental text in a course on discrete event systems or intelligent autonomous control.

The book presents a novel approach for the supervisory control of discrete event systems using Petri nets. The concepts of supervisory control and discrete event systems are explained, and the background material on general Petri net theory necessary for using the book's control techniques is provided. A large number of examples are used to illustrate the concepts and techniques presented in the text, and there are plenty of references for those interested in additional study or more information on a particular topic.

Though the book contains a fair amount of explanatory and background material, some mathematical background is required. The reader should be familiar with basic concepts of matrix algebra and understand concepts such as null spaces or the kernel of an integer matrix. Fundamental ideas from the areas of mathematical programming and constrained optimization are also used here. The reader should be familiar with basic formulations of linear programming and with slack variables. Though the reader need not have encountered Petri nets before, this book is not intended as an introductory text on net theory. Some readers may wish to learn more about general net theory in parallel with or before learning the specific techniques covered here.

In the area of supervisory control, Petri nets provide an alternative to automata for modeling discrete event system plants. Petri nets provide increased modeling expressiveness and complexity compared to automata, allowing for a richer range of possible plant behaviors. Unfortunately this increase in modeling power typically also increases the difficulty of synthesizing supervisory controllers. This difficulty is overcome here for a large class of supervisory control goals using a method that is based on Petri net place invariants. The approach is easy to use and computationally efficient, both in the design and implementation phases, making the technique appropriate also for online control reconfiguration.

Following the introductory and background material of chapter 1, chapter 2 introduces the Petri net model for discrete event systems. The basic supervisor synthesis technique is described in chapter 3. Uncontrollable and unobservable transitions present important problems for supervisory control. These structures are introduced in chapter 4, and chapter 5 presents computational techniques for designing controllers in the face of these transitions. Chapters 6 and 7 describe an array of supervisory control problems that can be solved with the techniques of the previous chapters. These include the management of finite resources, deadlock avoidance, exclusions between events and states, and many others. A number of detailed examples are collected together in chapter 8 to illustrate the use and utility of the control techniques.

Chapter 2 contains all background material on Petri nets necessary to understand and use the supervisory control techniques of this book. The dynamic system model is described from both the graph theoretical and algebraic view points. Important concepts such as Petri net invariants, traps, and siphons are covered in detail. The different classes of Petri nets, based on their structural and thus behavioral properties, are described, and the relationship between Petri nets and automata is discussed. The chapter concludes with a brief survey of the uses of Petri nets as plant or controller models in supervisory control.

Chapter 3 presents the basic control technique of the book. Given a Petri net modeled plant and a linear inequality indicating a set of desired or safe plant states, a supervisor is constructed to insure that all reachable plant states conform to this inequality. The supervisory is itself a Petri net, connected to the transitions of the plant. The control design is very efficient, with the size of the supervisor being proportional to the number of constraints being enforced, and the computation of the controller's structure involving little more than a matrix multiplication. The controller is shown to be "maximally permissive," meaning that it will only prevent an event from occurring in the plant when that event would cause a violation of one or more of the constraints.

Actuator failures, practical concerns, or cost factors may make it impossible for a supervisor to prevent certain events from occurring during the plant's evolution. Similarly, sensor failures or other concerns may make it impossible for the controller to directly observe the occurrence of certain events. These ideas are translated into the concepts of uncontrollable and unobservable transitions in chapter 4. It is shown how individual plant constraints can be classified as admissible or inadmissible due to the presence of uncontrollable and unobservable transitions.

Chapter 5 presents computational techniques for transforming inadmissible constraints into admissible constraints. Once a given constraint has been made admissible using these techniques, the new transformed constraint can be enforced on the plant using the procedure of chapter 3. Techniques are also presented in chapter 5 for characterizing all admissible linear constraints on a plant with uncontrollable and unobservable transitions. This characterization can then be used to identify constraints that satisfy the requirements of an inadmissible constraint, but are themselves admissible. A controller is then constructed that enforces the disjunction of all these admissible constraints on the Petri net plant.

Linear inequalities placed on the reachable state space of a plant are useful for realizing a wide range of supervisory control specifications. Chapters 6 and 7 present a number of problems, some of which the reader might not have realized could be expressed using state-based inequalities. Chapter 6 discusses the-modeling, management, and allocation of finite resources and presents supervisory techniques for liveness insurance and deadlock avoidance, problems that are often associated with the sharing of finite resources. Chapter 7 details a number of other control specifications, including the incorporation of events as well as states into constraints. Methods are presented for enforcing a class of logical predicates on system behavior, as well as means of including real time in the control specifications. Of course not all supervisory control specifications can be expressed as linear inequalities on the plant state, and chapter 7 includes a discussion on the limits of the control technique as well.

Small examples appear throughout the text to illustrate specific points and techniques as they are developed. Chapter 8 is used to collect the larger examples that incorporate multiple control procedures. This chapter need not be read in sequence. Readers may refer to specific examples within the chapter as they are cross referenced in the developmental material. The examples in chapter 8 include plants from the areas of flexible manufacturing, communications, process control, and hybrid systems.

Though the book follows a logical course, describing a particular approach to supervisory control, it is also intended to serve as a reference for readers who have become familiar with the material. Algorithms and mathematical propositions are easily identified within the text. The larger examples are cross referenced and collected within a single chapter for easy reference.

The end of the book contains a number of resources for the reader. All of the citations have been collected in a single section to make them easy to find while the book is being read and afterwards as a reference bibliography. The glossary covers many of the basics of Petri nets as well as the particular supervisory control techniques described in the text. A list of symbols is provided for the reader who wishes to understand a specific topic without going through all the developmental material. Finally, the complete index includes cross-references and topic sub-headings, making it easy to quickly find a specific subject in the text.

Readers of this book will learn the basics of supervisory control as well as an effective technique for its implementation using Petri nets. The reader will also receive an introduction to Petri nets, particularly the algebraic approach employed by the authors, showing that Petri nets can provide a useful paradigm for analysis, an efficient model for computation, and a powerful tool for implementation of supervisors for discrete event systems.

Acknowledgments

The authors gratefully acknowledge the support of the National Science Foundation, the Electric Power Research Institute, and the Army Research Office via grants NSF/MSS-9216559, EPRI/RP-8030-06, ARO/DAAH04-96- 1 -0134, ARO/ DAAH0495-1-0600, and NSF/ECS-9531485; the Arthur J. Schmitt Foundation and the University of Notre Dame's Center for Applied Mathematics for the fellowships they awarded; and of Notre Dame's Department of Electrical Engineering for providing an environment conducive to learning and academic pursuits.

JOHN MOODY AND PANOS ANTSAKLIS

University of Notre Dame, USA