Decentralized Supervisory Control of Discrete Event Systems for Bisimulation Equivalence

Yajuan Sun, Hai Lin, Ben M. ChenarXiv 2011 · arXiv

Abstract

This paper addresses a significant gap in control theory by extending decentralized supervisory control for Discrete Event Systems (DES) to bisimulation equivalence. While traditional control focuses on language equivalence—ensuring a system produces the correct sequences of events—it often ignores the "branching" choices available to a system at any given state. We present a formal framework and the necessary and sufficient conditions to ensure that a group of local controllers can make a complex, nondeterministic system behave exactly like a specification, preserving both action sequences and decision-making structures.

Introduction

In the management of Discrete Event Systems (DES)—such as manufacturing lines, traffic control networks, and communication protocols—the goal is typically to ensure the system adheres to a specific set of allowed behaviors. Historically, researchers have relied on language equivalence to verify that a controlled system matches its specification.

However, language equivalence has a critical limitation: it does not account for when a choice is made, only what strings are eventually produced. In decentralized systems, where multiple agents operate with partial views of the system, this branching behavior is vital. If a system branches into a state where a necessary action is no longer possible, language equivalence may fail to detect the error, whereas bisimulation equivalence—a much stricter, finer-grained metric—will. While centralized control for bisimulation is well-understood, achieving this in a decentralized architecture remained an unsolved challenge until this research.

Proposed Framework and Architectures

The authors propose a novel automata-based framework where the plant, the specification, and the supervised system are all modeled as nondeterministic automata. To address the decentralized nature of the problem, they develop three distinct control architectures based on how local decisions are fused:

  1. Conjunctive Architecture: Local supervisors are "permissive." An event is only enabled globally if all relevant local supervisors agree to enable it (an AND-like fusion rule).
  2. Disjunctive Architecture: Local supervisors are "anti-permissive." An event is enabled if at least one local supervisor enables it (an OR-like fusion rule).
  3. General Architecture: A hybrid approach where events are partitioned into those enabled by default and those disabled by default.

For each architecture, the authors derive necessary and sufficient conditions (existence theorems) to determine if a set of decentralized supervisors can achieve the desired bisimulation. They also provide a synthesis method—a blueprint for constructing these supervisors when the conditions are met.

Key Insights

The Importance of Branching

For systems requiring high-level logic (such as those defined by CTL* or mu-calculus), language equivalence is insufficient. Bisimulation is required to guarantee that the "logic" of the specification is preserved. The paper demonstrates that decentralized control for bisimulation is strictly more difficult than for language equivalence; a system might produce the correct strings but fail to manage branching points, thus failing the bisimulation standard.

Embracing Nondeterminism

Unlike many previous works that require deterministic plants, this framework embraces nondeterminism. This is a crucial advancement because system abstractions and unmodeled dynamics in real-world engineering often manifest as nondeterministic behavior.

Architecture Hierarchy

The paper proves that the Conjunctive and Disjunctive architectures are special cases of the General Architecture, mirroring the structure of traditional language-based DES theory and providing a unified view of decentralized bisimulation control.

Results and Validation

The research provides rigorous mathematical existence theorems that extend concepts like C&P and D&A co-observability. While the authors show that verifying these conditions has exponential complexity ($O(|X|^2 2^{|Q|^2})$), they note this is consistent with the inherent complexity of bisimulation problems and remains practical for many engineering applications.

The findings were validated using illustrative manufacturing examples, including a system with three robots and multiple storage stations. These examples demonstrate how to construct conjunctive supervisors to ensure robots return parts to correct locations and highlight cases where bisimulation control is possible even when traditional language-based co-observability fails.

Conclusion and Future Work

This work establishes the first formal framework for decentralized bisimulation control. Future research directions include the design of nondeterministic supervisors for nondeterministic plants, which may offer more flexibility than the current deterministic supervisor model. Additionally, the authors suggest investigating "supremal/infimal subspecifications" to determine the closest possible behavior when perfect bisimulation cannot be achieved.

Summary updated

Abstract

In decentralized systems, branching behaviors naturally arise due to communication, unmodeled dynamics and system abstraction, which can not be adequately captured by the traditional sequencing-based language equivalence. As a finer behavior equivalence than language equivalence, bisimulation not only allows the full set of branching behaviors but also explicitly specifies the properties in terms of temporal logic such as CTL* and mu-calculus. This observation motivates us to consider the decentralized control of discrete event systems (DESs) for bisimulation equivalence in this paper, where the plant and the specification are taken to be nondeterministic and the supervisor is taken to be deterministic. An automata-based control framework is formalized, upon which we develop three architectures with respect to different decision fusion rules for the decentralized bisimilarity control, named a conjunctive architecture, a disjunctive architecture and a general architecture. Under theses three architectures, necessary and sufficient conditions for the existence of decentralized bisimilarity supervisors are derived respectively, which extend the traditional results of supervisory control from language equivalence to bisimulation equivalence. It is shown that these conditions can be verified with exponential complexity. Furthermore, the synthesis of bisimilarity supervisors is presented when the existence condition holds.
BibTeX
@misc{sun2011decentralized,
  author = {Yajuan Sun and Hai Lin and Ben M. Chen},
  title = {{Decentralized Supervisory Control of Discrete Event Systems for Bisimulation Equivalence}},
  year = {2011},
  eprint = {1112.3555},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1112.3555},
}
Figure