跳转至

去除顺序，保留层级：HTN计划的反排序技术

文章背景与核心概要

本文探讨了分层任务网络（HTN）规划中的计划后优化（post-plan optimization）问题，特别聚焦于计划反排序（plan deordering）——这一技术在经典规划中得到了广泛研究，但在HTN领域却在很大程度上被忽视了。作者将两种经典的消序技术进行了扩展，使其能够结合分层分解约束。

在IPC 2023偏序HTN基准测试上的评估结果表明，与直接生成偏序计划的规划器 Optiplan 相比，这两种实现方案均成功大幅减少了不必要的排序约束，同时使关键路径长度得到了适度的改善。

摘要

分层任务网络（HTN）规划是一种基于任务分解的强大规划形式化方法。尽管大多数文献都在研究计划生成，但相对而言，对计划后优化的关注较少。特别是计划反排序在经典规划中已被广泛研究，但在HTN环境中的研究仍显不足。计划反排序在保持计划有效性的同时，消除了计划中动作之间不必要的排序约束。在本文中，我们通过扩展经典计划反排序技术以适应分层分解约束，调整并应用了两种成熟的计划反排序技术。我们在 IPC 2023 偏序 HTN 基准测试上评估了我们提出的方法，并将它们与直接生成偏序计划的 HTN 规划器 Optiplan 进行了比较。我们的结果表明，这两种实现在排序约束的数量上都有大幅减少。尽管我们也观察到关键路径长度的缩短，但改进相对没有那么显著。

Hierarchical Task Network (HTN) planning is a powerful planning formalism based on task decomposition. Although most of the literature studied plan generation, comparatively less attention has been paid to post-plan optimization. In particular, plan deordering has been extensively studied in classical planning but remains under-researched in the HTN setting. Plan deordering removes unnecessary ordering constraints between actions in a plan whilst keeping the plan valid. In this paper, we adapt two established plan deordering techniques from classical planning by extending the techniques to account for hierarchical decomposition constraints. We evaluate our proposed approaches on the IPC 2023 Partial-Order HTN benchmarks and we compare them against Optiplan, an HTN planner that generates partially ordered plans directly. Our results show a substantial reduction in number of ordering constraints in both our implementations. Although we also observe a reduction in critical path length, the improvements are less pronounced.

资源与链接