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

Source: [Improving Execution Concurrency in Partial-Order Plans via Block-Substitution](<https://www.sota2.com/research/paper/68fa73d61e209131cea5e6c4>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-02T05:00:04.464Z

Authors: Sabah Binte Noor, Fazlul Hasan Siddiqui

Published: 2024-06-25T23:36:13.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Automated Planning on IPC barman domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-barman-domain.md>): Automated Planning; IPC barman domain; CFlex: 0.006.

- [Automated Planning on IPC blocks domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-blocks-domain.md>): Automated Planning; IPC blocks domain; Cflex Score: 0.

- [Automated Planning on IPC child-snack domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-child-snack-domain.md>): Automated Planning; IPC child-snack domain; CFlex Score: 0.725.

- [Automated Planning on IPC data-network domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-data-network-domain.md>): Automated Planning; IPC data-network domain; Cflex: 30.1.

- [Automated Planning on IPC depots domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-depots-domain.md>): Automated Planning; IPC depots domain; cflex: 27.9.

- [Automated Planning on IPC elevator domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-elevator-domain.md>): Automated Planning; IPC elevator domain; Cflex: 16.8.

- [Automated Planning on IPC floor-tile domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-floor-tile-domain.md>): Automated Planning; IPC floor-tile domain; Cflex: 0.147.

- [Automated Planning on IPC freecell domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-freecell-domain.md>): Automated Planning; IPC freecell domain; Cflex: 0.077.

- [Automated Planning on IPC genome-edit-distances domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-genome-edit-distances-domain.md>): Automated Planning; IPC genome-edit-distances domain; CFlex: 0.005.

- [Automated Planning on IPC grid domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-grid-domain.md>): Automated Planning; IPC grid domain; Cflex Score: 0.

- [Automated Planning on IPC gripper domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-gripper-domain.md>): Automated Planning; IPC gripper domain; Cflex: 0.017.

- [Automated Planning on IPC hiking domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-hiking-domain.md>): Automated Planning; IPC hiking domain; Cflex: 0.056.

- [Automated Planning on IPC logistics domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-logistics-domain.md>): Automated Planning; IPC logistics domain; Cflex: 58.5.

- [Automated Planning on IPC mystery domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-mystery-domain.md>): Automated Planning; IPC mystery domain; Cflex Score: 12.3.

- [Automated Planning on IPC mystery-prime domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-mystery-prime-domain.md>): Automated Planning; IPC mystery-prime domain; CFlex Score: 17.6.

- [Automated Planning on IPC no-mystery domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-no-mystery-domain.md>): Automated Planning; IPC no-mystery domain; Cflex: 0.042.

- [Automated Planning on IPC parc-printer domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-parc-printer-domain.md>): Automated Planning; IPC parc-printer domain; Cflex: 0.629.

- [Automated Planning on IPC parking domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-parking-domain.md>): Automated Planning; IPC parking domain; Cflex Cost: 0.003.

- [Automated Planning on IPC pathways domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-pathways-domain.md>): Automated Planning; IPC pathways domain; Cflex Score: 54.

- [Automated Planning on IPC peg-solitaire domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-peg-solitaire-domain.md>): Automated Planning; IPC peg-solitaire domain; Cflex: 0.

- [Automated Planning on IPC pipesworld domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-pipesworld-domain.md>): Automated Planning; IPC pipesworld domain; CFlex: 17.4.

- [Automated Planning on IPC rovers domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-rovers-domain.md>): Automated Planning; IPC rovers domain; Cflex Score: 71.6.

- [Automated Planning on IPC satellite domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-satellite-domain.md>): Automated Planning; IPC satellite domain; cflex: 43.6.

- [Automated Planning on IPC scanalyzer-3d domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-scanalyzer-3d-domain.md>): Automated Planning; IPC scanalyzer-3d domain; CFlex: 7.

- [Automated Planning on IPC storage domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-storage-domain.md>): Automated Planning; IPC storage domain; CFlex: 0.12.

- [Automated Planning on IPC tetris domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-tetris-domain.md>): Automated Planning; IPC tetris domain; Cflex: 54.6.

- [Automated Planning on IPC thoughtful domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-thoughtful-domain.md>): Automated Planning; IPC thoughtful domain; Cflex Score: 8.5.

- [Automated Planning on IPC tidybot domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-tidybot-domain.md>): Automated Planning; IPC tidybot domain; Cflex: 0.067.

- [Automated Planning on IPC tpp domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-tpp-domain.md>): Automated Planning; IPC tpp domain; CFlex: 0.417.

- [Automated Planning on IPC transport domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-transport-domain.md>): Automated Planning; IPC transport domain; Cflex Score: 0.457.

- [Automated Planning on IPC trucks domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-trucks-domain.md>): Automated Planning; IPC trucks domain; CFlex: 0.025.

- [Automated Planning on IPC woodworking domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-woodworking-domain.md>): Automated Planning; IPC woodworking domain; Cflex: 0.907.

- [Automated Planning on IPC zenotravel domain](<https://www.sota2.com/research/sota/automated-planning-on-ipc-zenotravel-domain.md>): Automated Planning; IPC zenotravel domain; Cflex: 0.391.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2406.18615>)

[PDF](<https://arxiv.org/pdf/2406.18615.pdf>)
