Making an AI planner’s checks hold when the action starts

When should a condition count?

Hierarchical task network planning, or HTN planning, breaks larger tasks into smaller ones using rules called methods. A method might turn shipping an order into loading and dispatching it. Its precondition specifies a condition under which that method may be used—for example, that the loading bay is open.

But when must that condition hold? Harrison Oates’s preprint examines two established answers. In the SHOP family of planners, it must hold immediately before the first action produced by the method. In HDDL, the language used for the International Planning Competition’s HTN track, a separate checking action comes before the method’s subtasks.

These readings agree when everything is totally ordered. With partial ordering, however, tasks without a required order can interleave. Another action can change the world after the check but before the method starts.

A small example exposes the difference

The paper illustrates this with shipment and maintenance tasks. Maintenance closes a loading bay and later reopens it. Shipping requires the bay to be open when its method starts.

Under HDDL’s separate-check interpretation, the planner can check that the bay is open, close it for maintenance, and then begin shipping before reopening it. Under the first-action interpretation, that sequence is rejected.

The formal example deliberately gives the shipping actions no preconditions of their own, isolating the effect of method preconditions. It is not a robot experiment or a claim that every shipping model would permit this behavior.

The example contains five actions with ordering constraints that allow 30 distinct sequences. HDDL’s interpretation accepts all 30; the first-action interpretation accepts 19 and excludes 11. These are counts within a constructed example, not benchmark success rates.

Following the first action down the hierarchy

The proposed solution is a compilation: a translation into standard partially ordered HTN planning without method preconditions. Instead, ordinary actions enforce those conditions.

The difficulty is that a method’s first action may be buried several levels down its hierarchy. Where several subtasks are unordered, different plans may start through different branches. Nested methods can also share the same first action, requiring their conditions to hold in the same state.

The translation creates method variants that mark which eligible subtask will produce the first action. If that subtask is itself compound, it passes the obligation downward until it reaches an action.

Two new state facts, called free and lock, protect the interval between checking and acting. An opening check tests the method’s condition and acquires the lock. Checks along the marked branch can then run, but unrelated actions cannot intervene. The designated first action releases the lock.

The task hierarchy and ordering constraints ensure that another branch cannot release the active branch’s lock. After release, other tasks can interleave again. The construction does not require the condition to remain true throughout the method’s remaining actions.

What the result establishes

The paper proves soundness and completeness: removing the added checks and annotations from compiled solutions yields exactly the original first-action solutions. It also reports a machine-checked proof of language preservation in Lean 4 with Mathlib.

This is a mathematical result, not evidence of faster planning or improved physical-system performance. The supplied paper does not present a planner benchmark study. Its practical significance is that the intended semantics can be represented in a formalism without native method preconditions.

Two facts do not mean negligible overhead

Although only two state facts are added, the translation also introduces task copies, checking actions and method variants. Its description size is at most quadratic in the original problem size in general, and linear for totally ordered problems. Those bounds concern representation size, not solving time.

One boundary matters especially: empty methods are represented by no-effect actions, which count as possible first actions. The paper leaves open the alternative interpretation in which a condition must hold before the first action that is not such a no-op.

The work is an arXiv preprint. This briefing uses the supplied paper-text extraction, whose figures were omitted and whose layout or equations may be damaged; the linked proof development was not independently checked here.