# Improving Execution Concurrency in Partial-Order Plans via Block-Substitution

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 32 references that are in the map.
- First posted on arXiv 25 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)
- [Improving Plan Execution Flexibility using Block-Substitution](https://mlsanity.com/paper/2406.03091/) (2024)

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

- [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 and several other tasks, such as plan reuse, modification, and decomposition, due to their less constrained nature. A acrfull*pop specifies partial-order over actions, providing the flexibility of executing unordered actions in different sequences. This flexibility can be further extended by enabling parallel execution of actions in the POP to reduce its overall execution time. While extensive studies exist on improving the flexibility of a POP by optimizing its action orderings through plan deordering and reordering, there has been limited focus on the flexibility of executing actions concurrently in a plan. Flexibility of executing actions concurrently, referred to as concurrency, in a POP can be achieved by incorporating action non-concurrency constraints, specifying which actions can not be executed in parallel. This work establishes the necessary and sufficient conditions for non-concurrency constraints between two actions or two subplans with respect to a planning task. We also introduce an algorithm to improve a plan's concurrency by optimizing resource utilization through substitutions of the plan's subplans with respect to the corresponding planning task. Our algorithm employs block deordering that eliminates orderings in a POP by encapsulating coherent actions in blocks, and then exploits blocks as candidate subplans for substitutions. Experiments over the benchmark problems from International Planning Competitions (IPC) exhibit considerable improvement in plan concurrency.