自动规划与调度

自动规划（Automated Planning）是搜索与规划的进阶分支：给定初始状态、目标状态和一组可选动作，自动生成一个从初始到目标的动作序列。与一般搜索问题（如八数码、走迷宫）不同，规划问题的核心特征是动作本身具有结构——每个动作只改变世界的一部分状态变量，而不是像棋类那样由一个统一的转移函数定义全部状态变化。这种结构性使得规划算法可以利用动作的前提-效果逻辑来大幅剪枝，而不是盲目枚举所有状态。前置阅读：搜索与规划、符号主义 AI 概览。

一句话理解：如果搜索是”在地图上找路”，那么规划就是”在一张会因你的行为而改变的地图上找路”——你的每一步不仅移动自己，还改变了地图本身。

核心直觉

自动规划的本质是在状态空间里自动找到一条”做事的步骤”——不是一步棋，而是一连串有因果关系的动作链。规划问题的标准输入是一个三元组 $(\Sigma, s_0, g)$ ：世界模型 $\Sigma$ 定义了所有合法动作及其前提-效果， $s_0$ 是初始状态， $g$ 是目标条件。

状态（State）= 世界的快照，用一组逻辑命题描述（如”机器人在 A 室""手是空的”）。在经典规划中，状态就是一组为真的命题集合（类似数据库中的一行记录），世界的变化体现为命题的增删。这种表示被称为命题状态空间（Propositional State Space）——每个命题要么为真要么为假，没有中间态。
动作（Action）= 改变世界的操作，由前提条件（Precondition，动作执行前世界必须满足的命题集合）和效果（Effect，动作执行后添加或删除的命题集合）组成——前提全部满足才能执行，执行后按效果增删若干命题。一个动作的效果分为正效果（ADD，新增为真的命题）和负效果（DEL，删除即变为假的命题），因此动作的本质是”世界状态的一次原子更新”。
前向搜索（Forward Search）= 从当前状态出发，逐个尝试可用动作，看能否到达目标——直观但分支因子大（Branching Factor，每个状态下可执行的动作数量）。当动作数量和命题数量增长时，状态空间呈指数膨胀，即所谓维度灾难（Curse of Dimensionality）。
后向搜索（Backward Search）= 从目标倒推：什么动作能达到目标？它的前提又是什么？——分支更少（只需考虑效果与目标相关的动作）但实现更复杂（需要反向应用效果，且初始状态未知时难以剪枝）。
启发式规划（Heuristic Planning）= 用放松的问题（Relaxed Problem，人为简化后更容易求解的版本）快速估计”还差几步到目标”，像 A 星中的 h(n) 一样引导搜索。最常见的放松策略有两种：h+（delete relaxation） 忽略所有负效果（假设动作只增不删），h_max 只考虑每个命题到达的最小代价。放松问题的解代价是真实代价的下界（Admissible，即不会高估），因此可以用作 A 星的启发函数。
GraphPlan= 先构建一个”规划图”（Planning Graph，一种交替排列命题层和动作层的分层结构），再从目标层反向提取合法计划——分层结构利用了命题之间的**互斥关系（Mutual Exclusion，两个命题不可能在同一时刻为真）**来大幅缩小搜索空间。

原理图解

STRIPS 模型：动作 = 前提 + 增删效果

STRIPS（STanford Research Institute Problem Solver）是自动规划的经典形式化模型，由 Fikes 和 Nilsson 于 1971 年提出。它的核心思想是将”世界的变化”抽象为原子动作对命题集合的增删操作，这一简单但强大的模型影响了后续五十年的规划研究。每个动作定义为三元组 (前提, 正效果, 负效果)，在学术上也常记为 $\langle \text{pre}(a), \text{add}(a), \text{del}(a) \rangle$ ：

为什么 STRIPS 如此重要？ 因为它把规划从定理证明（Theorem Proving，用逻辑推导证明命题成立）的框架中解放出来——在 STRIPS 之前，规划被视为”找到一组动作使得目标命题可被证明”，但定理证明器在大型问题上效率太低。STRIPS 直接操作命题集合（增/删），跳过了推理步骤，让规划变得像数据库更新一样高效。

规划流程：初始状态到目标状态

前向状态空间规划（Forward State-Space Planning）从初始状态出发，逐步应用动作到达目标。每一步都检查”当前哪些动作的前提条件被满足”——这些动作就是可选的分支。这种方法被称为前向链式推理（Forward Chaining）：从已知事实出发，逐步推导到目标。

下面的例子展示了一个机器人搬运任务：机器人从 A 室出发，经过 B、C 室，最终把盒子搬到 D 室。每一步状态变化都是一次”动作应用”——前提被满足 → 执行 → 增删命题 → 得到新状态：

GraphPlan：分层规划图

GraphPlan（由 Blum 和 Furst 于 1995 年提出）是规划算法的一次飞跃。它的核心洞察是：与其一棵一棵地展开搜索树，不如先把所有可能到达的命题和动作分层”铺平”，再在分层结构上高效提取计划。GraphPlan 先向前扩展规划图（命题层与动作层交替），再从目标层向后搜索合法计划，避免了盲目展开整棵搜索树。

规划图的关键概念是互斥关系（Mutual Exclusion，简称 Mutex）：同一层中，如果两个动作不可能同时执行（例如一个动作的负效果会删除另一个动作的前提），则标记为互斥；同理，两个不可能同时为真的命题也标记为互斥。随着图层的推进，互斥关系会传播——如果到达某一层所有目标命题都不再互斥，就可以开始反向提取计划：

动手实践

STRIPS 前向搜索：机器人搬运规划

用纯 Python 实现 STRIPS 动作定义和前向状态空间搜索，解决经典的”机器人搬运”规划问题：

from copy import deepcopy

# 定义 STRIPS 动作模板：名称 -> (前提, 正效果, 负效果)
actions = {
    "Move(A,B)": ({"at_robot:A"}, {"at_robot:B"}, {"at_robot:A"}),
    "Move(B,A)": ({"at_robot:B"}, {"at_robot:A"}, {"at_robot:B"}),
    "Move(B,C)": ({"at_robot:B"}, {"at_robot:C"}, {"at_robot:B"}),
    "Move(C,B)": ({"at_robot:C"}, {"at_robot:B"}, {"at_robot:C"}),
    "Pick":      ({"at_robot:B", "at_box:B", "hand_empty"}, {"holding_box"}, {"at_box:B", "hand_empty"}),
    "Drop":      ({"at_robot:B", "holding_box"}, {"at_box:B", "hand_empty"}, {"holding_box"}),
}

def apply_action(state, action):
    """检查前提是否满足，满足则应用增删效果"""
    pre, add, dele = actions[action]
    if not pre.issubset(state):          # 前提不全 = 动作不可用
        return None
    new_state = set(state)
    new_state -= dele                     # 删除负效果
    new_state |= add                      # 添加正效果
    return new_state

def plan(initial_state, goal, max_depth=6):
    """前向 BFS 搜索：从初始状态找到达目标的动作序列"""
    queue = [(initial_state, [])]
    visited = {frozenset(initial_state)}
    for _ in range(2000):
        if not queue:
            return None
        state, path = queue.pop(0)
        if goal.issubset(state):          # 目标全部满足
            return path
        if len(path) >= max_depth:
            continue
        for act in actions:
            ns = apply_action(state, act)
            if ns and frozenset(ns) not in visited:
                visited.add(frozenset(ns))
                queue.append((ns, path + [act]))
    return None

# 机器人: A 室，盒子: B 室 → 目标: 把盒子搬到 A 室
init = {"at_robot:A", "at_box:B", "hand_empty"}
goal = {"at_box:A"}
result = plan(init, goal)
print("计划:", result)
# 输出: ['Move(A,B)', 'Pick', 'Move(B,A)', 'Drop']

实践要点

PDDL 是规划领域的通用接口：Planning Domain Definition Language 自 1998 年成为国际规划竞赛（ICAPS）的标准输入格式，几乎所有求解器都支持。将问题写成 PDDL 后，可以无缝切换不同求解后端。
前向搜索的瓶颈是分支因子：当可用动作很多时，盲目 BFS 指数爆炸。用放松启发式（如忽略删除效果的 h_plus，或忽略前提的 h_max）估计每个状态到目标的距离，配合 A 星搜索是主流做法。
规划与调度不同：规划（Planning）决定”做什么”——生成动作序列；调度（Scheduling）决定”何时做”——在资源约束下分配时间槽。两者常组合使用：先规划出动作集，再用 CP 求解器做调度。详见约束满足问题。
HTN（层次任务网络）是另一条路线：Hierarchical Task Network 将高层任务递归分解为子任务，直到原子动作——更接近人类思维，广泛用于游戏 AI 和机器人。
LLM + 规划器的混合趋势：大语言模型擅长生成自然语言计划，但在长链推理中易出错。将 LLM 的初步计划交给 PDDL 规划器验证和修正，是当前神经符号融合的热点方向。详见与现代方法的融合。

典型应用

NASA 航天任务：NASA 的 ASPEN（Automated Scheduling and Planning Environment）用于火星探测器的自主任务规划——给定科学目标和能量约束，自动生成观测、移动、通信的动作序列并上传执行。
物流与供应链：亚马逊、京东的仓储机器人（Kiva/Agility Robotics）需要规划最优搬运路径和取放顺序，将货架从存储区搬到拣货台，本质是多智能体任务规划问题。
机器人任务规划：波士顿动力 Spot、Fetch 等机器人接收高层指令（如”把咖啡从厨房拿到办公室”）后，用 PDDL 规划器自动分解为导航、抓取、放置等原子动作，再交给底层运动控制器执行。
游戏 AI：Killzone、F.E.A.R. 等游戏使用 HTN 规划器驱动 NPC 行为——NPC 根据当前态势（弹药、敌人位置）自动规划出战术行为序列，比固定状态机更灵活。
业务流程自动化：RPA（机器人流程自动化）中的任务编排、云计算中的工作流调度（如 Apache Airflow 的 DAG 规划）都涉及规划思想。

典型类库与工具

类库	语言	说明
Fast Downward	C++	学术界主流 PDDL 规划器，支持多种启发式搜索策略
PDDL4J	Java	PDDL 解析和规划框架，适合教学和原型开发
TFD / LAMA	C++	国际规划竞赛获奖规划器，基于前向搜索 + 启发式
pyhipsters / unified-planning	Python	统一规划建模框架，可对接多种后端求解器
SHOP2	Lisp/Java	经典的 HTN 规划器，广泛用于游戏和军事仿真
ASPEN	C/Java	NASA 的自动规划与调度系统，用于航天任务

术语表

术语	英文	解释
自动规划	Automated Planning	给定初始状态、目标和动作集，自动生成到达目标的动作序列
STRIPS	STRIPS	经典规划形式化模型，动作由前提条件和增删效果定义
PDDL	Planning Domain Definition Language	规划领域定义语言，自动规划领域的标准问题描述格式
前提条件	Precondition	动作执行前世界必须满足的命题集合
效果	Effect	动作执行后添加或删除的命题集合
规划图	Planning Graph	GraphPlan 中交替的命题层和动作层结构
启发式规划	Heuristic Planning	用放松问题估计到目标的距离来引导搜索的规划方法
层次任务网络	HTN (Hierarchical Task Network)	将高层任务递归分解为子任务直至原子动作的规划方法
规划与调度	Planning vs Scheduling	规划决定做什么（动作序列），调度决定何时做（时间分配）