**Next:**Hierarchical
Supervisory Control Theory
**Up:**Discrete
and Hybrid Systems
**Previous:**Feedback
Control of Nonholonomic
###
Hierarchically Accelerated Dynamic
Programming

*G. Shen, P.E. Caines*
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 (see caineshhc). 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 theory of HADP), these algorithms show very significant speed-up
with respect to any conventional method. (This is a property which cannot
be eroded by progress in the development of conventional single layer methods,
since HADP uses such methods as its building blocks.)

*Annual Report*

*Fri Nov 26 23:00:32 GMT 1999*