Abstract
In a discrete-event system (DES), multiple sensors generate multiple events that may occur in parallel. Traditional modeling approaches that interleave these events lead to state explosion. This paper proposes a new model—a generator with multi-threads—that produces structured languages incorporating parallel and alternative logic. By defining structured controllability and proving a supervisor existence theorem, the author provides a method for optimal supervision that avoids state explosion. The theory is validated through examples and a PLC implementation, demonstrating its practical utility for complex industrial systems.
The Challenge of Parallelism in DES
Traditional Discrete-Event Systems (DES) theory, pioneered by Wonham and Ramadge, typically assumes a single-event-at-a-time paradigm. In modern "Multi-Sensor and Multi-State" (MSMS) environments, however, sensors often trigger events simultaneously or in independent parallel branches.
To model such systems using classical tools, engineers must enumerate every possible sequence of these parallel events, a process known as interleaving. As shown in Figure 1, even a small number of events can result in multiple valid schedules. When scaled to industrial levels, this leads to the state explosion problem, where the state space grows exponentially, making system modeling and supervisor design nearly impossible.
Structured Languages and Multi-Threaded Modeling
To address these limitations, the paper proposes shifting from linear strings to structured languages. This approach incorporates logical operators directly into the language definition:
- Alternative Structures (+): Representing an "OR" choice between different event sequences.
- Parallel Structures (||): Representing an "AND" relationship where multiple threads run independently and concurrently.
The system is formally defined as a 5-tuple generator with multi-threads $G = (Q, \Sigma, \Delta, Q_o, Q_m)$. In this model, the system state is represented as a vector of current states across all active threads. This allows the model to reflect the physical reality of multi-sensor hardware more naturally and succinctly.
Supervisory Control Theory for Multi-Threads
The paper extends classical Supervisory Control Theory (SCT) to this new framework. Key technical contributions include:
- Structured Controllability: A definition of controllability tailored for structured languages, ensuring that uncontrollable events do not force the system into undesired states.
- Supervisor Existence Theorem: A proof that a nonblocking supervisor exists for a given specification if and only if the target structured language is controllable and closed relative to the system's behavior.
- Optimal Synthesis: A method for deriving the most permissive supervisor that satisfies the given specifications while maintaining system safety.
Practical Validation and Implementation
The theory was tested on two primary examples: a parallel process plant and a factory cell consisting of two machines and a shared buffer. The results showed that a single structured expression could represent over a dozen interleaved linear strings, significantly reducing model complexity.
Furthermore, the author implemented the supervisor for the parallel process plant on a Siemens S7-300 PLC using the GRAPH (Sequential Function Chart) language. This practical demonstration proved that the multi-thread approach is not only theoretically sound but also "convenient and natural" for implementation on standard industrial controllers.
Conclusion
By treating parallel sequences as first-class "threads" rather than interleaved strings, this research provides a robust solution to the state explosion problem in DES. The use of structured languages allows for more readable, maintainable, and computationally efficient models, paving the way for more advanced automation in Industry 4.0 environments.
Summary updated