Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

本文提出了一种将带有持续动作的时序数值规划问题编译为 PDDL+ 的实用多项式方法，该方法在仅假设动作不自我重叠的前提下完整保留了语义，并能在保持规划长度常数倍增长的同时有效解决高难度的时序数值问题。

要点

这篇论文讲述了一个关于**“如何把复杂的计时任务，翻译成机器更容易理解的规则”**的故事。

想象一下，你是一位总导演，正在指挥一场宏大的交响乐演出（这就是“规划”）。

1. 故事背景：两种不同的乐谱语言

在这个故事里，有两种描述演出的“乐谱语言”：

• 语言 A（PDDL 2.1）：传统的“动作乐谱”
  这种语言很直观。它告诉乐手：“在 10 点钟开始演奏小提琴，持续 5 分钟，期间必须保持音准，10 点 05 分结束。”

  • 特点：动作有“持续时间”（Durative Actions）。比如“切菜”这个动作，从开始切到切完，中间有一段时间。
  • 问题：虽然人类导演觉得这很自然，但很多聪明的“机器乐手”（现有的规划算法）不太擅长处理这种“持续中”的状态，尤其是当涉及到复杂的数字计算（比如切菜时刀速的变化、水量的减少）时，它们容易晕头转向。

• 语言 B（PDDL+）：现代的“过程与事件乐谱”
  这种语言更抽象，它把时间看作流动的河流。它不直接说“切菜持续 5 分钟”，而是说：

  • 事件（Event）：当时间到达 10 点，瞬间触发“开始切菜”的信号。
  • 过程（Process）：只要“开始切菜”的信号亮着，**水流（时间）**就会自动推动“切菜进度条”一直往前走（就像水龙头一直在滴水）。
  • 事件（Event）：当进度条走到 5 分钟，瞬间触发“结束切菜”的信号。
  • 特点：它把“持续的动作”拆解成了“开始瞬间”、“中间自动流动”和“结束瞬间”。

2. 核心难题：如何翻译？

以前，大家都知道语言 A 可以翻译成语言 B，但就像有一本只有理论没有实操手册的字典。没人能写出一个既准确、又高效、还能处理复杂数字问题的“翻译器”。

这篇论文的作者（Andrea, Enrico 和 Alessandro）就是来编写这本实操手册的。他们设计了一个**“万能翻译器”**，能把语言 A（带持续时间的动作）完美地转换成语言 B（过程 + 事件）。

3. 翻译器的三大“魔法道具”

为了让翻译既准确又不乱套，作者用了三个巧妙的“魔法道具”：

道具一：时间计数器（Clocks）

• 比喻：想象每个动作都有一个专属的秒表。
• 作用：当“开始切菜”发生时，秒表归零并开始走动。翻译器会一直盯着这个秒表，确保切菜动作不会太短（没切完就停了）也不会太长（切过头了）。

道具二：互斥锁（Locks）—— 防止“撞车”

• 比喻：想象厨房只有一个唯一的切菜板。
• 问题：如果两个乐手（动作）同时想切同一个菜（修改同一个变量），或者一个在切菜，另一个在数切好的菜（读取变量），就会发生混乱（冲突）。
• 作用：翻译器给每个变量都装了一把**“智能锁”**。
  • 当你想读数据时，必须确保没人正在写数据（锁是开着的）。
  • 当你想写数据时，必须确保没人正在读或写数据。
  • 一旦有人开始操作，锁就“咔嚓”一声锁上，别人必须排队等。这保证了在同一瞬间，不会有两个动作在捣乱。

道具三：紧急刹车（The "OK" Switch）

• 比喻：这是一个全局的“安全开关”。
• 作用：如果某个动作在持续过程中违反了规则（比如切菜时突然把刀扔了，或者时间还没到就强行结束），这个开关就会瞬间变成“红灯”（False）。
• 结果：一旦红灯亮起，整个演出计划就被判定为“失败”，机器会立刻放弃这个方案，去寻找新的路径。这确保了只有完全合规的计划才能被保留。

4. 实验结果：翻译器好用吗？

作者把这套翻译器装进了一个名为 ENHSP 的机器里，并拿它和市面上最顶尖的、专门懂“持续时间”的机器（如 ARIES, OPTIC 等）进行比赛。

• 比赛场地：一些非常烧脑的数学题，比如“给植物浇水”（需要控制水流和时间）、“帆船救援”（需要在特定时间内到达特定位置）。
• 结果：
  • 在纯时间问题上，老牌机器依然很快。
  • 但在**“时间 + 复杂数字”的混合难题上，用了这个翻译器的机器（ENHSP）竟然跑得更快、解得更多**！
  • 惊喜：这证明了，把复杂问题“翻译”成另一种形式，反而能让机器发挥得更好。就像把一道复杂的数学题翻译成图形，有时候一眼就能看出答案。

5. 总结：这篇论文意味着什么？

简单来说，这篇论文做了一件**“化繁为简”**的实事：

1. 填补空白：它把以前只存在于理论中的“翻译方法”，变成了真正能用的代码和逻辑。
2. 打破壁垒：它让那些擅长处理“过程”和“事件”的强力算法，也能解决那些需要“持续动作”的难题。
3. 提升效率：实验证明，这种“曲线救国”的翻译方法，在处理复杂的现实世界问题（如资源调度、物流、救援）时，往往比直接硬啃更有效。

一句话总结：
作者发明了一个聪明的“翻译官”，它能把人类觉得自然的“持续动作”指令，自动转换成机器最擅长的“瞬间事件 + 自动流程”指令，并且加上了严格的“互斥锁”防止打架，最终让机器在解决复杂的计时数学题时，变得更强、更快。

技术摘要

这是一份关于论文《Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version》（将时间数值规划编译为离散 PDDL+：扩展版）的详细技术总结。

1. 研究背景与问题定义

背景：
自动规划（Automated Planning）旨在寻找从初始状态到达目标状态的动作序列。时间规划（Temporal Planning）是经典规划的扩展，其中动作具有持续时间（durative actions），需要在特定的时间点上执行，并满足开始、结束及持续过程中的条件。PDDL 2.1 是描述此类问题的标准语言。PDDL+ 则是另一种扩展语言，通过过程（processes）、**事件（events）和瞬时动作（instantaneous actions）**的组合来建模随时间演化的系统（如混合系统）。

核心问题：
尽管早在 2006 年 Fox 和 Long 就指出 PDDL 2.1 中的持续动作理论上可以编译为 PDDL+，但长期以来缺乏实用的、形式化严谨的编译方案。现有的时间规划求解器在处理复杂的**时间 - 数值（temporal numeric）**问题时往往面临挑战。

研究目标：
本文提出了一种从 PDDL 2.1 Level 3（包含持续动作、数值变量、条件等）到 PDDL+ 的实用编译方法。该方法旨在完全捕捉时间规划的语义，并证明其在解决硬性的时间数值规划问题上的有效性。

---

2. 方法论：从 PDDL 2.1 到 PDDL+ 的编译

作者将 PDDL 2.1 中的持续动作（Durative Actions）映射为 PDDL+ 中的动作、过程和事件的组合。编译的核心挑战在于处理非自重叠（non-self-overlapping）约束、互斥条件以及持续过程中的不变量（invariants）。

2.1 核心映射机制

对于每一个 PDDL 2.1 中的持续动作 $a$，编译后的 PDDL+ 模型包含以下组件：

1. 瞬时动作（Snap Actions）：
   • 开始动作 ($\bar{a}_{\vdash}$)：对应持续动作的开始。设置标志位 $r_a$ 为真，重置计时器 $c_a$，并增加未结束动作计数器 $oc$。
   • 结束动作 ($\bar{a}_{\dashv}$)：对应可变持续时间动作的结束。检查持续时间是否在 $[l_a, u_a]$ 范围内，重置 $r_a$，减少 $oc$。
   • 固定持续时间动作：由事件自动触发结束，而非显式动作。
2. 过程（Processes）：
   • 计时过程 ($\bar{p}_a$)：当 $r_a$ 为真时，以速率 1 增加计时器 $c_a$，用于测量动作持续时间。
   • 全局时间过程 ($\bar{p}_E$)：持续增加全局计数器 $gc$，用于区分不同的时间步（在超密集时间模型中）。
3. 事件（Events）：
   • 固定结束事件 ($\bar{e}^{\dashv}_a$)：当 $c_a = l_a$ 时触发，结束固定持续时间的动作。
   • 不变量检查事件 ($\bar{e}^{\leftrightarrow}_a$)：如果动作运行期间不变量 $\gamma_a$ 被违反，将全局标志 $ok$ 设为假（导致规划失败）。
   • 过期检查事件 ($\bar{e}^{expire}$)：如果可变持续时间动作超过上限 $u_a$ 仍未结束，将 $ok$ 设为假。
   • 锁重置事件 ($\bar{e}_E$)：在每个时间步开始时触发，重置所有互斥锁变量。

2.2 关键创新：互斥锁机制（Lock Mechanism）

为了在 PDDL+ 中模拟 PDDL 2.1 的“非自重叠”和“无冲突”语义（即同一时刻不能对同一变量进行读写冲突），作者设计了一套锁机制：

• 锁变量：为每个变量 $f$ 引入三个布尔锁：$rl_f$（读锁）、$al_f$（赋值锁）、$il_f$（增量锁）。
• 工作原理：
  • 在时间步开始时，通过事件 $\bar{e}_E$ 将所有锁重置为真。
  • 当动作“读取”变量 $f$ 时，要求 $rl_f$ 为真，并在执行后将 $rl_f$ 设为假。
  • 当动作“赋值”或“增量”变量 $f$ 时，要求相应的锁为真，并在执行后设为假。
  • 互斥性：如果两个动作在同一超密集时间步（superdense time step）内发生，由于锁在第一个动作执行后即被设为假，第二个动作若尝试访问同一变量将因锁失效而无法执行。
  • 时间分离：全局计数器 $gc$ 由过程持续增加，并在每个时间步开始时被事件 $\bar{e}_E$ 重置。这确保了不同时间步的动作不会相互干扰，同时允许同一时间步内的动作按顺序执行（模拟超密集时间）。

2.3 离散化假设

该编译方案假设 PDDL+ 采用离散时间语义（Discretization time quantum $\delta$）。这避免了连续时间模型中可能出现的芝诺行为（Zeno behavior，即在有限时间内发生无限次事件），使得编译在计算上是可行的。

---

3. 主要贡献

1. 首个形式化严谨的编译方案：提供了从 PDDL 2.1 Level 3 到 PDDL+ 的完整形式化定义，填补了文献中缺乏实用编译方案的空白。
2. 语义完备性证明：
   • 可靠性（Soundness）：证明了如果编译后的 PDDL+ 问题有解，则原始 PDDL 2.1 问题也有解。
   • 完备性（Completeness）：证明了对于任何有效的 PDDL 2.1 规划，只要离散化步长 $\delta$ 足够小，总能找到对应的 PDDL+ 规划。
3. 多项式复杂度：编译后的问题规模相对于原问题是多项式增长的，且规划长度最多增加常数倍（通常翻倍）。
4. 扩展性：该框架易于扩展以支持延迟效应（delayed effects）和带时初始文字（timed initial literals）。

---

4. 实验评估

实验设置：

• 领域：选取了 5 个时间数值规划领域（MatchCellar, MaJSP, T-Plant-Watering, T-Sailing 等），涵盖经典 IPC 领域及新提出的具有时间 - 数值耦合挑战的领域。
• 求解器对比：
  • 编译后求解：使用 ENHSP 求解器（基于 PDDL+），配置了两种启发式策略（ENHSP-LG 和 ENHSP-WA）。
  • 原生求解：对比了多种先进的原生时间规划器（ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty）。
• 硬件环境：AMD EPYC 7413，超时 1800 秒，内存 20GB。

实验结果：

1. 覆盖率（Coverage）：ENHSP-WA（编译方案）在总实例数（80 个）中解决了 67 个，表现最佳。特别是在包含复杂数值和时间约束的领域（如 MaJSP, T-Plant-Watering）中，ENHSP-WA 显著优于原生时间规划器。
2. 性能分析：
   • 在纯时间领域，原生规划器通常更快。
   • 在时间数值领域，编译方案表现出更强的竞争力，甚至在某些领域（如 MaJSP）完全优于原生求解器。
   • 运行时间散点图显示，ARIES 和 ENHSP-WA 在不同问题上各有优势，体现了互补性。
3. 结论：实验表明，将时间规划编译为 PDDL+ 并利用强大的 PDDL+ 求解器（如 ENHSP）是解决复杂时间数值规划问题的有效途径。

---

5. 意义与未来工作

意义：

• 理论价值：首次严格证明了 PDDL+ 可以完全表达 PDDL 2.1 的持续动作语义，并解决了“非自重叠”和“不变量”等细微语义的编码问题。
• 实践价值：实验证明，利用 PDDL+ 求解器（通常针对过程控制和混合系统优化）来解决时间规划问题，往往能获得比专用时间规划器更好的性能，特别是在涉及数值变量的复杂场景中。这为时间规划领域提供了一种新的、高效的解决思路。

未来工作：

• 将编译方案扩展到 PDDL 2.1 Level 4，以支持连续变化（continuous change）。
• 研究针对连续时间语义的 PDDL+ 的替代编译方案，以消除离散化带来的潜在误差。

总结：
这篇论文不仅提供了一个实用的工具，将时间规划问题转化为 PDDL+ 问题，还通过理论证明和广泛的实验验证，确立了这种编译方法在处理高难度时间数值规划问题上的优越性，为自动化规划领域开辟了一条新的技术路径。