**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*