Complexity reduction in discrete event systems
Walter Murray Wonham, Rajinderjeet Singh Minhas · 2002
The aim of this thesis is to explore new ways to achieve complexity reduction in discrete event systems (DES). We present three different ways of reducing complexity. First, we present a symbolic supervisory control design method for composite systems such that the complete state space never needs to be computed. Instead of a supervisor implemented by a static lookup table, we provide a function that can be efficiently and dynamically computed at each state to determine the control action. This symbolic function can be suitably modified to ensure that the system under control is free of deadlocks. Secondly, we present a heuristic algorithm to reduce the size of a (static) supervisor. Our symbolic supervision scheme is not able to guarantee non-blocking behaviour in the system under control. So to ensure non-blockingness it may be necessary to use a lookup table. Finding the smallest lookup table for a given control task is an NP-hard problem. We propose a greedy supervisor reduction algorithm based on the concept of control covers. This algorithm seems to work quite well in a large number of cases. Finally, we present a compact model of timed discrete event systems (TDES). We use local timers at each state of the TDES to model the passage of time. This model is quite robust to changes in time scale and is closed under control.