我们研究在可行状态或动作随时间变化的环境下的规划问题。典型例子包括在移动障碍物之间的路径规划（SIPP），以及只有在列车停站时才能上车的情形。由于障碍物或列车的运动，某一位置或动作的可行性会随时间而改变，这导致最优计划及其执行时长取决于实际的开始时间。实际应用中，执行的开始时间往往在规划完成或收到其他代理的指令后才确定，而大多数已有的规划方法要么忽略这种动态性，要么假设已知开始时间，从而在评估可行性时过于简化，难以满足真实需求。
本文放宽了已知开始时间的假设，提出了 任意开始时间规划（any‑start‑time planning）的概念，并给出相应的算法。核心技术是 复合到达时间函数（compound arrival time function，cATF），它以紧凑的形式将最优计划映射为开始时间的函数。我们基于启发式图搜索，改进了传统的代价传播机制，使其在边上传播函数而非标量代价，从而能够在搜索过程中直接构建 cATF。
我们证明，cATF 的大小至多与问题规模线性相关。针对 SIPP 的实验表明，在困难实例上，依赖重新规划的代理往往会失败，而使用 cATF 的任意开始时间算法能够在知道实际开始时间后快速查表得到最优计划。
通过提供高效的时间依赖计划表示与推理，本工作为在动态世界中进行规划奠定了基础。
点评