时间规划与调度
时间规划与调度将规划扩展到处理需要时间、可以并发运行并消耗有限资源的操作，从而生成不仅指定做什么，还指定何时做的计划。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
时间规划生成一个计划，其中动作具有持续时间并可能重叠，受时间与资源约束；调度为一系列活动分配开始时间（和资源），以满足所有约束，例如排序、截止日期和容量。
Scope
本主题涵盖了具有明确时间和资源的规划与调度：持续性动作、并发性与时间约束、时间约束网络（如简单时间问题）的表示与求解以及艾伦区间代数，以及将规划与资源受限活动的调度相结合。它探讨了如何在行动选择的同时推理时间和资源的可行性。纯粹无资源的经典规划在相关主题中讨论。
Core questions
- 持续性动作及其开始和结束条件如何表示？
- 事件之间的时间约束如何建模和检查一致性？
- 有限资源如何在并发活动之间分配？
- 规划（决定采取哪些行动）和调度（决定何时行动）如何结合或分离？
Key concepts
- 持续性动作
- 并发与重叠
- 时间约束
- 简单时间问题
- 艾伦区间代数
- 资源约束
- 调度
- 截止日期和完工时间
Key theories
- 时间约束网络
- 时间点之间的定量时间约束可以表示为网络，其一致性和最紧密界限可以针对简单时间问题高效计算，为许多规划器和调度器提供了时间推理的核心。
- 定性时间区间代数
- 艾伦区间代数捕捉了时间区间之间可能的定性关系（之前、期间、重叠等），并支持在不确定确切时间时进行时间知识推理。
- 规划与调度的整合
- 现实问题需要同时选择行动并为其分配时间和资源；自动化规划理论将持续性动作、并发性和资源约束视为扩展，将行动选择与基于约束的调度相结合。
Clinical relevance
时间规划与调度在航天器和漫游车操作、制造和项目调度、运输和人员调度以及任何需要协调定时、并发、资源受限活动的场景中都至关重要；此类系统已为真实的太空任务规划了操作。
History
定性时间推理由艾伦区间代数（1983）形式化，定量时间约束网络由Dechter、Meiri和Pearl（1991）形式化。这些基础，加上2000年代初期添加到PDDL中的持续性动作模型，使得时间规划器能够应用于自主航天器控制等领域。
Key figures
- James F. Allen
- Rina Dechter
- Judea Pearl
- Itay Meiri
- Nicola Muscettola
Related topics
Seminal works
- dechter1991
- allen1983
Frequently asked questions
- 规划和调度有什么区别？
- 规划决定采取哪些行动以实现目标，而调度则根据排序和容量约束，决定这些行动何时发生以及使用哪些资源。许多实际问题需要两者兼顾，时间规划将行动选择与时间及资源推理相结合。
- 什么是简单时间问题？
- 简单时间问题是一种时间约束网络，其中每个约束都通过一个区间来限制两个时间点之间的差异。其一致性和最紧密的隐含界限可以高效计算，这使其成为规划器和调度器中时间推理的实用核心。