CENTRALIZED AND DISTRIBUTED ALGORITHMS FOR ONLINE SYNTHESIS OF MAXIMAL CONTROL POLICIES UNDER PARTIAL OBSERVATION

This paper deals with the on-line control of partially observed discre te event systems (DES). The goal is to restrict the behavior of the sy stem within a prefix-closed legal language while accounting for the pr esence of uncontrollable and unobservable events. In the spirit of rec ent work on the on-line control of partially observed DES (Heymann and Lin 1994) and on variable lookahead control of fully observed DES (Be n Hadj-Alouane et al. 1994c), we propose an approach where, following each observable event, a control action is computed on-line using an a lgorithm of linear worst-case complexity. This algorithm, called VLP-P O, has the following additional properties: (i) the resulting behavior is guaranteed to be a maximal controllable and observable sublanguage of the legal language; (ii) different maximals may be generated by va rying the priorities assigned to the controllable events, a parameter of VLP-PO; (iii) a maximal containing the supremal controllable and no rmal sublanguage of the legal language can be generated by a proper se lection of controllable event priorities; and (iv) no off-line calcula tions are necessary. We also present a parallel/distributed version of the VLP-PO algorithm called DI-VLP-PO. This version uses several comm unicating agents that simultaneously run (on-line) identical versions of the algorithm but on possibly different parts of the system model a nd the legal language, according to the structural properties of the s ystem and the specifications. While achieving the same behavior as VLO -PO, DI-VLP-PO runs at a total complexity (for computation and communi cation) that is significantly lower than its sequential counterpart.