Directed Control of Discrete Event Systems for Safety and Nonblocking

Abstract

We introduce the notion of <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">directed</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">control</i> , where a directed controller is one that selects at most one controllable event to be enabled at any instant. This is in contrast to <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">supervisory</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">control</i> , where a supervisory controller enables a maximum allowable set of controllable events at any instant, i.e., no specific selection for executing an enabled event is made. While the design of a supervisory controller is meaningful for plants that are <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">generator</i> of controllable events, a directed controller design makes more sense for plants that are <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">executor</i> of controllable events. The control goal is the same as that in a supervisory control setting, namely, safety and nonblockingness. A safe and nonblocking directed controller exists if and only if a safe and nonblocking supervisory controller exists, thereby proving the polynomiality of verifying existence. We also develop a set of algorithms of polynomial complexity to compute a safe and nonblocking directed controller (whenever one exists).