Hierarchically accelerated dynamic programming with applications ot transportation networks

摘要

In this paper, we propose a scheme called Hierarchically Accelerated Dynamic Programming which gives significant speedup of Dynamic Programming for discrete Event Systems modelled by finite state machines: this is at the cost of a degree of sub-optimality. This methodology is based upon a dynamical abstraction of the given DES by state aggregation which generates a so-called partition machine. We discuss necessary and sufficient conditions ofr the HADP procedure to generate global optimal solutions and, further, give bounds on the degree of sub-optimality which can occur. Finally, we use an example called the broken Manhattan Grid to illustrate out software implementation of HADP with a three level hierarchy.