Relaxing Is Hard: Complexity Results for Lifted Partial Order Causal Link Planning

Abstract

We investigate Partial Order Causal Link (POCL) planning in the lifted setting, where plan steps are represented as parameterised action schemas. While delete relaxation has been shown to reduce the complexity of plan existence in the ground POCL setting, operating on lifted representations may at times be necessary to avoid the prohibitive cost of grounding. This motivates a separate complexity analysis for the lifted case. We formalise delete-relaxation via filter functions that selectively suppress delete effects, yielding differently strong relaxation semantics, with and without respect for pre-existing delete effects and causal links of the input plan. We prove that plan existence is EXPTIME--complete for most variants, even when the input plan is totally ordered. Further, we prove results ranging from NP--completeness to PSPACE--completeness for fixed-schema plan existence, with a tractable case when planning is done from scratch.