Potential hierarchical decomposition: controlling hierarchical planning with uncertainty and resource constraints

The authors explore the hierarchical structuring of probabilistic decision models. The potential hierarchical decomposition (PHD) method computes an optimal sequential control strategy for hierarchical search with uncertainty and resource constraints. It is assumed that multiple competing hierarchical structures exist in a given domain and a problem space is depicted by an AND/OR graph with the known cost and the distribution of resource consumption for each link. The resource-bounded optimal performance of the PHD approach is achieved by controlling the concurrent exploration of these alternative hierarchical structures. The basic algorithm computes an optimal control strategy for conditionally independent distributions, has exponential complexity, and is an application of dynamic programming. It is shown that an optimal strategy in the case of uncertain costs depends only on the expected values of costs and not on the whole distributions. The algorithm is extended to handle dependencies and arbitrary interruptability of the actions