Approximating Minimal Communicated Event Sets for Decentralized Supervisory Control

This paper discusses the problem of selecting the minimal set of events to be communicated between decentralized supervisory controllers in order for the behavior of a controller system to match a given specification. This optimization problem is known to be computationally difficult, so this paper discusses the problem of approximating this set of communicated events. It is shown how the communication minimization problem is related to a centralized supervisory control minimal sensor selection problem and a special type of directed graph st-cut problem. Polynomial time algorithms to approximate solutions to these problems most likely do not exist (using worst-case analysis), but several effective heuristic approximation methods are shown for these problems that work well for average cases.