The Complexity of Optimal Monotonic Planning: The Bad, The Good, and The Causal Graph

Abstract

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.