Frontier Search and Plan Reconstruction in Oversubscription Planning

Check out work on “Frontier Search and Plan Reconstruction in Oversubscription Planning” – in AAAI 2019

Our paper on “Frontier Search and Plan Reconstruction in Oversubscription Planning” [1] will be presented in The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)

Oversubscription planning (OSP) [2] is a problem of choosing an action sequence which reaches a state with a high utility, given a budget for total action cost. This formulation allows to handle situations with under-constrained resources, which do not allow to achieve all possible goal propositions. In optimal OSP, the task is further constrained to finding a path which achieves a state with maximal utility. Best-First-Branch-and-Bound (BFBB) is a heuristic search algorithm which is widely used for solving OSP problems. <em>BFBB</em> relies on an admissible utility-upper-bounding heuristic function (with budget restrictions) \(h : S \times {\mathbb R}^{0+} \rightarrow R\) to estimate the true utility \(h*(s,b)\).
An incremental BFBB search algorithm with landmark-based approximations (<em>inc-compile-and-BFBB</em>) was proposed for OSP heuristic search [3] to address tasks with non-negative and 0-binary utility functions. <em>inc-compile-and-BFBB</em> maintains 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 information obtained along the search. Recent work presented a relative estimation of achievements with value-driven landmarks [4] addressing arbitrary additive utility functions, which incrementally improves the best solution so far eliminating the need to maintain a set of reference states.
This paper [1] proposes a <em>progressive frontier search</em> algorithm, which alleviates the computational cost of search restart once new information is acquired. Our technique allows the new search iteration to continue from any state on the frontier of the previous search iteration, leading to improved efficiency of the search. An extended version of this abstract is available online [5].

[1] D. Muller and E. Karpas, “Frontier search and plan reconstruction in oversubscription planning,” in Aaai, 2018.
[Bibtex]
@inproceedings{muller2018frontier,
title={Frontier Search and Plan Reconstruction in Oversubscription Planning},
author={Muller, Daniel and Karpas, Erez},
booktitle={AAAI},
year={2018}
}
[2] D. E. Smith, “Choosing objectives in over-subscription planning.,” in Icaps, 2004, p. 393.
[Bibtex]
@inproceedings{smith:icaps04,
title={Choosing Objectives in Over-Subscription Planning.},
author={Smith, David E},
booktitle={ICAPS},
volume={4},
pages={393},
year={2004}
}
[3] C. Domshlak and V. Mirkis, “Deterministic oversubscription planning as heuristic search: abstractions and reformulations,” Journal of artificial intelligence research, vol. 52, p. 97–169, 2015.
[Bibtex]
@article{mirkis:domshlak:jair15,
title={Deterministic oversubscription planning as heuristic search: Abstractions and reformulations},
author={Domshlak, Carmel and Mirkis, Vitaly},
journal={Journal of Artificial Intelligence Research},
volume={52},
pages={97--169},
year={2015}
}
[4] D. Muller and E. Karpas, “Value driven landmarks for oversubscription planning.,” in Icaps, 2018.
[Bibtex]
@inproceedings{muller:Karpas:icaps18,
title={Value Driven Landmarks for Oversubscription Planning.},
author={Muller, Daniel and Karpas, Erez},
booktitle={ICAPS},
year={2018}
}
[5] D. Muller and E. Karpas, “Value driven landmarks for oversubscription planning,” Technion, Faculty of Industrial Engineering and Management, IE/IS-2018-04, 2018.
[Bibtex]
@techreport{muller2018TRvalue,
title = {Value Driven Landmarks for Oversubscription Planning},
author = {Muller, Daniel and Karpas, Erez},
year = {2018},
institution = {Technion, Faculty of Industrial Engineering and Management},
number = {IE/IS-2018-04}
}

Leave a Reply

Your email address will not be published. Required fields are marked *