But It Was True When I Checked: Compiling SHOP-Style Method Preconditions into Partially-Ordered HTN Planning

Harrison OatesarXiv 2026 · arXiv

TL;DR

This paper resolves a long-standing open problem in Hierarchical Task Network (HTN) planning by showing how to strictly enforce "SHOP-style" method preconditions in partially ordered plans. By introducing a clever "global lock" compilation technique, the author proves that these rigorous preconditions can be transformed into standard HTN planning without losing expressivity or structural properties.

What Problem Does This Paper Address?

In HTN planning, complex tasks are broken down into simpler ones using "methods." These methods often have preconditions—conditions that must be true for the method to be applicable. However, there are two competing ways to interpret these preconditions:

  1. HDDL-style (Compilation Semantics): The precondition is checked once at the very beginning of the task decomposition.
  2. SHOP-style (First-action Semantics): The precondition must hold immediately before the method's first actual action executes.

In totally ordered plans (where everything happens in a strict sequence), these two are identical. But in partially ordered plans, tasks can interleave. Under HDDL semantics, an unrelated task could sneak in after the check but before the first action, changing the state and "clobbering" the precondition. This makes HDDL's interpretation physically unrealistic for certain domains.

Until now, it was widely believed that compiling the stricter SHOP-style semantics into standard partially ordered HTN planning was either impossible or prohibitively complex. This paper proves otherwise.

Methods

The author introduces a novel compilation approach called $C_{pc}(P)$ that enforces first-action semantics using standard HTN features. The key components are:

  • Nondeterministic Marking: Since a method might have several subtasks that could be the first to execute (depending on the final plan), the compilation creates variants of each method. Each variant "marks" one minimal subtask as the one responsible for producing the first action. This obligation is passed down the hierarchy until a primitive action is reached.
  • The Global Lock: The state is extended with two fresh facts: free and lock.
  • Lock Windows:
    • An opening check at the start of a method requires the precondition and free, then sets the state to lock.
  • The marked subtask (the one producing the first action) is the only one allowed to release the lock, setting the state back to free.
  • All normal actions (unrelated to the current method's start) are modified to require free.

This effectively "freezes" the state between the precondition check and the method's first action, preventing any interfering tasks from executing in that window.

Datasets

As a theoretical contribution to the foundations of AI planning, this paper does not use empirical datasets or benchmarks. Instead, the "dataset" is the formal logic of HTN planning. The author provided a machine-checked proof of the compilation's correctness using the Lean 4 interactive theorem prover.

Key Insights and Ideas

  • The "Ownerless" Lock: A surprising "aha" moment is that the global lock doesn't need to track which method "owns" it. The inherent ordering constraints of the HTN task network already ensure that only the specific chain of tasks that acquired the lock can release it.
  • Polynomial Efficiency: Despite the perceived difficulty, the compilation is efficient. It produces a problem of size $O(|P|^2)$ in the general case and is purely linear $O(|P|)$ for totally ordered domains.
  • Preservation of Structure: The compilation is "well-behaved"—it doesn't turn a simple planning problem into a complex one. It preserves properties like acyclicity, tail-recursion, and regularity, meaning existing specialized solvers can still be used.

Key Results

  • Soundness and Completeness: The author proves a bijection between the solutions of the original problem (under first-action semantics) and the compiled problem (under standard semantics).
  • Resolution of an Open Question: It formally answers a challenge posed by the creators of HDDL in 2020, who had opted for weaker semantics because they believed a compilation like this was "not easily possible."
  • Formal Verification: By using Lean 4, the author ensures the mathematical proofs are free of the subtle errors that often plague complex planning formalisms.

Limitations and Future Work

  • Empty Methods: The current approach handles empty methods by inserting "no-op" actions. While this matches SHOP2's behavior, the author notes that different conventions for empty methods might require further study.
  • Constraint Extensions: The paper focuses on preconditions at the start of a method. Future work could extend the "lock" mechanism to handle more complex constraints, such as "after-constraints" or "between-constraints" that apply to subsets of subtasks.
  • Quadratic Size: While polynomial, the $O(|P|^2)$ size increase in the worst-case (highly unordered domains) might still be a factor for very large-scale industrial planning problems. Exploring whether a linear-sized compilation exists for the general case remains an open question.

Summary updated

Abstract

Method preconditions specify when a method may be applied in hierarchical task network (HTN) planning, but their meaning differs under two established semantics. The SHOP planners, like the classical HTN formalism of Erol, Hendler and Nau, require the precondition to hold immediately before the method's first action. HDDL, the input language of the International Planning Competition's HTN track, instead introduces an auxiliary action to check it; under partial order, unrelated actions may invalidate the precondition before the method starts. HDDL's designers adopted this weaker semantics because the first-action reading could not easily be compiled. Subsequent work has repeatedly identified its compilation under partial order as an open question, with existing transformations limited to total order. We give a compilation of the first-action semantics into standard partially ordered HTN planning without method preconditions using only two additional facts, thereby resolving a longstanding question in the HTN planning community.
BibTeX
@misc{oates2026but,
  author = {Harrison Oates},
  title = {{But It Was True When I Checked: Compiling SHOP-Style Method Preconditions into Partially-Ordered HTN Planning}},
  year = {2026},
  eprint = {2611.11055},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11055},
}
Figure