AAAI Publications, Twenty-Fourth International Conference on Automated Planning and Scheduling

Font Size: 
The Complexity of Optimal Monotonic Planning: The Bad, The Good, and The Causal Graph
Carmel Domshlak, Anton Nazarenko

Last modified: 2014-05-11


For almost two decades, monotonic, or ``delete free,'' relaxation has been one of the key auxiliary tools in the practice of domain-independent deterministic planning. In the particular contexts of both satisficing and optimal planning, it  underlies most state-of-the-art heuristic functions. While satisficing planning for monotonic tasks is polynomial-time, optimal planning for monotonic tasks is NP-equivalent. We took a step towards a fine-grained classification of worst-case time complexity of optimal monotonic planning, with a focus on ``what gets harder" and ``what gets easier" when switching from optimal planning to optimal relaxed planning, in the context of finite-domain planning task representations.


Planning, Complexity, Delete relaxation, Monotonic relaxation, Causal graph

Full Text: PDF