Next:Hierarchical Supervisory Control Theory Up:Discrete and Hybrid Systems Previous:Discrete and Hybrid Systems

Hierarchically Accelerated Dynamic Programming

The HADP methodology is based on the theory of state aggregation (or abstraction) originally developed by Y.J. Wei, P.E. Caines and associates in CIM. This technique aggregates the states of a controlled system by use of the so-called dynamical consistency relation between blocks of states in a partition of the state space. The DC relation defines high level controlled events in such a way that all high level plans conceived in terms of the DC events (on the resulting so-called high level partition machine) must necessarily be realizable in the low level base machine. By using hierarchical systems whose successive layers are related in this manner, efficient dynamic programming (DP) algorithms have been designed called Hierarchically Accelerated Dynamic Programming (HADP) algorithms. At the cost of a degree of sub-optimality (which may be estimated by application of the developing HADP theory), these algorithms show very significant acceleration with respect to any conventional method. It is to be noted that any advances in DP methodology for single layer systems may be incorporated into the single layer subalgorthims of the HADP technique; hence the HADP methodology is able to profitably exploit progress in conventional optimization techniques. Current research is focusing on the algorithmic generation of the aggregates constituting the states of the partition machines at successive hierarchical layers.

G. Shen, P.E. Caines

Annual Report

Mon Jun 26 21:22:20 GMT 2000