规划图与启发式算法

规划图和领域无关启发式算法是通过紧凑分析可达性并自动估计从一个状态到目标的距离，使经典规划变得快速的技术。

Definition

规划图是一种分层结构，它交错命题层和动作层，并带有互斥约束，以近似可达性；规划启发式算法是通常从这些结构或从删除松弛问题计算出来的函数，用于估计从一个状态到达目标的成本。

Scope

本主题涵盖了Graphplan引入的规划图数据结构，包括命题和动作的层次，以及捕获哪些事实和动作不能同时发生的互斥（mutex）关系。它还涵盖了源自松弛问题（特别是忽略删除效应）的领域无关启发式算法家族，这些算法驱动着现代启发式搜索规划器。本主题探讨了可达性信息是如何计算并用于指导搜索的。相关的经典规划模型在相关主题中有所介绍。

Core questions

• 规划图如何逐层表示可达的命题和动作？
• 什么是互斥关系？它们如何捕捉事实和动作之间的不兼容性？
• 删除松弛如何用于推导出可采纳或信息丰富的规划启发式算法？
• 这些启发式算法如何将规划转化为高效的启发式搜索？

Key concepts

• 规划图
• 命题和动作层
• 互斥（mutex）
• Graphplan
• 删除松弛
• h-max和h-add启发式算法
• FF启发式算法和松弛计划
• 启发式前向搜索

Key theories

规划图与Graphplan

Graphplan构建了一个规划图，紧凑地编码了每个层次上哪些命题和动作是可达的，以及哪些对是互斥的，然后通过反向搜索该结构来提取计划，从而显著加快了规划速度。

删除松弛启发式算法

忽略动作的删除效应会产生一个更容易解决的松弛规划问题；解决这个松弛问题的成本提供了信息丰富、通常是可采纳的启发式算法（如h-max、h-add和FF启发式算法），从而指导前向搜索。

启发式搜索规划

最先进的经典规划器将自动推导的启发式算法与最佳优先或贪婪搜索以及偏好操作符等增强功能相结合，在不同领域实现了强大的通用性能。

Clinical relevance

规划图和删除松弛启发式算法是赢得竞赛的规划器的核心技术，这些规划器应用于机器人、物流和自主控制领域，它们使领域无关规划器能够快速解决大型问题，而无需手动编写搜索指导。

History

Blum和Furst的Graphplan（1995年，期刊版本1997年）引入了规划图，彻底改变了规划速度。1990年代末和2000年代见证了删除松弛启发式算法的兴起，FF规划器（Hoffmann和Nebel，2001年）以及后来的Fast Downward（Helmert，2006年）确立了启发式前向搜索作为主导方法。

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

规划图中的互斥（mutex）是什么？

互斥（mutual exclusion）关系标记了两个命题或两个动作不能同时在同一层次上成立或应用，例如因为一个动作删除了另一个动作的先决条件。互斥关系使规划图成为对真实可达性更紧密的近似。

为什么忽略删除效应能提供有用的启发式算法？

如果没有删除效应，实现一个目标永远不会撤销另一个目标，因此松弛问题更容易解决，并且永远不会比原始问题更难。因此，松弛计划的成本是真实成本的下限或有根据的估计，使其成为指导搜索的有效启发式算法。