Symbolic Search for Oversubscription Planning

Authors

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

Keywords:

Deterministic Planning

Abstract

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.

Downloads

Published

2021-05-18

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 https://ojs.aaai.org/index.php/AAAI/article/view/17422

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling