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.