# Improving Plan Execution Flexibility using Block-Substitution

arXiv: https://arxiv.org/abs/2406.03091 · HTML: https://mlsanity.com/paper/2406.03091/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 48 references that are in the map.
- First posted on arXiv 5 Jun 2024.

## Builds on (most cited first, 2 of 2)

- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [FAPE: a Constraint-based Planner for Generative and Hierarchical Temporal Planning](https://mlsanity.com/paper/2010.13121/) (2020)

## Built on by (most cited first, 2 of 2)

- [Improving Execution Concurrency in Partial-Order Plans via Block-Substitution](https://mlsanity.com/paper/2406.18615/) (2024)
- [Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies](https://mlsanity.com/paper/2609.16822/) (2026)

## Abstract (arXiv)

Partial-order plans in AI planning facilitate execution flexibility due to their less-constrained nature. Maximizing plan flexibility has been studied through the notions of plan deordering, and plan reordering. Plan deordering removes unnecessary action orderings within a plan, while plan reordering modifies them arbitrarily to minimize action orderings. This study, in contrast with traditional plan deordering and reordering strategies, improves a plan's flexibility by substituting its subplans with actions outside the plan for a planning problem. Our methodology builds on block deordering, which eliminates orderings in a POP by encapsulating coherent actions in blocks, yielding a hierarchically structured plan termed a Block Decomposed Partial-Order (BDPO) plan. We consider the action blocks in a BDPO plan as candidate subplans for substitutions, and ensure that each successful substitution produces a plan with strictly greater flexibility. In addition, this paper employs plan reduction strategies to eliminate redundant actions within a BDPO plan. We also evaluate our approach when combined with MaxSAT-based reorderings. Our experimental result demonstrates a significant improvement in plan execution flexibility on the benchmark problems from International Planning Competitions (IPC), maintaining good coverage and execution time.