Oversubscription Planning: Complexity and Compilability

AAAI 2014 pp. 2221-2227

doi:10.1609/AAAI.V28I1.9025 /aaai/2014/aghighi2014aaai-oversubscription/

Abstract

Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder & Geffner.

PDF AAAI Semantic Scholar

Cite

Text

Aghighi and Jonsson. "Oversubscription Planning: Complexity and Compilability." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.9025

Markdown

[Aghighi and Jonsson. "Oversubscription Planning: Complexity and Compilability." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/aghighi2014aaai-oversubscription/) doi:10.1609/AAAI.V28I1.9025

BibTeX

@inproceedings{aghighi2014aaai-oversubscription,
  title     = {{Oversubscription Planning: Complexity and Compilability}},
  author    = {Aghighi, Meysam and Jonsson, Peter},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2014},
  pages     = {2221-2227},
  doi       = {10.1609/AAAI.V28I1.9025},
  url       = {https://mlanthology.org/aaai/2014/aghighi2014aaai-oversubscription/}
}