Similarity-based supervisory control of discrete-event systems

Yongzhi Cao, Mingsheng YingIEEE Trans. Automatic Control 2006 · OpenReview

TL;DR

This paper introduces a novel framework for supervisory control of discrete-event systems (DES) that allows for "similar" behaviors to be tolerated, even if they are not strictly controllable. By incorporating metrics into traditional control theory, they define $\lambda$-controllability, a generalization of controllability that enables more flexible and intelligent system design.

What Problem Does This Paper Address?

Traditional supervisory control theory for DES, pioneered by Ramadge and Wonham, aims to ensure a system adheres to a predefined "legal" behavior by preventing it from exhibiting "uncontrollable" events. However, in many real-world scenarios, a system might exhibit behaviors that are not strictly legal but are "similar" to the desired ones. For instance, if a printer is unavailable, a computer job might try to use a disk instead – a similar, albeit not ideal, outcome. The challenge is to formally capture and manage this notion of "similarity" in control, allowing for more robust and adaptable systems when strict adherence to specifications is infeasible or overly conservative. This paper addresses this by proposing a way to quantify and utilize the similarity between system behaviors.

Methods

The core of this paper is the introduction of a metric-based approach to supervisory control.

  • Event Metrics: The authors start by assuming a metric $d$ is defined on the set of events $E$. This metric quantifies the similarity between individual events.
  • Baire Metric for Strings: This event metric is extended to strings (sequences of events) using the Baire metric. This metric prioritizes similarity at the beginning of strings, which is often crucial in DES.
  • Hausdorff Metric for Languages: The Baire metric is further used to define the Hausdorff metric on sets of strings (languages). This metric measures the similarity between two languages.
  • $\lambda$-Controllability: Based on the Hausdorff metric, the concept of $\lambda$-controllability is introduced. A language $K$ is $\lambda$-controllable if there exists a controllable language $K'$ such that the Hausdorff distance between $K$ and $K'$ is at most $\lambda$. This means $K$ is "close enough" to a controllable behavior.
  • Pareto Optimality for Realizations: The paper also addresses the problem of finding "optimal" realizations. Given a $\lambda$-controllable language $K$, an optimal realization $K'$ is one that maximizes the common behavior ($K' \cap K$) while minimizing the differing behavior ($K' \setminus K$). This is framed as a Pareto optimization problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and provides examples with custom-defined automata and metrics rather than using standard datasets.

Key Insights and Ideas

  • Generalizing Controllability: $\lambda$-controllability is a natural generalization of traditional controllability. When $\lambda=0$, it reduces to the standard definition. This provides a spectrum of controllability, allowing for more practical control objectives.
  • Metric as a Similarity Measure: The paper demonstrates how metrics on events can be systematically extended to measure similarity between complex system behaviors (languages). This opens doors for applying metric-based reasoning to control problems.
  • Balancing Desired and Tolerated Behavior: The concept of $\lambda$-controllability allows for a trade-off: if a desired behavior is not controllable, we can aim for a similar, controllable behavior. This is crucial for systems where strict adherence is impossible.
  • Pareto Optimality for Realizations: Finding a "best" realization is not just about being close to the desired language, but also about maximizing overlap and minimizing divergence. The Pareto optimality concept formalizes this trade-off.

Key Results

  • Necessary and Sufficient Condition for $\lambda$-Controllability: The paper provides a formal condition for a language to be $\lambda$-controllable, involving the $\lambda$-ball of the language.
  • Algorithm for $\lambda$-Controllability: An algorithm is presented to determine if a finite language is $\lambda$-controllable.
  • Supremal $\lambda$-Controllable Sublanguage: The existence and properties of the largest $\lambda$-controllable sublanguage are established.
  • Pareto Optimal Realization Algorithm: A constructive method is outlined to find a Pareto optimal realization from any given realization, demonstrating that such optimal solutions exist when the language is $\lambda$-controllable.

Limitations and Future Work

  • Algorithm for Finite Languages: The presented algorithm for computing $\lambda$-balls is currently limited to finite languages. Extending this to infinite languages is identified as a key area for future research.
  • Metric Choice Dependency: The choice of metric significantly impacts the notion of similarity. The paper uses Baire and Hausdorff metrics, which emphasize early events. Future work could explore other metrics (e.g., Hamming distance) that might be more suitable for different practical problems.
  • Observability and Nonblocking: The paper focuses on controllability. Incorporating other standard DES concepts like observability and nonblocking behavior within the $\lambda$-controllability framework is suggested for future work.

Summary updated

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 /spl lambda/-controllability, where /spl lambda/ indicates the similarity degree of two languages. A necessary and sufficient condition for a language to be /spl lambda/-controllable is provided. We then examine some properties of /spl lambda/-controllable languages and present an approach to optimizing a realization.
BibTeX
@article{cao2006similarity,
  author = {Yongzhi Cao and Mingsheng Ying},
  title = {{Similarity-based supervisory control of discrete-event systems}},
  journal = {IEEE Trans. Automatic Control},
  year = {2006},
  url = {https://openreview.net/forum?id=1EdMuwhl8N},
}
Figure