4. 经典规划算法：STRIPS、PDDL语言入门、前向搜索与后向搜索
好，咱们进入经典规划的世界。说实话，这部分内容是我个人觉得最「有味道」的——它奠定了现代任务规划的理论基础。你想想看，在深度学习火起来之前，机器人怎么思考？靠的就是这些逻辑清晰、结构分明的符号规划方法。
今天我们要聊三个核心东西：STRIPS（斯坦福研究院问题求解器）、PDDL（规划领域定义语言），以及两种最基本的搜索策略——前向搜索和后向搜索。它们就像规划领域的「三原色」，理解了它们，后面再学HTN、Temporal Planning就轻松多了。
4.1 STRIPS：规划算法的老祖宗
STRIPS是1971年Richard Fikes和Nils Nilsson搞出来的。我刚开始读时觉得这名字挺土，但真正用起来才发现——简洁就是力量。
STRIPS的核心思想很简单：世界由一组逻辑命题描述，动作会改变这些命题的真值。每个动作定义三样东西：
- 前提条件（Preconditions）：动作执行前必须为真的命题
- 添加列表（Add List）：动作执行后变为真的命题
- 删除列表（Delete List）：动作执行后变为假的命题
举个例子，机器人抓取一个物体：
Action: PickUp(robot, obj)
Preconditions: At(robot, loc) ∧ At(obj, loc) ∧ Free(robot) ∧ Not(Heavy(obj))
Add: Holding(robot, obj)
Delete: Free(robot), At(obj, loc)嗯，这里要注意——STRIPS假设世界是「封闭世界」，也就是说，没明确说为真的命题都视为假。我在项目中遇到过有人忘了这个前提，结果规划器一直报错，排查了半天才发现是初始状态没写全。
STRIPS的核心假设：动作只改变显式列出的命题，其他所有命题保持不变。这就是所谓的「框架问题」的经典解法——虽然简单，但够用。
4.2 PDDL语言入门：让规划可移植
STRIPS虽然好，但每个团队都有自己的描述格式，互相不兼容。1998年，一群规划研究者坐在一起，搞出了PDDL——规划领域定义语言。说白了，就是给规划问题定了个「普通话」标准。
PDDL把规划问题拆成两个文件：
| 文件 | 内容 | 类比 |
|---|---|---|
| domain.pddl | 定义谓词、动作、类型 | 像编程里的「类定义」 |
| problem.pddl | 定义对象、初始状态、目标状态 | 像编程里的「实例化」 |
我习惯先写domain再写problem，这样逻辑更清晰。来看一个简单的搬运机器人例子：
;; domain.pddl
(define (domain transport)
(:requirements :strips :typing)
(:types location robot package)
(:predicates
(at ?r - robot ?l - location)
(at ?p - package ?l - location)
(carrying ?r - robot ?p - package)
(connected ?l1 ?l2 - location)
)
(:action move
:parameters (?r - robot ?from ?to - location)
:precondition (and (at ?r ?from) (connected ?from ?to))
:effect (and (not (at ?r ?from)) (at ?r ?to))
)
(:action pick-up
:parameters (?r - robot ?p - package ?l - location)
:precondition (and (at ?r ?l) (at ?p ?l) (not (carrying ?r ?p)))
:effect (and (carrying ?r ?p) (not (at ?p ?l)))
)
);; problem.pddl
(define (problem transport-p1)
(:domain transport)
(:objects
robot1 - robot
pkg1 - package
locA locB - location
)
(:init
(at robot1 locA)
(at pkg1 locA)
(connected locA locB)
(connected locB locA)
)
(:goal (and (at robot1 locB) (at pkg1 locB)))
)个人经验：写PDDL时，:requirements一定要写对。我刚开始经常漏写:typing，结果规划器报「未定义类型」的错误。另外，动作的:parameters里变量名前面要加问号，这个细节容易忘。
4.3 前向搜索：从初始状态往前推
前向搜索，顾名思义，就是从初始状态出发，不断应用可用的动作，直到达到目标状态。它的逻辑很直观：
- 当前状态 = 初始状态
- 找出所有前提条件满足的动作
- 选一个动作执行，更新状态
- 检查新状态是否满足目标
- 如果满足，返回动作序列；否则回到第2步
你想想看，这其实就是广度优先搜索或深度优先搜索在规划问题上的应用。但有个大问题——状态空间爆炸。我记得有一次用前向搜索解一个10个物体的抓取问题，搜索树直接膨胀到几百万个节点，跑了半小时没出结果。
避坑指南：前向搜索虽然直观，但分支因子太大。我曾经在一个仓储机器人项目里用纯前向搜索，结果规划时间比机器人执行时间还长。后来加了启发式函数才解决问题。
4.4 后向搜索：从目标状态往回推
后向搜索的思路正好反过来——从目标状态出发，反向推导出哪些动作能产生这个状态，然后一步步往回走到初始状态。它的好处是：只关注与目标相关的动作，搜索空间通常小很多。
后向搜索的关键概念是「回归」（regression）：给定一个状态S和一个动作a，如果a的效果能产生S，那么a的前提条件就是S的「前驱状态」。
举个例子：
- 目标状态：
Holding(robot, obj) - 能产生这个状态的动作：
PickUp(robot, obj) - 该动作的前提条件：
At(robot, loc) ∧ At(obj, loc) ∧ Free(robot) - 所以前驱状态就是这些前提条件
我个人更喜欢后向搜索，尤其是在目标状态比较明确、初始状态很复杂的情况下。但后向搜索也有坑——它需要处理「相关动作」的筛选，如果领域模型写得不好，容易漏掉关键动作。
4.5 前向 vs 后向：怎么选？
我整理了一个对比表，方便你快速决策：
| 维度 | 前向搜索 | 后向搜索 |
|---|---|---|
| 搜索方向 | 初始状态 → 目标状态 | 目标状态 → 初始状态 |
| 分支因子 | 大（所有可用动作） | 小（只考虑相关动作） |
| 启发式容易度 | 容易（有明确距离度量） | 较难（目标状态不唯一） |
| 适用场景 | 初始状态简单、目标复杂 | 目标明确、初始状态复杂 |
| 典型算法 | FF、FastDownward | BFS(regression)、GSP |
我的建议：实际项目中，别死磕纯前向或纯后向。现代规划器（比如FastDownward）都是双向搜索+启发式函数的混合策略。你只需要理解这两种思路，然后交给规划器去选。
4.6 知识体系总览
下面这张图把本章的核心逻辑串起来了——从STRIPS到PDDL，再到两种搜索策略，最后到实际应用：
这张图你看懂了吗？从上到下，STRIPS定义了「动作是什么」，PDDL让这些定义可读可写，前向和后向搜索则提供了两种求解思路。最后，它们都汇入到实际的任务规划器中。
好了，经典规划算法的核心就这些。说实话，STRIPS和PDDL虽然老，但思想至今仍在用。我去年做的一个仓储机器人项目，底层规划器用的还是PDDL 2.1标准——经典的东西，生命力就是这么强。