Frontier Search and Plan Reconstruction in Oversubscription Planning


  • Daniel Muller Technion-Israel Institute of Technology



Oversubscription planning (OSP) is the problem of choosing an action sequence which reaches a state with a high utility, given a budget for total action cost. This formulation allows us to handle situations with under-constrained resources, which do not allow us to achieve all possible goal facts. In optimal OSP, the task is further constrained to finding a path which achieves a state with maximal utility. An incremental BFBB search algorithm with landmark-based approximations, proposed for OSP heuristic search to address tasks with non-negative and 0-binary utility functions. Incremental BFBB maintained with the best solution so far and a set of reference states, extended with all the non-redundant value-carrying states discovered during the search. Each iteration requires search re-start in order to exploit the new knowledge obtained along the search. Recent work proposed an approach of relative estimation of achievements with value-driven landmarks to address arbitrary utility functions, which incrementally improves the best existing solution so far eliminating the need to maintain a set of reference states. We now propose a progressive frontier search algorithm, which alleviates the need to re-start from scratch once new information is acquired by capturing the frontier achieved at the end of each iteration which is used as a dynamic reference point to continue the search, leading to improved efficiency of the search.




How to Cite

Muller, D. (2019). Frontier Search and Plan Reconstruction in Oversubscription Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 9999-10000.



Student Abstract Track