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

Book One

Volume

Proceedings of the International Conference on Automated Planning and Scheduling, 24

Journal Special Track

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.

10.1609/icaps.v24i1.13657