Control consistency and hierarchically accelerated dynamic programming

The concept of control consistency (CC) for pairs of hierarchically ordered finite state machines, ⟨M^lo, M ^hi⟩, 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^hi are given by the dynamical consistency (DC) relation associated with a partition π of the states of M=M^lo. Conversely, subject to the in-block controllability (IBC) condition, if the dynamics of M_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^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