HTN planners no longer have to choose between two precondition semantics: a new compilation folds SHOP-style checks into partially ordered planning with just two facts
Synopsis
In hierarchical task network (HTN) planning, method preconditions mean different things under the SHOP family and under HDDL: the former requires a precondition to hold immediately before the method's first action, the latter only in some earlier state, and under partial order the two can yield different solutions. A new compilation turns the SHOP-style first-action semantics exactly into a standard partially ordered HTN problem without method preconditions, adding only two facts, with a bijection between solutions and a machine-checked proof of language preservation.
Interpretation
Method preconditions in hierarchical task network planning can now be used under partial order with their SHOP-style meaning, instead of HDDL's looser check. HDDL adopted the auxiliary-check compilation from the start; its designers noted that the first-action reading "needs to (natively) support this feature, because a compilation is not easily possible," and later work repeatedly listed compilation under partial order as open, with existing transformations limited to total order. Compiled solutions correspond one-to-one with first-action solutions, and language preservation has a machine-checked proof; in the shipping example the HDDL-accepted linearisation that checks the open bay, closes it, then loads is excluded, while the linearisations the first-action semantics keeps are all reproduced.
The construction lets each method nondeterministically mark the subtask that will produce its first action and passes that obligation down the decomposition hierarchy. Marking uses two copies of each compound task: a normal copy carrying no obligation and a first copy whose first action must also be the first action of an already-checked ancestor; a marked chain ends at a release action. Two fresh facts act as a global lock, exactly one holding at any time; an opening check requires the precondition and flips the lock, inner checks only require the precondition, the release restores the lock, and every other action requires the lock to be free, so only the chain's own checks and release can run inside a lock window.
The compilation is polynomial in size, quadratic in general and linear when every method is totally ordered. Each method yields two variants per minimal subtask, each adding one task and some ordering pairs; since the number of minimal subtasks is bounded by method size, the overall bound is quadratic. The compilation preserves total order, acyclicity, tail recursion and regularity, so existing tight plan-existence bounds carry over to the first-action semantics; the acyclic and tail-recursive cases are new.
Perspective
The discussion covers the first-action semantics and its compilation within the ground HTN formalism, with empty methods evaluated at task removal via a no-op following the SHOP2 convention; the compilation also applies to lifted HDDL domains without grounding them first.
The author leaves several questions open: whether a similar compilation exists when an ancestor's precondition must hold before its first action that is not a no-op; whether the lock extends to before-constraints on subsets of subtasks and to after- and between-constraints; and whether quadratic size is necessary.