自动化规划中的执行灵活性：去序与重排序策略的比较评估

# 自动规划中的执行灵活性：解序与重排序策略的比较评估
来源：https://arxiv.org/html/2609.16822
Md\. Monjurul Islam电子邮箱：[monjurul\.islam\.cs@gmail\.com](mailto:[email protected])所属单位：孟加拉国加济布尔1707-07，达卡工程技术大学计算机科学与工程系Sabah Binte Noor电子邮箱：[sabah@duet\.ac\.bd](mailto:[email protected])所属单位：孟加拉国加济布尔1707-07，达卡工程技术大学计算机科学与工程系Fazlul Hasan Siddiqui电子邮箱：[siddiqui@duet\.ac\.bd](mailto:[email protected])所属单位：孟加拉国加济布尔1707-07，达卡工程技术大学计算机科学与工程系Gahangir Hossain电子邮箱：[Gahangir\.Hossain@unt\.edu](mailto:[email protected])所属单位：美国德克萨斯州丹顿市，北德克萨斯大学数据科学系

###### 摘要

本研究涵盖了增强计划执行灵活性的基础概念，包括部分序规划、生产者-消费者-威胁形式化体系，以及一系列解序与重排序策略。通过移除不必要顺序约束将顺序计划转化为部分序计划，是提高执行灵活性的一种实用方法，已有多种方法被提出用于此任务。本研究从顺序约束、动作处理、参数处理、计划结构、并发性和复杂性等多个维度分析了这些方法的能力，并在同一基准测试集上对它们进行了评估。核心发现是，基于块解序的方法通过块级分组和子计划替换重构因果依赖关系，尽管基于最大可满足性问题的方法在理论上保证了最小重排序，但前者性能显著优于后者。其原因在于结构层面：最小重排序优化的是计划中已存在的因果结构，而基于块解序的方法则改变了该结构，暴露了那些原本看似必要的顺序约束。另一个实际区别是：基于块解序的方法是随时算法，总能返回有效结果；而基于最大可满足性问题的方法在相当大比例的计划上完全失败，且失败时无法提供部分解决方案。块替换通过形式化非并发约束进一步扩展了并行执行，但其影响仅限于存在基于资源交互的领域。在效率方面，基于块解序的方法在单位计算时间内获得了最高的灵活性增益，而基于最大可满足性问题的编码则带来了巨大的计算开销。

###### 关键词

自动规划，灵活性，并发性，部分序规划

## 1引言

智能体适应不可预见情况的能力是其在动态环境中有效运作的基本要求。在自动规划领域，已发展出多种方法来增强智能体的灵活性，从为智能体提供备选计划选择（Graham等人，2003 (https://arxiv.org/html/2609.16822#bib.bib8)）到通过泛化技术扩展现有计划的适用性（Anderson和Farley，1988 (https://arxiv.org/html/2609.16822#bib.bib7)）等。计划泛化方法通过推迟特定动作排序直到该排序不可避免，来生成部分序计划。这种最小化动作排序决策的策略已通过多种概念进行了探索，包括计划解序（Nguyen和Kambhampati，2001 (https://arxiv.org/html/2609.16822#bib.bib18)；Veloso等人，2002 (https://arxiv.org/html/2609.16822#bib.bib16)；Siddiqui和Haslum，2012 (https://arxiv.org/html/2609.16822#bib.bib4)）和重排序（Muise等人，2016 (https://arxiv.org/html/2609.16822#bib.bib10)）方法。解序移除了计划中非必要的动作顺序，而重排序则允许对动作序列进行任意更改。

生成部分序计划的一种方式是通过部分序因果链接规划（Weld，1994 (https://arxiv.org/html/2609.16822#bib.bib35)），该规划增量式地构建计划，同时为每个动作前提条件维持因果支持。一种实用的替代方法是从快速启发式规划器中获取顺序计划，并移除那些非必要的顺序约束。

已有多种方法被开发用于这一后处理任务。基于解释的顺序泛化（Kambhampati和Kedar，1994 (https://arxiv.org/html/2609.16822#bib.bib20)；Veloso等人，2002 (https://arxiv.org/html/2609.16822#bib.bib16)）为每个顺序约束添加因果理由注解，并移除那些没有理由的约束。块解序（Siddiqui和Haslum，2012 (https://arxiv.org/html/2609.16822#bib.bib4)）将连贯的操作符分组为块，并通过将每个块视为一个单元来消除额外的顺序约束。最小重排序（Muise等人，2016 (https://arxiv.org/html/2609.16822#bib.bib10)）将解序问题编码为部分加权最大可满足性问题，以找到可证明的最小重排序并移除冗余动作；最小重新例化重排序（Waters等人，2020 (https://arxiv.org/html/2609.16822#bib.bib9)）扩展了此方法，在同名操作符内进行参数重新绑定。更近的方法如FIBS（Noor和Siddiqui，2024 (https://arxiv.org/html/2609.16822#bib.bib1)）使用块替换用备选方案替换子计划，而CIBS（Noor和Siddiqui，2025 (https://arxiv.org/html/2609.16822#bib.bib3)）扩展了FIBS，以建模和最小化并行执行中的非并发约束。

我们从多个维度（顺序约束、动作处理、参数处理、计划结构、并发性和复杂性）分析了不同算法的能力，并在来自46个国际规划竞赛领域的3345个计划上进行了评估。分析产生了一个从上述描述中并不明显的结果。最小重排序和最小重新例化重排序旨在找到最小重排序。然而，块解序和FIBS在相同的基准测试上产生了显著更高的灵活性值，并且相对于所有其他方法具有大且统计显著的效应量。原因是，最小重排序优化的是原始计划中已存在的因果结构。块解序的工作方式不同：它通过将操作符分组为块来重组哪些操作符共享因果依赖关系，从而暴露了那些原本看似必要的顺序约束。块替换更进一步，用携带完全不同因果蕴含的备选方案替换子计划。这两类方法与其说是竞争，不如说是在解决不同的问题；重构因果结构被证明是提高灵活性的更有效途径。

## 2预备知识

本节概述了理解这些方法所需的基础概念。首先定义有限域表示中的规划任务和计划，然后介绍部分序规划、因果依赖关系和威胁的概念。最后，阐述计划解序和重排序的关键概念。

### 2.1规划任务

经典规划问题通常使用有限域表示进行描述，该表示通过状态变量及其关联的值域来描述规划任务。以下定义为后续分析建立了数学基础。

###### 定义1\.

在有限域表示中，一个规划任务记为Π=⟨X,O,si,sg⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle，其中：

- •X\\mathcal\{X\}表示一个有限的非空状态变量集。每个x∈Xx\\in\\mathcal\{X\}关联一个具有有限元素个数的域Dx\\mathcal\{D\}\_\{x\}。二元组⟨x,d⟩\\langle x,d\\rangle（其中x∈Xx\\in\\mathcal\{X\}且d∈Dxd\\in\\mathcal\{D\}\_\{x\}）称为一个事实。状态的概念对应于定义在X\\mathcal\{X\}上的函数s，使得对所有x∈Xx\\in\\mathcal\{X\}，s⁡\(x\)∈Dxs(x)∈\\mathcal\{D\}\_\{x\}。函数涉及的变量集合记为vars⁡\(s\)\\mathit\{vars\}(s)。一个定义在X\\mathcal\{X\}的真子集上的函数s^\{\\hat\{s\}\}类似于状态s，但表示一个部分状态，其中vars⁡\(s^\)⊂X\\mathit\{vars\}(\\hat\{s\})\\subset\\mathcal\{X\}。
- •O\\mathcal\{O\}表示一个有限的非空操作符集。每个操作符o∈Oo\\in\\mathcal\{O\}关联两个部分状态：前提条件preo\\mathit\{pre\_\{o\}\}和效果effo\\mathit\{eff\_\{o\}\}，以及一个非负关联代价costo∈R0+\\mathit\{cost\_\{o\}}\\in\\mathbb\{R\}^{\+}\_\{0\}。一个操作符o在状态s下可应用，当且仅当preo⊆s\\mathit\{pre\_\{o\}}\\subseteq s。在状态s下应用操作符o会将其转换为状态s′=apply\(s,o\)s'=apply(s,o)，如公式(1) (https://arxiv.org/html/2609.16822#S2.E1)所示。s′\(x\)=apply\(s,o\)=\{effo\(x\)若x∈vars⁡\(effo\)s⁡\(x\)其他情况s'(x)=apply(s,o)=\\begin\{cases\}\\mathit\{eff\_\{o\}}(x)&\\text\{若 \}x\\in\\mathit\{vars\(eff\_\{o\})\}\\\\ s(x)&\\text\{其他情况\}\\end\{cases\}(1)
- •sis\_\{i\}对应初始状态，
- •sgs\_\{g\}指定了目标条件的部分状态。

###### 定义2\.

令π=⟨o1,o2,...,ok,...,on⟩\\pi=\\langle o\_\{1\},o\_\{2\},\\dots,o\_\{k\},\\dots,o\_\{n\}\\rangle是规划任务Π=⟨X,O,si,sg⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle的一个计划，即操作符序列。计划π是有效的，当且仅当preo1⊆sipre\_\{o\_\{1\}}\\subseteq s\_\{i\}，且对每个k∈\{1,2,...,n−1\}k∈\{1,2,\\dots,n-1\}，preok+1⊆skpre\_\{o\_\{k+1\}}\\subseteq s\_\{k\}，其中sk=apply⁡\(sk−1,ok\)s\_\{k\}=\\mathit\{apply\}(s\_\{k-1},o\_\{k\})，并且sg⊆sns\_\{g\}\\subseteq s\_\{n\}。

###### 定义3\.

prod、cons和del分别表示一个操作符o产生、消耗和删除的事实。事实⟨x,d⟩

- •⟨x,d⟩∈prodo\\langle x,d\\rangle\\in prod\_\{o\}当且仅当⟨x,d⟩∈effo\\langle x,d\\rangle\\in\\mathit\{eff\_\{o\}}\。
- •⟨x,d⟩∈conso\\langle x,d\\rangle\\in cons\_\{o\}当且仅当⟨x,d⟩∈preo\\langle x,d\\rangle\\in\\mathit\{pre\_\{o\}}\。
- •⟨x,d⟩∈delo\\langle x,d\\rangle\\in del\_\{o\}当且仅当1. i\.要么x∉vars\(conso\)x\\notin vars(\\mathit\{cons\_\{o\}})，要么conso\(x\)=d\\mathit\{cons\_\{o\}}(x)=d，并且2. ii\.effo\(x\)=d'\\mathit\{eff\_\{o\}}(x)=d'使得d'∈\(Dx∖\{d\}\)\\ d'\\in(\\mathcal\{D\}\_\{x\}\\setminus\\{d\\})\。

### 2.2部分序规划

在部分序计划框架中，操作符可以在任何可能的序列中执行，同时对其施加部分顺序约束。假设每个操作符都是可唯一识别的，即使一个操作符可能在部分序计划中出现多次。

###### 定义4\.

部分序计划表示为πpop=⟨O,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\rangle，关于规划任务Π=⟨X,O,si,sg⟩\\Pi=\\langle\\mathcal\{X\},\\mathcal\{O\},s\_\{i\},s\_\{g\}\\rangle，其中：

- •O\\mathcal\{O\}表示操作符集，
- •≺\\prec表示O\\mathcal\{O\}上的顺序约束。记法oa≺ob\\mathbf\{o\_\{a\}\\prec o\_\{b\}}表示两个操作符oa,ob∈Oo\_\{a},o\_\{b\}\\in\\mathcal\{O\}之间的顺序约束，指定了操作符oao\_\{a\}需要在操作符obo\_\{b\}执行之前的某个时间执行。≺\\prec具有传递性，这意味着如果oa≺obo\_\{a\}\\prec o\_\{b\}且ob≺oco\_\{b\}\\prec o\_\{c\}，则oa≺oco\_\{a\}\\prec o\_\{c\}。基本顺序约束是指那些不能通过集合中其他约束传递推导出的约束。

计划灵活性使用度量flex\\mathit\{flex\}（Siddiqui和Haslum，2012 (https://arxiv.org/html/2609.16822#bib.bib4)）进行量化，它是指没有基本或传递顺序约束的操作符对占所有操作符对的比例。更高的flex\\mathit\{flex\}值表示更大的执行灵活性，尽管灵活性与实际适应能力之间的关系取决于特定领域因素。

###### 定义5\.

令πpop=⟨O,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\rangle为一个部分序计划。计划πpop的flex值为flex⁡\(πpop\)\\mathit\{flex\}(\\pi\_\{pop\})，计算如公式(2) (https://arxiv.org/html/2609.16822#S2.E2)所示。

flex⁡\(πpop\)=1−\|≺\|Σi=1\|O\|−1i\\mathit\{flex\}(\\pi\_\{pop\})=1-\\frac{\|\\prec\|}{\\Sigma\_\{i=1\}^{\|\mathcal\{O\}|-1}i}(2)
其中Σi=1\|O\|−1i\\Sigma\_\{i=1\}^{\|\mathcal\{O\}|-1}i是使用\|O\|\|\\mathcal\{O\}|个项目可能构建的最大配对数。

生产者-消费者-威胁框架通过识别操作符在事实产生、消费和删除方面的关系来建立顺序结构。该形式化引入了将操作符前提条件映射到效果提供者的因果链接。

###### 定义6\.

op→⟨x,d⟩oco\_\{p\}\\xrightarrow{\langle x,d\rangle}o\_\{c\}之间的因果链接指定了op≺oco\_\{p\}\\prec o\_\{c\}，并且操作符opo\_\{p\}为操作符oco\_\{c\}产生⟨x,d⟩\\langle x,d\\rangle，其中⟨x,d⟩∈\(prodop∩consoc\)\\langle x,d\\rangle\\in(prod\_\{o\_\{p\}}\\cap cons\_\{o\_\{c\}})\。威胁定义为因果链接op→⟨x,d⟩oco\_\{p\}\\xrightarrow{\langle x,d\rangle}o\_\{c\}与一个操作符odo\_\{d\}的效果之间的冲突，其中odo\_\{d\}删除⟨x,d⟩\\langle x,d\\rangle且可以被排序在opo\_\{p\}和oco\_\{c\}之间。

通过添加顺序od≺opo\_\{d\}\\prec o\_\{p\}（称为提升），或添加顺序oc≺odo\_\{c\}\\prec o\_\{d\}（称为降级），可以解决因果链接op→⟨x,d⟩oco\_\{p\}\\xrightarrow{\langle x,d\rangle}o\_\{c\}与操作符odo\_\{d\}之间的威胁。一个部分序计划是有效的，如果因果关系在没有任何威胁的情况下支持每个操作符前提条件（Weld，1994 (https://arxiv.org/html/2609.16822#bib.bib35)）。Siddiqui和Haslum (2012) (https://arxiv.org/html/2609.16822#bib.bib4)引入了三个标签：PC、CT和TP，以概述部分序计划的顺序约束。

###### 定义7\.

令πpop=⟨O,≺⟩\\pi\_\{pop\}=\\langle\\mathcal\{O\},\\prec\\rangle为一个部分序计划，Re\(oa≺ob\)Re(o\_\{a\}\\prec o\_\{b\})表示顺序约束oa≺obo\_\{a\}\\prec o\_\{b\}的顺序理由。一个顺序限制oa≺obo\_\{a\}\\prec o\_\{b\}可能由三个原因形成：

- •PC\(⟨x,d⟩\)∈Re\(oa≺ob\)PC(\\langle x,d\\rangle)\\in Re(o\_\{a\}\\prec o\_\{b\})是事实⟨x,d⟩\\langle x,d\\rangle的生产者-消费者关系，其中oao\_\{a\}产生⟨x,d⟩\\langle x,d\\rangle，obo\_\{b\}消耗⟨x,d⟩\\langle x,d\\rangle。事实⟨x,d⟩\\langle x,d\\rangle可能由多个操作符产生和消耗。通过因果链接将一个操作符oao\_\{a\}分配给obo\_\{b\}以获取⟨x,d⟩\\langle x,d\\rangle。
- •CT\(⟨x,d⟩\)∈Re\(oa≺ob\)CT(\\langle x,d\\rangle)\\in Re(o\_\{a\}\\prec o\_\{b\})是事实⟨x,d⟩\\langle x,d\\rangle的消费者-威胁关系，其中操作符oao\_\{a\}消耗⟨x,d⟩\\langle x,d\\rangle，obo\_\{b\}删除⟨x,d⟩\\langle x,d\\rangle。
- •TP\(⟨x,d⟩\)∈Re\(oa≺ob\)TP(\\langle x,d\\rangle)\\in Re(o\_\{a\}\\prec o\_\{b\})是事实⟨x,d⟩\\langle x,d\\rangle的威胁-生产者关系，其中操作符oao\_\{a\}删除事实⟨x,d⟩\\langle x,d\\rangle，且存在一个或多个因果链接ob→⟨x,d⟩oco\_\{b\}\\xrightarrow{\langle x,d\rangle}o\_\{c\}，其中oc∈Oo\_\{c\}\\in\\mathcal\{O\}。

部分序计划的因果链接由标签PC标记，降级和提升顺序约束分别标记为CT和TP。