Click on a search word OR use the drop-down choices to search for a paper.
2008
Pantelic, Vera; Postma, Steven; Lawford, Mark
SQRL Report No. 21 ” Supervisory Control of Probabilistic Discrete Event Systems.” Technical Report
2008.
Abstract | Links | BibTeX | Tags: discrete-event systems, supervisory control
@techreport{Pantelic2008,
title = {SQRL Report No. 21 ” Supervisory Control of Probabilistic Discrete Event Systems.”},
author = {Vera Pantelic and Steven Postma and Mark Lawford},
url = {http://www.cas.mcmaster.ca/sqrl/papers/SQRLreport21.pdf},
year = {2008},
date = {2008-07-15},
abstract = {This paper considers supervisory control of probabilistic discrete event systems (PDES). PDESs are modelled as generators of probabilistic languages. The supervisory control problem considered is to find, if possible, a supervisor under whose control the behaviour of a plant is identical to a given probabilistic specification. The probabilistic supervisors we employ are a generalization of the deterministic ones previously employed in the literature. At any state, the supervisor enables/disables events with certain probabilities. Necessary and sufficient conditions for the existence of such a supervisor, and an algorithm for its computation are presented.},
keywords = {discrete-event systems, supervisory control},
pubstate = {published},
tppubtype = {techreport}
}
2007
Leduc, Ryan J; Dai, Pengcheng; Song, Raoguang
SQRL Report No. 46 “Synthesis Method for Hierarchical Interface-Based Supervisory Control.” Technical Report
2007.
Abstract | Links | BibTeX | Tags: automata, discrete-event systems, formal methods, hierarchical systems, interfaces, supervisory control, synthesis
@techreport{LeducDaiSong2007,
title = {SQRL Report No. 46 “Synthesis Method for Hierarchical Interface-Based Supervisory Control.”},
author = {Ryan J Leduc and Pengcheng Dai and Raoguang Song},
url = {http://www.cas.mcmaster.ca/sqrl/papers/SQRLreport46.pdf},
year = {2007},
date = {2007-08-15},
abstract = {Hierarchical Interface-Based Supervisory Control (HISC) decomposes a discrete-event system (DES) into a high-level subsystem which communicates with n >= 1 low-level subsystems, through separate interfaces. It provides a set of local conditions that can be used to verify global conditions such as nonblocking and controllability such that the complete system model never needs to be constructed.
Currently, a designer must create the supervisors himself and then verify that they satisfy the HISC conditions. In this paper, we develop a synthesis method that can take advantage of the HISC structure. We replace the supervisor for each level by a corresponding specification DES. We then construct for each level a maximally permissive supervisor that satisfies the corresponding HISC conditions.
We define a set of language based fixpoint operators and show that they compute the required level-wise supremal languages. We then discuss the complexity of our algorithms and show that they potentially offer significant savings over the monolithic approach. We also briefly discuss a symbolic HISC verification and synthesis method using Binary Decision Diagrams, that we have also developed.
A large manufacturing system example (worst case state space on the order of 10^30) extended from the AIP example is briefly discussed. The example showed that we can now handle a given level with a statespace as large as 10^15 states, using less than 160MB of memory. This represents a significant improvement in the size of systems that can be handled by the HISC approach. A software tool for synthesis and verification of HISC systems using our approach was also developed.},
keywords = {automata, discrete-event systems, formal methods, hierarchical systems, interfaces, supervisory control, synthesis},
pubstate = {published},
tppubtype = {techreport}
}
Currently, a designer must create the supervisors himself and then verify that they satisfy the HISC conditions. In this paper, we develop a synthesis method that can take advantage of the HISC structure. We replace the supervisor for each level by a corresponding specification DES. We then construct for each level a maximally permissive supervisor that satisfies the corresponding HISC conditions.
We define a set of language based fixpoint operators and show that they compute the required level-wise supremal languages. We then discuss the complexity of our algorithms and show that they potentially offer significant savings over the monolithic approach. We also briefly discuss a symbolic HISC verification and synthesis method using Binary Decision Diagrams, that we have also developed.
A large manufacturing system example (worst case state space on the order of 10^30) extended from the AIP example is briefly discussed. The example showed that we can now handle a given level with a statespace as large as 10^15 states, using less than 160MB of memory. This represents a significant improvement in the size of systems that can be handled by the HISC approach. A software tool for synthesis and verification of HISC systems using our approach was also developed.
Leduc, Ryan
SQRL Report No. 44 “Hierarchical Interface-Based Supervisory Control with Data Events.” Technical Report
2007.
Abstract | Links | BibTeX | Tags: discrete-event systems, supervisory control
@techreport{Leduc2007,
title = {SQRL Report No. 44 “Hierarchical Interface-Based Supervisory Control with Data Events.”},
author = {Ryan Leduc},
url = {http://www.cas.mcmaster.ca/sqrl/papers/SQRLreport44.pdf},
year = {2007},
date = {2007-07-15},
abstract = {Hierarchical Interface-Based Supervisory Control (HISC) decomposes a discrete-event system (DES) into a high-level subsystem which communicates with n >= 1 low-level subsystems, through separate interfaces which restrict the interaction of the subsystems. It provides a set of local conditions that can be used to verify global conditions such as nonblocking and controllability. As each clause of the definition can be verified using a single subsystem, the complete system model never needs to be stored in memory, offering potentially significant savings in computational resources.
In this report, we extend the range of the behavior of low-levels that interfaces can model by adding a new type of event, low data events, and by relaxing some restrictions in the HISC definitions. This now allows us to have (1) request events that don't need to be followed by an answer event, (2) to start a low-level on a task and then poll it for completion, (3) to be able to send additional commands while a low-level is already processing a command (4) to model low-levels that behave as buffers, and (5) to allow unsolicited information (status etc.) to be sent up from a low-level.
Besides greatly enriching the behavior that can be modelled as interfaces and thus expanding the systems that HISC can effectively be applied to, the changes can enable behavior to be moved from the high-level to the low-levels. We demonstrate this when we discuss the application of our method to a large manufacturing system example based upon the AIP example, where we saw a 3.4 times reduction in computation time and a 6.5 times reduction in memory use. This helps prevent the high-level from growing too large, allowing the HISC method to apply to larger systems.},
keywords = {discrete-event systems, supervisory control},
pubstate = {published},
tppubtype = {techreport}
}
In this report, we extend the range of the behavior of low-levels that interfaces can model by adding a new type of event, low data events, and by relaxing some restrictions in the HISC definitions. This now allows us to have (1) request events that don't need to be followed by an answer event, (2) to start a low-level on a task and then poll it for completion, (3) to be able to send additional commands while a low-level is already processing a command (4) to model low-levels that behave as buffers, and (5) to allow unsolicited information (status etc.) to be sent up from a low-level.
Besides greatly enriching the behavior that can be modelled as interfaces and thus expanding the systems that HISC can effectively be applied to, the changes can enable behavior to be moved from the high-level to the low-levels. We demonstrate this when we discuss the application of our method to a large manufacturing system example based upon the AIP example, where we saw a 3.4 times reduction in computation time and a 6.5 times reduction in memory use. This helps prevent the high-level from growing too large, allowing the HISC method to apply to larger systems.
2003
Leduc, RJ; Brandin, BA; Lawford, Mark; Wonham, WM
SQRL Report No. 12 “Hierarchical Interface-based Supervisory Control: Part I: Serial Case” Technical Report
2003.
Abstract | Links | BibTeX | Tags: discrete-event systems, supervisory control
@techreport{Leduc2003,
title = {SQRL Report No. 12 “Hierarchical Interface-based Supervisory Control: Part I: Serial Case”},
author = {RJ Leduc and
BA Brandin and
Mark Lawford and
WM Wonham },
url = {http://www.cas.mcmaster.ca/sqrl/papers/serialJournal.pdf},
year = {2003},
date = {2003-08-15},
abstract = {In this paper we present a hierarchical method that decomposes a system into two subsystems, and restricts the interaction of the subsystems by means of an interface. We present definitions for two types of interfaces (represented as discrete-event systems (DES)), and define a set of interface consistency properties that can be used to verify if a DES is nonblocking and controllable. Each clause of the definitions can be verified using only one of the two subsystems; thus the complete system model never needs to be constructed, offering potentially significant savings in computational effort. Additionally, the development of clean interfaces facilitates re-use of the component subsystems. Finally, we examine a simple example to illustrate the method.},
keywords = {discrete-event systems, supervisory control},
pubstate = {published},
tppubtype = {techreport}
}
Bourdon, Sean E.; Lawford, Mark; Wonham, W. Murray
SQRL Report No. 9 “Robust Nonblocking Supervisory Control of Discrete-Event Systems” Technical Report
2003.
Abstract | Links | BibTeX | Tags: discrete-event systems, robustness
@techreport{Bourdon2003,
title = {SQRL Report No. 9 “Robust Nonblocking Supervisory Control of Discrete-Event Systems”},
author = {Sean E. Bourdon and Mark Lawford and W. Murray Wonham },
url = {http://www.cas.mcmaster.ca/sqrl/papers/robustness.pdf},
year = {2003},
date = {2003-02-15},
abstract = {In the first part of this paper, we generalize a notion of robust supervisory control to deal with marked languages. We show how to synthesize a supervisor to control a family of plant models, each with its own specification. The solution we obtain is the most general in that it provides the closest approximation to the supremal controllable sublanguage for each plant/specification pair. The second part of this paper extends these results to deal with timed discrete-event systems.},
keywords = {discrete-event systems, robustness},
pubstate = {published},
tppubtype = {techreport}
}