Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McMaster University

$23,000.00

Complexity and Implementation for Discrete-Event Systems

FY 2020-21

Summary
Discrete-Event Systems (DES) model a system's behaviour as automata, and use this to formally verify properties such as controllability (will the system stay within desired behaviour) and nonblocking (a form of deadlock detection). Application areas include manufacturing, communication, and transport systems, as well as automotive applications. The long-term goal of this project is to improve the adoption of Discrete-Event Systems by industry. The short-term objectives we will focus on in this proposal are 1) simplifying supervisor implementation and 2) design, and 3) improving scalability. The short-term objective of simplifying implementation will be addressed by building upon the Sampled-Data (SD) supervisory control work of Wang. This method addresses a number of concurrency and timing issues involved in converting a Timed DES (TDES) supervisor into an implementation as a Moore Finite State Machine (FSM). To make this translation possible, a number of SD properties must be satisfied, many of which may not be easy to address by hand, nor specified based solely on safety and deadlock concerns. To make all steps of the translation easy and automatic, we will develop a synthesis method and a discrete optimization approach that will resolve any remaining control decisions. This will provide a key missing step that will not only provide a higher quality result, but remove a difficult and time consuming process from the design. The short-term objective of simplifying supervisor design will be addressed by creating a method to allow the designer to specify controllers directly as Moore finite state machine (FSM), and then automatically convert the FSM (a common design format for engineers) into equivalent supervisors for verification. As a major barrier to the adoption of formal methods is the lack of users trained in the area, this should make this approach much more accessible to non-experts. The short-term objective of improving scalability will be primarily addressed by leveraging the Hierarchical Interface-based Hierarchical Supervisory Control (HISC) approach of Leduc. This project will start with extending timed DES to HISC. This will allow TDES to be applied to much larger systems, making the method more useful to industry, and lay the foundation for extending the sampled-data method to HISC as well. We will also investigate improving the scalability of fault diagnosis and the fault-tolerant supervisors. These topics were chosen as the ability to detect and handle faults is of wide interest to industry, so improving the size of systems they can handle is highly desirable. For fault diagnosis, a method to manually design diagnosers (as opposed to the current synthesis-based approach) will be developed that should allow for significant reduction in algorithm complexity. For fault-tolerance, we will adapt the approach of Leduc to make use of the HISC infrastructure.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-05267
Name nom
Leduc, Ryan
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2017
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Installment
inst:4-5
Partie
2
Nb partie
5
Application title
Complexity and Implementation for Discrete-Event Systems
Keyword
NSERC
Application summary
Discrete-Event Systems (DES) model a system's behaviour as automata, and use this to formally verify properties such as controllability (will the system stay within desired behaviour) and nonblocking (a form of deadlock detection). Application areas include manufacturing, communication, and transport systems, as well as automotive applications. The long-term goal of this project is to improve the adoption of Discrete-Event Systems by industry. The short-term objectives we will focus on in this proposal are 1) simplifying supervisor implementation and 2) design, and 3) improving scalability. The short-term objective of simplifying implementation will be addressed by building upon the Sampled-Data (SD) supervisory control work of Wang. This method addresses a number of concurrency and timing issues involved in converting a Timed DES (TDES) supervisor into an implementation as a Moore Finite State Machine (FSM). To make this translation possible, a number of SD properties must be satisfied, many of which may not be easy to address by hand, nor specified based solely on safety and deadlock concerns. To make all steps of the translation easy and automatic, we will develop a synthesis method and a discrete optimization approach that will resolve any remaining control decisions. This will provide a key missing step that will not only provide a higher quality result, but remove a difficult and time consuming process from the design. The short-term objective of simplifying supervisor design will be addressed by creating a method to allow the designer to specify controllers directly as Moore finite state machine (FSM), and then automatically convert the FSM (a common design format for engineers) into equivalent supervisors for verification. As a major barrier to the adoption of formal methods is the lack of users trained in the area, this should make this approach much more accessible to non-experts. The short-term objective of improving scalability will be primarily addressed by leveraging the Hierarchical Interface-based Hierarchical Supervisory Control (HISC) approach of Leduc. This project will start with extending timed DES to HISC. This will allow TDES to be applied to much larger systems, making the method more useful to industry, and lay the foundation for extending the sampled-data method to HISC as well. We will also investigate improving the scalability of fault diagnosis and the fault-tolerant supervisors. These topics were chosen as the ability to detect and handle faults is of wide interest to industry, so improving the size of systems they can handle is highly desirable. For fault diagnosis, a method to manually design diagnosers (as opposed to the current synthesis-based approach) will be developed that should allow for significant reduction in algorithm complexity. For fault-tolerance, we will adapt the approach of Leduc to make use of the HISC infrastructure.