Symbolic Search for Oversubscription Planning


  • David Speck University of Freiburg
  • Michael Katz IBM T. J. Watson Research Center


Deterministic Planning


The objective of optimal oversubscription planning is to find a plan that yields an end state with a maximum utility while keeping plan cost under a certain bound. In practice, the situation occurs whenever a large number of possible, often competing goals of varying value exist, or the resources are not sufficient to achieve all goals. In this paper, we investigate the use of symbolic search for optimal oversubscription planning. Specifically, we show how to apply symbolic forward search to oversubscription planning tasks and prove that our approach is sound, complete and optimal. An empirical analysis shows that our symbolic approach favorably competes with explicit state-space heuristic search, the current state of the art for oversubscription planning.




How to Cite

Speck, D., & Katz, M. (2021). Symbolic Search for Oversubscription Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11972-11980. Retrieved from



AAAI Technical Track on Planning, Routing, and Scheduling