Are White Knights Worth the Trouble? Reconciling POCL and Partial-Order Plans for Plan Optimization

1 Introduction

Plan optimization - finding plans that minimize makespan, cost, or other quality metrics - is a central problem in automated planning. Partial order (PO) planning is highly attractive here because it avoids unnecessary total orderings, exposing flexibility that can be exploited during both optimization and execution [Bercher et al., 2024]. This flexibility can yield strictly higher-quality plans than alternative representations [Oates and Bercher, 2026b]. Among PO representations, partial order causal link (POCL) plans [McAllester and Rosenblitt, 1991; Penberthy and Weld, 1992] have proven especially effective. By explicitly identifying which actions support which preconditions, causal links clarify why particular ordering constraints exist [Bercher et al., 2024]. Consequently, despite the computational hardness of reasoning over POCL structures [Bercher, 2021; Oates and Bercher, 2026c], they remain integral to state-of-the-art hierarchical planning [Bit-Monnot et al., 2020; Bit-Monnot, 2023], temporal planning [Bit-Monnot and Godet, 2025], and plan optimization systems [Bercher et al., 2024].

Despite often being treated interchangeably, PO plans and POCL plans are not equivalent under standard semantics.

While every POCL plan induces a valid PO plan, the converse is false: some valid PO plans cannot be represented as threat-free POCL plans without introducing additional ordering constraints [Bercher and Olz, 2020]. As a result, techniques optimizing POCL plans search a strict subset of the PO solution space. This mismatch means that output plans may be more constrained and less flexible than necessary.

The cause of this gap is the classical definition of causal threats. Under standard semantics, if an action deletes a fluent protected by a causal link, the threat must be resolved via promotion (ordering the consumer before the deleter) or demotion (ordering the deleter before the producer). Both strategies force the threatening action outside the protection interval. However, this ignores a third possibility: the threatened fluent could be re-established by an intermediate action before it is needed by the consumer. Such an action, commonly called a white knight, ensures the plan remains executable without requiring promotion or demotion.

White knights are not a new idea: they appear in early work on partial order planning [Chapman, 1987], where they can be used to verify that a PO plan is a solution to a planning problem in polynomial time [Kambhampati and Nau, 1996]. More recently, a POCL threat definition incorporating white knights was used by Siddiqui and Haslum [2015] for plan quality optimization through block deordering, and the same definition was used in a textbook on the Planning Domain Definition Language [Haslum et al., 2019, p. 41]. However, the semantic implications of white knights have not been fully recognized; in particular, their role in reconciling PO and POCL plan representations has remained unexplored.

In this paper, we show that adopting a white-knight-aware threat definition eliminates the representational gap between PO and POCL plans. We prove that under these refined threat semantics, the sets of valid PO plans and valid POCL plans coincide: every PO plan admits a threat-free POCL plan with exactly the same ordering constraints, and vice versa. This resolves the limitation identified by Bercher and Olz [2020] and clarifies the precise conditions under which causal-link reasoning can be applied without loss of generality.

This equivalence has immediate practical applications for plan optimization. In particular, we revisit the MaxSATbased framework of Muise et al. [2016], which aims to optimize partial order plans but, due to its reliance on the standard threat definition, in fact optimizes only over standard POCL plans. By incorporating white knight semantics into the encoding, we restore alignment between the optimization framework and its intended PO-plan solution space.

The remainder of this paper is structured as follows. Section 2 formalizes classical, PO, and POCL planning. Section 3 introduces white knight threat semantics, proves the equivalence of the solution spaces (Theorem 1), and details the corrected MaxSAT optimization encoding. Section 4 presents our empirical analysis, demonstrating both the structural necessity of white knights on synthetic domains and their minimal overhead on standard benchmarks. Finally, Section 5 summarizes our contributions.

2 Formal Framework

In this section, we provide a formal framework for classical planning, sequential plans, partial order (PO) plans, and partial order causal link (POCL) plans. We take care to build up these concepts systematically, as the distinction between PO and POCL plans is crucial to our main contributions. We base our work on a ground, i.e., propositional formalism, as solution plans are necessarily ground and this choice simplifies our presentation considerably.

A classical planning problem is a tuple (F, A, I, G) where F is a finite set of fluents, I ∈ 2F is the initial state, G ⊆ F is the goal description, and A is the finite set of actions. A state is any s ∈ 2F .

An action a ∈ A is a tuple a = (pre(a), add(a), del (a)), where pre(a) ⊆ F denotes its preconditions, add(a) ⊆ F its add effects, and del (a) ⊆ F its delete effects. An action a is applicable (or executable) in state s if and only if pre(a) ⊆ s. The resulting state after applying a is given by the transition function γ(a, s) = (s \ del (a)) ∪ add (a). The most common plan representation is the sequential plan, which specifies a complete linear ordering of actions. An action sequence ¯a = a1, a2, . . . , an is applicable in a state s0 if and only if there exists a sequence of states s0, s1, . . . , sn such that for all i ∈ [1, n], it holds that ai is applicable in state si-1 and generates state si = γ(ai, si-1). We call sn the state generated by ¯a.

Definition 1. An action sequence ¯a is called a sequential plan for a classical planning problem if and only if it is applicable in the initial state I and generates a goal state s ⊇ G.

While sequential plans are intuitive, they impose unnecessary constraints by specifying a total ordering over all actions. In many cases, certain actions are independent and could be executed in any relative order without affecting the plan's validity. Generalizing from a total order to a partial order allows us to represent this flexibility explicitly, which proves valuable both for plan execution and for reasoning about plan structure.

A partial PO plan is a tuple (PS,≺) consisting of a finite set of plan steps PS, with each step (l, a) ∈ PS consisting of an action a with unique label l. The labelling is necessary to differentiate between multiple occurrences of the same action within a plan. The relation ≺ ⊆ PS × PS is a strict partial order over the plan steps. A total ordering of the actions in PS that respects ≺ is a linearization.

Definition 2. A partial PO plan P = (PS,≺) is called a PO plan for a classical planning problem if and only if every linearization is executable in the initial state I and generates a goal state s ⊇ G.

While PO plans elegantly represent ordering flexibility, they lack explicit representation of why particular orderings are necessary to guarantee executability. POCL plans address this limitation by making causal dependencies explicit through the addition of causal links, which annotate precisely which action produces which fluent for consumption by which other action.

A partial POCL plan is a tuple (PS, ≺, CL) with PS and ≺ defined the same as in PO plans, and CL ⊆ P S × F × P S a finite set of causal links. In POCL plans, the initial and goal states are encoded as special plan steps, init = (init, (∅, I, ∅)) and goal = (goal , (G, ∅, ∅)). init is ordered strictly before all other plan steps, while goal is ordered strictly after all plan steps. As we shall shortly see, this is necessary to obtain a coherent plan definition.

A causal link (ps, f, ps′ ) ∈ CL indicates that the fact f is produced by the plan step ps and consumed by the plan step ps′ . This implies that f ∈ pre(ps′ ) ∩ add(ps). To ease definitions, we require that a causal link (ps, f, ps′ ) ∈ CL implies an ordering constraint (ps, ps′ ) ∈ ≺. In such a causal link, we call f protected by that link.

In standard POCL planning, we define a causal threat in the following manner.

Definition 3 (Causal Threat). A plan step ps′′ threatens a causal link (ps, f, ps′ ) if and only if f ∈ del(ps′′ ) and the transitive closure of ≺∪{(ps, ps′′ ), (ps′′ , ps′ )} is a strict partial order.

Causal threats are resolved by imposing additional ordering constraints on the threatening step. For a causal link (psp, f, psc) threatened by the plan step pst, promotion enforces an ordering psc ≺ pst, preventing pst from deleting f before it can be used by psc. Similarly, demotion enforces an ordering constraint pst ≺ psp so pst cannot execute over the interval. We can now define valid POCL plans.

Definition 4. A partial POCL plan (PS,≺,CL) is a POCL plan for a classical planning problem if and only if every precondition is protected by a causal link and there are no causal threats.

This definition implies that every linearization of a POCL plan is executable, and so every POCL plan induces a valid PO plan simply by discarding all causal links. However, the converse is known not to hold under the standard definitions [McAllester and Rosenblitt, 1991; Kambhampati and Nau, 1996; Bercher and Olz, 2020]. To show this, consider the partial POCL plan in Figure 1. Straightforwardly, if we remove its causal links, it is a PO plan as all six of its linearizations are executable and end up in a goal state. However, adding a causal link from w1 or w2 to support the open precondition P will raise a causal threat with s2 or s1, respectively. Resolving the threat in each case requires promotion or demotion, thereby adding ordering constraints to the induced PO plan and reducing the set of valid linearizations.

Consequently, 'partial order' plan optimization techniques which use causal links, such as the MaxSAT encoding of Muise et al. [2016], actually optimize over the space of POCL

plans, rather than over PO plans as claimed. In the next section, we discuss how a slight adjustment to the causal threat definition makes PO and POCL plans equivalent, thus allowing MaxSAT and other POCL-oriented techniques to be applicable to PO plan optimization.

3 White Knights To The Rescue

In fairy tales, a white knight saves the kingdom. In planning, the stakes are slightly lower, but the mechanism is the same: a white knight rescues a once-established and then deleted fluent, reasserting a necessary condition just in time to save the plan from failure [Chapman, 1987]. Siddiqui and Haslum [2015, Def. 1] and Haslum et al. [2019, p. 41] use a formalization that can be regarded as a hybrid between the standard POCL plan and PO plan formalizations we introduced in the previous section. In this formalization, causal links are used, but the definition of causal threat now depends on white knights.

Definition 5 (White Knight). Let (psp, f, psc) be a causal link and psdel be a plan step such that f ∈ del(psdel). A plan step pswk is a white knight for this link with respect to psdel if and only if: (1) f ∈ add(pswk), and (2) the ordering constraints enforce psdel ≺ pswk ≺ psc.

Definition 6 (White Knight Causal Threat). A causal link (psp, f, psc) is threatened under white knight semantics if and only if there exists a plan step psdel with f ∈ del (psdel) such that: (1) The step is a standard causal threat (i.e., it is not the case that psdel ≺ psp or psc ≺ psdel), and (2) There exists no white knight pswk for the link with respect to psdel.

With this refined threat definition, we can now define valid POCL plans under the white knight semantics.

Definition 7 (wk-POCL plans). A partial POCL plan P = (PS,≺,CL) is a wk-POCL plan for a classical problem if and only if every precondition of every step in PS is protected by a causal link in CL, and there are no white knight causal threats.

To see how this definition resolves the gap identified in the introduction, consider again the plan structure in Figure 1. Suppose we satisfy the goal's precondition P with a causal link from w1, i.e., (w1, P, goal) ∈ CL. Under standard semantics, step s2 threatens this link because it deletes P and is unordered with respect to the protection interval w1 → goal . However, under Definition 7, we evaluate whether s2 constitutes a white knight causal threat. We identify step w2

as a white knight because P ∈ add(w2) and the orderings s2 ≺ w2 ≺ goal hold (enforced by the link (s2,W2,w2) and the goal constraint). Since a valid white knight exists, the threat from s2 is resolved. Symmetrically, if P were supported by w2, step w1 would act as the white knight for the threat from s1. Thus, the plan is a valid wk-POCL plan without the spurious ordering constraints (e.g., s2 ≺ w1) required by the standard definition. With white knight semantics introduced, we can now state our main theoretical result.

Theorem1. Let Πbe a planning problem. (PS,≺) is a valid PO plan for Π if and only if there exists a set of causal links CL such that (PS, ≺, CL) is a valid wk-POCL plan for Π.

Proof. ⇐. Let P be a wk-POCL plan. It is straightforward to see that Definition 7 implies every linearization of P is executable, and so P is a valid PO plan.

• ⇒. Let P = (PS,≺) be a valid PO plan. We construct a wk-POCL plan P ′ = (PS, ≺, CL) from P by adding causal links, and prove that there are no causal threats.

Construction of causal links: For each plan step psc ∈ PS and each precondition f ∈ pre(psc), we must choose a producer psp such that f ∈ add(psp) and psp ≺ psc, then add the causal link (psp, f, psc) to CL.

To see that such a psp exists: Since P is valid, f holds at psc in every linearization, so some step must add f before psc in every linearization. Let Af = {ps ∈ PS : f ∈ add(ps)} be the set of all steps that add f. If no psp ∈ Af satisfies psp ≺ psc, then for each producer we could construct a linearization placing psc before that producer. Since ≺ would not constrain any producer to precede psc, we could construct a linearization where psc appears before all producers of f , meaning f would not hold at psc, contradicting validity. Hence some psp ∈ Af satisfies psp ≺ psc, and we select any such psp for the causal link.

No causal link is threatened: We now prove that for any causal link (psp, f, psc) ∈ CL, the link is not threatened under white knight semantics.

Consider any plan step psd such that f ∈ del(psd). We must show that at least one of the following holds:

1. psc ≺ psd, or
2. There exists pswk such that f ∈ add(pswk) and psd ≺ pswk ≺ psc.

Suppose condition (1) does not hold, i.e., psc ̸≺ psd. We prove condition (2) must hold by contradiction. Assume condition (2) also fails. Then for every step ps′ ∈ PS with f ∈ add(ps′ ), we have ¬(psd ≺ ps′ ≺ psc). This means each producer of f falls into one of the following categories:

• ps′ ≺ psd: the producer is constrained to appear before the deleter, or
• psc ≺ ps′ : the producer is constrained to appear after the consumer, or
• The producer is not constrained by ≺ to appear strictly between psd and psc.

We now construct a linearization of P in which f does not hold at psc, contradicting the validity of P .

Since psc ̸≺ psd, the ordering psd before psc is consistent with ≺. We build a linearization π∗ that respects ≺, places psd before psc, and for each producer ps′ ∈ Af :

• If ps′ ≺ psd, then ps′ appears before psd in π∗ .
• If psc ≺ ps′ , then ps′ appears after psc in π∗ .
• Otherwise, since ¬(psd ≺ ps′ ≺ psc), we can place ps′ either before psd or after psc without violating ≺. We choose one such placement.

By construction, π∗ respects all constraints in ≺. In π∗ :

• Every step that adds f appears either before psd or after psc.
• The step psd deletes f and appears before psc.
• No step re-establishes f between psd and psc.

Therefore, f does not hold when psc executes in π∗ . But π∗ is a valid linearization of P, contradicting the assumption that P is a valid PO plan. Hence condition (2) must hold.

Since for every deleter psd at least one of conditions (1) or (2) holds, the causal link (psp, f, psc) is not threatened. Since every precondition in P ′ is supported by a causal link, and we have shown that no such link is threatened under white knight semantics, P ′ satisfies Definition 7. Thus, every valid PO plan can be augmented into a valid wk-POCL plan.

Having established that wk-POCL semantics capture the entire space of valid PO plans, we can now formally quantify their advantage over the standard formulation. The following result confirms that our definition is a strict generalization of the classical approach.

Theorem 2 (Strict Subsumption). Every valid POCL plan is a valid wk-POCL plan. Furthermore, the inclusion is strict: there exist valid wk-POCL plans (PS,≺,CL) for which there exists no valid standard POCL plan (PS, ≺′ , CL) such that ≺′⊆≺.

Proof. The first claim is trivial by definition: standard semantics resolve threats via promotion or demotion, which satisfies the first condition of the white knight threat definition (Definition 5). Thus, any plan valid under standard semantics is valid under wk-semantics. The second claim follows from the counter-example in Figure 1. As detailed above, this plan can be augmented into a valid wk-POCL plan with the depicted orderings ≺ by choosing either w1 or w2 to support the open precondition P . However, under standard semantics, the threat from s2 (respectively, s1) must be resolved by demotion. This yields a plan with orderings ≺′ where ≺⊂≺′ .

3.1 Optimizing PO Plans UsingMaxSAT

Having established the theoretical equivalence of wk-POCL plans with PO plans, we now show how to leverage white knights for plan optimization. We adopt the partial weighted MaxSAT framework of Muise et al. [2016]. For the sake of completeness, we reproduce their base encoding variables and constraints (Equations 1-7), which enforce standard POCL validity. Our specific contribution is the replacement of the standard threat resolution constraint with a white-knight-aware formulation, thereby enabling optimization over the full PO space.

The aim of our optimization efforts is to produce maximally flexible PO plans, in the sense that decisions regarding plan execution can be deferred. In this context, we use the number of ordering constraints in the transitive closure of the plan as a proxy for flexibility. Consequently, when we discuss minimizing 'ordering constraints', we refer to minimizing the cardinality of the strict partial order relation, |≺|.

We first provide the necessary definition for the allowed plan modification [B¨ackstr¨om, 1998].

Definition 8. Let P and Q be wk-POCL plans for a problem Π, with P = (PS,≺,CL) and Q = (PS ′ ,≺′ ,CL′ ). Then Q is a reordering of P if and only if PS = PS′ .

Definition 9 (Minimum Reordering). Let P be a wk-POCL plan. A reordering Q of P is minimum if there exists no reordering Q′ of P such that |≺′ | < |≺|.

Partial weighted MaxSAT is an optimization variant of the Boolean satisfiability problem where clauses are partitioned into hard clauses (which must be satisfied) and soft clauses (which we attempt to maximize the sum of the weights of the satisfied clauses). For plan optimization, hard clauses encode plan validity while soft clauses encode quality metrics.

Let P = (PS,≺,CL) be a valid wk-POCL plan. A satisfying assignment to the encoding Φ(P) induces a target wk-POCL plan. We use the following Boolean variables: xps indicates that the plan step ps appears in the target plan, κ(psi, psj) indicates that psi ≺ psj in the target plan, and Υ(psp, f, psc) indicates that (psp, f, psc) is a causal link in the target plan.

The following hard clauses ensure that the induced ordering relation is a strict partial order and that all plan steps are properly embedded between init and goal .

Under the POCL solution criterion, every included plan step must have each of its preconditions protected by a causal link.

(6)

The crucial difference from the original encoding is in the treatment of causal threats. Standard POCL allows for threats to be resolved through promotion and demotion, and so the constraint is defined accordingly:

Under wk-POCL semantics, we add a disjunct in the threat resolution clause to account for white knights:

To define the necessary optimization metric, soft clauses ¬κ(psi, psj) for all psi, psj ∈ PS with weight 1 are used. In this paper, we focus on optimal reorderings to isolate the effects of white knights on plan flexibility, and so we require every plan step to be in the target plan, i.e., xpsi for all psi ∈ PS. However, Muise et al. [2016] define several additional optimization variants, including action elimination. Our extension to white-knight semantics leaves the objective function and step-selection constraints unchanged. Consequently, the wk-POCL encoding is compatible with all optimization variants they propose.

4 Experimental Evaluation

While a minimum reorder of a PO plan can lead to fewer ordering constraints and hence more flexibility regarding execution orders compared to a minimum POCL plan, it is unclear whether this occurs often in practice, and at what cost. To answer this question, we extended the MaxSAT POCL encoding library POPGEN to support wk-POCL plans. 1 We conducted a comparative analysis by computing the optimal reordering for each instance under both definitions. All experiments were run on a Linux environment equipped with an Intel Core i5-1240P CPU and 32GB of RAM. We utilized the RC2 MaxSAT solver [Ignatiev et al., 2019] provided by the PySAT library. Experimental details and reproducibility data are available online [Oates and Bercher, 2026a].

4.1 Plan Generation and Setup

For the broad evaluation, we selected domains from the International Planning Competitions (IPC). To generate the initial sequential plans, we utilized the planutils toolkit [Muise et al., 2022] to run the SCORPION MAIDU planner [Corrˆea et al., 2023], a joint winner in the IPC 2023 Satisficing Track. Initial plan generation was limited to 30 min and 8 GB RAM per instance, while plan optimization (encoding + solving) was limited to 30 min and 4 GB RAM per instance. We report coverage (instances solved), total optimization time, and the resulting plan quality. Our primary quality metric is the cardinality of the transitive closure (|≺|), as this corresponds directly to the objective function of the MaxSAT encoding.

It is important to note that for a fixed number of ordering constraints (the optimization objective), there may exist multiple distinct partial orderings that yield varying numbers of linearizations. Since the optimizer solely targets constraint minimization, it is indifferent between two plans with the same number of constraints, even if one allows significantly more linearizations. Consequently, differences in linearization counts between plans of identical cost are often artifacts of solver tie-breaking. Therefore, we adopt a conservative criterion: we consider the wk-POCL encoding to have strictly outperformed the standard encoding only when it yields a plan with strictly fewer ordering constraints (|≺|wk < |≺|std ).

4.2 Results on Standard Benchmarks

We first compare the performance of both encodings across a number of domains from previous International Planning Competitions. The goal of this experiment was to quantify the overhead of white knight semantics in scenarios where they may not be strictly necessary, and to verify that the encoding scales gracefully compared to the standard approach.

1 Code available at https://github.com/HarrisonOates/popgen.

Table 1 summarizes domain-specific performance across solved instances. Across each instance, both coverage and the number of ordering constraints found by the wk-POCL encoding were identical to that of the standard encoding. That is, the wk-encoding did not find strictly more flexible plans than the standard encoding.

A potential concern with a more expansive threat definition is the inflation of the SAT instance size. We analyzed the size of the CNF encodings generated for all 81 valid instances. As shown in Table 2, the introduction of white knight semantics necessitates auxiliary variables to maintain a compact CNF representation. Empirically, this resulted in a mean increase of 16.1% in the number of Boolean variables. However, the impact on constraint complexity is minimal, with the number of clauses increasing by only 2.7% on average.

The runtime penalty for the added completeness is negligible. The average total time (encoding + solving) rose from 38.87s to 41.55s. A Wilcoxon signed-rank test [Wilcoxon, 1945] on the plan runtimes yields p = 0.30, indicating no statistically significant difference in performance. Similarly, separate tests for encoding time (p ≈ 0.27) and solving time (p ≈ 0.13) confirm that the wk-POCL encoding is computationally competitive with the incomplete standard encoding. As shown in Table 4 and Figure 2, the average problem actually benefits slightly from the modification. The median total overhead ratio is 0.990×, indicating that for the typical instance, the wk-encoding is marginally faster than the standard encoding. The discrepancy between the rise in aggregate average time and the neutral mean ratio (0.998×) suggests that the cost of completeness is concentrated in specific outliers (Max Total Ratio 1.699×), rather than presenting a systematic slowdown across the benchmark set.

4.3 Synthetic Benchmark

The results on standard IPC benchmarks indicate that while the standard and white knight encodings yield plans with identical ordering constraints, their internal causal justifications frequently differ. As shown in Table 1, white knights were actively exploited to ensure plan validity in 40 of the 64 solved instances, with an average of 7.45 white knights among those instances in which they were used. The fact that this utilization did not result in fewer ordering constraints suggests that standard domains exhibit a high degree of structural rigidity: while the establish-delete-reestablish patterns exist and are used, other parallel causal dependencies enforce the same strict partial order, masking the potential flexibility gains of the white knight.

To strictly evaluate the benefit of the white knight definition, we constructed a synthetic "Resource Borrowing" domain that generalizes the counter-example from Figure 1. The problem consists of N agents and a single global fluent (shared-resource). The goal requires (shared-resource) to be present at the end of the plan. Crucially, each agent must perform a task sequence that temporarily violates this goal condition: a threat action (deleting the resource) followed immediately by a restore action (readding it). Under standard POCL semantics, these threats force the imposition of ordering constraints to serialize the agents. Under wk-POCL, the restore action serves as a white knight, allowing the agents to operate in parallel.

We scaled the problem size from N = 3 to N = 10 agents. The results (Table 5) strongly validate our theoretical claims. The wk-POCL encoding consistently found plans with fewer ordering constraints than the standard encoding. On average, wk-POCL solutions contained 14.1% fewer ordering constraints. For the largest instance (N = 10), the standard encoding required 60 constraints to ensure validity, while the white knight encoding required only 51. As illustrated in Figure 3, this widening gap empirically confirms that the standard definition introduces spurious ordering constraints to resolve threats that are effectively benign under white knight semantics.

This reduction in constraints directly translates to increased plan flexibility. The wk-POCL plans admitted strictly more valid linearizations in every instance tested (8/8). The degree of improvement scales with problem complexity: at N = 3, wk-POCL offered a 1.36× increase in valid linearizations; at N = 10, this factor grew to 2.14×.

This domain also serves as a "stress test" for the encoding size. Unlike the IPC domains where threats are sparse, the Resource Borrowing domain features dense causal interference: every agent's Threaten action constitutes a threat to the global goal that requires resolution. This maximizes the instantiation of the white knight disjunctions (Eq. 8).

Consequently, the encoding overhead was higher here than in the general evaluation: the wk-POCL encoding generated 24.0% more variables and 6.9% more clauses on average compared to the standard encoding. However, this increase in logical density did not translate to intractable solve times, as shown in Figure 3. The average solving time increased by only 11.6%, which in absolute terms corresponds to a negligible difference of approximately 12ms (0.112s vs 0.125s). This confirms that even in scenarios where the white knight machinery is heavily utilized, the optimization remains computationally efficient.

We note two important methodological details regarding these results. First, while counting linear extensions is generally #P-complete [Brightwell and Winkler, 1991], the structure of these instances allowed for exact enumeration within our timeout. Second, in general optimization scenarios, different partial orderings with the same number of constraints may yield different linearization counts due to solver tiebreaking. This was observed in the rovers, storage, and depot domains. However, that ambiguity does not apply here: the wk-POCL encoding achieved a strict reduction in the number of ordering constraints in the transitive closure in all cases (e.g., 51 vs 60). The results confirm that wk-POCL captures a significantly larger volume of the valid solution space as the causal complexity of the problem increases.

5 Conclusion

This paper re-examines the relationship between partial order (PO) plans and partial order causal link (POCL) plans, with a particular focus on the role played by the causal threat definition. Our main theoretical contribution is a proof that, under white knight semantics, the sets of valid PO plans and valid POCL plans coincide. Every PO plan admits a threat-free wkPOCL representation with identical ordering constraints, and every wk-POCL plan induces a valid PO plan. This result resolves the representational gap brought to renewed attention by Bercher and Olz [2020] and clarifies the conditions under which causal-link reasoning can be used without loss of generality for partial order planning.

This equivalence has direct implications for plan optimization. We show that MaxSAT-based approaches that claim to optimize PO plans (e.g., Muise et al. [2016]) in fact optimize over standard POCL plans due to their reliance on the classical threat definition. Adopting white knight semantics restores alignment between the optimization framework and the intended PO-plan solution space, with negligible computational overhead in practice.

In summary, we conclude that white knights are indeed worth the trouble: they reconcile the usefulness of POCL planning with the full generality of partial order plans, without sacrificing computational efficiency.

Acknowledgments

The authors thank Christian Muise for making POPGEN available and for helpful discussions. Pascal Bercher is the recipient of an Australian Research Council (ARC) Discovery Early Career Researcher Award (DECRA), project number DE240101245, funded by the Australian Government.