Metraipolis › archive › dc_64451b1e30fd
Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies — arXiv:2609.16822
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.16822
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T18:32:14.626Z
- SHA-256 of the archived text
e49aaf6f0fe2adacaf51a1d76b578d1d166d3edf4e28382fd55b1ce68ee756fe- Stable URL of this page
https://metraipolis.com/documento/dc_64451b1e30fd
How to cite
Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies — arXiv:2609.16822 — arXiv (en), https://arxiv.org/abs/2609.16822 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_64451b1e30fd (Metraipolis archive dc_64451b1e30fd, sha256 e49aaf6f0fe2adacaf51a1d76b578d1d166d3edf4e28382fd55b1ce68ee756fe)
BibTeX
@misc{dc64451b1e30fd,
title = {Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies — arXiv:2609.16822},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.16822},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_64451b1e30fd; sha256 e49aaf6f0fe2adacaf51a1d76b578d1d166d3edf4e28382fd55b1ce68ee756fe},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16822. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-16 in cs.AI). Categorie arXiv: Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2609.16822 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T18:03:09.480Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).