TITLE: Designing compact and maximally permissive liveness-enforcing supervisors for complex resource allocation systems through classification theory

SPEAKER: Professor Spiridon Reveliotis

ABSTRACT:

The problem of liveness-enforcing supervision -- or, deadlock avoidance -- for complex resource allocation systems (RAS) is a well-documented problem in supervisory control theory. Most of the past research on it has acknowledged the fact that the maximally permissive liveness-enforcing supervisor (LES) possesses super-polynomial complexity for most RAS classes, and therefore, it has resorted to solutions that trade off maximal permissiveness for computational tractability. In the presented work, we distinguish between the "off-line" and the "on-line" computation that is required for the effective implementation of the maximally permissive LES, and we seek to develop representations of the maximally permissive LES that require "minimal" on-line computation.

The particular representation that we adopt is that of a compact classifier that will effect the underlying dichotomy of the reachable state space into safe and unsafe subspaces. Through a series of reductions of the derived classification problem, we are able to attain extensive reductions in, both, (i) the computational complexity of the off-line task of the construction of the sought classifier, and (ii) the complexity involved in the on-line classification process itself. We formally establish completeness and optimality properties for the proposed design procedures. We also offer heuristics that, if necessary, can alleviate the computational effort that is necessary for the construction of the sought classifier. Finally, we demonstrate the efficacy of the developed approaches through a series of computational experiments. To the best of our knowledge, these experiments also establish the ability of the proposed methodology to effectively compute tractable implementations of the maximally permissive LES for problem instances significantly beyond the capacity of any other approach currently available in the literature.