Centralized and distributed algorithms for on-line synthesis of maximal control policies under partial observation

This paper deals with the on-line control of partially observed discrete event systems (DES). The goal is to restrict the behavior of the system within a prefix-closed legal language while accounting for the presence ofuncontrollable andunobservable events. In the spirit of recent work on the on-line control of partially observed DES (Heymann and Lin 1994) and on variable lookahead control of fully observed DES (Ben Hadj-Alouane et al. 1994c), we propose an approach where, following each observable event, a control action is computed on-line using an algorithm oflinear worst-case complexity. This algorithm, calledVLP-PO, has the following additional properties: (i) the resulting behavior is guaranteed to be amaximal controllable and observable sublanguage of the legal language; (ii) different maximals may be generated by varying the priorities assigned to the controllable events, a parameter ofVLP-PO; (iii) a maximal containing the supremal controllable and normal sublanguage of the legal language can be generated by a proper selection of controllable event priorities; and (iv) no off-line calculations are necessary. We also present a parallel/distributed version of theVLP-PO algorithm calledDI-VLP-PO. This version uses several communicating agents that simultaneously run (on-line) identical versions of the algorithm but on possibly different parts of the system model and the legal language, according to the structural properties of the system and the specifications. While achieving the same behavior asVLO-PO, DI-VLP-PO runs at a total complexity (for computation and communication) that is significantly lower than its sequential counterpart.