Abstract
Due to the appearance of uncontrollable events in discrete event systems, one may wish to replace the behavior leading to the uncontrollability of pre-specified language by some quite similar one. To capture this similarity, we introduce metric to traditional supervisory control theory and generalize the concept of original controllability to $\lambda$-controllability, where $\lambda$ indicates the similarity degree of two languages. A necessary and sufficient condition for a language to be $\lambda$-controllable is provided. We then examine some properties of $\lambda$-controllable languages and present an approach to optimizing a realization.
Introduction
In classical Supervisory Control Theory (SCT), a control objective is defined by a "legal" language—a set of allowed event sequences. If this language is uncontrollable, meaning the system might perform prohibited actions that a supervisor cannot prevent, the standard approach is to find the "largest" controllable subset of that language.
However, this binary, "all-or-nothing" approach is often too conservative for real-world engineering. In many practical scenarios, a behavior that is slightly different from the ideal is perfectly acceptable, especially if the ideal behavior is impossible to enforce. This paper addresses the lack of a formal mathematical framework to measure and exploit "similarity" between behaviors in discrete event systems (DES). The authors propose a fundamental shift: instead of asking if a specification is strictly controllable, they ask, "If we cannot achieve exactly what we want, how can we find the closest controllable behavior that we can tolerate?"
A Metric-Based Framework for Languages
To move beyond binary controllability, the authors bridge the gap between control theory and topology by introducing metric spaces to the study of languages. They establish a three-tiered metric hierarchy:
- Event Metrics: The framework begins by assigning a distance $d$ between individual events. For example, in a manufacturing context, "repairing" a component might be considered more similar to "replacing" it than to "discarding" it.
- Baire Metric for Strings: To compare sequences of events (strings), the authors utilize the Baire metric. This metric is particularly suited for DES because it gives more weight to events occurring earlier in a sequence. This reflects the intuition that early deviations in a system's history are more significant than later ones.
- Hausdorff Metric for Languages: To compare entire sets of behaviors (languages), the authors employ the Hausdorff metric. This measures the maximum distance from any point in one set to the nearest point in another, providing a rigorous way to define the distance between a desired specification and a realizable control policy.
$\lambda$-Controllability and Optimization
The core contribution of the paper is the definition of $\lambda$-controllability. A language $K$ is defined as $\lambda$-controllable if there exists a controllable language $\tilde{K}$ (referred to as a "realization") within a distance $\lambda$ of $K$. This framework is a true generalization of SCT; if the similarity index $\lambda$ is set to 0, the theory collapses back into standard Ramadge-Wonham supervisory control.
Recognizing that multiple "similar" controllable behaviors might exist, the authors introduce a method to find a Pareto optimal realization. This optimization process balances two competing goals:
- Maximizing Overlap: Keeping as much of the desired behavior as possible.
- Minimizing Inclusion: Reducing the amount of undesired "extra" behaviors that the supervisor might inadvertently allow.
Key Results and Theoretical Significance
The paper establishes several critical theoretical results:
- Existence of Supremal Solutions: The authors prove that for any language, there exists a "largest" $\lambda$-controllable sublanguage ($K^{\Uparrow}$), mirroring the supremal controllable sublanguage found in standard SCT.
- Decidability: The authors provide a concrete algorithm to determine if a finite language is $\lambda$-controllable.
- Realization Refinement: A two-step process is outlined to take any valid realization and refine it into one that is Pareto optimal, ensuring the resulting supervisor is as efficient as possible.
Limitations and Future Directions
While this similarity-based approach provides a powerful new tool for control designers, the authors identify several areas for future research. Currently, the specific algorithm for calculating the $\lambda$-ball ($B(K, \lambda)$) is limited to finite languages; extending this to infinite or regular languages is a necessary next step. Additionally, the effectiveness of the approach is sensitive to the choice of the event metric $d$, which remains a subjective engineering challenge. Finally, the current framework focuses solely on controllability, leaving the incorporation of other vital SCT concepts—such as observability (partial sensing) and nonblocking (deadlock avoidance)—for future investigation.
Summary updated