On the complexity of supervisory control design in the RW framework
Authors:
- W.M. WonhamWWW.M. Wonham
- 1 January 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
- Vol. 30 (5) , 643-652
Abstract
The time complexity of supervisory control design for a general class of problems is studied. It is shown to be very unlikely that a polynomial-time algorithm can be found when either (1) the plant is composed of m components running concurrently or (2) the set of legal behaviors is given by the intersection of n legal specifications. That is to say, in general, there is no way to avoid constructing a state space which has size exponential in m+n. It is suggested that, rather than discouraging future work in the field, this result should point researchers to more fruitful directions, namely, studying special cases of the problem, where certain structural properties possessed by the plant or specification lend themselves to more efficient algorithms for designing supervisory controls. As no background on the subject of computational complexity is assumed, we have tried to explain all the borrowed material in basic terms, so that this paper may serve as a tutorial for a system engineer not familiar with the subject.Keywords
This publication has 6 references indexed in Scilit:
- On the control of discrete-event dynamical systemsMathematics of Control, Signals, and Systems, 1989
- Some tractable supervisory control problems for discrete-event systems modeled by Buchi automataIEEE Transactions on Automatic Control, 1989
- Modular supervisory control of discrete-event systemsMathematics of Control, Signals, and Systems, 1988
- On the Supremal Controllable Sublanguage of a Given LanguageSIAM Journal on Control and Optimization, 1987
- Supervisory Control of a Class of Discrete Event ProcessesSIAM Journal on Control and Optimization, 1987
- The complexity of theorem-proving procedures1971