Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies

# Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies
Source: [https://arxiv.org/html/2609.16822](https://arxiv.org/html/2609.16822)
Md\. Monjurul IslamEmail:[monjurul\.islam\.cs@gmail\.com](mailto:[email protected])Affiliation:Department of Computer Science and Engineering, Dhaka University of Engineering & Technology, Gazipur, Gazipur\-1707, BangladeshSabah Binte NoorEmail:[sabah@duet\.ac\.bd](mailto:[email protected])Affiliation:Department of Computer Science and Engineering, Dhaka University of Engineering & Technology, Gazipur, Gazipur\-1707, BangladeshFazlul Hasan SiddiquiEmail:[siddiqui@duet\.ac\.bd](mailto:[email protected])Affiliation:Department of Computer Science and Engineering, Dhaka University of Engineering & Technology, Gazipur, Gazipur\-1707, BangladeshGahangir HossainEmail:[Gahangir\.Hossain@unt\.edu](mailto:[email protected])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\.

###### keywords

Automated Planning, Flexibility, Concurrency, Partial Order Planning

## 1Introduction

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](https://arxiv.org/html/2609.16822#bib.bib8)\)to extending the applicability of existing plans through generalization techniques\([Anderson and Farley, 1988](https://arxiv.org/html/2609.16822#bib.bib7)\)\. 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](https://arxiv.org/html/2609.16822#bib.bib18);[Veloso et al\., 2002](https://arxiv.org/html/2609.16822#bib.bib16);[Siddiqui and Haslum, 2012](https://arxiv.org/html/2609.16822#bib.bib4)\)and reordering\([Muise et al\., 2016](https://arxiv.org/html/2609.16822#bib.bib10)\)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](https://arxiv.org/html/2609.16822#bib.bib35)\), 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](https://arxiv.org/html/2609.16822#bib.bib20);[Veloso et al\., 2002](https://arxiv.org/html/2609.16822#bib.bib16)\)annotates each ordering with its causal justification and removes those without one\. Block deordering \(BD\)\([Siddiqui and Haslum, 2012](https://arxiv.org/html/2609.16822#bib.bib4)\)groups coherent operators into blocks and eliminates additional orderings by treating each block as a unit\. Minimum reordering \(MR\)\([Muise et al\., 2016](https://arxiv.org/html/2609.16822#bib.bib10)\)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](https://arxiv.org/html/2609.16822#bib.bib9)\)extends this with parameter rebinding within same\-name operators\. More recently, FIBS\([Noor and Siddiqui, 2024](https://arxiv.org/html/2609.16822#bib.bib1)\)replaces subplans with alternatives using block\-substitution, and CIBS\([Noor and Siddiqui, 2025](https://arxiv.org/html/2609.16822#bib.bib3)\)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\.

## 2Preliminaries

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\.1Planning Task

Classical planning problems are commonly represented using finite domain representation \(FDR\)\([Helmert, 2011](https://arxiv.org/html/2609.16822#bib.bib21)\), 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⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle, where:

- •𝒳\\mathcal\{X\}represents a finite non\-empty set ofstate variables\. A domain𝒟x\\mathcal\{D\}\_\{x\}with a finite number of elements is associated with eachx∈𝒳x\\in\\mathcal\{X\}\. The pair⟨x,d⟩\\langle x,d\\ranglewithx∈𝒳x\\in\\mathcal\{X\}andd∈𝒟xd\\in\\mathcal\{D\}\_\{x\}is afact\. The notion ofstatecorresponds to a functionsdefined over𝒳\\mathcal\{X\}, such thats⁡\(x\)∈𝒟xs\(x\)\\in\\mathcal\{D\}\_\{x\}for allx∈𝒳x\\in\\mathcal\{X\}\. The set of variables involved in a function is denoted as𝑣𝑎𝑟𝑠⁡\(s\)\\mathit\{vars\}\(s\)\. A functions^\{\\hat\{s\}\}similar to a states, but defined over a proper subset of𝒳\\mathcal\{X\}, represents apartial statewhere𝑣𝑎𝑟𝑠⁡\(s^\)⊂𝒳\\mathit\{vars\}\(\\hat\{s\}\)\\subset\\mathcal\{X\}\.
- •𝒪\\mathcal\{O\}represents the finite non\-empty set ofoperators\. Every operatoro∈𝒪o\\in\\mathcal\{O\}is associated with two partial states,precondition\(𝑝𝑟𝑒o\\mathit\{pre\_\{o\}\}\) andeffect\(𝑒𝑓𝑓o\\mathit\{eff\_\{o\}\}\), along with an associatedcostthat is nonnegative \(𝑐𝑜𝑠𝑡o∈ℝ0\+\\mathit\{cost\_\{o\}\}\\in\\mathbb\{R\}^\{\+\}\_\{0\}\)\. An operatoroocan be applied in a statessiff𝑝𝑟𝑒o⊆s\\mathit\{pre\_\{o\}\}\\subseteq s\. Applying the operatoroowithin statesstransforms it into states′=a​p​p​l​y​\(s,o\)s^\{\\prime\}=apply\(s,o\)as specified in \([1](https://arxiv.org/html/2609.16822#S2.E1)\)\. s′​\(x\)=a​p​p​l​y​\(s,o\)=\{𝑒𝑓𝑓o​\(x\)if​x∈𝑣𝑎𝑟𝑠⁡\(𝑒𝑓𝑓o\)s⁡\(x\)otherwises^\{\\prime\}\(x\)=apply\(s,o\)=\\begin\{cases\}\\mathit\{eff\_\{o\}\}\(x\)&\\text\{if \}x\\in\\mathit\{vars\(eff\_\{o\}\)\}\\\\ s\(x\)&\\text\{otherwise\}\\end\{cases\}\(1\)
- •sis\_\{i\}corresponds to theinitial state,
- •sgs\_\{g\}refers to a partial state that specifies thegoal conditions\.

###### Definition 2\.

Letπ=⟨o1,o2,…,ok,…,on⟩\\pi=\\langle o\_\{1\},o\_\{2\},\\dots,o\_\{k\},\\dots,o\_\{n\}\\ranglebe aplan, a sequence of operators, for a planning taskΠ=⟨𝒳,𝒪,si,sg⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle\. The planπ\\piisvalidiffp​r​eo1⊆sipre\_\{o\_\{1\}\}\\subseteq s\_\{i\},p​r​eok\+1⊆skpre\_\{o\_\{k\+1\}\}\\subseteq s\_\{k\}for everyk∈\{1,2,…,n−1\}k\\in\\\{1,2,\\dots,n\-1\\\}wheresk=𝑎𝑝𝑝𝑙𝑦⁡\(sk−1,ok\)s\_\{k\}=\\mathit\{apply\}\(s\_\{k\-1\},o\_\{k\}\), andsg⊆sns\_\{g\}\\subseteq s\_\{n\}\.

###### Definition 3\.

Theprodo,conso, anddelorepresent the facts that an operatorooproduces, consumes, and deletes, respectively\. The fact−\-

- •⟨x,d⟩∈p​r​o​do\\langle x,d\\rangle\\in prod\_\{o\}iff⟨x,d⟩∈𝑒𝑓𝑓o\\langle x,d\\rangle\\in\\mathit\{eff\_\{o\}\}\.
- •⟨x,d⟩∈c​o​n​so\\langle x,d\\rangle\\in cons\_\{o\}iff⟨x,d⟩∈𝑝𝑟𝑒o\\langle x,d\\rangle\\in\\mathit\{pre\_\{o\}\}\.
- •⟨x,d⟩∈d​e​lo\\langle x,d\\rangle\\in del\_\{o\}iff\- 1. i\.eitherx∉v​a​r​s​\(𝑐𝑜𝑛𝑠o\)x\\notin vars\(\\mathit\{cons\_\{o\}\}\)or𝑐𝑜𝑛𝑠o​\(x\)=d\\mathit\{cons\_\{o\}\}\(x\)=d, and 2. ii\.𝑒𝑓𝑓o​\(x\)=d′\\mathit\{eff\_\{o\}\}\(x\)=d^\{\\prime\}such thatd′∈\(𝒟x∖\{d\}\)\\ d^\{\\prime\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\)\.

### 2\.2Partial\-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\.

APOPis represented asπp​o​p=⟨𝒪,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\rangle, regarding a planning taskΠ=⟨𝒳,𝒪,si,sg⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle, where:

- •𝒪\\mathcal\{O\}denotes the set of operators, and
- •≺\\precrepresents ordering constraints over𝒪\\mathcal\{O\}\. The notation𝐨𝐚≺𝐨𝐛\\mathbf\{o\_\{a\}\\prec o\_\{b\}\}represents aordering constraintbetween two operatorsoa,ob∈𝒪o\_\{a\},o\_\{b\}\\in\\mathcal\{O\}, which specifies that the operatoroao\_\{a\}needs to be executed at any time before the execution of operatorobo\_\{b\}\.≺\\precexhibits transitive property, which means that ifoa≺obo\_\{a\}\\prec o\_\{b\}andob≺oco\_\{b\}\\prec o\_\{c\}, thenoa≺oco\_\{a\}\\prec o\_\{c\}\. Basic orderings represent constraints that are not transitively inferred by other constraints in the set\.

Plan flexibility quantification uses the metric𝑓𝑙𝑒𝑥\\mathit\{flex\}\([Siddiqui and Haslum, 2012](https://arxiv.org/html/2609.16822#bib.bib4)\), which is the proportion of the pairs of operators that do not have fundamental or transitive ordering to all operator pairs\. Higher𝑓𝑙𝑒𝑥\\mathit\{flex\}values indicate greater execution flexibility, though the relationship between flexibility and practical adaptability depends on domain\-specific factors\.

###### Definition 5\.

Letπp​o​p=⟨𝒪,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\ranglebe a POP\. Theflexvalue of the planπp​o​p\\pi\_\{pop\}is𝑓𝑙𝑒𝑥⁡\(πp​o​p\)\\mathit\{flex\}\(\\pi\_\{pop\}\)and is calculated as specified in \([2](https://arxiv.org/html/2609.16822#S2.E2)\)\.

𝑓𝑙𝑒𝑥⁡\(πp​o​p\)=1−\|≺\|Σi=1\|𝒪\|−1​i\\mathit\{flex\}\(\\pi\_\{pop\}\)=1\-\\frac\{\|\\prec\|\}\{\\Sigma\_\{i=1\}^\{\|\\mathcal\{O\}\|\-1\}i\}\(2\)whereΣi=1\|𝒪\|−1​i\\Sigma\_\{i=1\}^\{\|\\mathcal\{O\}\|\-1\}iis the maximum number of pairings that might be constructed with a collection of\|𝒪\|\|\\mathcal\{O\}\|items\.

The framework of producer\-consumer\-threat \(PCT\)\([Bäckström, 1998](https://arxiv.org/html/2609.16822#bib.bib17)\)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\.

Acausal linkop→⟨x,d⟩oco\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}o\_\{c\}betweenopo\_\{p\}andoco\_\{c\}specifies thatop≺oco\_\{p\}\\prec o\_\{c\}and the operatoropo\_\{p\}produces⟨x,d⟩\\langle x,d\\ranglefor the operatoroco\_\{c\}, where⟨x,d⟩∈\(p​r​o​dop∩c​o​n​soc\)\\langle x,d\\rangle\\in\(prod\_\{o\_\{p\}\}\\cap cons\_\{o\_\{c\}\}\)\. Athreatis defined as a conflict between a causal linkop→⟨x,d⟩oco\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}o\_\{c\}and the effect of an operatorodo\_\{d\}, whereodo\_\{d\}deletes⟨x,d⟩\\langle x,d\\rangleand can be ordered in betweenopo\_\{p\}andoco\_\{c\}\.

Apromotion, which adds the orderingod≺opo\_\{d\}\\prec o\_\{p\}, or ademotion, which adds the orderingoc≺odo\_\{c\}\\prec o\_\{d\}, can resolve a threat between a causal linkop→⟨x,d⟩oco\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}o\_\{c\}and an operatorodo\_\{d\}\. A POP is valid if causal relationships support each operator precondition without any threat\([Weld, 1994](https://arxiv.org/html/2609.16822#bib.bib35)\)\. Three labels,P​C,C​TPC,CT, andT​PTP, are introduced by[Siddiqui and Haslum \(2012\)](https://arxiv.org/html/2609.16822#bib.bib4)to outline a POP’s ordering constraints\.

###### Definition 7\.

Letπp​o​p=⟨𝒪,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\ranglebe a POP andR​e​\(oa≺ob\)Re\(o\_\{a\}\\prec o\_\{b\}\)represents the ordering reasons for an ordering constraintoa≺obo\_\{a\}\\prec o\_\{b\}\. An ordering restrictionoa≺obo\_\{a\}\\prec o\_\{b\}might form for three reasons:

- •P​C​\(⟨x,d⟩\)∈R​e​\(oa≺ob\)PC\(\\langle x,d\\rangle\)\\in Re\(o\_\{a\}\\prec o\_\{b\}\)is theproducer\-consumerof a fact⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangle, whereoao\_\{a\}produces⟨x,d⟩\\langle x,d\\rangleandobo\_\{b\}consumes⟨x,d⟩\\langle x,d\\rangle\. The fact⟨x,d⟩\\langle x,d\\ranglemay be produced and consumed by multiple operators\. One operatoroao\_\{a\}is assigned via a causal link to obtain⟨x,d⟩\\langle x,d\\rangleforobo\_\{b\}\.
- •C​T​\(⟨x,d⟩\)∈R​e​\(oa≺ob\)CT\(\\langle x,d\\rangle\)\\in Re\(o\_\{a\}\\prec o\_\{b\}\)is theconsumer\-threatof a fact⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangle, where operatoroao\_\{a\}consumes⟨x,d⟩\\langle x,d\\rangleandobo\_\{b\}deletes⟨x,d⟩\\langle x,d\\rangle\.
- •T​P​\(⟨x,d⟩\)∈R​e​\(oa≺ob\)TP\(\\langle x,d\\rangle\)\\in Re\(o\_\{a\}\\prec o\_\{b\}\)is thethreat\-producerof a fact⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangle, where operatoroao\_\{a\}deletes the fact⟨x,d⟩\\langle x,d\\rangleand there exist one or more causal linkob→⟨x,d⟩oco\_\{b\}\\xrightarrow\{\\langle x,d\\rangle\}o\_\{c\}for someoc∈𝒪o\_\{c\}\\in\\mathcal\{O\}\.

Causal links of a POP are denoted by the labelP​CPC, and the demotion and promotion ordering constraints of the plan are denoted byC​TCTandT​PTP, respectively\. These labels assist in identifying and monitoring the rationale behind the orderings in a POP\.

### 2\.3Plan 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\)](https://arxiv.org/html/2609.16822#bib.bib17)\. A POP is assumed to be transitively closed in the Definition[8](https://arxiv.org/html/2609.16822#Thmdefinition8)\.

###### Definition 8\.

Letπp=⟨𝒪,≺p⟩\\pi\_\{p\}=\\langle\\mathcal\{O\},\\prec\_\{p\}\\rangleandπq=⟨𝒪,≺q⟩\\pi\_\{q\}=\\langle\\mathcal\{O\},\\prec\_\{q\}\\ranglebe two different POPs with respect toΠ\\Pi\(a planning task\)\. Therefore:

- •πq\\pi\_\{q\}is adeorderingofπp\\pi\_\{p\}with respect toΠ\\Piiff bothπp\\pi\_\{p\}andπq\\pi\_\{q\}are valid POP and≺q⊆≺p\\prec\_\{q\}\\subseteq\\prec\_\{p\}\.
- •πq\\pi\_\{q\}is aproper deorderingofπp\\pi\_\{p\}with respect toΠ\\Piiffπq\\pi\_\{q\}is a deordering ofπp\\pi\_\{p\}and≺q⊂≺p\\prec\_\{q\}\\subset\\prec\_\{p\}\.
- •πq\\pi\_\{q\}is areorderingofπp\\pi\_\{p\}with respect toΠ\\Piiff bothπp\\pi\_\{p\}andπq\\pi\_\{q\}are valid POP\.
- •πq\\pi\_\{q\}is aproper reorderingofπp\\pi\_\{p\}with respect toΠ\\Piiffπq\\pi\_\{q\}is a reordering ofπp\\pi\_\{p\}with≺q≠≺p\\prec\_\{q\}\\neq\\prec\_\{p\}\.
- •πq\\pi\_\{q\}is aminimum deorderingofπp\\pi\_\{p\}with respect toΠ\\Piiff−\- 1. 1\.πq\\pi\_\{q\}is a deordering ofπp\\pi\_\{p\}, and 2. 2\.there exists no partial\-order planπr=⟨𝒪,≺r⟩\\pi\_\{r\}=\\langle\\mathcal\{O\},\\prec\_\{r\}\\ranglesuch thatπr\\pi\_\{r\}is a deordering ofπp\\pi\_\{p\}with\|≺r\|<\|≺q\|\|\\prec\_\{r\}\|<\|\\prec\_\{q\}\|\.
- •πq\\pi\_\{q\}is aminimum reorderingofπp\\pi\_\{p\}with respect toΠ\\Piiff−\- 1. 1\.πq\\pi\_\{q\}is a reordering ofπp\\pi\_\{p\}, and 2. 2\.there exists no partial\-order planπr=⟨𝒪,≺r⟩\\pi\_\{r\}=\\langle\\mathcal\{O\},\\prec\_\{r\}\\ranglesuch thatπr\\pi\_\{r\}is a reordering ofπp\\pi\_\{p\}and\|≺r\|<\|≺q\|\|\\prec\_\{r\}\|<\|\\prec\_\{q\}\|\.

## 3Partial\-Order Causal Link\-based Approach

The partial\-order causal link \(POCL\)\([Weld, 1994](https://arxiv.org/html/2609.16822#bib.bib35)\)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](https://arxiv.org/html/2609.16822#bib.bib11)\)and UCPOP\([Penberthy and Weld, 1992](https://arxiv.org/html/2609.16822#bib.bib23)\)\. Furthermore, the POCL strategy has been adapted to find temporal plans through state\-based forward search techniques\([Coles et al\., 2021](https://arxiv.org/html/2609.16822#bib.bib29)\), and it also forms the foundation for numerous hierarchical planning approaches\([Bercher et al\., 2017](https://arxiv.org/html/2609.16822#bib.bib30);[Bercher et al\., 2016](https://arxiv.org/html/2609.16822#bib.bib31);[Bit\-Monnot et al\., 2020](https://arxiv.org/html/2609.16822#bib.bib32);[Bit\-Monnot et al\., 2016](https://arxiv.org/html/2609.16822#bib.bib33)\)\.

In addition to POCL, other techniques have been developed to generate POPs\. One such method is*Petri net unfolding*\([Hickmott et al\., 2007](https://arxiv.org/html/2609.16822#bib.bib12)\), 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](https://arxiv.org/html/2609.16822#bib.bib24)\), 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](https://arxiv.org/html/2609.16822#bib.bib14)\), IPP\([Koehler, 1999](https://arxiv.org/html/2609.16822#bib.bib15)\), and Blackbox\([Kautz and Selman, 1998](https://arxiv.org/html/2609.16822#bib.bib13)\)\.

## 4Partial 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](https://arxiv.org/html/2609.16822#bib.bib27);[Fikes and Nilsson, 1971](https://arxiv.org/html/2609.16822#bib.bib25)\), 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](https://arxiv.org/html/2609.16822#bib.bib28)\)\. More recent work has applied partial weighted MaxSAT encodings to enhance execution flexibility by reducing the orderings in a plan\([Muise et al\., 2016](https://arxiv.org/html/2609.16822#bib.bib10)\)\. Building on this, the*action reinstantiation*extends the MaxSAT formulation with additional constraints, allowing operator parameter reassignment\([Waters et al\., 2018](https://arxiv.org/html/2609.16822#bib.bib34);[Waters et al\., 2020](https://arxiv.org/html/2609.16822#bib.bib9)\)\.

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\.1MR 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\)](https://arxiv.org/html/2609.16822#bib.bib10)\. The solution of the instance corresponds to a POP, which they denote as the*target*POP\. For a given POP or sequential planπ=⟨𝒪,≺⟩\\pi=\\langle\\mathcal\{O\},\\prec\\rangle, the encoding employs three categories of propositional variables−\-

- •xox\_\{o\}: Indicates the presence of operatorooin the*target*POP for eacho∈𝒪o\\in\\mathcal\{O\}\.
- •κ⁡\(oa,ob\)\\kappa\(o\_\{a\},o\_\{b\}\): Indicates that the the*target*POP includes the ordering constraintoa≺obo\_\{a\}\\prec o\_\{b\}for each operator pairoa,ob∈𝒪o\_\{a\},o\_\{b\}\\in\\mathcal\{O\}\.
- •Υ⁡\(op,⟨x,d⟩,oc\)\\Upsilon\(o\_\{p\},\\langle x,d\\rangle,o\_\{c\}\): Indicates that a causal linkop→⟨x,d⟩oco\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}o\_\{c\}is present in the*target*POP, for a pair of operatorop,oc∈𝒪o\_\{p\},o\_\{c\}\\in\\mathcal\{O\}, specifies that the operatoropo\_\{p\}produces⟨x,d⟩\\langle x,d\\ranglefor the operatoroco\_\{c\}, where⟨x,d⟩∈\(p​r​o​dop∩c​o​n​soc\)\\langle x,d\\rangle\\in\(prod\_\{o\_\{p\}\}\\cap 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 weightkkis represented by the syntax\(…\)k\\stackrel\{\{\\scriptstyle k\}\}\{\{\(\\dots\)\}\}, whereas no weight indication represents a hard clause\. To guarantee correctness, the encoding defines formulae \([3](https://arxiv.org/html/2609.16822#S4.E3)\) and \([4](https://arxiv.org/html/2609.16822#S4.E4)\) that enforce acyclicity in the target POP, where \([4](https://arxiv.org/html/2609.16822#S4.E4)\) ensures that the ordering constraints include the transitive closure\. Formula \([5](https://arxiv.org/html/2609.16822#S4.E5)\) includes the initial and goal operators\. Operators are treated as universally quantified, and in the case of formula \([6](https://arxiv.org/html/2609.16822#S4.E6)\), it is assumed thatoI≠oi≠oGo\_\{I\}\\neq o\_\{i\}\\neq o\_\{G\}\. Formula \([7](https://arxiv.org/html/2609.16822#S4.E7)\) guarantees that every causal link remains threat\-free by enforcing the required promotion or demotion orderings, while formula \([8](https://arxiv.org/html/2609.16822#S4.E8)\) ensures that each precondition is backed by an appropriate causal link\.

\(¬κ⁡\(o,o\)\)\\displaystyle\(\\neg\\kappa\(o,o\)\)\(3\)κ⁡\(op,oq\)∧κ⁡\(oq,or\)→κ⁡\(op,or\)\\displaystyle\\kappa\(o\_\{p\},o\_\{q\}\)\\land\\kappa\(o\_\{q\},o\_\{r\}\)\\xrightarrow\{\}\\kappa\(o\_\{p\},o\_\{r\}\)\(4\)\(xoI\)∧\(xoG\)\\displaystyle\(x\_\{o\_\{I\}\}\)\\land\(x\_\{o\_\{G\}\}\)\(5\)xoi→κ⁡\(oI,oi\)∧κ⁡\(oi,oG\)\\displaystyle x\_\{o\_\{i\}\}\\xrightarrow\{\}\\kappa\(o\_\{I\},o\_\{i\}\)\\land\\kappa\(o\_\{i\},o\_\{G\}\)\(6\)Υ\(op,⟨x,d⟩,oc\)→⋀od:⟨x,d⟩∈d​e​lodxod→κ\(od,op\)∨κ\(oc,od\)\\displaystyle\\Upsilon\(o\_\{p\},\\langle x,d\\rangle,o\_\{c\}\)\\xrightarrow\{\}\\bigwedge\\limits\_\{o\_\{d\}:\\langle x,d\\rangle\\in del\_\{o\_\{d\}\}\}x\_\{o\_\{d\}\}\\xrightarrow\{\}\\kappa\(o\_\{d\},o\_\{p\}\)\\lor\\kappa\(o\_\{c\},o\_\{d\}\)\(7\)xoc→⋀⟨x,d⟩∈c​o​n​soc⋁op:⟨x,d⟩∈p​r​o​dopκ\(op,oc\)∧Υ\(op,⟨x,d⟩,oc\)\\displaystyle x\_\{o\_\{c\}\}\\xrightarrow\{\}\\bigwedge\\limits\_\{\\langle x,d\\rangle\\in cons\_\{o\_\{c\}\}\}\\ \\bigvee\\limits\_\{o\_\{p\}:~\\langle x,d\\rangle\\in prod\_\{o\_\{p\}\}\}\\kappa\(o\_\{p\},o\_\{c\}\)\\land\\Upsilon\(o\_\{p\},\\langle x,d\\rangle,o\_\{c\}\)\(8\)For each operator and ordering variable in the encoding, a soft unit clause is introduced in formulae \([9](https://arxiv.org/html/2609.16822#S4.E9)\) and \([10](https://arxiv.org/html/2609.16822#S4.E10)\) 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\)c​o​s​to\+\|𝒪\|2\+1,∀o∈\(𝒪∖\{oI,oG\}\)\\displaystyle\\stackrel\{\{\\scriptstyle cost\_\{o\}\+\|\\mathcal\{O\}\|^\{2\}\+1\}\}\{\{\(\\neg x\_\{o\}\)\}\}~~,~~\\forall o\\in\(\\mathcal\{O\}\\setminus\\\{o\_\{I\},o\_\{G\}\\\}\)\(9\)\(¬κ⁡\(oi,oj\)\)1,∀oi,oj∈𝒪\\displaystyle\\stackrel\{\{\\scriptstyle 1\}\}\{\{\(\\neg\\kappa\(o\_\{i\},o\_\{j\}\)\)\}\}~~,~~\\forall o\_\{i\},o\_\{j\}\\in\\mathcal\{O\}\(10\)

### 4\.2MRR Encodings

The partial weighted MaxSAT encoding for achieving a plan’s minimum reordering is extended by[Waters et al\. \(2020\)](https://arxiv.org/html/2609.16822#bib.bib9)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 likexx,yy, andzz, constants bycc, and terms bytt,uu, andvv\. The definition of a termttis an ordered series of items, wheret⁡\[i\]t\[i\]is theii\-th element in the sequence\. A mapping of terms with variables is designated as substitutionΨ\\Psi; for instance,Ψ=\{x1/t1,x2/t2,…,xn/tn\}\\Psi=\\\{x\_\{1\}/t\_\{1\},x\_\{2\}/t\_\{2\},\\dots,x\_\{n\}/t\_\{n\}\\\}mapsxix\_\{i\}to the corresponding termtit\_\{i\}for alli∈\{1,2,…,n\}i\\in\\\{1,2,\\dots,n\\\}\. The sets of variables and constants that appear in a given structureη\\etaare denoted byv​a​r​s​\(η\)vars\(\\eta\)andc​o​n​s​t​s​\(η\)consts\(\\eta\)\. In this approach, a POP is represented asπ=⟨𝒪,Ψ,≺⟩\\pi=\\langle\\mathcal\{O\},\\Psi,\\prec\\rangle, where the set of operators is represented by𝒪\\mathcal\{O\},≺\\precis a strict partial order over𝒪\\mathcal\{O\}that is transitively closed, andΨ\\Psiis complete with respect to𝒪\\mathcal\{O\}\.

###### Definition 9\.

Letπp=⟨𝒪,Ψ,≺⟩\\pi\_\{p\}=\\langle\\mathcal\{O\},\\Psi,\\prec\\rangleandπq=⟨𝒪,Ψ′,≺′⟩\\pi\_\{q\}=\\langle\\mathcal\{O\},\\Psi^\{\\prime\},\\prec^\{\\prime\}\\ranglebe two different POPs, then:

- •πq\\pi\_\{q\}is areinstantiated reorderingofπp\\pi\_\{p\}ifπp\\pi\_\{p\}andπq\\pi\_\{q\}both are valid\.
- •πq\\pi\_\{q\}is aminimum reinstantiated reorderingofπp\\pi\_\{p\}ifπq\\pi\_\{q\}is a reinstantiated reordering ofπp\\pi\_\{p\}and there does not exist a POPπr=⟨𝒪,Ψ′′,≺′′⟩\\pi\_\{r\}=\\langle\\mathcal\{O\},\\Psi^\{\\prime\\prime\},\\prec^\{\\prime\\prime\}\\ranglesuch thatπr\\pi\_\{r\}is a reinstantiated reordering ofπp\\pi\_\{p\}with\|≺′′\|<\|≺′\|\|\\prec^\{\\prime\\prime\}\|<\|\\prec^\{\\prime\}\|\.

An operator is defined as a tupleo=⟨𝑣𝑎𝑟𝑠o,𝑝𝑟𝑒o,𝑒𝑓𝑓o⟩o=\\langle\\mathit\{vars\}\_\{o\},\\mathit\{pre\}\_\{o\},\\mathit\{eff\}\_\{o\}\\rangle, wherev​a​r​sovars\_\{o\}denotes the set of variables, and both𝑒𝑓𝑓o\\mathit\{eff\}\_\{o\}andp​r​eopre\_\{o\}are the finite sets of facts containingv​a​r​sovars\_\{o\}’s variables\. If bothp​r​eopre\_\{o\}and𝑒𝑓𝑓o\\mathit\{eff\}\_\{o\}are made up entirely of ground facts, thenoois considered as a ground operator\.⟨op,q⁡\(t→\),oc,q⁡\(u→\)⟩\\langle o\_\{p\},q\(\\overrightarrow\{t\}\),o\_\{c\},q\(\\overrightarrow\{u\}\)\\ranglerepresents a causal link, whereq⁡\(u→\)q\(\\overrightarrow\{u\}\)andq⁡\(t→\)q\(\\overrightarrow\{t\}\)are literals, withq⁡\(t→\)∈p​r​o​doq\(\\overrightarrow\{t\}\)\\in prod\_\{o\}andq⁡\(u→\)∈c​o​n​soq\(\\overrightarrow\{u\}\)\\in cons\_\{o\}\. The MRR encoding adds two additional categories of propositional variables in addition to thexxandκ\\kappautilized in the MR encoding:

- •ε⁡\(u,v\)\\varepsilon\(u,v\): Encodes that in the final POP the conditionΨ⁡\(t\)=Ψ⁡\(u\)\\Psi\(t\)=\\Psi\(u\)must be satisfied\.
- •τ⁡\(op,t→,oc,u→\)\\tau\(o\_\{p\},\\overrightarrow\{t\},o\_\{c\},\\overrightarrow\{u\}\): Encodes that there exists someqqsuch that the⟨op,q⁡\(t→\),oc,q⁡\(u→\)⟩\\langle o\_\{p\},q\(\\overrightarrow\{t\}\),o\_\{c\},q\(\\overrightarrow\{u\}\)\\ranglecausal link remains threat\-free within the final POP\.

To compute the MRR of a partial\-order planπp=⟨𝒪,Ψ,≺⟩\\pi\_\{p\}=\\langle\\mathcal\{O\},\\Psi,\\prec\\rangle, the following encoding together with formulae \([3](https://arxiv.org/html/2609.16822#S4.E3)\) through \([6](https://arxiv.org/html/2609.16822#S4.E6)\) is used\. Formulae \([11](https://arxiv.org/html/2609.16822#S4.E11)\) and \([12](https://arxiv.org/html/2609.16822#S4.E12)\) 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](https://arxiv.org/html/2609.16822#S4.E13)\)\. Formulae \([14](https://arxiv.org/html/2609.16822#S4.E14)\) and \([15](https://arxiv.org/html/2609.16822#S4.E15)\) formalize the conditions required for the validity of the target POP\.

ε⁡\(u,v\)↔ε⁡\(v,u\)\\displaystyle\\varepsilon\(u,v\)\\leftrightarrow\\varepsilon\(v,u\)\(11\)ε⁡\(u,v\)∧ε⁡\(v,t\)→ε⁡\(u,t\)\\displaystyle\\varepsilon\(u,v\)\\land\\varepsilon\(v,t\)\\rightarrow\\varepsilon\(u,t\)\(12\)⋀x∈v​a​r​s𝒪\(⋁c∈c​o​n​s​t​s𝒪ε⁡\(x,c\)∧⋀c′≠c′′c′,c′′∈c​o​n​s​t​s𝒪:¬ε⁡\(x,c′\)∨¬ε⁡\(x,c′′\)\)\\displaystyle\\bigwedge\\limits\_\{x\\in vars\_\{\\mathcal\{O\}\}\}\(\\bigvee\\limits\_\{c\\in consts\_\{\\mathcal\{O\}\}\}\\varepsilon\(x,c\)~~~\\land\\bigwedge\\limits\_\{\\stackrel\{\{\\scriptstyle c^\{\\prime\},c^\{\\prime\\prime\}\\in consts\_\{\\mathcal\{O\}\}:\}\}\{\{c^\{\\prime\}\\neq c^\{\\prime\\prime\}\}\}\}\\neg\\varepsilon\(x,c^\{\\prime\}\)\\lor\\neg\\varepsilon\(x,c^\{\\prime\\prime\}\)\)\(13\)⋀q⁡\(u→\)∈c​o​n​soc⋁q⁡\(t→\)∈p​r​o​dopτ⁡\(op,t→,oc,u→\)∧κ⁡\(op,oc\)\\displaystyle\\bigwedge\\limits\_\{q\(\\overrightarrow\{u\}\)\\in cons\_\{o\_\{c\}\}\}\\ \\bigvee\\limits\_\{q\(\\overrightarrow\{t\}\)\\in prod\_\{o\_\{p\}\}\}\\tau\(o\_\{p\},\\overrightarrow\{t\},o\_\{c\},\\overrightarrow\{u\}\)\\land\\kappa\(o\_\{p\},o\_\{c\}\)\(14\)τ⁡\(op,t→,oc,u→\)→⋀1≤i≤\|t→\|ε⁡\(t→​\[i\],u→​\[i\]\)∧⋀t→=v→,od≠ocq⁡\(v→\)∈d​e​lod:\(κ⁡\(od,op\)∨κ⁡\(oc,od\)\)\\displaystyle\\tau\(o\_\{p\},\\overrightarrow\{t\},o\_\{c\},\\overrightarrow\{u\}\)\\rightarrow\\bigwedge\\limits\_\{1\\leq i\\leq\|\\overrightarrow\{t\}\|\}\\varepsilon\(\\overrightarrow\{t\}\[i\],\\overrightarrow\{u\}\[i\]\)~~~\\land\\bigwedge\\limits\_\{\\stackrel\{\{\\scriptstyle q\(\\overrightarrow\{v\}\)\\in del\_\{o\_\{d\}\}:\}\}\{\{\\overrightarrow\{t\}=\\overrightarrow\{v\},o\_\{d\}\\neq o\_\{c\}\}\}\}\(\\kappa\(o\_\{d\},o\_\{p\}\)\\lor\\kappa\(o\_\{c\},o\_\{d\}\)\)\(15\)If a POP has fewer thankkordering constraints, determining if it admits a minimal reinstantiated reordering is𝑁𝑃\\mathit\{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\.

## 5Explanation\-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](https://arxiv.org/html/2609.16822#bib.bib16);[Kambhampati, 1994](https://arxiv.org/html/2609.16822#bib.bib19);[Kambhampati and Hendler, 1992](https://arxiv.org/html/2609.16822#bib.bib26)\)\. EOG has been further refined to support conditional effects\([Noor and Siddiqui, 2022](https://arxiv.org/html/2609.16822#bib.bib2)\)\. The EOG deorders plans by creating a validation structure, creating a causal link for each operator’s preconditions, and usingpromotionsordemotionsto mitigate threats to those causal links\([Kambhampati and Kedar, 1994](https://arxiv.org/html/2609.16822#bib.bib20);[Veloso et al\., 2002](https://arxiv.org/html/2609.16822#bib.bib16)\)\. Given a total\-order planπ\\piof a planning taskΠ=⟨𝒳,𝒪,si,sg⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle, EOG emulates the initial and goal conditions ofΠ\\Piby augmentingπ\\piwith a couple of additional operators,oIo\_\{I\}andoGo\_\{G\}\. Specifically,p​r​eoI=∅pre\_\{o\_\{I\}\}=\\emptyset,𝑒𝑓𝑓oI=si\\mathit\{eff\}\_\{o\_\{I\}\}=s\_\{i\},p​r​eoG=sgpre\_\{o\_\{G\}\}=s\_\{g\}, and𝑒𝑓𝑓oG=∅\\mathit\{eff\}\_\{o\_\{G\}\}=\\emptyset, withoI≺oGo\_\{I\}\\prec o\_\{G\}andoI≺o≺oGo\_\{I\}\\prec o\\prec o\_\{G\}for allo∈\(𝒪∖\{oI,oG\}\)o\\in\(\\mathcal\{O\}\\setminus\\\{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\.1Plan Deordering with Conditional Effects

Conditional effects\([Haslum et al\., 2019](https://arxiv.org/html/2609.16822#bib.bib22)\)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\)](https://arxiv.org/html/2609.16822#bib.bib2)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⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\}\_\{c\},s\_\{i\},s\_\{g\}\\ranglebe a planning task, where𝒪c\\mathcal\{O\}\_\{c\}is a set of a finite number of operators with conditional effects\. An effect of an operatoro∈𝒪co\\in\\mathcal\{O\}\_\{c\}consists of triples⟨c​o​n​d,x,d⟩\\langle cond,x,d\\rangle, forming a partial state wherec​o​n​dconddenotes the effect condition, which may be empty\. Whenoois applicable in the statess, applying it yields the states′=a​p​p​l​y​\(o,s\)s^\{\\prime\}=apply\(o,s\), wherex∈𝒳x\\in\\mathcal\{X\}takes the valued∈Dxd\\in D\_\{x\}if and only ifc​o​n​d⊆scond\\subseteq s\.

###### Definition 11\.

Letπp​o​p=⟨𝒪,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\ranglebe a POP and two operatorsoi,oj∈𝒪o\_\{i\},o\_\{j\}\\in\\mathcal\{O\}with conditional effects\.

- •oio\_\{i\}is considered as acandidate producerof⟨x,d⟩\\langle x,d\\ranglefor operatorojo\_\{j\}iff: 1. 1\.oj⊀oio\_\{j\}\\nprec o\_\{i\}, 2. 2\.⟨c​o​n​d,x,d⟩∈𝑒𝑓𝑓oi\\langle cond,x,d\\rangle\\in\\mathit\{eff\}\_\{o\_\{i\}\}and there exists other candidate producerop∈𝒪o\_\{p\}\\in\\mathcal\{O\}for every⟨x′,d′⟩∈c​o​n​d\\langle x^\{\\prime\},d^\{\\prime\}\\rangle\\in condwhereop≠ojo\_\{p\}\\neq o\_\{j\}, and 3. 3\.there exists no operatorok∈𝒪o\_\{k\}\\in\\mathcal\{O\}with⟨c​o​n​d1,x,d1⟩∈𝑒𝑓𝑓ok\\langle cond\_\{1\},x,d\_\{1\}\\rangle\\in\\mathit\{eff\}\_\{o\_\{k\}\}such thatoj⊀ok⊀oio\_\{j\}\\nprec o\_\{k\}\\nprec o\_\{i\},d1∈\(𝒟x∖\{d\}\)d\_\{1\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\), and there exists other candidate producerop∈𝒪o\_\{p\}\\in\\mathcal\{O\}for each⟨x′′,d′′⟩∈c​o​n​d1\\langle x^\{\\prime\\prime\},d^\{\\prime\\prime\}\\rangle\\in cond\_\{1\}\.
- •oio\_\{i\}is considered as anearliest candidate producerof⟨x,d⟩\\langle x,d\\ranglefor operatorojo\_\{j\}iffoio\_\{i\}is a candidate producer of⟨x,d⟩\\langle x,d\\rangleforojo\_\{j\}and there does not exists any candidate produceroko\_\{k\}of⟨x,d⟩\\langle x,d\\rangleforojo\_\{j\}withok≺oio\_\{k\}\\prec o\_\{i\}\.

###### Definition 12\.

Letπp​o​p=⟨𝒪,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O,\\prec\\rangle\}be a POP ando∈𝒪o\\in\\mathcal\{O\}be an operator with conditional effects\. The operatoroproduces, consumes, and deletes facts, which are represented by𝐩𝐫𝐨𝐝𝐨\\mathbf\{prod\_\{o\}\},𝐜𝐨𝐧𝐬𝐨\\mathbf\{cons\_\{o\}\}, and𝐝𝐞𝐥𝐨\\mathbf\{del\_\{o\}\}, respectively\. The fact−\-:

- •⟨x,d⟩∈c​o​n​so\\langle x,d\\rangle\\in cons\_\{o\}if⟨x,d⟩∈p​r​eo\\langle x,d\\rangle\\in pre\_\{o\}or⟨x,d⟩∈c​o​n​d\\langle x,d\\rangle\\in condsuch that⟨c​o​n​d,x′,d′⟩∈𝑒𝑓𝑓o\\langle cond,x^\{\\prime\},d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{o\}and there exists an operatorok∈𝒪\{o\_\{k\}\\in\\mathcal\{O\}\}witho→⟨x′,d′⟩oko\\xrightarrow\{\\langle x^\{\\prime\},d^\{\\prime\}\\rangle\}o\_\{k\}\.
- •⟨x,d⟩∈p​r​o​do\\langle x,d\\rangle\\in prod\_\{o\}if⟨c​o​n​d,x,d⟩∈𝑒𝑓𝑓o\\langle cond,x,d\\rangle\\in\\mathit\{eff\}\_\{o\}and there exists other candidate producerop∈𝒪o\_\{p\}\\in\\mathcal\{O\}for each⟨x′,d′⟩∈c​o​n​d\\langle x^\{\\prime\},d^\{\\prime\}\\rangle\\in condsuch thatop≺oo\_\{p\}\\prec o\.
- •⟨x,d⟩∈d​e​lo\\langle x,d\\rangle\\in del\_\{o\}ifx∉v​a​r​s​\(𝑐𝑜𝑛𝑠o\)x\\notin vars\(\\mathit\{cons\}\_\{o\}\)orc​o​n​so​\(x\)=dcons\_\{o\}\(x\)=d,⟨c​o​n​d,x,d′⟩∈𝑒𝑓𝑓o\\langle cond,x,d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{o\}, whered′∈\(𝒟x∖\{d\}\)d^\{\\prime\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\), and there exists a candidate producerop∈𝒪o\_\{p\}\\in\\mathcal\{O\}for each⟨x′,d′′⟩∈c​o​n​d\\langle x^\{\\prime\},d^\{\\prime\\prime\}\\rangle\\in cond\.

R​e​\(oa≺ob\)Re\(o\_\{a\}\\prec o\_\{b\}\)denotes the ordering reasons between two operatorsoao\_\{a\}andobo\_\{b\}with conditional effects, which can fall into the categories PC, CT, TP, and OC\.O​C​\(⟨x,d⟩\)OC\(\\langle x,d\\rangle\)denotes an*obstructor\-consumer*relation for a fact⟨x,d⟩\\langle x,d\\rangle, which occurs whenoao\_\{a\}preventsobo\_\{b\}from receiving the fact⟨x,d⟩∈c​o​n​d\\langle x,d\\rangle\\in cond, such that⟨c​o​n​d,x′,d′⟩∈𝑒𝑓𝑓ob\\langle cond,x^\{\\prime\},d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{o\_\{b\}\}\. If there is an operatoroko\_\{k\}that yields⟨x,d⟩\\langle x,d\\rangleandob≺ok≺oao\_\{b\}\\prec o\_\{k\}\\prec o\_\{a\}, thenO​C​\(⟨x,d⟩\)∈R​e​\(oa≺ob\)OC\(\\langle x,d\\rangle\)\\in Re\(o\_\{a\}\\prec o\_\{b\}\)is considered*threatened*\. This identified threat may be mitigated in two ways: through*Promotion*, by includingp​O​C​\(⟨x,d⟩\)pOC\(\\langle x,d\\rangle\)inR​e​\(ok≺oa\)Re\(o\_\{k\}\\prec o\_\{a\}\), or through*Demotion*, by includingO​C​p​\(⟨x,d⟩\)OCp\(\\langle x,d\\rangle\)inR​e​\(ob≺ok\)Re\(o\_\{b\}\\prec 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⟩\\langle x,d\\ranglerequired by an operator\. While determining a candidate producer of⟨x,d⟩\\langle x,d\\ranglefor an operatoroio\_\{i\}, additional orderings may be needed due toO​COC\(obstructor\-consumer\) reasons\. This occurs when an operatorodo\_\{d\}prevents another operatoropo\_\{p\}from providing⟨x,d⟩\\langle x,d\\rangletooio\_\{i\}through a conditional effect⟨c​o​n​d,x,d′⟩∈𝑒𝑓𝑓od\\langle cond,x,d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{o\_\{d\}\}, whered′∈\(𝒟x∖\{d\}\)d^\{\\prime\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\)\. To address this, the algorithm introduces an ordering reasonO​C​\(⟨x,d⟩\)OC\(\\langle x,d\\rangle\)inR​e​\(oq≺od\)Re\(o\_\{q\}\\prec o\_\{d\}\)for some operatoroqo\_\{q\}that obstructs the effect⟨c​o​n​d,x,d′⟩\\langle cond,x,d^\{\\prime\}\\rangleofodo\_\{d\}from being triggered\. The orderingoq≺odo\_\{q\}\\prec o\_\{d\}preventsc​o​n​dcondfrom holding, ensuring thatodo\_\{d\}no longer deletes⟨x,d⟩\\langle x,d\\rangle\. 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 toP​CPCandO​COCreasons through promotion or demotion of the threatening operators\.

## 6Block Deordering\-based Approach

Block deordering\([Siddiqui and Haslum, 2012](https://arxiv.org/html/2609.16822#bib.bib4)\)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](https://arxiv.org/html/2609.16822#bib.bib6)\)\. 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](https://arxiv.org/html/2609.16822#bib.bib6)\), generate*macro\-actions*\([Chrpa and Siddiqui, 2015](https://arxiv.org/html/2609.16822#bib.bib5)\), and improve flexibility via block\-substitution\([Noor and Siddiqui, 2024](https://arxiv.org/html/2609.16822#bib.bib1)\)\.

###### Definition 13\.

ABDPO planis denoted asπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\rangle, where𝒪\\mathcal\{O\}be a collection of operators,≺\\precis a collection of orderings within𝒪\\mathcal\{O\}, andℬ\\mathcal\{B\}is a set of blocks\. For a blockb∈ℬb\\in\\mathcal\{B\}, ifop,oq∈bo\_\{p\},o\_\{q\}\\in bandop≺oqo\_\{p\}\\prec o\_\{q\}, then there does not exist an operatoror∉bo\_\{r\}\\notin bsuch thatop≺or≺oqo\_\{p\}\\prec o\_\{r\}\\prec o\_\{q\}\. For any two blocksbp,bq∈ℬb\_\{p\},b\_\{q\}\\in\\mathcal\{B\}, exactly one of the following holds:bp⊂bqb\_\{p\}\\subset b\_\{q\},bq⊂bpb\_\{q\}\\subset b\_\{p\}, orbp∩bq=∅b\_\{p\}\\cap b\_\{q\}=\\emptyset\.

A block b can be characterized by its preconditions and effects, similar to an operator\. If some operatoro∈bo\\in bconsumes⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangleand no operatoro′∈bo^\{\\prime\}\\in bprovides⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangleto operatoroo, then a fact⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangleis one of the preconditions ofbb\. Conversely, if an operatoro∈bo\\in bgenerates⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangleand no subsequent operator withinbbmodifies it, then⟨x,d⟩\\langle\\textit\{\{x\}\},\\textit\{d\}\\rangleis included in the effects ofbb\. Unlike an individual operator, a block can have multiple effects on the same or different variables\. For example, ifoi,oj∈bo\_\{i\},o\_\{j\}\\in bwithoi⊀ojo\_\{i\}\\nprec o\_\{j\},oj⊀oio\_\{j\}\\nprec o\_\{i\},⟨x,d⟩∈𝑒𝑓𝑓oi\\langle x,d\\rangle\\in\\mathit\{eff\}\_\{o\_\{i\}\}, and⟨x,d′⟩∈𝑒𝑓𝑓oj\\langle x,d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{o\_\{j\}\}, then a blockbbhas both⟨x,d⟩\\langle x,d\\rangleand⟨x,d′⟩\\langle x,d^\{\\prime\}\\rangleas its effects \(whered≠d′d\\neq d^\{\\prime\}\)\. The labelsP​CPC\(producer\-consumer\),C​TCT\(consumer\-threat\), andT​PTP\(threat\-producer\) can also be used to annotate ordering relations between blocks\.

###### Definition 14\.

Let a BDPO planπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\ranglewithb∈ℬb\\in\\mathcal\{B\}be a block, then:

- •Ifoi∈bo\_\{i\}\\in bbe an operator with⟨x,d⟩∈p​r​eoi\\langle x,d\\rangle\\in pre\_\{o\_\{i\}\}and there exists no operatoroj∈bo\_\{j\}\\in bwithi≠ji\\neq jthat delivers⟨x,d⟩\\langle x,d\\rangletooio\_\{i\}via a causal linkoj→⟨x,d⟩oio\_\{j\}\\xrightarrow\{\\langle x,d\\rangle\}o\_\{i\}, then the fact⟨x,d⟩∈p​r​eb\\langle x,d\\rangle\\in pre\_\{b\}\.
- •Ifoi∈bo\_\{i\}\\in bbe an operator with⟨x,d⟩∈𝑒𝑓𝑓oi\\langle x,d\\rangle\\in\\mathit\{eff\}\_\{o\_\{i\}\}and no subsequent operatoroj∈bo\_\{j\}\\in b\(withoi≺ojo\_\{i\}\\prec o\_\{j\}\) produces a different value⟨x,d′⟩\\langle x,d^\{\\prime\}\\ranglefor the same variablexxwithd′∈\(𝒟x∖\{d\}\)d^\{\\prime\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\), then the fact⟨x,d⟩∈𝑒𝑓𝑓b\\langle x,d\\rangle\\in\\mathit\{eff\}\_\{b\}\.

###### Definition 15\.

For a blockbb, the sets of facts that it consumes, produces, and deletes are denoted asconsb,prodb, anddelb, respectively\. Where:

- •A fact⟨x,d⟩∈c​o​n​sb\\langle x,d\\rangle\\in cons\_\{b\}if and only if⟨x,d⟩∈p​r​eb\\langle x,d\\rangle\\in pre\_\{b\}\.
- •A fact⟨x,d⟩∈p​r​o​db\\langle x,d\\rangle\\in prod\_\{b\}if and only if⟨x,d⟩∉c​o​n​sb\\langle x,d\\rangle\\notin cons\_\{b\},⟨x,d⟩∈𝑒𝑓𝑓b\\langle x,d\\rangle\\in\\mathit\{eff\}\_\{b\}, and no other effect⟨x,d′⟩∈𝑒𝑓𝑓b\\langle x,d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{b\}exists withd′∈\(𝒟x∖\{d\}\)d^\{\\prime\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\)\.
- •A fact⟨x,d⟩∈d​e​lb\\langle x,d\\rangle\\in del\_\{b\}if and only if eitherx∉v​a​r​s​\(c​o​n​sb\)x\\notin vars\(cons\_\{b\}\)orc​o​n​sb​\(x\)=dcons\_\{b\}\(x\)=d, and there exists an effect⟨x,d′⟩∈𝑒𝑓𝑓b\\langle x,d^\{\\prime\}\\rangle\\in\\mathit\{eff\}\_\{b\}withd′∈\(𝒟x∖\{d\}\)d^\{\\prime\}\\in\(\\mathcal\{D\}\_\{x\}\\setminus\\\{d\\\}\)\.

###### Definition 16\.

Let a BDPO planπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\ranglewith a pair of blocksb,b′∈ℬb,b^\{\\prime\}\\in\\mathcal\{B\}and⟨x,d⟩∈c​o​n​sb′\\langle x,d\\rangle\\in cons\_\{b^\{\\prime\}\}, then:

- •If⟨x,d⟩∈𝑒𝑓𝑓b\\langle x,d\\rangle\\in\\mathit\{eff\}\_\{b\},b≺b′b\\prec b^\{\\prime\}, and no other blockb′′∈ℬb^\{\\prime\\prime\}\\in\\mathcal\{B\}exists such that⟨x,d⟩∈d​e​lb′′\\langle x,d\\rangle\\in del\_\{b^\{\\prime\\prime\}\}andb′⊀b′′⊀bb^\{\\prime\}\\nprec b^\{\\prime\\prime\}\\nprec b, then blockbbis acandidate producerof the fact⟨x,d⟩\\langle x,d\\rangleforb′b^\{\\prime\}\.
- •If there is no other candidate producerb′′b^\{\\prime\\prime\}of⟨x,d⟩\\langle x,d\\rangleforb′b^\{\\prime\}withb′′≺bb^\{\\prime\\prime\}\\prec b, then blockbbis considered as anearliest candidate producerof⟨x,d⟩\\langle x,d\\rangleforb′b^\{\\prime\}\.

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π=⟨𝒪,≺⟩\\pi=\\langle\\mathcal\{O\},\\prec\\rangleusing EOG\. Next, a blockb=\{o\}b=\\\{o\\\}is created and added toℬ\\mathcal\{B\}for every operatoro∈𝒪o\\in\\mathcal\{O\}to construct an initial BDPO planπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\rangle\. Ordering constraintb≺b′b\\prec b^\{\\prime\}is introduced for every orderingo≺o′o\\prec o^\{\\prime\}present in≺\\prec, whereo∈bo\\in b,o′∈b′o^\{\\prime\}\\in b^\{\\prime\}, andb,b′∈ℬb,b^\{\\prime\}\\in\\mathcal\{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πb​d​p​o​p\\pi\_\{bdpop\}\.

###### Rule 1\.

A valid BDPO planπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\ranglewith an orderingbp≺bqb\_\{p\}\\prec b\_\{q\}and letbbbe a block\.

1. i\.Ifbp∈bb\_\{p\}\\in b,bq∉bb\_\{q\}\\notin b, andbp⊀b′b\_\{p\}\\nprec b^\{\\prime\}for allb′∈\(b∖bp\)b^\{\\prime\}\\in\(b\\setminus b\_\{p\}\), therefore,P​C​\(⟨x,d⟩\)PC\(\\langle x,d\\rangle\)can be eliminated fromR​e​\(bp≺bq\)Re\(b\_\{p\}\\prec b\_\{q\}\)if⟨x,d⟩∈p​r​eb\\langle x,d\\rangle\\in pre\_\{b\}and there existsbp∉bb\_\{p\}\\notin bwhich can create causal linksbp→⟨x,d⟩bqb\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}b\_\{q\}andbp→⟨x,d⟩bb\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}b\.
2. ii\.Ifbp∈bb\_\{p\}\\in b,bq∉bb\_\{q\}\\notin b, andb∩bq=∅b\\cap b\_\{q\}=\\emptyset, therefore,C​T​\(⟨x,d⟩\)CT\(\\langle x,d\\rangle\)can be eliminated fromR​e​\(bp≺bq\)Re\(b\_\{p\}\\prec b\_\{q\}\)if⟨x,d⟩∉c​o​n​sb\\langle x,d\\rangle\\notin cons\_\{b\}\.
3. iii\.Ifbp∉bb\_\{p\}\\notin b,bq∈bb\_\{q\}\\in b, andbp∩b=∅b\_\{p\}\\cap b=\\emptyset, therefore,C​T​\(⟨x,d⟩\)CT\(\\langle x,d\\rangle\)can be eliminated fromR​e​\(bp≺bq\)Re\(b\_\{p\}\\prec b\_\{q\}\)if⟨x,d⟩∉d​e​lb\\langle x,d\\rangle\\notin del\_\{b\}\.
4. iv\.Ifbq∈bb\_\{q\}\\in bandbp∉bb\_\{p\}\\notin b, therefore,T​P​\(⟨x,d⟩\)TP\(\\langle x,d\\rangle\)can be eliminated fromR​e​\(bp≺bq\)Re\(b\_\{p\}\\prec b\_\{q\}\)ifbbcontains all blocksb′b^\{\\prime\}withbq→⟨x,d⟩b′b\_\{q\}\\xrightarrow\{\\langle x,d\\rangle\}b^\{\\prime\}\.

Block deordering begins by examining each ordering in the initial BDPO plan from top to bottom, attempting to remove them greedily\. If Rule[1](https://arxiv.org/html/2609.16822#Thmrules1)can eliminate all of the ordering reasons for an orderingbp≺bqb\_\{p\}\\prec b\_\{q\}, then that ordering is eliminated\. The orderingbp≺bqb\_\{p\}\\prec 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\.1Flexibility Improvement via Block\-Substitution

Block\-substitution\([Noor and Siddiqui, 2024](https://arxiv.org/html/2609.16822#bib.bib1)\)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πb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\ranglebe a valid BDPO plan,b∈ℬb\\in\\mathcal\{B\}, and a subplanb~=⟨𝒪~,≺~⟩\\tilde\{b\}=\\langle\\tilde\{\\mathcal\{O\}\},\\tilde\{\\prec\}\\ranglewith𝒪~⊂𝒪\\tilde\{\\mathcal\{O\}\}\\subset\\mathcal\{O\}\. A new BDPO planπb​d​p​o​p′=⟨𝒪′,≺′,ℬ′⟩\\pi^\{\\prime\}\_\{bdpop\}=\\langle\\mathcal\{O^\{\\prime\}\},\\prec^\{\\prime\},\\mathcal\{B^\{\\prime\}\}\\rangleis produced ifbbis substituted withb~\\tilde\{b\}whereb∉ℬ′b\\notin\\mathcal\{B\}^\{\\prime\}andb~∈ℬ′\\tilde\{b\}\\in\\mathcal\{B\}^\{\\prime\}\. Ifπb​d​p​o​p′\\pi^\{\\prime\}\_\{bdpop\}is a valid BDPO plan, then the block\-substitution is considered*valid*\.

###### Definition 18\.

Letπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\ranglebe a valid BDPO plan and some causal linkbp→⟨x,d⟩bcb\_\{p\}\\xrightarrow\{\\langle x,d\\rangle\}b\_\{c\}is threatened bybt∈ℬb\_\{t\}\\in\\mathcal\{B\}, where⟨x,d⟩∈d​e​lbt\\langle x,d\\rangle\\in del\_\{b\_\{t\}\}andbp,bc∈ℬb\_\{p\},b\_\{c\}\\in\\mathcal\{B\}\. A threat is considered resolved if athreat\-resolution strategyfrom the following can be used without creating a cycle inπb​d​p​o​p\\pi\_\{bdpop\}:

1. i\.Promotion: introduce the orderingbt≺bpb\_\{t\}\\prec b\_\{p\}into≺\\prec\.
2. ii\.Demotion: introduce the orderingbc≺btb\_\{c\}\\prec b\_\{t\}into≺\\prec\.
3. iii\.Internal substitution: replacebtb\_\{t\}withbcb\_\{c\}, orbcb\_\{c\}withbtb\_\{t\}\.

The procedure replaces a blockbbwith a substituting blockb~\\tilde\{b\}\. The process starts by making sure that every precondition of theb~\\tilde\{b\}is supported by a causal link, butb~\\tilde\{b\}’s preconditions are already satisfied if it is internal\. For an external block,b~\\tilde\{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, usingb~\\tilde\{b\}as the new producer, every causal link that blockbbinitially supported is restored\. Ifb~\\tilde\{b\}does not produce a required fact for any dependent block, the substitution is unsuccessful\. Once these causal links are in place,bbis 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 withb~\\tilde\{b\}resolves threats while maintaining plan validity\. The block\-substitution process has an overall worst\-case complexity ofO⁡\(n2​p2\)O\(n^\{2\}p^\{2\}\), whereppis the highest possible number of facts in any operator’s effect or precondition andnnis the number of operators in the plan\.

Flexibility Improvement via Block\-Substitution \(FIBS\)\([Noor and Siddiqui, 2024](https://arxiv.org/html/2609.16822#bib.bib1)\)algorithm generates a valid BDPO plan given a valid total\-order planπ\\pias input\. First, using EOG, a partial\-order planπp​o​p=\(𝒪,≺\)\\pi\_\{pop\}=\(\\mathcal\{O\},\\prec\)is created fromπ\\pi\. A BDPO planπb​d​p​o​p=⟨𝒪,≺,ℬ⟩\\pi\_\{bdpop\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\rangleis then created from this partial\-order plan by constructing a blockb=\{o\}b=\\\{o\\\}for eacho∈𝒪o\\in\\mathcal\{O\}\. In the next phase, ordering constraints are removed fromπb​d​p​o​p\\pi\_\{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 orderingbi≺bjb\_\{i\}\\prec b\_\{j\}in the BDPO plan and attempts to remove it by substitutingbjb\_\{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\.2Concurrency 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\)](https://arxiv.org/html/2609.16822#bib.bib3)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\.

Aparallel planis denoted asπ𝒫=⟨𝒪,≺,\#⟩\\pi\_\{\\mathcal\{P\}\}=\\langle\\mathcal\{O\},\\prec,\\\#\\rangle, which basically extends a POP⟨𝒪,≺⟩\\langle\\mathcal\{O\},\\prec\\ranglewith an irreflexive and symmetric relation\#\\\#, which represents non\-concurrency constraints over𝒪\\mathcal\{O\}\. Two operators,oao\_\{a\}andobo\_\{b\}, have a non\-concurrency constraint, expressed asoa​\#​obo\_\{a\}\\\#o\_\{b\}, ifc​o​n​soa​\(x\)≠c​o​n​sob​\(x\)cons\_\{o\_\{a\}\}\(x\)\\neq cons\_\{o\_\{b\}\}\(x\),p​r​o​doa​\(x\)≠p​r​o​dob​\(x\)prod\_\{o\_\{a\}\}\(x\)\\neq prod\_\{o\_\{b\}\}\(x\), orc​o​n​soa​\(x\)≠p​r​o​dob​\(x\)cons\_\{o\_\{a\}\}\(x\)\\neq prod\_\{o\_\{b\}\}\(x\)for any variablex∈𝒳x\\in\\mathcal\{X\}, which means that they cannot be executed simultaneously\.

###### Definition 20\.

Letπ𝒫=⟨𝒪,≺,\#⟩\\pi\_\{\\mathcal\{P\}\}=\\langle\\mathcal\{O\},\\prec,\\\#\\ranglebe a parallel plan\. The ratio of the operator pairs that can be executed simultaneously to the maximum possible operator pairs is theconcurrent flexibilityvalue of the parallel planπ𝒫\\pi\_\{\\mathcal\{P\}\}, as specified in \([16](https://arxiv.org/html/2609.16822#S6.E16)\), expressed as𝑐𝑓𝑙𝑒𝑥⁡\(π𝒫\)\\mathit\{cflex\}\(\\pi\_\{\\mathcal\{P\}\}\)\.

𝑐𝑓𝑙𝑒𝑥⁡\(π𝒫\)=1−∑1≤b<a≤\|𝒪\|\{1ifoa≺ob,ob≺oa, oroa​\#​ob0otherwise∑n=1\|𝒪\|−1n\\mathit\{cflex\}\(\\pi\_\{\\mathcal\{P\}\}\)=1\-\\frac\{\\sum\\limits\_\{1\\leq b<a\\leq\|\\mathcal\{O\}\|\}\\begin\{cases\}1&\\text\{if $o\_\{a\}\\prec o\_\{b\}$, $o\_\{b\}\\prec o\_\{a\}$, or $o\_\{a\}\\\#o\_\{b\}$\}\\\\ 0&\\text\{otherwise\}\\end\{cases\}\}\{\\sum\_\{n=1\}^\{\|\\mathcal\{O\}\|\-1\}n\}\(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\)](https://arxiv.org/html/2609.16822#bib.bib36)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\)](https://arxiv.org/html/2609.16822#bib.bib3)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\)](https://arxiv.org/html/2609.16822#bib.bib36)and[Boutilier and Brafman \(2001\)](https://arxiv.org/html/2609.16822#bib.bib37)handle this by explicitly defining which resources each operator used, but none established how to identify parallelism without such information\.[Noor and Siddiqui \(2025\)](https://arxiv.org/html/2609.16822#bib.bib3)extended the idea of the BDPO plan by adding the non\-concurrency relation to allow blocks to be executed in parallel\.

###### Definition 21\.

Aparallel block decomposed partial\-order\(PBDPO\) plan is denoted asπp​b​d​p=⟨𝒪,≺,ℬ,\#⟩\\pi\_\{pbdp\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\},\\\#\\rangle, which basically extends a BDPO plan⟨𝒪,≺,ℬ⟩\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\}\\ranglewith an symmetric, irreflexive relation\#\\\#overℬ\\mathcal\{B\}, depicting non\-concurrency constraints between blocks\. Blocksbpb\_\{p\}andbqb\_\{q\}are considered non\-concurrent, expressed asbp​\#​bqb\_\{p\}\\\#b\_\{q\}, if two primitive operatorsop∈bpo\_\{p\}\\in b\_\{p\}andoq∈bqo\_\{q\}\\in b\_\{q\}are non\-concurrent \(op​\#​oqo\_\{p\}\\\#o\_\{q\}\)\. Variables causing this non\-concurrency are denoted by the setv​a​r​s​\(bp​\#​bq\)vars\(b\_\{p\}\\\#b\_\{q\}\)\.

###### Definition 22\.

Letπp​b​d​p=⟨𝒪,≺,ℬ,\#⟩\\pi\_\{pbdp\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\},\\\#\\ranglebe a valid parallel BDPO plan withbp​\#​bqb\_\{p\}\\\#b\_\{q\}, where blocksbp,bq∈ℬb\_\{p\},b\_\{q\}\\in\\mathcal\{B\}are two disjoint blocks\. Thebp​\#​bqb\_\{p\}\\\#b\_\{q\}is considerednecessary non\-concurrency constraintwithinπp​b​d​p\\pi\_\{pbdp\}if−\-

1. i\.bp⊀bq⊀bpb\_\{p\}\\nprec b\_\{q\}\\nprec b\_\{p\}, and
2. ii\.ifbpb\_\{p\}is in the blockbx∈Bb\_\{x\}\\in B, thenbqb\_\{q\}is also in the blockbxb\_\{x\}\.

The Concurrent Flexibility Improvement via Block\-Substitution \(CIBS\) algorithm generates a valid PBDPO plan from a valid total\-order planπ\\pifor a planning taskΠ\\Pi\. The CIBS algorithm extends blocks before substitution\. It selects two blocksbpb\_\{p\}andbqb\_\{q\}withbp​\#​bqb\_\{p\}\\\#b\_\{q\}in a PBDPO planπp​b​d​p\\pi\_\{pbdp\}with respect to a planning taskΠ\\Pi\. Then, the procedure includes the necessary blocks to the blockbpb\_\{p\}to achieve a new blockbp′b\_\{p\}^\{\\prime\}so that another blockb^p\\hat\{b\}\_\{p\}can be used in place ofbp′b\_\{p\}^\{\\prime\}wherev​a​r​s​\(b^p​\#​bq\)=∅vars\(\\hat\{b\}\_\{p\}\\\#b\_\{q\}\)=\\emptyset\.

The CIBS algorithm enhances the concurrent flexibility through block\-substitution in three steps\. In the first step, EOG is applied to convertπ\\piinto a parallel planπe​o​g=⟨𝒪,≺,\#⟩\\pi\_\{eog\}=\\langle\\mathcal\{O\},\\prec,\\\#\\ranglefirst, 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πe​o​g\\pi\_\{eog\}and yields a PBDPO planπp​b​d​p=⟨𝒪,≺,ℬ,\#⟩\\pi\_\{pbdp\}=\\langle\\mathcal\{O\},\\prec,\\mathcal\{B\},\\\#\\rangle\. In the last stage, blocks are replaced to improve the concurrent flexibility ofπp​b​d​p\\pi\_\{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𝑐𝑓𝑙𝑒𝑥\\mathit\{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𝑐𝑓𝑙𝑒𝑥\\mathit\{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\.

## 7Analysis

The optimization capabilities of the six algorithms are summarized in Table[1](https://arxiv.org/html/2609.16822#S7.T1)across six categories: ordering, action handling, parameter handling, plan structure, concurrency, and complexity and optimality\.

Table 1:Optimization capability comparison among algorithmsCriteriaEOGBDMRMRRFIBSCIBSOrderingRemove OrderingsYesYesYesYesYesYesArbitrary ReorderingNoNoYesYesNoNoBlock\-level DeorderingNoYesNoNoYesYesMinimizes OrderingsNoNoYesYesNoNoAction HandlingRemove Redundant ActionsNoNoYesYesNoNoIntroduce New ActionsNoNoNoNoYesYesReplace Action Sets \(Subplans\)NoNoNoNoYesYesReplace Actions of Different NameNoNoNoNoYesYesParameter HandlingRebind ParametersNoNoNoYesNoNoSame\-name Operator Rebinding Only\-\-\-Yes\-\-Plan structureProduces Partial\-order PlanYesYesYesYesYesYesProduces BDPO PlanNoYesNoNoYesYesProduces Parallel PlanNoNoNoNoNoYesProduces Parallel BDPO PlanNoNoNoNoNoYesExternal Planner for SubplansNoNoNoNoYesYesConcurrencyNon\-concurrency Constraints \(\#\)NoNoNoNoNoYesMinimizes\#NoNoNoNoNoYesImproves Parallel ExecutionNoPartialNoNoPartialYesUses FDR for\#ConditionsNoNoNoNoNoYesBlock Extension via DTG AnalysisNoNoNoNoNoYesComplexity and OptimalityPolynomial\-time AlgorithmYesYesNoNoPartialPartialMaxSAT\-based EncodingNoNoYesYesNoNoAnytime / Iterative ImprovementNoNoNoNoYesYesComposable on top of MR/MRRNoNo\-\-YesNoAll 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 inO⁡\(n2​p2\)O\(n^\{2\}p^\{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\.

## 8Evaluation

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](https://arxiv.org/html/2609.16822#S2.E2)\)\. 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\.1Flex\-Time Trade\-off

Figure[1](https://arxiv.org/html/2609.16822#S8.F1)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\.2Flex Efficiency

Figure[2](https://arxiv.org/html/2609.16822#S8.F2)shows flex efficiency per algorithm and domain, measured as flex gain over EOG per additional second spent \(Δ\\Deltaflex/Δ\\Deltatime\)\. 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](https://arxiv.org/html/2609.16822#S8.F2)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\.3Statistical Effect Size

Figure[3](https://arxiv.org/html/2609.16822#S8.F3)presents a pairwise effect\-size heatmap using the rank\-biserial correlationrrfrom a two\-sided Mann–Whitney U test on the flex distributions\. A positiverrin rowAAand columnBBmeans algorithmAAproduces higher flex on more plans than algorithmBB; significance levels are marked as \*\(p<0\.05p<0\.05\), \*\* \(p<0\.01p<0\.01\), and \*\*\* \(p<0\.001p<0\.001\)\.

![Refer to caption](https://arxiv.org/html/2609.16822v1/effect_size_heatmap.png)Figure 3:Effect Size \- Rank\-biserial rBD and FIBS show strong positiverrvalues 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 negativerrvalues 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\.4Multi\-Criteria Comparison

Figure[4](https://arxiv.org/html/2609.16822#S8.F4)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 ChartMR 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\.

## 9Conclusion

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𝑐𝑓𝑙𝑒𝑥\\mathit\{cflex\}to account for this, instead of relying on𝑓𝑙𝑒𝑥\\mathit\{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

- J\. S\. Anderson and A\. M\. FarleyPlan abstraction based on operator generalization\.InProceedings of the Seventh AAAI National Conference on Artificial Intelligence,AAAI’88,pp\. 100–104\.Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p1.1)\.
- Bäckström \(1998\)C\. BäckströmComputational aspects of reordering plans\.Journal of Artificial Intelligence Research9,pp\. 99–137\.Cited by:[§2\.2](https://arxiv.org/html/2609.16822#S2.SS2.p3.1),[§2\.3](https://arxiv.org/html/2609.16822#S2.SS3.p1.1)\.
- Bercheret al\.\(2017\)P\. Bercher, G\. Behnke, D\. Höller, and S\. BiundoAn admissible HTN planning heuristic\.InProceedings of the Twenty\-Sixth International Joint Conference on Artificial Intelligence, IJCAI\-17,pp\. 480–488\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2017/68)Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Bercheret al\.\(2016\)P\. Bercher, D\. Höller, G\. Behnke, and S\. BiundoMore than a name? on implications of preconditions and effects of compound HTN planning tasks\.InProceedings of the Twenty\-Second European Conference on Artificial Intelligence,ECAI’16,NLD,pp\. 225–233\.External Links:ISBN 9781614996712,[Document](https://dx.doi.org/10.3233/978-1-61499-672-9-225)Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Bit\-Monnotet al\.\(2020\)A\. Bit\-Monnot, M\. Ghallab, F\. Ingrand, and D\. E\. SmithFAPE: a constraint\-based planner for generative and hierarchical temporal planning\.External Links:2010\.13121Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Bit\-Monnotet al\.\(2016\)A\. Bit\-Monnot, D\. E\. Smith, and M\. DoDelete\-free Reachability Analysis for Temporal and Hierarchical Planning \(full version\)\.InICAPS Workshop on Heuristics and Search for Domain\-independent Planning \(HSDIP\),London, United Kingdom\.External Links:[Link](https://ut3-toulouseinp.hal.science/hal-01319768)Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Blum and Furst \(1997\)A\. L\. Blum and M\. L\. FurstFast planning through planning graph analysis\.Artificial Intelligence90\(1\),pp\. 281–300\.External Links:ISSN 0004\-3702,[Document](https://dx.doi.org/10.1016/S0004-3702%2896%2900047-1)Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p2.1)\.
- Boutilier and Brafman \(2001\)C\. Boutilier and R\. I\. BrafmanPartial\-order planning with concurrent interacting actions\.Journal of Artificial Intelligence Research14,pp\. 105–136\.External Links:ISSN 1076\-9757,[Document](https://dx.doi.org/10.1613/jair.740)Cited by:[§6\.2](https://arxiv.org/html/2609.16822#S6.SS2.p2.1)\.
- Chrpa and Siddiqui \(2015\)L\. Chrpa and F\. H\. SiddiquiExploiting block deordering for improving planners efficiency\.InProceedings of the 24th International Conference on Artificial Intelligence,IJCAI’15,pp\. 1537–1543\.External Links:ISBN 9781577357384Cited by:[§6](https://arxiv.org/html/2609.16822#S6.p1.1)\.
- Coleset al\.\(2021\)A\. Coles, A\. Coles, M\. Fox, and D\. LongForward\-chaining partial\-order planning\.Proceedings of the International Conference on Automated Planning and Scheduling20\(1\),pp\. 42–49\.External Links:[Link](https://ojs.aaai.org/index.php/ICAPS/article/view/13403),[Document](https://dx.doi.org/10.1609/icaps.v20i1.13403)Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Fikes and Nilsson \(1971\)R\. E\. Fikes and N\. J\. NilssonSTRIPS: a new approach to the application of theorem proving to problem solving\.Artificial Intelligence2\(3\),pp\. 189–208\.External Links:ISSN 0004\-3702,[Document](https://dx.doi.org/10.1016/0004-3702%2871%2990010-5)Cited by:[§4](https://arxiv.org/html/2609.16822#S4.p1.1)\.
- Fox and Long \(2001\)M\. Fox and D\. LongHybrid STAN: identifying and managing combinatorial optimisation sub\-problems in planning\.InProceedings of the 17th International Joint Conference on Artificial Intelligence \- Volume 1,IJCAI’01,San Francisco, CA, USA,pp\. 445–450\.External Links:ISBN 1558608125Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p2.1)\.
- Grahamet al\.\(2003\)J\. R\. Graham, K\. S\. Decker, and M\. MersicDECAF \- a flexible multi agent system architecture\.Autonomous Agents and Multi\-Agent Systems7\(1–2\),pp\. 7–27\.External Links:ISSN 1387\-2532,[Document](https://dx.doi.org/10.1023/A%3A1024120703127)Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p1.1)\.
- Haslumet al\.\(2019\)P\. Haslum, N\. Lipovetzky, D\. Magazzeni, and C\. MuiseAn introduction to the planning domain definition language\.Synthesis Lectures on Artificial Intelligence and Machine Learning,Morgan & Claypool\.External Links:ISBN 9781681735122Cited by:[§5\.1](https://arxiv.org/html/2609.16822#S5.SS1.p1.1)\.
- Helmert \(2011\)M\. HelmertThe fast downward planning system\.Journal of Artificial Intelligence Research26,pp\.\.External Links:[Document](https://dx.doi.org/10.1613/jair.1705)Cited by:[§2\.1](https://arxiv.org/html/2609.16822#S2.SS1.p1.1)\.
- Hickmottet al\.\(2007\)S\. Hickmott, J\. Rintanen, S\. Thiébaux, and L\. WhitePlanning via petri net unfolding\.InProceedings of the 20th International Joint Conference on Artificial Intelligence,IJCAI’07,San Francisco, CA, USA,pp\. 1904–1911\.Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p2.1)\.
- Kambhampati and Hendler \(1992\)S\. Kambhampati and J\. A\. HendlerA validation\-structure\-based theory of plan modification and reuse\.Artificial Intelligence55\(2\),pp\. 193–258\.External Links:ISSN 0004\-3702,[Document](https://dx.doi.org/10.1016/0004-3702%2892%2990056-4)Cited by:[§5](https://arxiv.org/html/2609.16822#S5.p1.1)\.
- Kambhampati and Kedar \(1994\)S\. Kambhampati and S\. KedarA unified framework for explanation\-based generalization of partially ordered and partially instantiated plans\.Artificial Intelligence67\(1\),pp\. 29–70\.External Links:[Document](https://dx.doi.org/10.1016/0004-3702%2894%2990011-6),ISSN 0004\-3702Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§5](https://arxiv.org/html/2609.16822#S5.p1.1)\.
- Kambhampati \(1994\)S\. KambhampatiMulti\-contributor causal structures for planning: a formalization and evaluation\.Artificial Intelligence69\(1\-2\),pp\. 235–278\(English \(US\)\)\.External Links:[Document](https://dx.doi.org/10.1016/0004-3702%2894%2990083-3),ISSN 0004\-3702Cited by:[§5](https://arxiv.org/html/2609.16822#S5.p1.1)\.
- Kautz and Selman \(1998\)H\. Kautz and B\. SelmanBLACKBOX: a new approach to the application of theorem proving to problem solving\.InAIPS98 Workshop on Planning as Combinatorial Search,Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p2.1)\.
- Knoblock \(1994\)C\. A\. KnoblockGenerating parallel execution plans with a partial\-order planner\.InInternational Conference on Artificial Intelligence Planning Systems,pp\. 98–103\.Cited by:[§6\.2](https://arxiv.org/html/2609.16822#S6.SS2.p2.1)\.
- Koehler \(1999\)J\. KoehlerHandling of conditional effects and negative goals in IPP\.Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p2.1)\.
- Muiseet al\.\(2016\)C\. Muise, J\. Beck, and S\. McIlraithOptimal partial\-order plan relaxation via MaxSAT\.Journal of Artificial Intelligence Research57,pp\. 113–149\.External Links:[Document](https://dx.doi.org/10.1613/jair.5128)Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p1.1),[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§4\.1](https://arxiv.org/html/2609.16822#S4.SS1.p1.1),[§4](https://arxiv.org/html/2609.16822#S4.p1.1)\.
- Nguyen and Kambhampati \(2001\)X\. Nguyen and S\. KambhampatiReviving partial order planning\.pp\. 459–466\.Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p1.1)\.
- Noor and Siddiqui \(2022\)S\. B\. Noor and F\. H\. SiddiquiPlan deordering with conditional effects\.InIntelligent Systems and Applications,K\. Arai \(Ed\.\),pp\. 852–870\.External Links:ISBN 978\-3\-031\-16078\-3Cited by:[§5\.1](https://arxiv.org/html/2609.16822#S5.SS1.p1.1),[§5](https://arxiv.org/html/2609.16822#S5.p1.1)\.
- Noor and Siddiqui \(2024\)S\. B\. Noor and F\. H\. SiddiquiImproving plan execution flexibility using block\-substitution\.arXiv preprint arXiv:2406\.03091\.Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§6\.1](https://arxiv.org/html/2609.16822#S6.SS1.p1.1),[§6\.1](https://arxiv.org/html/2609.16822#S6.SS1.p3.1),[§6](https://arxiv.org/html/2609.16822#S6.p1.1)\.
- Noor and Siddiqui \(2025\)S\. B\. Noor and F\. H\. SiddiquiImproving execution concurrency in partial\-order plans via block\-substitution\.Autonomous Agents and Multi\-Agent Systems39\(1\),pp\. 1–43\.Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§6\.2](https://arxiv.org/html/2609.16822#S6.SS2.p1.1),[§6\.2](https://arxiv.org/html/2609.16822#S6.SS2.p2.1)\.
- Penberthy and Weld \(1992\)J\. S\. Penberthy and D\. S\. WeldUCPOP: a sound, complete, partial order planner for adl\.InProceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning,KR’92,pp\. 103–114\.External Links:ISBN 1558602623Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Regnier and Fade \(1991\)P\. Regnier and B\. FadeComplete determination of parallel actions and temporal optimization in linear plans of action\.InEuropean Workshop on Planning, volume 522 of Lecture,pp\. 100–111\.Cited by:[§4](https://arxiv.org/html/2609.16822#S4.p1.1)\.
- Siddiqui and Haslum \(2012\)F\. H\. Siddiqui and P\. HaslumBlock\-structured plan deordering\.InAI 2012: Advances in Artificial Intelligence,M\. Thielscher and D\. Zhang \(Eds\.\),Berlin, Heidelberg,pp\. 803–814\.Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p1.1),[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.16822#S2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2609.16822#S2.SS2.p4.1),[§6](https://arxiv.org/html/2609.16822#S6.p1.1)\.
- Siddiqui and Haslum \(2015\)F\. H\. Siddiqui and P\. HaslumContinuing plan quality optimisation\.Journal of Artificial Intelligence Research54,pp\. 369–435\.Cited by:[§6](https://arxiv.org/html/2609.16822#S6.p1.1)\.
- Simmons and Younes \(2011\)R\. Simmons and H\. YounesVHPOP: versatile heuristic partial order planner\.Journal of Artificial Intelligence Research20,pp\.\.External Links:[Document](https://dx.doi.org/10.1613/jair.1136)Cited by:[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Velosoet al\.\(2002\)M\. Veloso, M\. Perez, and J\. CarbonellNonlinear planning with parallel resource allocation\.Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p1.1),[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§5](https://arxiv.org/html/2609.16822#S5.p1.1)\.
- Waterset al\.\(2018\)M\. Waters, B\. Nebel, L\. Padgham, and S\. SardinaPlan relaxation via action debinding and deordering\.Proceedings of the International Conference on Automated Planning and Scheduling28\(1\),pp\. 278–287\.External Links:[Link](https://ojs.aaai.org/index.php/ICAPS/article/view/13901),[Document](https://dx.doi.org/10.1609/icaps.v28i1.13901)Cited by:[§4](https://arxiv.org/html/2609.16822#S4.p1.1)\.
- Waterset al\.\(2020\)M\. Waters, L\. Padgham, and S\. SardinaOptimising partial\-order plans via action reinstantiation\.InProceedings of the Twenty\-Ninth International Joint Conference on Artificial Intelligence,IJCAI’20\.External Links:ISBN 9780999241165Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p3.1),[§4\.2](https://arxiv.org/html/2609.16822#S4.SS2.p1.1),[§4](https://arxiv.org/html/2609.16822#S4.p1.1)\.
- Weld \(1994\)D\. S\. WeldAn introduction to least commitment planning\.AI Magazine15\(4\),pp\. 27\.External Links:[Document](https://dx.doi.org/10.1609/aimag.v15i4.1109)Cited by:[§1](https://arxiv.org/html/2609.16822#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.16822#S2.SS2.p4.1),[§3](https://arxiv.org/html/2609.16822#S3.p1.1)\.
- Winner and Veloso \(2002\)E\. Winner and M\. M\. VelosoAnalyzing plans with conditional effects\.\.InAIPS,pp\. 23–33\.Cited by:[§4](https://arxiv.org/html/2609.16822#S4.p1.1)\.