×

Methods for the estimation of the size of lookahead tree state-space. (English) Zbl 1268.93102

Summary: Limited lookahead supervision is a discrete-event systems framework in which control decisions are made by looking at finite-step projections of the behaviour of the system’s underlying automata. Projected system behaviour is represented as a lookahead tree with some depth limit decided on by the user. It can be difficult to strike a balance between the complexities associated with storing and analyzing the trees and the amount of information available to make decisions, both of which increase with depth. This paper considers the problem of accurately estimating the state space of lookahead trees with the intent of simplifying the process of determining a favourable depth to use. Although the estimation methods presented here apply cleanly to only certain kinds of automata, they also shed light onto the more complex behaviour of the others.

MSC:

93C65 Discrete event control/observation systems
93A15 Large-scale systems
68Q80 Cellular automata (computational aspects)

Software:

UMDES; SPIN
Full Text: DOI

References:

[1] Auer A, Dingel J, Rudie K (2009) Concurrency control generation for dynamic threads using discrete-event systems. In: Forty-seventh annual Allerton conference, Monticello, Illinois, USA, 30 Sept-2 Oct, pp 927-934
[2] Barkaoui K, Pradat-Peyre JF (1996) On liveness and controlled siphons in Petri nets. Lect Notes Comput Sci 1091:57-72 · Zbl 1418.68131 · doi:10.1007/3-540-61363-3_4
[3] Brunsch T, Rudie K (2008) Discrete-event systems model of an outbreak response. In: American control conference, Seattle, Washington, USA, 11-13 June, pp 1709-1714 · Zbl 0618.93033
[4] Cassandras CG, Lafortune S (2008) Introduction to discrete event systems, 2nd edn. Springer Publishers · Zbl 1165.93001
[5] Chung SL, Lafortune S, Lin F (1992) Limited lookahead policies in supervisory control of discrete event systems. IEEE Trans Automat Control 37(12):1921-1935 · Zbl 0773.93004 · doi:10.1109/9.182478
[6] Chung SL, Lafortune S, Lin F (1993) Recursive computation of limited lookahead supervisory controls for discrete event systems. Discrete Event Dyn Syst: Theory Appl 1(1):71-100 · Zbl 0772.93001 · doi:10.1007/BF01439177
[7] Chung SL, Lafortune S, Lin F (1994) Supervisory control using variable lookahead policies. Discrete Event Dyn Syst: Theory Appl 4(3):237-268 · Zbl 0808.93001 · doi:10.1007/BF01438709
[8] Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge, MA · Zbl 1047.68161
[9] Friedberg SH, Insel AJ, Spence LE (2003) Linear algebra. Prentice Hall, Englewood Cliffs, NJ
[10] Gawrychowski P, Krieger D, Rampersad N, Shallit J (2008) Finding the growth rate of a regular or context-free language in polynomial time. Lect Notes Comput Sci 5257:339-358 · Zbl 1161.68528 · doi:10.1007/978-3-540-85780-8_27
[11] Grigorov L, Rudie K (2006) Near-optimal online control of dynamic discrete-event systems. Discrete Event Dyn Syst 16(4):419-449 · Zbl 1103.93038 · doi:10.1007/s10626-006-0020-x
[12] Holzmann GJ (2011) The SPIN model checker: primer and reference manual. Addison-Wesley, Reading, MA
[13] Java Pathfinder (2011) NASA Ames Research Center. http://babelfish.arc.nasa.gov/trac/jpf. Accessed on 24 Oct 2011
[14] Kumar R, Cheung HM, Marcus SI (1998) Extension based limited lookahed supervision of discrete event systems. Automatica 34(11):1327-1344 · Zbl 0938.93045 · doi:10.1016/S0005-1098(98)00077-6
[15] Meyer C (2000) Matrix analysis and applied linear algebra. SIAM, Philadelphia, PA · Zbl 0962.15001
[16] Ramadge PJ, Wonham WM (1987) Supervisory control of a class of discrete event processes. SIAM J Control Optim 25(1):206-230 · Zbl 0618.93033 · doi:10.1137/0325013
[17] Rosen KH (2007) Discrete mathematics and its applications, 6th edn. McGraw-Hill, New York
[18] Rudie K (2006) The integrated discrete-event systems tool. In: Proceedings of the 8th international Workshop on Discrete Event Systems (WODES), Ann Arbor, MI, 10-12 July 2006, pp 394-395
[19] Shallit J (2008) The Frobenius problem and its generalizations. Lect Notes Comput Sci 1091:57-72 · Zbl 1161.11319
[20] Whittaker S-J, Rudie K, McLellan J, Haar S (2009) Choice-point nets: a discrete-event modelling technique for analyzing health care protocols. In: Forty-seventh annual Allerton conference, Monticello, Illinois, USA, 30 Sept-2 Oct 2009, pp 652-659 · Zbl 1103.93038
[21] Whittaker S-J, Rudie K, McLellan J, Haar S (2010) Augmenting Petri nets to model health-care protocols. In: Proceedings of the international workshop on discrete event systems (WODES), Berlin, 30 Aug-1 Sept 2010, pp 341-346 · Zbl 0938.93045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.