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:
- 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).
- Disjunctive Architecture: Local supervisors are "anti-permissive." An event is enabled if at least one local supervisor enables it (an OR-like fusion rule).
- 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