chap3

本文深入探讨了确定性模型中的规划问题，将其视为搜索过程。它详细介绍了前向状态空间搜索、各种确定性搜索算法（如BFS、DFS、A*），以及启发式函数的设计与应用。此外，文章还涵盖了后向搜索的原理，并着重阐述了如何将规划问题转化为约束满足问题的方案空间规划（PSP），包括其核心概念、缺陷及解决策略。

前向状态空间搜索

• 搜索树术语: 定义了规划搜索中关键概念，如节点（包含状态和计划）、路径、深度和分支因子，以及扩展节点的流程。
• 确定性算法框架: 详细介绍了通用确定性前向搜索算法（Forward-Search-Det），通过管理“前沿”和“已扩展”集合来选择和剪枝节点。
• 主流搜索算法: 阐述了广度优先搜索 (BFS)、深度优先搜索 (DFS)、统一代价搜索 (Uniform-Cost Search)、贪婪最佳优先搜索 (Greedy Best-First Search) 和 A* 搜索的节点选择、剪枝策略及其特性（如完备性、最优性）。
• 启发式理论: 引入了启发式函数的“可采纳性”和“支配性”概念，解释了它们如何影响 A* 算法寻找最优解的能力。

启发式函数

• 核心作用: 启发式函数用于估计从当前状态到达目标状态的最小成本。
• 创建方法: 一种主要方法是通过“松弛”原始规划问题（即弱化约束）来获得一个更容易解决的近似问题，并从其最优解中导出启发式。
• 删除松弛启发式: 介绍了允许状态变量同时拥有多个值的松弛模型，如最优松弛解启发式 h+（可采纳）和快速前向启发式 hFF（非可采纳但有效）。
• 地标启发式: 识别在任何解决方案中都必须被满足的关键公式（地标），通过将其分解为子问题或利用松弛规划图 (RPG) 来计算。

后向搜索

• 基本原理: 后向搜索从目标状态逆向工作，通过选择相关动作并应用逆状态转移函数来推导出前一个状态应满足的条件。
• 动作相关性: 定义了动作被视为对给定目标“相关”的条件，即它必须使目标中的某个原子为真且不使任何目标原子为假。
• 算法与特性: 介绍了非确定性后向搜索算法，并通过循环检查机制确保其健全性和完备性。
• 提升式搜索: 讨论了通过保持变量未实例化（提升）来有效降低搜索分支因子的策略。

方案空间规划 (PSP)

• 规划范式: 将规划问题建模为约束满足问题，旨在生成部分有序的计划，以提供更大的执行灵活性。
• 核心概念: 定义了部分有序计划、因果链接（表示动作间的前后条件依赖）以及部分计划中的“缺陷”（开放目标和威胁）。
• 缺陷解决: 解释了如何解决开放目标（通过添加新动作或现有动作来满足前置条件）和威胁（通过添加优先级或不等式约束来消除冲突）。
• 启发式策略: 探讨了在 PSP 算法中选择缺陷（如“最少替代优先”FAF）和选择解析器（如“最少约束解析器”LCR、“避免新动作”ANA）的启发式方法。