Synthesis Method for Hierarchical Interface-based Supervisory Control

Pengcheng Dai, M.A.Sc. Thesis, Dept. of Computing and Software, McMaster University, April 2006.


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.

Currently, a designer must create the supervisors for a HISC system himself, and then verify that they satisfy the HISC conditions. In this thesis, we develop a synthesis method that respects the HISC hierarchical structure. We replace the supervisor for each level by a corresponding specification DES. We then do a per level synthesis to 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 present algorithms that implement the fixpoint operators. We present a complexity analysis for the algorithms and show that they potentially offer significant improvement over the monolithic approach.

A large manufacturing system example (estimated worst case state space on the order of 10^22) extended from the AIP example is discussed. A software tool for synthesis and verification of HISC systems using our approach was also developed.


Shift+click to download: PDaiMASCthesis.pdf (1.5MB PDF).