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].

[Bibtex]

```
@inproceedings{muller2018frontier,
title={Frontier Search and Plan Reconstruction in Oversubscription Planning},
author={Muller, Daniel and Karpas, Erez},
booktitle={AAAI},
year={2018}
}
```

[Bibtex]

```
@inproceedings{smith:icaps04,
title={Choosing Objectives in Over-Subscription Planning.},
author={Smith, David E},
booktitle={ICAPS},
volume={4},
pages={393},
year={2004}
}
```

[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}
}
```

[Bibtex]

```
@inproceedings{muller:Karpas:icaps18,
title={Value Driven Landmarks for Oversubscription Planning.},
author={Muller, Daniel and Karpas, Erez},
booktitle={ICAPS},
year={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}
}
```