自动化规划

自动化规划是人工智能的一个分支，它关注在给定可用行动形式化描述的情况下，计算将世界的初始状态转化为所需目标状态的行动序列。

Definition

自动化规划是计算一个计划——一个有序（或部分有序）的行动集合——它在给定每个行动如何改变世界状态的模型的情况下，能够从初始状态可靠地实现目标。

Scope

该领域涵盖了规划问题的表示（状态、具有前置条件和效果的行动、目标）以及解决这些问题的算法：确定性、完全可观察领域中的经典规划、规划图和启发式搜索方法、分层任务网络规划，以及对时间、资源和调度的扩展。它处理STRIPS和PDDL等标准形式主义以及规划的复杂性。概率不确定性下的规划与不确定性推理相关联，而从数据中学习行动模型或策略则属于机器学习子领域。

Sub-topics

• 经典规划与STRIPS
• 分层任务网络规划
• 规划图与启发式算法
• 时间规划与调度

Core questions

• 如何紧凑地表示行动、状态和目标，以描述大型领域？
• 尽管状态空间呈指数级增长，如何有效地搜索规划问题？
• 如何从领域描述中自动推导出可接受且信息丰富的启发式方法？
• 计划如何分层构建，以及如何整合时间和资源约束？

Key concepts

• 状态、行动、目标
• 前置条件和效果
• STRIPS和PDDL
• 前向和后向状态空间搜索
• 规划图
• 领域无关启发式方法
• 分层任务网络
• 时间规划和调度

Key theories

STRIPS行动表示

STRIPS形式主义通过前置条件以及对一组命题的添加/删除效果来描述行动，提供了一种紧凑、分解的表示，使规划成为对符号状态的搜索，而不是对显式世界状态的枚举。

用于规划的领域无关启发式搜索

现代规划器将规划视为启发式搜索，并从问题描述中自动推导启发式方法，例如通过忽略删除效果或利用因果结构，从而实现强大的通用性能。

规划作为问题类别的层次结构

规划涵盖了从经典确定性规划到分层、时间性和资源受限变体的范围，每种变体都具有其特有的表示和复杂性，并在自动化规划的标准理论中进行组织。

Clinical relevance

自动化规划应用于机器人和自主系统、航天器和任务操作、物流和供应链、制造业以及游戏和叙事生成；源自这些技术的规划器已经控制了真实的自主航天器并协调了复杂的工作流程。

History

自动化规划始于1971年左右SRI为Shakey机器人开发的STRIPS，它将规划构建为对行动描述的定理证明。该领域通过偏序规划、Graphplan突破（1995年）以及从1990年代后期开始的快速领域无关启发式搜索规划器和PDDL标准的兴起而发展，并通过国际规划竞赛进行跟踪。

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Malik Ghallab
• Dana Nau
• Paolo Traverso
• Malte Helmert

Seminal works

• fikes1971
• ghallab2004
• helmert2006

Frequently asked questions

自动化规划与通用搜索有何不同？

自动化规划是一种搜索形式，但它基于行动的声明性、分解描述（前置条件和效果）而非不透明的后继函数。这种结构使规划器能够自动推导启发式方法并推理哪些行动是相关的，这是通用搜索无法做到的。

什么是PDDL？

PDDL，即规划领域定义语言，是一种描述规划领域和问题的标准语言——包括对象、谓词、行动、初始状态和目标。它允许在共同的基准上比较领域无关的规划器，例如在国际规划竞赛中。