经典规划与STRIPS

经典规划通过前置条件和效果的STRIPS式分解表示来解决在确定性、完全可观测、静态环境中寻找一系列动作以达到目标的问题。

Definition

经典规划旨在寻找一系列确定性动作，将完全已知的初始状态转换为满足目标的状态，其中每个动作都由其适用所需满足的条件及其所产生的变化来描述。

Scope

本主题涵盖经典规划模型及其假设（确定性动作、完全可观测性、单一智能体、原子时间）、状态和动作的STRIPS和ADL/PDDL表示、前向（进展）和后向（回溯）状态空间搜索以及偏序规划的基本求解方法，以及命题规划的计算复杂性。启发式引导和规划图在相关主题中讨论，非确定性或概率变体不在本主题范围内。

Core questions

• 定义经典规划模型的假设是什么？它们何时适用？
• STRIPS表示如何将状态分解为命题，将动作分解为前置条件和添加/删除效果？
• 进展搜索和回溯搜索作为规划策略有何不同？
• 经典规划的计算难度一般如何？

Key concepts

• 确定性、完全可观测模型
• STRIPS前置条件和效果
• 添加和删除列表
• PDDL和ADL
• 进展（前向）搜索
• 回溯（后向）搜索
• 偏序规划
• 规划存在性复杂性

Key theories

STRIPS表示

STRIPS将世界描述为一组真命题，并将每个动作描述为一个前置条件列表以及添加和删除列表，因此应用一个动作只是简单地添加和删除命题；这种分解模型是几乎所有经典规划器的基础。

进展和回溯搜索

经典规划可以通过从初始状态向前搜索应用适用动作（进展）或从目标向后计算回溯子目标（回溯）来找到，而偏序规划则放宽了对总动作排序的承诺。

规划的复杂性

判断命题STRIPS规划是否存在通常是PSPACE完全的，这正式解释了规划为何困难，并促使人们采用启发式和结构化方法使其变得实用。

Clinical relevance

经典规划表示是机器人任务规划、自动化装配和物流以及任何需要按顺序执行确定性动作以达到目标的应用程序的通用接口；基于PDDL的经典规划器是该领域和国际规划竞赛的主力工具。

History

STRIPS于1971年左右在斯坦福研究院（SRI）开发，用于控制Shakey机器人，引入了定义经典规划的前置条件/效果动作模型。偏序规划在20世纪70-80年代成熟，Bylander于1994年确立了命题规划的PSPACE完全性，PDDL标准随后统一了该领域的基准。

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

经典规划的假设是什么？

经典规划假设单一智能体在确定性、完全可观测和静态环境中行动，动作耗时单位时间，并且初始状态完全已知。放宽这些假设中的任何一个，例如允许不确定性或并发性，都会导致超出经典模型的更丰富的规划问题。

STRIPS的添加列表和删除列表意味着什么？

当应用STRIPS动作时，其添加列表中的命题变为真，删除列表中的命题变为假；所有其他命题保持不变。这种简单的更新规则使得STRIPS成为一种紧凑且计算方便的表示动作如何改变世界的方式。