Supervisory control of discrete event systems for bisimulation or simulation equivalence

Abstract

<p>The supervisory control of discrete event systems provides a framework for control of event-driven systems. Applications of supervisory control theory include protocol design for communication processes, control logic synthesis in manufacturing systems, and collision avoidance in human-computer interaction systems.;When designing a system at a certain level of abstraction, lower level details of the system and its specification are normally omitted to obtain higher level models that may be (non-deterministic) event-driven systems. Nondeterministic systems exhibit both branching and sequential behaviors and are captured using bisimulation equivalence (the traditional language equivalence only captures sequential behaviors). Simulation equivalence is more expressive than language equivalence but captures only the universal fragment of branching behaviors.;This dissertation presents supervisory control of discrete event systems for enforcing bisimulation equivalence or simulation equivalence with respect to given specifications. We show that in the general setting of nondeterministic systems and specifications, the complexity for bisimilarity enforcing control is doubly exponential and for similarity enforcing control remains polynomial solvable. So the choice of behavioral equivalence used depends on the application at hand and there is a trade-off between the expressivity and the complexity. We further show that the bisimilarity enforcing control problem becomes polynomially solvable when the system model is deterministic and there is complete observability of events. When the complete observability requirement is relaxed, the control existence problem remains polynomially solvable and the control synthesis problem becomes singly exponential. These complexities are similar to the ones for control under partial observation in completely deterministic setting Tsitsiklis (1989).;We introduce various notions of state-controllability (SC), state-recognizability (SR), state-achievability (SA), state-controllable-similar (SCS), state-controllability-bisimilar (SCB), and state-achievability-bisimilar (SAB) for deterministic system model. SC is a property of a controlled system under complete observation. Under partial observation, an additional property of a controlled system due to the partial observation is SR. The combined property of SC and SR is called SA. We show that properties of SC, SR and SA are not preserved under bisimulation equivalence and therefore cannot be served as a necessary condition for the existence of a bisimilarity enforcing supervisor. We introduce the notions of SCB and SAB, which are preserved under bisimulation, as part of the necessary and sufficient condition for the existence of a supervisor under complete and partial observation, respectively. We show that SC is not preserved under simulation equivalence and introduce SCS as a necessary and sufficient condition for the existence of a similarity enforcing supervisor under complete observation.;The aforementioned results use strict synchronous composition (SSC) of the system and supervisor as a mechanism of control. In SSC, it is required that individual systems synchronously execute all events. Prioritized synchronous composition (PSC) relaxed such synchronization requirements and this has been shown to enrich the control capability when the plant is non-deterministic. (The presence of nondeterminism in a plant model may cause the current state to be known with ambiguity, and allowing the flexibility of not synchronizing an event at all the candidate states that plant may have reached provides for additional benefits.) This dissertation introduces a notion of prioritized synchronous composition under mask (PSCM) to account for partial observation. We study the supervisory control when PSCM is adopted as a mechanism of interaction for both language and bisimulation equivalences. We show that the control & observation-compatibility requirements are removed of a supervisor. For control to achieve a language equivalence, the existence condition is given by achievability that is weaker than controllability and observability combined. (The weaker condition is required since we allow supervisors to be nondeterministic.) This suggests that the notion of PSCM is an appropriate generalization of PSC to account for partial observation.</p>