经典规划与决策

AI规划概述

什么是AI规划

AI规划（AI Planning）是研究如何让智能体自动生成行动序列以从初始状态到达目标状态的领域。与搜索问题不同，规划问题需要显式地表示世界状态、动作及其效果。

规划的核心问题可以形式化为：

\[\text{给定} \langle S_0, G, A \rangle \text{，找到动作序列} a_1, a_2, \ldots, a_n \text{使得} S_0 \xrightarrow{a_1} S_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} S_n \models G\]

其中 \(S_0\) 是初始状态，\(G\) 是目标条件，\(A\) 是可用动作集合。

规划问题的分类

维度	简单	复杂
可观测性	完全可观测	部分可观测
确定性	确定性	随机性
时间	离散	连续
智能体数量	单智能体	多智能体
目标类型	达到目标	优化目标函数

规划与搜索的区别

• 搜索：状态是"黑箱"，仅定义后继函数和目标测试
• 规划：状态有结构化表示（命题/谓词），动作有前条件和效果的显式描述

这种结构化表示使规划器可以利用问题的内部结构来高效求解，而非盲目搜索。

规划的应用领域

• 机器人学：任务规划、运动规划、操纵规划
• 自动驾驶：行为决策、路径规划、轨迹生成
• 游戏AI：NPC行为、战略规划
• 物流与调度：供应链优化、资源分配
• 航天：卫星任务规划、火星探测器自主规划
• 自然语言处理：对话管理、故事生成

---

经典规划表示

经典规划（Classical Planning）是AI规划中最基础的问题设定：完全可观测、确定性、静态、离散的单智能体环境。

STRIPS表示

STRIPS（Stanford Research Institute Problem Solver, 1971）是最早的规划表示语言之一：

• 状态：一组命题（ground atoms）的集合
• 动作：由三元组 \(\langle \text{Precondition}, \text{Add}, \text{Delete} \rangle\) 描述
  • Precondition：动作执行的前提条件
  • Add List：执行后新增的命题
  • Delete List：执行后删除的命题

示例：积木世界（Blocks World）

Action: Move(B, x, y)
  Precondition: On(B, x) ∧ Clear(B) ∧ Clear(y)
  Add: On(B, y) ∧ Clear(x)
  Delete: On(B, x) ∧ Clear(y)

PDDL — 规划领域定义语言

PDDL（Planning Domain Definition Language）是经典规划的标准化表示语言，将规划问题分为两部分：

1. Domain文件：定义类型、谓词和动作模板
2. Problem文件：定义具体对象、初始状态和目标

;; Domain: Logistics
(:action drive-truck
  :parameters (?truck ?from ?to ?city)
  :precondition (and (truck ?truck) (location ?from)
                     (location ?to) (in-city ?from ?city)
                     (in-city ?to ?city) (at ?truck ?from))
  :effect (and (at ?truck ?to) (not (at ?truck ?from))))

PDDL经过多次扩展：PDDL 2.1引入时间和数值、PDDL 3.0引入偏好和约束。

状态空间搜索

将规划问题转化为图搜索问题：

前向搜索（Forward Search / Progression）：

• 从初始状态出发，逐步应用动作直到满足目标
• 分支因子大，需要良好的启发式

后向搜索（Backward Search / Regression）：

• 从目标出发，反向寻找哪些动作能达成子目标
• 天然只考虑相关动作，但需要处理部分状态

规划图（Planning Graph）

Graphplan算法（Blum & Furst, 1997）引入了规划图数据结构：

• 命题层（Proposition Level）与动作层（Action Level）交替排列
• 每层记录互斥关系（Mutex），表示不能同时成立的命题/动作对
• 可以用于：
  • 提取有效规划方案
  • 作为启发式函数估计目标距离（\(h^{\max}\), \(h^{\text{add}}\), \(h^{FF}\)）

启发式规划

现代经典规划器的核心思想是：自动从问题描述中提取启发式函数。

常见启发式：

启发式	方法	特点
\(h^{\max}\)	取各子目标最大代价	可容（admissible），但不够精确
\(h^{\text{add}}\)	取各子目标代价之和	不可容，但信息量大
\(h^{FF}\)	规划图中忽略delete效果	平衡精度与计算量
LM-cut	基于地标（landmark）的切割	可容，适合最优规划

代表性规划器：Fast Downward、LAMA、FF Planner。

部分序规划

与全序规划不同，部分序规划（Partial-Order Planning）只约束有因果依赖的动作之间的顺序：

• 更灵活，允许并行执行
• 维护因果链（Causal Links）和威胁（Threats）
• 经典算法：POP（Partial-Order Planner）

---

行为决策

行为决策（Behavior Decision-Making）关注智能体如何在复杂环境中选择高层行为策略，是连接感知与底层控制的桥梁。

有限状态机 (FSM)

最简单的行为决策模型，智能体在有限个状态之间切换：

• 状态：表示智能体的行为模式（如巡逻、追击、逃跑）
• 转移：由条件触发的状态切换
• 优点：直观、易于实现和调试
• 缺点：状态爆炸——\(n\) 个状态变量产生 \(O(2^n)\) 个组合状态

层次状态机（HFSM） 通过嵌套减少复杂度，但仍难以处理大规模问题。

行为树 (Behavior Tree)

行为树是游戏AI和机器人领域广泛使用的行为决策框架：

核心节点类型：

节点类型	功能	行为
Sequence (→)	顺序执行	全部成功才成功，遇到失败即停止
Selector (?)	选择执行	遇到成功即停止，全部失败才失败
Parallel (⇉)	并行执行	按策略判定成功/失败
Condition	条件检查	返回成功/失败
Action	执行动作	返回成功/失败/运行中
Decorator	修饰子节点	反转、重复、超时等

优点：模块化、可复用、易于扩展和调试。

与FSM对比：行为树的状态隐含在树的遍历位置中，不需要显式管理状态转移。

分层任务网络 (HTN)

HTN（Hierarchical Task Network）规划通过任务分解来求解：

• 原子任务（Primitive Task）：可直接执行的动作
• 复合任务（Compound Task）：需要分解为子任务
• 方法（Method）：描述如何将复合任务分解为子任务序列

Task: Deliver(package, destination)
  Method 1: [Pick(package), Drive(destination), Drop(package)]
  Method 2: [Pick(package), Fly(destination), Drop(package)]

HTN利用领域知识减少搜索空间，适合结构化程度高的实际应用（如物流、制造）。

代表性系统：SHOP2、SIPE-2。

决策理论规划

当环境具有不确定性时，需要引入概率和效用：

MDP（马尔可夫决策过程）：

\[V^*(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} T(s, a, s') V^*(s') \right]\]

POMDP（部分可观测MDP）：

• 智能体无法直接观测到完整状态
• 维护信念状态（belief state）——状态上的概率分布
• 计算复杂度极高（PSPACE-complete），通常需要近似求解

博弈论规划

多智能体场景下，需要考虑其他智能体的行为：

• 纳什均衡：没有智能体有单方面偏离的动机
• 极大极小策略：零和博弈中的最优策略
• 多智能体规划的核心挑战：协调（coordination）与通信（communication）

---

规划中的优化方法

规划问题的许多变体都可以转化为数学优化问题。

线性规划与混合整数规划

线性规划 (LP)：

\[\min \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0\]

• 目标函数和约束都是线性的
• 单纯形法（Simplex）和内点法（Interior Point）
• 应用：资源分配、流网络、调度问题的松弛

混合整数规划 (MIP)——当部分决策变量必须取整数值时：

\[\min \mathbf{c}^T \mathbf{x} + \mathbf{d}^T \mathbf{y} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} + \mathbf{B}\mathbf{y} \leq \mathbf{b}, \quad \mathbf{y} \in \mathbb{Z}^p\]

• MILP（混合整数线性规划）：NP-hard，但现代求解器（Gurobi, CPLEX）能处理相当规模
• 应用：避障（用二元变量表示障碍物的哪一侧）、任务分配（0-1决策）、车辆路径规划（TSP/VRP）

非线性规划与凸优化

非线性规划 (NLP)：

\[\min f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \quad h_j(\mathbf{x}) = 0\]

求解方法：

• 梯度下降 / 牛顿法：适用于无约束或简单约束
• 序列二次规划（SQP）：在每步将问题近似为QP
• 内点法（IPM）：将不等式约束转化为障碍函数
• 增广拉格朗日法（ALM）：结合拉格朗日乘子和惩罚项

凸优化——当 \(f\) 和可行域都是凸的时，局部最优即全局最优：

• 二次规划（QP）：\(\min \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{f}^T\mathbf{x}\)
• 二阶锥规划（SOCP）：约束为二阶锥
• 半定规划（SDP）：约束为半正定矩阵

轨迹优化中，很多问题可以转化或近似为凸优化。

约束优化在规划中的应用

任务分配问题——将 \(n\) 个任务分配给 \(m\) 个智能体，最小化总代价：

\[\min \sum_{i,j} c_{ij} x_{ij} \quad \text{s.t.} \quad \sum_j x_{ij} = 1, \quad x_{ij} \in \{0, 1\}\]

匈牙利算法可以在多项式时间内求解。

车辆路径问题 (VRP)——TSP的推广，多辆车辆从仓库出发服务所有客户并返回：

• 容量约束VRP（CVRP）
• 时间窗VRP（VRPTW）
• 通常使用MIP + 启发式（如列生成、自适应大邻域搜索）

调度问题——作业车间调度（Job Shop Scheduling）：

• \(n\) 个作业、\(m\) 台机器，每个作业有工序约束
• 目标：最小化完工时间（makespan）
• NP-hard，实际中结合CP（约束规划）和MIP求解

---

经典参考

• Stuart Russell & Peter Norvig, Artificial Intelligence: A Modern Approach (AIMA) — Part III: Planning
• Dana Nau et al., Automated Planning: Theory and Practice
• Steven LaValle, Planning Algorithms

---

评论