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