Paper deep dive
Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies
Md. Monjurul Islam, Sabah Binte Noor, Fazlul Hasan Siddiqui, Gahangir Hossain
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This study covers foundational concepts for enhancing plan-execution flexibility, including partial-order planning, the producer-consumer-threat formalism, and a range of deordering and reordering strategies. Creating a partial-order plan from a sequential one by removing unnecessary ordering constraints is a practical way to improve execution flexibility, and several methods have been proposed for this task. This study analyzes their capabilities across ordering, action handling, parameter handling, plan structure, concurrency, and complexity, and evaluates them against each other on a shared benchmark. The central finding is that block deordering-based approaches, which restructure causal dependencies through block-level grouping and subplan substitution, substantially outperform MaxSAT-based approaches despite the latter's theoretical guarantees of minimum reordering. The reason is structural: minimum reordering optimizes within the causal structure already present in the plan, whereas block deordering-based methods change that structure, exposing orderings that would otherwise appear necessary. A further distinction is practical: block deordering-based methods are anytime algorithms that always return a valid result, while MaxSAT-based methods fail entirely on a substantial portion of plans and offer no partial solution when they do. Block substitution further extends the parallel execution by formalizing non-concurrency constraints, though its impact is limited to domains with resource-based interactions. On efficiency, block deordering-based approaches achieve the highest flex gain per unit of computation time, while MaxSAT-based encodings incur large computational overhead.
Tags
Links
- Source: https://arxiv.org/abs/2609.16822v1
- Canonical: https://arxiv.org/abs/2609.16822v1
Trouble viewing inline? Open PDF directly →
Full Text
75,969 characters extracted from source content.
Expand or collapse full text
Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies Md. Monjurul Islam Email: monjurul.islam.cs@gmail.com Affiliation: Department of Computer Science and Engineering, Dhaka University of Engineering & Technology, Gazipur, Gazipur-1707, Bangladesh Sabah Binte Noor Email: sabah@duet.ac.bd Affiliation: Department of Computer Science and Engineering, Dhaka University of Engineering & Technology, Gazipur, Gazipur-1707, Bangladesh Fazlul Hasan Siddiqui Email: siddiqui@duet.ac.bd Affiliation: Department of Computer Science and Engineering, Dhaka University of Engineering & Technology, Gazipur, Gazipur-1707, Bangladesh Gahangir Hossain Email: Gahangir.Hossain@unt.edu Affiliation: Department of Data Science, , University of North Texas, Denton, TX, USA Abstract This study covers foundational concepts for enhancing plan-execution flexibility, including partial-order planning, the producer-consumer-threat formalism, and a range of deordering and reordering strategies. Creating a partial-order plan from a sequential one by removing unnecessary ordering constraints is a practical way to improve execution flexibility, and several methods have been proposed for this task. This study analyzes their capabilities across ordering, action handling, parameter handling, plan structure, concurrency, and complexity, and evaluates them against each other on a shared benchmark. The central finding is that block deordering-based approaches, which restructure causal dependencies through block-level grouping and subplan substitution, substantially outperform MaxSAT-based approaches despite the latter’s theoretical guarantees of minimum reordering. The reason is structural: minimum reordering optimizes within the causal structure already present in the plan, whereas block deordering-based methods change that structure, exposing orderings that would otherwise appear necessary. A further distinction is practical: block deordering-based methods are anytime algorithms that always return a valid result, while MaxSAT-based methods fail entirely on a substantial portion of plans and offer no partial solution when they do. Block substitution further extends the parallel execution by formalizing non-concurrency constraints, though its impact is limited to domains with resource-based interactions. On efficiency, block deordering-based approaches achieve the highest flex gain per unit of computation time, while MaxSAT-based encodings incur large computational overhead. keywordsAutomated Planning, Flexibility, Concurrency, Partial Order Planning 1 Introduction The capability of autonomous agents to adapt to unforeseen circumstances represents a fundamental requirement for effective operation in dynamic environments. Within the domain of automated planning, multiple methodologies have been developed to enhance agent flexibility, ranging from providing agents with alternative plan selections (Graham et al., 2003) to extending the applicability of existing plans through generalization techniques (Anderson and Farley, 1988). Plan generalization approaches generate partial-order plans (POPs) by reprieving specific action orderings until such orderings become inevitable. This strategy of minimizing action ordering decisions has been explored through various concepts, including plan deordering (Nguyen and Kambhampati, 2001; Veloso et al., 2002; Siddiqui and Haslum, 2012) and reordering (Muise et al., 2016) methodologies. While deordering the plan removes inessential action orderings, reordering the plan permits arbitrary changes to the action sequence. One way to produce a POP is through partial-order causal link (POCL) planning (Weld, 1994), which constructs a plan incrementally while maintaining causal support for every action precondition. A practical alternative is to take a sequential plan from a fast heuristic planner and remove the ordering constraints that are not necessary. Several methods have been developed for this post-processing task. Explanation-based order generalization (EOG) (Kambhampati and Kedar, 1994; Veloso et al., 2002) annotates each ordering with its causal justification and removes those without one. Block deordering (BD) (Siddiqui and Haslum, 2012) groups coherent operators into blocks and eliminates additional orderings by treating each block as a unit. Minimum reordering (MR) (Muise et al., 2016) encodes the deordering problem as partial weighted MaxSAT to find provably minimum reorderings and remove redundant actions; minimum reinstantiated reordering (MRR) (Waters et al., 2020) extends this with parameter rebinding within same-name operators. More recently, FIBS (Noor and Siddiqui, 2024) replaces subplans with alternatives using block-substitution, and CIBS (Noor and Siddiqui, 2025) extends FIBS to model and minimize non-concurrency constraints for parallel execution. We analyze capabilities of different algorithms across multiple dimensions (ordering, action handling, parameter handling, plan structure, concurrency, and complexity), and evaluate on 3,345 plans from 46 IPC domains. The analysis produces a result that is not obvious from the descriptions above. MR and MRR are designed to find minimum reorderings. Yet BD and FIBS produce substantially higher flex values on the same benchmarks, with large and statistically significant effect sizes against all other methods. The reason is that minimum reordering optimizes within the causal structure the original plan already has. Block deordering works differently: it reorganizes which operators share causal dependencies by grouping them into blocks, exposing ordering constraints that would otherwise appear necessary. Block-substitution goes further, replacing subplans with alternatives that carry different causal entailments entirely. The two families of methods are not in competition so much as they are solving different problems; restructuring causal structure turns out to be the more productive one for increasing flexibility. 2 Preliminaries This section outlines the foundational concepts required to comprehend the methods. It begins with defining planning tasks and plans within the finite-domain representation, followed by notions of partial-order planning, causal dependencies, and threats. Finally, it outlines key concepts of plan deordering and reordering. 2.1 Planning Task Classical planning problems are commonly represented using finite domain representation (FDR) (Helmert, 2011), which describes planning tasks through state variables and their associated value domains. The following definitions establish the mathematical foundation for subsequent analysis. Definition 1. In FDR, a planning task is denoted as Π=⟨,,si,sg⟩ = ,O,s_i,s_g , where: • X represents a finite non-empty set of state variables. A domain xD_x with a finite number of elements is associated with each x∈x . The pair ⟨x,d⟩ x,d with x∈x and d∈xd _x is a fact. The notion of state corresponds to a function s defined over X, such that s(x)∈xs(x) _x for all x∈x . The set of variables involved in a function is denoted as (s)vars(s). A function s s similar to a state s, but defined over a proper subset of X, represents a partial state where (s^)⊂vars( s) . • O represents the finite non-empty set of operators. Every operator o∈o is associated with two partial states, precondition (opre_o) and effect (oeff_o), along with an associated cost that is nonnegative (o∈ℝ0+cost_o ^+_0). An operator o can be applied in a state s iff o⊆spre_o s. Applying the operator o within state s transforms it into state s′=apply(s,o)s =apply(s,o) as specified in (1). s′(x)=apply(s,o)=o(x)if x∈(o)s(x)otherwises (x)=apply(s,o)= caseseff_o(x)&if x (eff_o)\\ s(x)&otherwise cases (1) • sis_i corresponds to the initial state, • sgs_g refers to a partial state that specifies the goal conditions. Definition 2. Let π=⟨o1,o2,…,ok,…,on⟩π= o_1,o_2,…,o_k,…,o_n be a plan, a sequence of operators, for a planning task Π=⟨,,si,sg⟩ = ,O,s_i,s_g . The plan π is valid iff preo1⊆sipre_o_1 s_i, preok+1⊆skpre_o_k+1 s_k for every k∈1,2,…,n−1k∈\1,2,…,n-1\ where sk=(sk−1,ok)s_k=apply(s_k-1,o_k), and sg⊆sns_g s_n. Definition 3. The prodo, conso, and delo represent the facts that an operator o produces, consumes, and deletes, respectively. The fact−- • ⟨x,d⟩∈prodo x,d ∈ prod_o iff ⟨x,d⟩∈o x,d _o. • ⟨x,d⟩∈conso x,d ∈ cons_o iff ⟨x,d⟩∈o x,d _o. • ⟨x,d⟩∈delo x,d ∈ del_o iff- i. either x∉vars(o)x∉ vars(cons_o) or o(x)=dcons_o(x)=d, and i. o(x)=d′eff_o(x)=d such that d′∈(x∖d)\ d ∈(D_x \d\). 2.2 Partial-Order Planning Operators can be executed in any possible sequence using the partial-order plan (POP) framework while imposing partial orderings over them. It is assumed that each operator is individually identifiable, even if an operator may appear multiple times within a POP. Definition 4. A POP is represented as πpop=⟨,≺⟩ _pop= , , regarding a planning task Π=⟨,,si,sg⟩ = ,O,s_i,s_g , where: • O denotes the set of operators, and • ≺ represents ordering constraints over O. The notation ≺o_a o_b represents a ordering constraint between two operators oa,ob∈o_a,o_b , which specifies that the operator oao_a needs to be executed at any time before the execution of operator obo_b. ≺ exhibits transitive property, which means that if oa≺obo_a o_b and ob≺oco_b o_c, then oa≺oco_a o_c. Basic orderings represent constraints that are not transitively inferred by other constraints in the set. Plan flexibility quantification uses the metric flex (Siddiqui and Haslum, 2012), which is the proportion of the pairs of operators that do not have fundamental or transitive ordering to all operator pairs. Higher flex values indicate greater execution flexibility, though the relationship between flexibility and practical adaptability depends on domain-specific factors. Definition 5. Let πpop=⟨,≺⟩ _pop= , be a POP. The flex value of the plan πpop _pop is (πpop)flex( _pop) and is calculated as specified in (2). (πpop)=1−|≺|Σi=1||−1iflex( _pop)=1- | | _i=1^|O|-1i (2) where Σi=1||−1i _i=1^|O|-1i is the maximum number of pairings that might be constructed with a collection of |||O| items. The framework of producer-consumer-threat (PCT) (Bäckström, 1998) establishes ordering structures by identifying operator relationships regarding fact production, consumption, and deletion. This formalism introduces causal links that map operator preconditions to effect providers. Definition 6. A causal link op→⟨x,d⟩oco_p x,d o_c between opo_p and oco_c specifies that op≺oco_p o_c and the operator opo_p produces ⟨x,d⟩ x,d for the operator oco_c, where ⟨x,d⟩∈(prodop∩consoc) x,d ∈(prod_o_p∩ cons_o_c). A threat is defined as a conflict between a causal link op→⟨x,d⟩oco_p x,d o_c and the effect of an operator odo_d, where odo_d deletes ⟨x,d⟩ x,d and can be ordered in between opo_p and oco_c. A promotion, which adds the ordering od≺opo_d o_p, or a demotion, which adds the ordering oc≺odo_c o_d, can resolve a threat between a causal link op→⟨x,d⟩oco_p x,d o_c and an operator odo_d. A POP is valid if causal relationships support each operator precondition without any threat (Weld, 1994). Three labels, PC,CTPC,CT, and TPTP, are introduced by Siddiqui and Haslum (2012) to outline a POP’s ordering constraints. Definition 7. Let πpop=⟨,≺⟩ _pop= , be a POP and Re(oa≺ob)Re(o_a o_b) represents the ordering reasons for an ordering constraint oa≺obo_a o_b. An ordering restriction oa≺obo_a o_b might form for three reasons: • PC(⟨x,d⟩)∈Re(oa≺ob)PC( x,d )∈ Re(o_a o_b) is the producer-consumer of a fact ⟨x,d⟩ x,d , where oao_a produces ⟨x,d⟩ x,d and obo_b consumes ⟨x,d⟩ x,d . The fact ⟨x,d⟩ x,d may be produced and consumed by multiple operators. One operator oao_a is assigned via a causal link to obtain ⟨x,d⟩ x,d for obo_b. • CT(⟨x,d⟩)∈Re(oa≺ob)CT( x,d )∈ Re(o_a o_b) is the consumer-threat of a fact ⟨x,d⟩ x,d , where operator oao_a consumes ⟨x,d⟩ x,d and obo_b deletes ⟨x,d⟩ x,d . • TP(⟨x,d⟩)∈Re(oa≺ob)TP( x,d )∈ Re(o_a o_b) is the threat-producer of a fact ⟨x,d⟩ x,d , where operator oao_a deletes the fact ⟨x,d⟩ x,d and there exist one or more causal link ob→⟨x,d⟩oco_b x,d o_c for some oc∈o_c . Causal links of a POP are denoted by the label PCPC, and the demotion and promotion ordering constraints of the plan are denoted by CTCT and TPTP, respectively. These labels assist in identifying and monitoring the rationale behind the orderings in a POP. 2.3 Plan Deordering and Reordering Plan deordering and reordering are two key concepts for attaining plan execution flexibility. Formal definitions of these notions are given in Bäckström (1998). A POP is assumed to be transitively closed in the Definition 8. Definition 8. Let πp=⟨,≺p⟩ _p= , _p and πq=⟨,≺q⟩ _q= , _q be two different POPs with respect to Π (a planning task). Therefore: • πq _q is a deordering of πp _p with respect to Π iff both πp _p and πq _q are valid POP and ≺q⊆≺p _q _p. • πq _q is a proper deordering of πp _p with respect to Π iff πq _q is a deordering of πp _p and ≺q⊂≺p _q⊂ _p. • πq _q is a reordering of πp _p with respect to Π iff both πp _p and πq _q are valid POP. • πq _q is a proper reordering of πp _p with respect to Π iff πq _q is a reordering of πp _p with ≺q≠≺p _q≠ _p. • πq _q is a minimum deordering of πp _p with respect to Π iff−- 1. πq _q is a deordering of πp _p, and 2. there exists no partial-order plan πr=⟨,≺r⟩ _r= , _r such that πr _r is a deordering of πp _p with |≺r|<|≺q|| _r|<| _q|. • πq _q is a minimum reordering of πp _p with respect to Π iff−- 1. πq _q is a reordering of πp _p, and 2. there exists no partial-order plan πr=⟨,≺r⟩ _r= , _r such that πr _r is a reordering of πp _p and |≺r|<|≺q|| _r|<| _q|. 3 Partial-Order Causal Link-based Approach The partial-order causal link (POCL) (Weld, 1994) planning framework serves as the foundation for the traditional method of creating a partial-order plan (POP). An initial POP is iteratively refined through modifications involving operators, causal links, and ordering constraints in this paradigm. Such a preliminary plan typically begins with an initial operator and a goal operator. Refinement steps may introduce a new operator, insert a causal link connecting two operators, or establish an ordering constraint between them. A POP is considered completed once each operator’s precondition is protected by a threat-free causal link. The two most popular POCL-based partial-order planners are VHPOP (Simmons and Younes, 2011) and UCPOP (Penberthy and Weld, 1992). Furthermore, the POCL strategy has been adapted to find temporal plans through state-based forward search techniques (Coles et al., 2021), and it also forms the foundation for numerous hierarchical planning approaches (Bercher et al., 2017; Bercher et al., 2016; Bit-Monnot et al., 2020; Bit-Monnot et al., 2016). In addition to POCL, other techniques have been developed to generate POPs. One such method is Petri net unfolding (Hickmott et al., 2007), which uses iterative unfolding of a specifically constructed Petri net to simulate the execution of a forward planning system. Another prominent approach is Graphplan (Blum and Furst, 1997), which leverages a compact structure called a planning graph to derive optimal POPs. Over time, this planning graph has been used as a preprocessing mechanism for diverse planning systems, including STAN (Fox and Long, 2001), IPP (Koehler, 1999), and Blackbox (Kautz and Selman, 1998). 4 Partial Weighted MaxSAT-based Approach Transforming sequential plans into partial-order plans through deordering or reordering is a prominent approach for generating POPs. Early strategies for deordering involved generalizing and storing sequential plans in triangle tables (Regnier and Fade, 1991; Fikes and Nilsson, 1971), primarily to support plan modification and reuse. Triangle tables were later utilized as a preprocessing technique to take a sequential plan with conditional effects and extract partial ordering (Winner and Veloso, 2002). More recent work has applied partial weighted MaxSAT encodings to enhance execution flexibility by reducing the orderings in a plan (Muise et al., 2016). Building on this, the action reinstantiation extends the MaxSAT formulation with additional constraints, allowing operator parameter reassignment(Waters et al., 2018; Waters et al., 2020). The partial weighted MaxSAT problem extends the traditional satisfiability (SAT) problem by introducing two categories of clauses: hard and soft. Hard clauses function like those in the standard SAT problem and must always be satisfied. Soft clauses are not mandatory; instead, each is assigned a weight indicating its relative importance. Finding an assignment that satisfies all hard clauses and maximizes the cumulative weight of completely satisfied soft clauses is the goal. 4.1 MR Encodings The task of achieving a plan’s minimum reordering (MR) as a partial weighted MaxSAT problem instance is formulated by Muise et al. (2016). The solution of the instance corresponds to a POP, which they denote as the target POP. For a given POP or sequential plan π=⟨,≺⟩π= , , the encoding employs three categories of propositional variables−- • xox_o: Indicates the presence of operator o in the target POP for each o∈o . • κ(oa,ob)κ(o_a,o_b): Indicates that the the target POP includes the ordering constraint oa≺obo_a o_b for each operator pair oa,ob∈o_a,o_b . • Υ(op,⟨x,d⟩,oc) (o_p, x,d ,o_c): Indicates that a causal link op→⟨x,d⟩oco_p x,d o_c is present in the target POP, for a pair of operator op,oc∈o_p,o_c , specifies that the operator opo_p produces ⟨x,d⟩ x,d for the operator oco_c, where ⟨x,d⟩∈(prodop∩consoc) x,d ∈(prod_o_p∩ cons_o_c). The encoding procedure starts with defining hard clauses as Boolean formulae, which are then converted into conjunctive normal form (CNF), followed by the introduction of soft clauses and their associated weights. A soft clause with weight k is represented by the syntax (…)k k(…), whereas no weight indication represents a hard clause. To guarantee correctness, the encoding defines formulae (3) and (4) that enforce acyclicity in the target POP, where (4) ensures that the ordering constraints include the transitive closure. Formula (5) includes the initial and goal operators. Operators are treated as universally quantified, and in the case of formula (6), it is assumed that oI≠oi≠oGo_I≠ o_i≠ o_G. Formula (7) guarantees that every causal link remains threat-free by enforcing the required promotion or demotion orderings, while formula (8) ensures that each precondition is backed by an appropriate causal link. (¬κ(o,o)) ( κ(o,o)) (3) κ(op,oq)∧κ(oq,or)→κ(op,or) κ(o_p,o_q) κ(o_q,o_r) κ(o_p,o_r) (4) (xoI)∧(xoG) (x_o_I) (x_o_G) (5) xoi→κ(oI,oi)∧κ(oi,oG) x_o_i κ(o_I,o_i) κ(o_i,o_G) (6) Υ(op,⟨x,d⟩,oc)→⋀od:⟨x,d⟩∈delodxod→κ(od,op)∨κ(oc,od) (o_p, x,d ,o_c) _o_d: x,d ∈ del_o_dx_o_d κ(o_d,o_p) κ(o_c,o_d) (7) xoc→⋀⟨x,d⟩∈consoc⋁op:⟨x,d⟩∈prodopκ(op,oc)∧Υ(op,⟨x,d⟩,oc) x_o_c _ x,d ∈ cons_o_c\ _o_p:~ x,d ∈ prod_o_pκ(o_p,o_c) (o_p, x,d ,o_c) (8) For each operator and ordering variable in the encoding, a soft unit clause is introduced in formulae (9) and (10) containing the negation of that variable. If any of these unit clauses is violated, it indicates that the operator or the ordering constraint associated with the variable of the violated clause is incorporated into the solution. As a result, solutions with higher weights in the encoding correspond to target POPs that contain fewer ordering constraints. (¬xo)costo+||2+1,∀o∈(∖oI,oG) cost_o+|O|^2+1( x_o)~~,~~∀ o∈(O \o_I,o_G\) (9) (¬κ(oi,oj))1,∀oi,oj∈ 1( κ(o_i,o_j))~~,~~∀ o_i,o_j (10) 4.2 MRR Encodings The partial weighted MaxSAT encoding for achieving a plan’s minimum reordering is extended by Waters et al. (2020) through allowing modifications to both operator parameters and ordering constraints to achieve greater flexibility, defined as minimum reinstantiated reordering (MRR). Variables are denoted by symbols like x, y, and z, constants by c, and terms by t, u, and v. The definition of a term t is an ordered series of items, where t[i]t[i] is the i-th element in the sequence. A mapping of terms with variables is designated as substitution Ψ ; for instance, Ψ=x1/t1,x2/t2,…,xn/tn =\x_1/t_1,x_2/t_2,…,x_n/t_n\ maps xix_i to the corresponding term tit_i for all i∈1,2,…,ni∈\1,2,…,n\. The sets of variables and constants that appear in a given structure η are denoted by vars(η)vars(η) and consts(η)consts(η). In this approach, a POP is represented as π=⟨,Ψ,≺⟩π= , , , where the set of operators is represented by O, ≺ is a strict partial order over O that is transitively closed, and Ψ is complete with respect to O. Definition 9. Let πp=⟨,Ψ,≺⟩ _p= , , and πq=⟨,Ψ′,≺′⟩ _q= , , be two different POPs, then: • πq _q is a reinstantiated reordering of πp _p if πp _p and πq _q both are valid. • πq _q is a minimum reinstantiated reordering of πp _p if πq _q is a reinstantiated reordering of πp _p and there does not exist a POP πr=⟨,Ψ′,≺′⟩ _r= , , such that πr _r is a reinstantiated reordering of πp _p with |≺′|<|≺′|| |<| |. An operator is defined as a tuple o=⟨o,o,o⟩o= _o,pre_o,eff_o , where varsovars_o denotes the set of variables, and both oeff_o and preopre_o are the finite sets of facts containing varsovars_o’s variables. If both preopre_o and oeff_o are made up entirely of ground facts, then o is considered as a ground operator. ⟨op,q(t→),oc,q(u→)⟩ o_p,q( t),o_c,q( u) represents a causal link, where q(u→)q( u) and q(t→)q( t) are literals, with q(t→)∈prodoq( t)∈ prod_o and q(u→)∈consoq( u)∈ cons_o. The MRR encoding adds two additional categories of propositional variables in addition to the x and κ utilized in the MR encoding: • ε(u,v) (u,v): Encodes that in the final POP the condition Ψ(t)=Ψ(u) (t)= (u) must be satisfied. • τ(op,t→,oc,u→)τ(o_p, t,o_c, u): Encodes that there exists some q such that the ⟨op,q(t→),oc,q(u→)⟩ o_p,q( t),o_c,q( u) causal link remains threat-free within the final POP. To compute the MRR of a partial-order plan πp=⟨,Ψ,≺⟩ _p= , , , the following encoding together with formulae (3) through (6) is used. Formulae (11) and (12) specify that the equality relation over variables and constants is both symmetric and transitive, whereas the mapping of each variable to a single object is guaranteed by Formula (13). Formulae (14) and (15) formalize the conditions required for the validity of the target POP. ε(u,v)↔ε(v,u) (u,v) (v,u) (11) ε(u,v)∧ε(v,t)→ε(u,t) (u,v) (v,t)→ (u,t) (12) ⋀x∈vars(⋁c∈constsε(x,c)∧⋀c′≠c′c′,c′∈consts:¬ε(x,c′)∨¬ε(x,c′)) _x∈ vars_O( _c∈ consts_O (x,c)~~~ _ c ,c ∈ consts_O:c ≠ c (x,c ) (x,c )) (13) ⋀q(u→)∈consoc⋁q(t→)∈prodopτ(op,t→,oc,u→)∧κ(op,oc) _q( u)∈ cons_o_c\ _q( t)∈ prod_o_pτ(o_p, t,o_c, u) κ(o_p,o_c) (14) τ(op,t→,oc,u→)→⋀1≤i≤|t→|ε(t→[i],u→[i])∧⋀t→=v→,od≠ocq(v→)∈delod:(κ(od,op)∨κ(oc,od)) τ(o_p, t,o_c, u)→ _1≤ i≤| t| ( t[i], u[i])~~~ _ q( v)∈ del_o_d: t= v,o_d≠ o_c(κ(o_d,o_p) κ(o_c,o_d)) (15) If a POP has fewer than k ordering constraints, determining if it admits a minimal reinstantiated reordering is NP-complete. It is impossible to approximate the problem of finding such a reordering within a constant factor. A key limitation of MRR is that substitutions are restricted to operators sharing the same name, but it does not permit replacing operator sets with different operator names or sizes. 5 Explanation-based Order Generalization Another well-known approach, Explanation-based Order Generalization (EOG), employs validation structures as proofs of correctness and modifies plans to resolve inconsistencies (Veloso et al., 2002; Kambhampati, 1994; Kambhampati and Hendler, 1992). EOG has been further refined to support conditional effects (Noor and Siddiqui, 2022). The EOG deorders plans by creating a validation structure, creating a causal link for each operator’s preconditions, and using promotions or demotions to mitigate threats to those causal links (Kambhampati and Kedar, 1994; Veloso et al., 2002). Given a total-order plan π of a planning task Π=⟨,,si,sg⟩ = ,O,s_i,s_g , EOG emulates the initial and goal conditions of Π by augmenting π with a couple of additional operators, oIo_I and oGo_G. Specifically, preoI=∅pre_o_I= , oI=sieff_o_I=s_i, preoG=sgpre_o_G=s_g, and oG=∅eff_o_G= , with oI≺oGo_I o_G and oI≺o≺oGo_I o o_G for all o∈(∖oI,oG)o∈(O \o_I,o_G\). The validation structure is subsequently constructed, and threats are resolved by introducing promotion and demotion orderings. To minimize unnecessary transitive orderings, it systematically binds causal links to the earliest possible producers. 5.1 Plan Deordering with Conditional Effects Conditional effects (Haslum et al., 2019) enable operators to present complex scenarios more effectively by allowing a single operator to produce different outcomes depending on the specific conditions. Noor and Siddiqui (2022) introduce a method for annotating operator orderings in plans with conditional effects, allowing such plans to be transformed into a Partial-Order Plan (POP). Definition 10. Let Π=⟨,c,si,sg⟩ = ,O_c,s_i,s_g be a planning task, where cO_c is a set of a finite number of operators with conditional effects. An effect of an operator o∈co _c consists of triples ⟨cond,x,d⟩ cond,x,d , forming a partial state where condcond denotes the effect condition, which may be empty. When o is applicable in the state s, applying it yields the state s′=apply(o,s)s =apply(o,s), where x∈x takes the value d∈Dxd∈ D_x if and only if cond⊆scond s. Definition 11. Let πpop=⟨,≺⟩ _pop= , be a POP and two operators oi,oj∈o_i,o_j with conditional effects. • oio_i is considered as a candidate producer of ⟨x,d⟩ x,d for operator ojo_j iff: 1. oj⊀oio_j o_i, 2. ⟨cond,x,d⟩∈oi cond,x,d _o_i and there exists other candidate producer op∈o_p for every ⟨x′,d′⟩∈cond x ,d ∈ cond where op≠ojo_p≠ o_j, and 3. there exists no operator ok∈o_k with ⟨cond1,x,d1⟩∈ok cond_1,x,d_1 _o_k such that oj⊀ok⊀oio_j o_k o_i, d1∈(x∖d)d_1∈(D_x \d\), and there exists other candidate producer op∈o_p for each ⟨x′,d′⟩∈cond1 x ,d ∈ cond_1. • oio_i is considered as an earliest candidate producer of ⟨x,d⟩ x,d for operator ojo_j iff oio_i is a candidate producer of ⟨x,d⟩ x,d for ojo_j and there does not exists any candidate producer oko_k of ⟨x,d⟩ x,d for ojo_j with ok≺oio_k o_i. Definition 12. Let πpop=⟨,≺⟩ _pop= , be a POP and o∈o be an operator with conditional effects. The operator o produces, consumes, and deletes facts, which are represented by prod_o, cons_o, and del_o, respectively. The fact−-: • ⟨x,d⟩∈conso x,d ∈ cons_o if ⟨x,d⟩∈preo x,d ∈ pre_o or ⟨x,d⟩∈cond x,d ∈ cond such that ⟨cond,x′,d′⟩∈o cond,x ,d _o and there exists an operator ok∈o_k with o→⟨x′,d′⟩oko x ,d o_k. • ⟨x,d⟩∈prodo x,d ∈ prod_o if ⟨cond,x,d⟩∈o cond,x,d _o and there exists other candidate producer op∈o_p for each ⟨x′,d′⟩∈cond x ,d ∈ cond such that op≺o_p o. • ⟨x,d⟩∈delo x,d ∈ del_o if x∉vars(o)x∉ vars(cons_o) or conso(x)=dcons_o(x)=d, ⟨cond,x,d′⟩∈o cond,x,d _o, where d′∈(x∖d)d ∈(D_x \d\), and there exists a candidate producer op∈o_p for each ⟨x′,d′⟩∈cond x ,d ∈ cond. Re(oa≺ob)Re(o_a o_b) denotes the ordering reasons between two operators oao_a and obo_b with conditional effects, which can fall into the categories PC, CT, TP, and OC. OC(⟨x,d⟩)OC( x,d ) denotes an obstructor-consumer relation for a fact ⟨x,d⟩ x,d , which occurs when oao_a prevents obo_b from receiving the fact ⟨x,d⟩∈cond x,d ∈ cond, such that ⟨cond,x′,d′⟩∈ob cond,x ,d _o_b. If there is an operator oko_k that yields ⟨x,d⟩ x,d and ob≺ok≺oao_b o_k o_a, then OC(⟨x,d⟩)∈Re(oa≺ob)OC( x,d )∈ Re(o_a o_b) is considered threatened. This identified threat may be mitigated in two ways: through Promotion, by including pOC(⟨x,d⟩)pOC( x,d ) in Re(ok≺oa)Re(o_k o_a), or through Demotion, by including OCp(⟨x,d⟩)OCp( x,d ) in Re(ob≺ok)Re(o_b o_k). The Deordering Plan with Conditional Effects (DConE) algorithm constructs causal links to build a validation framework for a POP. Similar to the EOG, DConE identifies causal links using the earliest candidate producers for each fact ⟨x,d⟩ x,d required by an operator. While determining a candidate producer of ⟨x,d⟩ x,d for an operator oio_i, additional orderings may be needed due to OCOC (obstructor-consumer) reasons. This occurs when an operator odo_d prevents another operator opo_p from providing ⟨x,d⟩ x,d to oio_i through a conditional effect ⟨cond,x,d′⟩∈od cond,x,d _o_d, where d′∈(x∖d)d ∈(D_x \d\). To address this, the algorithm introduces an ordering reason OC(⟨x,d⟩)OC( x,d ) in Re(oq≺od)Re(o_q o_d) for some operator oqo_q that obstructs the effect ⟨cond,x,d′⟩ cond,x,d of odo_d from being triggered. The ordering oq≺odo_q o_d prevents condcond from holding, ensuring that odo_d no longer deletes ⟨x,d⟩ x,d . This process repeats iteratively until a valid candidate producer is found. After establishing a causal link between two operators, DConE adds conditional causal links for each fact in the producer’s effect condition and resolves all threats to PCPC and OCOC reasons through promotion or demotion of the threatening operators. 6 Block Deordering-based Approach Block deordering (Siddiqui and Haslum, 2012) identifies coherent sets of operators, known as blocks, to remove additional orderings from the plan. Block deordering groups coherent operators into blocks to reduce the POP’s ordering constraints, resulting in a block decomposed partial-order (BDPO) plan (Siddiqui and Haslum, 2015). Each block contains a set of operators; operators from two disjoint blocks cannot interleave, allowing the blocks to be executed in any sequence. Additionally, blocks can be nested, which allows a block to have one or more inner blocks. Overlapping between blocks is not permitted. A block fully enclosed within another is called an inner block, while a block not contained within any other is referred to as an outer block. Block deordering has also been leveraged to improve overall plan quality (Siddiqui and Haslum, 2015), generate macro-actions (Chrpa and Siddiqui, 2015), and improve flexibility via block-substitution (Noor and Siddiqui, 2024). Definition 13. A BDPO plan is denoted as πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B , where O be a collection of operators, ≺ is a collection of orderings within O, and ℬB is a set of blocks. For a block b∈ℬb , if op,oq∈bo_p,o_q∈ b and op≺oqo_p o_q, then there does not exist an operator or∉bo_r∉ b such that op≺or≺oqo_p o_r o_q. For any two blocks bp,bq∈ℬb_p,b_q , exactly one of the following holds: bp⊂bqb_p⊂ b_q, bq⊂bpb_q⊂ b_p, or bp∩bq=∅b_p∩ b_q= . A block b can be characterized by its preconditions and effects, similar to an operator. If some operator o∈bo∈ b consumes ⟨x,d⟩ x,d and no operator o′∈bo ∈ b provides ⟨x,d⟩ x,d to operator o, then a fact ⟨x,d⟩ x,d is one of the preconditions of b. Conversely, if an operator o∈bo∈ b generates ⟨x,d⟩ x,d and no subsequent operator within b modifies it, then ⟨x,d⟩ x,d is included in the effects of b. Unlike an individual operator, a block can have multiple effects on the same or different variables. For example, if oi,oj∈bo_i,o_j∈ b with oi⊀ojo_i o_j, oj⊀oio_j o_i, ⟨x,d⟩∈oi x,d _o_i, and ⟨x,d′⟩∈oj x,d _o_j, then a block b has both ⟨x,d⟩ x,d and ⟨x,d′⟩ x,d as its effects (where d≠d′d≠ d ). The labels PCPC (producer-consumer), CTCT (consumer-threat), and TPTP (threat-producer) can also be used to annotate ordering relations between blocks. Definition 14. Let a BDPO plan πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B with b∈ℬb be a block, then: • If oi∈bo_i∈ b be an operator with ⟨x,d⟩∈preoi x,d ∈ pre_o_i and there exists no operator oj∈bo_j∈ b with i≠ji≠ j that delivers ⟨x,d⟩ x,d to oio_i via a causal link oj→⟨x,d⟩oio_j x,d o_i, then the fact ⟨x,d⟩∈preb x,d ∈ pre_b. • If oi∈bo_i∈ b be an operator with ⟨x,d⟩∈oi x,d _o_i and no subsequent operator oj∈bo_j∈ b (with oi≺ojo_i o_j) produces a different value ⟨x,d′⟩ x,d for the same variable x with d′∈(x∖d)d ∈(D_x \d\), then the fact ⟨x,d⟩∈b x,d _b. Definition 15. For a block b, the sets of facts that it consumes, produces, and deletes are denoted as consb, prodb, and delb, respectively. Where: • A fact ⟨x,d⟩∈consb x,d ∈ cons_b if and only if ⟨x,d⟩∈preb x,d ∈ pre_b. • A fact ⟨x,d⟩∈prodb x,d ∈ prod_b if and only if ⟨x,d⟩∉consb x,d ∉ cons_b, ⟨x,d⟩∈b x,d _b, and no other effect ⟨x,d′⟩∈b x,d _b exists with d′∈(x∖d)d ∈(D_x \d\). • A fact ⟨x,d⟩∈delb x,d ∈ del_b if and only if either x∉vars(consb)x∉ vars(cons_b) or consb(x)=dcons_b(x)=d, and there exists an effect ⟨x,d′⟩∈b x,d _b with d′∈(x∖d)d ∈(D_x \d\). Definition 16. Let a BDPO plan πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B with a pair of blocks b,b′∈ℬb,b and ⟨x,d⟩∈consb′ x,d ∈ cons_b , then: • If ⟨x,d⟩∈b x,d _b, b≺b′b b , and no other block b′∈ℬb exists such that ⟨x,d⟩∈delb′ x,d ∈ del_b and b′⊀b′⊀b b b, then block b is a candidate producer of the fact ⟨x,d⟩ x,d for b′b . • If there is no other candidate producer b′b of ⟨x,d⟩ x,d for b′b with b′≺b b, then block b is considered as an earliest candidate producer of ⟨x,d⟩ x,d for b′b . Block deordering builds a valid BDPO plan by taking a total-order plan as input. The total-order plan is first converted into a POP π=⟨,≺⟩π= , using EOG. Next, a block b=ob=\o\ is created and added to ℬB for every operator o∈o to construct an initial BDPO plan πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B . Ordering constraint b≺b′b b is introduced for every ordering o≺o′o o present in ≺ , where o∈bo∈ b, o′∈b′o ∈ b , and b,b′∈ℬb,b . The blocks with a single operator are denoted as primitive block and the blocks with multiple operators are denoted as compound block. The term block is used in a general sense to cover both. Block deordering then applies a set of rules to remove additional orderings in πbdpop _bdpop. Rule 1. A valid BDPO plan πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B with an ordering bp≺bqb_p b_q and let b be a block. i. If bp∈b_p∈ b, bq∉b_q∉ b, and bp⊀b′b_p b for all b′∈(b∖bp)b ∈(b b_p), therefore, PC(⟨x,d⟩)PC( x,d ) can be eliminated from Re(bp≺bq)Re(b_p b_q) if ⟨x,d⟩∈preb x,d ∈ pre_b and there exists bp∉b_p∉ b which can create causal links bp→⟨x,d⟩bqb_p x,d b_q and bp→⟨x,d⟩b_p x,d b. i. If bp∈b_p∈ b, bq∉b_q∉ b, and b∩bq=∅b∩ b_q= , therefore, CT(⟨x,d⟩)CT( x,d ) can be eliminated from Re(bp≺bq)Re(b_p b_q) if ⟨x,d⟩∉consb x,d ∉ cons_b. i. If bp∉b_p∉ b, bq∈b_q∈ b, and bp∩b=∅b_p∩ b= , therefore, CT(⟨x,d⟩)CT( x,d ) can be eliminated from Re(bp≺bq)Re(b_p b_q) if ⟨x,d⟩∉delb x,d ∉ del_b. iv. If bq∈b_q∈ b and bp∉b_p∉ b, therefore, TP(⟨x,d⟩)TP( x,d ) can be eliminated from Re(bp≺bq)Re(b_p b_q) if b contains all blocks b′b with bq→⟨x,d⟩b′b_q x,d b . Block deordering begins by examining each ordering in the initial BDPO plan from top to bottom, attempting to remove them greedily. If Rule 1 can eliminate all of the ordering reasons for an ordering bp≺bqb_p b_q, then that ordering is eliminated. The ordering bp≺bqb_p b_q is kept, and the algorithm proceeds to the subsequent ordering if some reasons cannot be eliminated. Whenever an ordering is successfully removed, the modified BDPO plan is returned by the algorithm. The deordering process is then restarted by the algorithm from the top of this most recent plan. Until no more orderings can be eliminated from the most recent BDPO plan, this iterative process keeps going. 6.1 Flexibility Improvement via Block-Substitution Block-substitution (Noor and Siddiqui, 2024) permits changing a block inside a valid BDPO plan without compromising the plan’s validity. The block that is being replaced is referred to as the original block, and the block that is replacing it is referred to as the substituting block. Block substitution permits the replacement block to originate either from within the plan or from an external source. When the replacement block is drawn from within the same plan, the process is referred to as an internal block substitution. Establishing causal links for the replacing block’s preconditions is required for the substitution process, as well as restoring all causal links that the original block had previously supported. Furthermore, any threats introduced by the substitution must be identified and resolved to maintain the validity of the plan. Definition 17. Let πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B be a valid BDPO plan, b∈ℬb , and a subplan b~=⟨~,≺~⟩ b= O, with ~⊂ O . A new BDPO plan πbdpop′=⟨′,≺′,ℬ′⟩π _bdpop= , ,B is produced if b is substituted with b~ b where b∉ℬ′b and b~∈ℬ′ b . If πbdpop′π _bdpop is a valid BDPO plan, then the block-substitution is considered valid. Definition 18. Let πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B be a valid BDPO plan and some causal link bp→⟨x,d⟩bcb_p x,d b_c is threatened by bt∈ℬb_t , where ⟨x,d⟩∈delbt x,d ∈ del_b_t and bp,bc∈ℬb_p,b_c . A threat is considered resolved if a threat-resolution strategy from the following can be used without creating a cycle in πbdpop _bdpop: i. Promotion: introduce the ordering bt≺bpb_t b_p into ≺ . i. Demotion: introduce the ordering bc≺btb_c b_t into ≺ . i. Internal substitution: replace btb_t with bcb_c, or bcb_c with btb_t. The procedure replaces a block b with a substituting block b~ b. The process starts by making sure that every precondition of the b~ b is supported by a causal link, but b~ b’s preconditions are already satisfied if it is internal. For an external block, b~ b is first included in the plan, and causal links are established using the earliest candidate producers for each precondition; if any precondition cannot be supported, the substitution fails. Then, using b~ b as the new producer, every causal link that block b initially supported is restored. If b~ b does not produce a required fact for any dependent block, the substitution is unsuccessful. Once these causal links are in place, b is removed from the plan. Finally, any threats introduced by the substitution are identified and resolved using threat-resolution strategies, including promotion, demotion, or internal block-substitution. In some situations, replacing a conflicting block with b~ b resolves threats while maintaining plan validity. The block-substitution process has an overall worst-case complexity of O(n2p2)O(n^2p^2), where p is the highest possible number of facts in any operator’s effect or precondition and n is the number of operators in the plan. Flexibility Improvement via Block-Substitution (FIBS) (Noor and Siddiqui, 2024) algorithm generates a valid BDPO plan given a valid total-order plan π as input. First, using EOG, a partial-order plan πpop=(,≺) _pop=(O, ) is created from π. A BDPO plan πbdpop=⟨,≺,ℬ⟩ _bdpop= , ,B is then created from this partial-order plan by constructing a block b=ob=\o\ for each o∈o . In the next phase, ordering constraints are removed from πbdpop _bdpop by substituting blocks, where initially only primitive blocks are considered, since no compound blocks have yet been formed. Subsequently, block deordering introduces compound blocks to eliminate additional orderings, further increasing plan flexibility. Finally, the procedure of substituting blocks is employed once more to replace both compound and primitive blocks, minimizing orderings in the plan. The procedure of substituting blocks examines each basic ordering bi≺bjb_i b_j in the BDPO plan and attempts to remove it by substituting bjb_j or, if necessary, bib_i, while ensuring causal links and plan validity are maintained. After a successful removal, the procedure is restarted from the current BDPO plan’s beginning, iterating until no further orderings can be eliminated. This two-stage application, before and after block deordering, allows the algorithm to separately evaluate the impact of primitive and compound block substitutions on overall plan flexibility. FIBS significantly enhances plan flexibility while reducing computational and plan costs through efficient block-substitution within BDPO plans, outperforming existing approaches like EOG and MaxSAT reorderings. However, FIBS restricts candidate subplans for substitution to blocks within a BDPO plan, leaving other potentially useful subplans unexplored, and it has not yet been evaluated across diverse planning paradigms or with planners beyond LAMA. 6.2 Concurrency Improvement via Block- Substitution Partial-order plans enable parallel execution by indicating which operators cannot run concurrently. A parallel plan is a POP that permits concurrent operator execution. Noor and Siddiqui (2025) transform sequential plans into parallel ones and define non-concurrency constraints in FDR. They improved the flexibility of a plan’s execution by expanding block deordering and block substitution approaches, thereby exploiting potential parallelism to minimize overall execution time. Definition 19. A parallel plan is denoted as π=⟨,≺,#⟩ _P= , ,\# , which basically extends a POP ⟨,≺⟩ , with an irreflexive and symmetric relation #\#, which represents non-concurrency constraints over O. Two operators, oao_a and obo_b, have a non-concurrency constraint, expressed as oa#obo_a\#o_b, if consoa(x)≠consob(x)cons_o_a(x)≠ cons_o_b(x), prodoa(x)≠prodob(x)prod_o_a(x)≠ prod_o_b(x), or consoa(x)≠prodob(x)cons_o_a(x)≠ prod_o_b(x) for any variable x∈x , which means that they cannot be executed simultaneously. Definition 20. Let π=⟨,≺,#⟩ _P= , ,\# be a parallel plan. The ratio of the operator pairs that can be executed simultaneously to the maximum possible operator pairs is the concurrent flexibility value of the parallel plan π _P, as specified in (16), expressed as (π)cflex( _P). (π)=1−∑1≤b<a≤||1if oa≺ob, ob≺oa, or oa#ob0otherwise∑n=1||−1ncflex( _P)=1- Σ _1≤ b<a≤|O| cases1&if $o_a o_b$, $o_b o_a$, or $o_a\#o_b$\\ 0&otherwise cases _n=1^|O|-1n (16) Two unordered operators of a partial-order plan can be executed in any sequence without invalidating the plan, but they can’t always run at the same time because they might use the same resources. To safely run operators in parallel, we must make sure they don’t interfere with each other. Knoblock (1994) grouped parallel plans based on how operators depend on each other, describing the simplest kind as those where operators are independent with respect to the goal, meaning the final result is the same whether they run one after another or together. Noor and Siddiqui (2025) focus on using such independent operators to speed up plan execution, not because parallelism is required, but because it can make plans more efficient. Methods like Knoblock (1994) and Boutilier and Brafman (2001) handle this by explicitly defining which resources each operator used, but none established how to identify parallelism without such information. Noor and Siddiqui (2025) extended the idea of the BDPO plan by adding the non-concurrency relation to allow blocks to be executed in parallel. Definition 21. A parallel block decomposed partial-order (PBDPO) plan is denoted as πpbdp=⟨,≺,ℬ,#⟩ _pbdp= , ,B,\# , which basically extends a BDPO plan ⟨,≺,ℬ⟩ , ,B with an symmetric, irreflexive relation #\# over ℬB, depicting non-concurrency constraints between blocks. Blocks bpb_p and bqb_q are considered non-concurrent, expressed as bp#bqb_p\#b_q, if two primitive operators op∈bpo_p∈ b_p and oq∈bqo_q∈ b_q are non-concurrent (op#oqo_p\#o_q). Variables causing this non-concurrency are denoted by the set vars(bp#bq)vars(b_p\#b_q). Definition 22. Let πpbdp=⟨,≺,ℬ,#⟩ _pbdp= , ,B,\# be a valid parallel BDPO plan with bp#bqb_p\#b_q, where blocks bp,bq∈ℬb_p,b_q are two disjoint blocks. The bp#bqb_p\#b_q is considered necessary non-concurrency constraint within πpbdp _pbdp if−- i. bp⊀bq⊀bpb_p b_q b_p, and i. if bpb_p is in the block bx∈Bb_x∈ B , then bqb_q is also in the block bxb_x . The Concurrent Flexibility Improvement via Block-Substitution (CIBS) algorithm generates a valid PBDPO plan from a valid total-order plan π for a planning task Π . The CIBS algorithm extends blocks before substitution. It selects two blocks bpb_p and bqb_q with bp#bqb_p\#b_q in a PBDPO plan πpbdp _pbdp with respect to a planning task Π . Then, the procedure includes the necessary blocks to the block bpb_p to achieve a new block bp′b_p so that another block b^p b_p can be used in place of bp′b_p where vars(b^p#bq)=∅vars( b_p\#b_q)= . The CIBS algorithm enhances the concurrent flexibility through block-substitution in three steps. In the first step, EOG is applied to convert π into a parallel plan πeog=⟨,≺,#⟩ _eog= , ,\# first, and then non-concurrency constraints between every pair of operators are identified. In the next step, cohesive operators are encapsulated into blocks using block deordering, which removes ordering constraints from πeog _eog and yields a PBDPO plan πpbdp=⟨,≺,ℬ,#⟩ _pbdp= , ,B,\# . In the last stage, blocks are replaced to improve the concurrent flexibility of πpbdp _pbdp. The CIBS effectively enhances concurrent flexibility across a wide range of planning domains, outperforming both EOG and block deordering in most cases. Its consistent improvements in cflex, particularly in domains rich with resource-based interactions, show the benefit of incorporating substitution alongside block deordering. The observed correlations suggest that CIBS scales reasonably well with plan complexity, though execution time grows notably with larger plan sizes and more variables. However, the performance drop in extensive plans and the limited impact of block deordering on cflex highlight scalability and efficiency challenges. Additionally, the algorithm’s reliance on available resources for substitution restricts its applicability in domains lacking such elements, indicating room for improvement in generalizing CIBS to more diverse planning tasks. 7 Analysis The optimization capabilities of the six algorithms are summarized in Table 1 across six categories: ordering, action handling, parameter handling, plan structure, concurrency, and complexity and optimality. Table 1: Optimization capability comparison among algorithms Criteria EOG BD MR MRR FIBS CIBS Ordering Remove Orderings Yes Yes Yes Yes Yes Yes Arbitrary Reordering No No Yes Yes No No Block-level Deordering No Yes No No Yes Yes Minimizes Orderings No No Yes Yes No No Action Handling Remove Redundant Actions No No Yes Yes No No Introduce New Actions No No No No Yes Yes Replace Action Sets (Subplans) No No No No Yes Yes Replace Actions of Different Name No No No No Yes Yes Parameter Handling Rebind Parameters No No No Yes No No Same-name Operator Rebinding Only - - - Yes - - Plan structure Produces Partial-order Plan Yes Yes Yes Yes Yes Yes Produces BDPO Plan No Yes No No Yes Yes Produces Parallel Plan No No No No No Yes Produces Parallel BDPO Plan No No No No No Yes External Planner for Subplans No No No No Yes Yes Concurrency Non-concurrency Constraints (#) No No No No No Yes Minimizes # No No No No No Yes Improves Parallel Execution No Partial No No Partial Yes Uses FDR for # Conditions No No No No No Yes Block Extension via DTG Analysis No No No No No Yes Complexity and Optimality Polynomial-time Algorithm Yes Yes No No Partial Partial MaxSAT-based Encoding No No Yes Yes No No Anytime / Iterative Improvement No No No No Yes Yes Composable on top of MR/MRR No No - - Yes No All six algorithms remove unnecessary orderings from a plan, but they differ in scope. EOG operates at the operator level and produces a standard POP without block structure. Block Deordering (BD) groups coherent operators into blocks and eliminates more orderings than EOG by treating each block as a unit. MR and MRR allow arbitrary reordering and find minimum reorderings via MaxSAT encodings, though neither produces block-structured plans. Flexibility Improvement via Block-Substitution (FIBS) and Concurrency Improvement via Block-Substitution (CIBS) use block-level deordering but, unlike MR and MRR, do not seek a globally minimum reordering; instead, they improve the plan iteratively through substitution. On action handling, EOG and BD leave the operator set unchanged. MR removes redundant actions as part of its encoding. MRR does the same and additionally reorders operator parameters, though only within operators of the same name. FIBS and CIBS replace entire subplans with new ones drawn from the planning task, including operators with different names and different numbers of actions. Block-substitution is therefore the only mechanism in the table that can introduce actions absent from the original plan. Parameter rebinding is exclusive to MRR, and even there it is constrained to same-name operators. All other algorithms treat operator parameters as fixed. All six algorithms produce a valid POP. BD, FIBS, and CIBS additionally produce BDPO plans by organizing operators into blocks. Only CIBS produces a parallel plan by incorporating a non-concurrency constraint relation (#\#), which is a parallel block decomposed (PBD) plan. FIBS and CIBS both use an external planner to generate candidate subplans for substitution; the remaining algorithms are self-contained. The concurrency category distinguishes CIBS from everything else in the table. EOG, BD, MR, MRR, and FIBS do not model non-concurrency constraints (#\#). CIBS formalizes necessary and sufficient conditions for non-concurrency using FDR variables, uses a Domain Transition Graph (DTG) to determine when a block must be extended before substitution, and directly minimizes #\# constraints to maximize parallel execution flexibility. EOG and BD run in polynomial time. MR and MRR are NP-complete due to their MaxSAT formulations. FIBS and CIBS are partially polynomial: the block-substitution procedure runs in O(n2p2)O(n^2p^2) time, but both use an external planner, which is not guaranteed to be polynomial. Both are anytime algorithms that produce a valid result at any point during execution. Finally, FIBS can be applied on top of MR or MRR-generated POPs for further flexibility gains; CIBS takes a sequential plan directly as input and is not designed to compose with MaxSAT reorderings. 8 Evaluation We evaluate seven plan execution flexibility-improving methods on 3,345 plans from 46 IPC domains. These methods are EOG, BD, MR, MRR, FIBS, FIBS applied on MR output (FIBS+MR), and FIBS applied on MRR output (FIBS+MRR). EOG and BD achieve full coverage by construction, while MR, MRR, FIBS+MR, and FIBS+MRR solve 81.4%, 47.8%, 48.2%, and 21.0% of plans, respectively. When an algorithm fails to find a solution, we assume its flex value with the EOG flex for that plan, which is the lowest flex any plan achieves before any reordering or substitution. We measure flexibility using the flex metric defined in (2). For a multi-dimensional comparison, we compute five normalized scores per algorithm: Flex (mean flex value), Coverage (proportion of plans solved), Speed (inverse mean execution time), Consistency (inverse coefficient of variation of flex), and Unique Best (proportion of plans on which the algorithm achieves the strictly highest flex). All five are min-max normalized, so a value of 1.0 denotes the best algorithm on that dimension. 8.1 Flex-Time Trade-off Figure 1 plots mean flex against mean time per plan for all seven methods, with the Pareto frontier connecting those not dominated on both dimensions at once. EOG is the fastest at 1.06 seconds with a mean flex of 0.247. MR and FIBS+MR reach mean flex values of 0.247 and 0.249 at 29.3 and 30.4 seconds, respectively, both on the frontier. BD and FIBS improve mean flex to 0.339 and 0.341 at 44.0 and 47.4 seconds, also on the frontier. MRR and FIBS+MRR take 58.8 and 59.9 seconds but reach only 0.249 mean flex each, placing them off the frontier. The Pareto front therefore has two natural operating points: fast with modest gains (EOG, MR) and moderate cost with substantially better flex (BD, FIBS). MRR and FIBS+MRR roughly double MR’s computation time without improving its position on the frontier. Figure 1: Mean flex score vs. mean planning time with Pareto Frontier. 8.2 Flex Efficiency Figure 2 shows flex efficiency per algorithm and domain, measured as flex gain over EOG per additional second spent (Δ /Δ ). BD has the highest median efficiency across domains: block deordering removes a large number of ordering constraints at relatively low per-plan overhead. FIBS reaches comparable efficiency because its substitution phases build directly on BD. MR and FIBS+MR cluster at intermediate values. MRR and FIBS+MRR fall to the lowest efficiency, as MRR’s encoding cost is large relative to the flex improvement it achieves. Bubble size in Figure 2 encodes absolute mean flex gain per domain; the largest bubbles belong to BD and FIBS, confirming that these two algorithms also produce the greatest absolute improvements. Figure 2: Flex efficiency 8.3 Statistical Effect Size Figure 3 presents a pairwise effect-size heatmap using the rank-biserial correlation r from a two-sided Mann–Whitney U test on the flex distributions. A positive r in row A and column B means algorithm A produces higher flex on more plans than algorithm B; significance levels are marked as *(p<0.05p<0.05), ** (p<0.01p<0.01), and *** (p<0.001p<0.001). Figure 3: Effect Size - Rank-biserial r BD and FIBS show strong positive r values against all other algorithms, with statistically significant differences in the majority of pairwise comparisons. The effect size between BD and FIBS itself is small and non-significant, so the two algorithms perform equivalently at the population level despite FIBS having a marginally higher mean. EOG, MR, MRR, FIBS+MR, and FIBS+MRR cluster together, with near-zero or weakly negative r values against the block-based methods. Within this cluster, pairwise effect sizes are consistently small and non-significant, indicating that the MaxSAT-based methods do not meaningfully separate from one another in terms of flex on the full plan distribution. 8.4 Multi-Criteria Comparison Figure 4 places all seven methods on a radar chart with one axis per normalized dimension; the outer rim corresponds to the best score on each axis. BD and FIBS occupy the largest area, with normalized Flex scores of 0.985 and 1.0, perfect Coverage, and perfect Consistency. FIBS has a Unique Best score of 0.119, meaning it produces the strictly highest flex on roughly 12% of individual plans. BD’s normalized Unique Best score is 1.0, as it achieves the best flex on the largest number of plans overall. EOG scores perfectly on Speed and Coverage, and its normalized Unique Best of 0.625 is notably high: since EOG is used as the fallback for plans where MaxSAT methods time out, it retains the best score wherever all alternatives fail to terminate. Figure 4: Radar Chart MR achieves moderate Speed (0.520) and Coverage (0.765) but a near-zero normalized Flex score relative to BD and FIBS. MRR scores near zero on Speed, Coverage, and Unique Best. FIBS+MR and FIBS+MRR also score near zero on Unique Best, since when the MaxSAT component does find a solution, FIBS adds only a small additional flex increment, and the combined pipeline rarely produces the globally best result for any individual plan. 9 Conclusion The methods reviewed in this study approach plan flexibility from three distinct angles: causal-link reasoning (POCL, EOG), operator coherence and block structure (BD, FIBS, CIBS), and constraint optimization (MR, MRR). Each angle captures something real about what makes a plan flexible, but the empirical results show that these angles are not equally productive. Restructuring causal dependencies at the block level, without any guarantee of minimality, yields substantially more flexibility than minimizing ordering constraints within a fixed causal structure. This is the central finding of the study, and is somewhat counterintuitive given how much theoretical work has gone into minimum reordering. The theoretical promise of finding minimum reorderings with the MaxSAT-based methods is legitimate. Yet minimum reordering within a fixed action set is a ceiling set by the original plan’s causal structure. Block deordering raises that ceiling by reorganizing how causal dependencies are grouped, which exposes ordering constraints that would otherwise appear necessary. Block-substitution raises it further by replacing subplans with alternatives that carry different causal entailments entirely. BD’s greedy, polynomial-time heuristic therefore outperforms MR’s NP-complete search on a broad collection of IPC benchmarks. Minimum reordering has been studied extensively as an optimization target, but the quality of the causal structure itself has received less attention. The success of block-substitution suggests that reordering and action-set modification interact in non-trivial ways. MRR takes a step in this direction by allowing parameter rebinding, but only within same-name operators, and the evaluation shows this restriction is too tight to close the gap with BD. A method that jointly optimizes ordering and action selection without the coverage failures of MaxSAT encodings is still missing. CIBS introduces a separate question that none of the other methods address. Two unordered operators may still be concurrent if they do not share a state variable. CIBS introduces cflex to account for this, instead of relying on flex, and the gap between the two metrics is non-trivial in resource-rich domains. However, whether a domain-independent characterization of practical concurrency is achievable, and how to extend concurrent flexibility improvement to domains without explicit resource contention, remain open. Statements and Declarations Competing Interests The authors have no relevant financial or non-financial interests to disclose. References Anderson and Farley (1988) J. S. Anderson and A. M. Farley Plan abstraction based on operator generalization. In Proceedings of the Seventh AAAI National Conference on Artificial Intelligence, AAAI’88, p. 100–104. Cited by: §1. Bäckström (1998) C. Bäckström Computational aspects of reordering plans. Journal of Artificial Intelligence Research 9, p. 99–137. Cited by: §2.2, §2.3. Bercher et al. (2017) P. Bercher, G. Behnke, D. Höller, and S. Biundo An admissible HTN planning heuristic. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, p. 480–488. External Links: Document Cited by: §3. Bercher et al. (2016) P. Bercher, D. Höller, G. Behnke, and S. Biundo More than a name? on implications of preconditions and effects of compound HTN planning tasks. In Proceedings of the Twenty-Second European Conference on Artificial Intelligence, ECAI’16, NLD, p. 225–233. External Links: ISBN 9781614996712, Document Cited by: §3. Bit-Monnot et al. (2020) A. Bit-Monnot, M. Ghallab, F. Ingrand, and D. E. Smith FAPE: a constraint-based planner for generative and hierarchical temporal planning. External Links: 2010.13121 Cited by: §3. Bit-Monnot et al. (2016) A. Bit-Monnot, D. E. Smith, and M. Do Delete-free Reachability Analysis for Temporal and Hierarchical Planning (full version). In ICAPS Workshop on Heuristics and Search for Domain-independent Planning (HSDIP), London, United Kingdom. External Links: Link Cited by: §3. Blum and Furst (1997) A. L. Blum and M. L. Furst Fast planning through planning graph analysis. Artificial Intelligence 90 (1), p. 281–300. External Links: ISSN 0004-3702, Document Cited by: §3. Boutilier and Brafman (2001) C. Boutilier and R. I. Brafman Partial-order planning with concurrent interacting actions. Journal of Artificial Intelligence Research 14, p. 105–136. External Links: ISSN 1076-9757, Document Cited by: §6.2. Chrpa and Siddiqui (2015) L. Chrpa and F. H. Siddiqui Exploiting block deordering for improving planners efficiency. In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, p. 1537–1543. External Links: ISBN 9781577357384 Cited by: §6. Coles et al. (2021) A. Coles, A. Coles, M. Fox, and D. Long Forward-chaining partial-order planning. Proceedings of the International Conference on Automated Planning and Scheduling 20 (1), p. 42–49. External Links: Link, Document Cited by: §3. Fikes and Nilsson (1971) R. E. Fikes and N. J. Nilsson STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence 2 (3), p. 189–208. External Links: ISSN 0004-3702, Document Cited by: §4. Fox and Long (2001) M. Fox and D. Long Hybrid STAN: identifying and managing combinatorial optimisation sub-problems in planning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI’01, San Francisco, CA, USA, p. 445–450. External Links: ISBN 1558608125 Cited by: §3. Graham et al. (2003) J. R. Graham, K. S. Decker, and M. Mersic DECAF - a flexible multi agent system architecture. Autonomous Agents and Multi-Agent Systems 7 (1–2), p. 7–27. External Links: ISSN 1387-2532, Document Cited by: §1. Haslum et al. (2019) P. Haslum, N. Lipovetzky, D. Magazzeni, and C. Muise An introduction to the planning domain definition language. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool. External Links: ISBN 9781681735122 Cited by: §5.1. Helmert (2011) M. Helmert The fast downward planning system. Journal of Artificial Intelligence Research 26, p. . External Links: Document Cited by: §2.1. Hickmott et al. (2007) S. Hickmott, J. Rintanen, S. Thiébaux, and L. White Planning via petri net unfolding. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI’07, San Francisco, CA, USA, p. 1904–1911. Cited by: §3. Kambhampati and Hendler (1992) S. Kambhampati and J. A. Hendler A validation-structure-based theory of plan modification and reuse. Artificial Intelligence 55 (2), p. 193–258. External Links: ISSN 0004-3702, Document Cited by: §5. Kambhampati and Kedar (1994) S. Kambhampati and S. Kedar A unified framework for explanation-based generalization of partially ordered and partially instantiated plans. Artificial Intelligence 67 (1), p. 29–70. External Links: Document, ISSN 0004-3702 Cited by: §1, §5. Kambhampati (1994) S. Kambhampati Multi-contributor causal structures for planning: a formalization and evaluation. Artificial Intelligence 69 (1-2), p. 235–278 (English (US)). External Links: Document, ISSN 0004-3702 Cited by: §5. Kautz and Selman (1998) H. Kautz and B. Selman BLACKBOX: a new approach to the application of theorem proving to problem solving. In AIPS98 Workshop on Planning as Combinatorial Search, Cited by: §3. Knoblock (1994) C. A. Knoblock Generating parallel execution plans with a partial-order planner. In International Conference on Artificial Intelligence Planning Systems, p. 98–103. Cited by: §6.2. Koehler (1999) J. Koehler Handling of conditional effects and negative goals in IPP. Cited by: §3. Muise et al. (2016) C. Muise, J. Beck, and S. McIlraith Optimal partial-order plan relaxation via MaxSAT. Journal of Artificial Intelligence Research 57, p. 113–149. External Links: Document Cited by: §1, §1, §4.1, §4. Nguyen and Kambhampati (2001) X. Nguyen and S. Kambhampati Reviving partial order planning. p. 459–466. Cited by: §1. Noor and Siddiqui (2022) S. B. Noor and F. H. Siddiqui Plan deordering with conditional effects. In Intelligent Systems and Applications, K. Arai (Ed.), p. 852–870. External Links: ISBN 978-3-031-16078-3 Cited by: §5.1, §5. Noor and Siddiqui (2024) S. B. Noor and F. H. Siddiqui Improving plan execution flexibility using block-substitution. arXiv preprint arXiv:2406.03091. Cited by: §1, §6.1, §6.1, §6. Noor and Siddiqui (2025) S. B. Noor and F. H. Siddiqui Improving execution concurrency in partial-order plans via block-substitution. Autonomous Agents and Multi-Agent Systems 39 (1), p. 1–43. Cited by: §1, §6.2, §6.2. Penberthy and Weld (1992) J. S. Penberthy and D. S. Weld UCPOP: a sound, complete, partial order planner for adl. In Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, KR’92, p. 103–114. External Links: ISBN 1558602623 Cited by: §3. Regnier and Fade (1991) P. Regnier and B. Fade Complete determination of parallel actions and temporal optimization in linear plans of action. In European Workshop on Planning, volume 522 of Lecture, p. 100–111. Cited by: §4. Siddiqui and Haslum (2012) F. H. Siddiqui and P. Haslum Block-structured plan deordering. In AI 2012: Advances in Artificial Intelligence, M. Thielscher and D. Zhang (Eds.), Berlin, Heidelberg, p. 803–814. Cited by: §1, §1, §2.2, §2.2, §6. Siddiqui and Haslum (2015) F. H. Siddiqui and P. Haslum Continuing plan quality optimisation. Journal of Artificial Intelligence Research 54, p. 369–435. Cited by: §6. Simmons and Younes (2011) R. Simmons and H. Younes VHPOP: versatile heuristic partial order planner. Journal of Artificial Intelligence Research 20, p. . External Links: Document Cited by: §3. Veloso et al. (2002) M. Veloso, M. Perez, and J. Carbonell Nonlinear planning with parallel resource allocation. Cited by: §1, §1, §5. Waters et al. (2018) M. Waters, B. Nebel, L. Padgham, and S. Sardina Plan relaxation via action debinding and deordering. Proceedings of the International Conference on Automated Planning and Scheduling 28 (1), p. 278–287. External Links: Link, Document Cited by: §4. Waters et al. (2020) M. Waters, L. Padgham, and S. Sardina Optimising partial-order plans via action reinstantiation. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20. External Links: ISBN 9780999241165 Cited by: §1, §4.2, §4. Weld (1994) D. S. Weld An introduction to least commitment planning. AI Magazine 15 (4), p. 27. External Links: Document Cited by: §1, §2.2, §3. Winner and Veloso (2002) E. Winner and M. M. Veloso Analyzing plans with conditional effects.. In AIPS, p. 23–33. Cited by: §4.