Affiliations: Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan 106, R.O.C. yen@cc.ee.ntu.edu.tw
Note: [] Supported in part by NSC Grant NSC-97-2221-E-002-095-MY3, Taiwan. Address for correspondence: Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan 106, R.O.C.
Abstract: Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems.
Keywords: Forbidden-state avoidance, Petri net, probabilistic controlled transition system, reachability
