Control consistency and hierarchically accelerated dynamic programming
Gang Shen, Peter E. Caines · 2002
The concept of control consistency (CC) for pairs of hierarchically ordered finite state machines,, is introduced which is analogous to that given by Wong and Wonham (1992) for supervisory control. It is shown that, when CC holds, the dynamics of M/sup hi/ are given by the dynamical consistency (DC) relation associated with a partition /spl pi/ of the states of M=M/sup lo/. Conversely, subject to the in-block controllability (IBC) condition, if the dynamics of M/sub hi/ are given by the DC relation, then CC holds. For a hierarchy with a given low level cost function d on transition events in M, we introduce the so-called hierarchically accelerated dynamic programming (HADP) procedure for DP problems posed in M: for a two level hierarchy, the HADP algorithm first solves a DP problem given in terms of a certain high level cost function (D) on controlled events in M/sup hi/ and then solves a restricted DP problem (with respect to d) within the resulting (D-optimal) connected sequence of high level blocks. Conditions are given which ensure that the high level path generated by HADP contains a globally d-optimal low level path. Finally, the class of so-called broken Manhattan grid problems is used to generate examples.