第7章：自动规划（Automated Planning）
一、导读
1.1 本章学习目标
第7章介绍自动规划——让AI系统自动生成达到目标的行动序列。与搜索（第3章）不同，规划利用问题的结构（状态、行动、目标的形式化表示）来设计更高效的算法。
本章的核心学习目标包括：
- 掌握经典规划的形式化：理解 STRIPS 语言、前件、后件、前提条件。
- 理解前向搜索与后向搜索：状态空间搜索与目标回归搜索的区别和适用场景。
- 掌握规划图方法：理解 Graphplan 算法的原理。
- 了解层次任务网络（HTN）：如何通过任务分解来处理复杂规划。
- 了解偏序规划：最小承诺策略如何减少不必要的搜索。
- 理解规划在实际中的应用：机器人、自动驾驶、物流调度等。
1.2 为什么第七章如此重要
规划是智能体的核心能力之一。一个理性的智能体不仅要能对当前情况做出反应，还要能为未来制定计划。规划算法是连接"目标"和"行动"的桥梁。
规划技术在实际中有广泛应用：机器人需要规划运动轨迹，自动驾驶需要规划行驶路线，物流系统需要规划配送方案，项目管理需要规划任务执行顺序。掌握规划算法，就掌握了让AI系统"未雨绸缪"的能力。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
规划与搜索的关系：规划可以转化为搜索问题，但为什么专门的规划算法通常更高效？
状态空间搜索 vs 计划空间搜索：为什么在计划空间中搜索通常比在状态空间中搜索更高效？
规划图的威力：规划图如何表示行动的并行性和互斥关系？
层次规划的必要性：为什么我们需要将复杂任务分解为子任务？
规划的不确定性：当行动效果不确定时，如何制定稳健的计划？
二、核心概念详解
2.1 经典规划
2.1.1 STRIPS 语言
STRIPS（Stanford Research Institute Problem Solver）是经典的规划语言，用命题逻辑描述状态和行动。
- 状态：一组正文字（propositions）的合取
- 行动：由前提条件（precondition）和效果（effect）描述
- 目标：一组正文字的合取
python
class STRIPSAction:
def __init__(self, name, preconds, effects):
self.name = name
self.preconds = set(preconds)
self.add_effects = set()
self.del_effects = set()
for e in effects:
if e.startswith('~'):
self.del_effects.add(e[1:])
else:
self.add_effects.add(e)
def is_applicable(self, state):
return self.preconds.issubset(state)
def apply(self, state):
if not self.is_applicable(state):
return None
new_state = (state | self.add_effects) - self.del_effects
return new_state
def __repr__(self):
return f"Action({self.name})"
class PlanningProblem:
def __init__(self, initial, actions, goal):
self.initial = set(initial)
self.actions = actions
self.goal = set(goal)
def is_goal(self, state):
return self.goal.issubset(state)
# 积木世界
actions = [
STRIPSAction('Move(A,B)', {'Clear(A)', 'Clear(B)', 'On(A)', 'Block(A)', 'Block(B)'},
{'On(A,B)', 'Clear(A)', '~Clear(B)'}),
STRIPSAction('Move(A,Table)', {'Clear(A)', 'On(A,B)'},
{'On(A)', 'Clear(B)', '~On(A,B)'}),
STRIPSAction('Move(B,A)', {'Clear(B)', 'Clear(A)', 'On(B)', 'Block(B)', 'Block(A)'},
{'On(B,A)', '~Clear(A)'}),
STRIPSAction('Move(B,Table)', {'Clear(B)', 'On(B,A)'},
{'On(B)', 'Clear(A)', '~On(B,A)'}),
]
initial = {'On(A)', 'On(B)', 'Clear(A)', 'Clear(B)', 'Block(A)', 'Block(B)'}
goal = {'On(A,B)'}
problem = PlanningProblem(initial, actions, goal)2.1.2 前向状态空间搜索
从初始状态出发，通过应用行动逐步达到目标状态。
python
from collections import deque
def forward_state_space_search(problem):
initial = frozenset(problem.initial)
frontier = deque([(initial, [])])
visited = {initial}
while frontier:
state, plan = frontier.popleft()
if problem.is_goal(state):
return plan
for action in problem.actions:
if action.is_applicable(state):
new_state = frozenset(action.apply(state))
if new_state not in visited:
visited.add(new_state)
frontier.append((new_state, plan + [action]))
return None
solution = forward_state_space_search(problem)
print(f"前向搜索解: {[a.name for a in solution] if solution else '无解'}")2.1.3 后向目标回归搜索
从目标出发，反向寻找能达到目标的行动。
python
def backward_goal_regression(problem):
def regress(goal, action):
if not action.add_effects.intersection(goal):
return None
new_goal = (goal - action.add_effects) | action.preconds
return new_goal
goal = frozenset(problem.goal)
frontier = deque([(goal, [])])
visited = {goal}
while frontier:
current_goal, plan = frontier.popleft()
if current_goal.issubset(problem.initial):
return list(reversed(plan))
for action in problem.actions:
new_goal = regress(current_goal, action)
if new_goal is not None:
new_goal = frozenset(new_goal)
if new_goal not in visited:
visited.add(new_goal)
frontier.append((new_goal, [action] + plan))
return None2.2 规划图
2.2.1 规划图的构建
规划图是一个交替包含状态层和行动层的有向图。它表示哪些行动在哪些时刻可能执行，以及哪些命题之间互斥。
python
class PlanningGraph:
def __init__(self, problem):
self.problem = problem
self.state_levels = [set(problem.initial)]
self.action_levels = []
self.mutex_propositions = [set()]
self.mutex_actions = []
def expand(self):
current_state = self.state_levels[-1]
current_mutex = self.mutex_propositions[-1]
actions = self._get_applicable_actions(current_state)
self.action_levels.append(actions)
next_state = set(current_state)
for action in actions:
if action.is_applicable(current_state):
result = action.apply(current_state)
if result:
next_state.update(result)
self.state_levels.append(next_state)
self.mutex_propositions.append(set())
return len(next_state) > len(current_state)
def _get_applicable_actions(self, state):
applicable = []
for action in self.problem.actions:
if action.is_applicable(state):
applicable.append(action)
persistence = [STRIPSAction(f'Persist({p})', {p}, {p}) for p in state]
return applicable + persistence
def graph_plan(self, max_levels=20):
for level in range(max_levels):
self.expand()
if self._goal_reachable():
solution = self._extract_plan()
if solution is not None:
return solution
return None
def _goal_reachable(self):
return self.problem.goal.issubset(self.state_levels[-1])
def _extract_plan(self):
return []
# 使用规划图
problem = PlanningProblem(
initial={'At(Home)', 'Have(Mail)'},
actions=[
STRIPSAction('Go(PostOffice)', {'At(Home)'}, {'At(PostOffice)', '~At(Home)'}),
STRIPSAction('SendMail', {'At(PostOffice)', 'Have(Mail)'}, {'Mailed', '~Have(Mail)'}),
STRIPSAction('GoHome', {'At(PostOffice)'}, {'At(Home)', '~At(PostOffice)'}),
],
goal={'Mailed'}
)
pg = PlanningGraph(problem)
plan = pg.graph_plan()
print(f"规划图解: {plan}")2.3 层次任务网络（HTN）
2.3.1 任务分解
HTN 规划通过将复杂任务分解为子任务来工作。
python
class HTNPlanner:
def __init__(self):
self.methods = {}
self.operators = {}
def add_method(self, task_name, preconds, subtasks):
if task_name not in self.methods:
self.methods[task_name] = []
self.methods[task_name].append((preconds, subtasks))
def add_operator(self, name, preconds, effects):
self.operators[name] = STRIPSAction(name, preconds, effects)
def decompose(self, task, state, depth=0, max_depth=20):
if depth > max_depth:
return None
if task in self.operators:
op = self.operators[task]
if op.is_applicable(state):
return [op]
return None
if task in self.methods:
for preconds, subtasks in self.methods[task]:
if set(preconds).issubset(state):
plan = []
current_state = set(state)
for subtask in subtasks:
subplan = self.decompose(subtask, current_state, depth + 1)
if subplan is None:
break
plan.extend(subplan)
for action in subplan:
result = action.apply(current_state)
if result:
current_state = result
else:
return plan
return None
# 示例：做早餐的 HTN 规划
htn = HTNPlanner()
htn.add_operator('Toast_Bread', {'Has(Bread)', 'Has(Toaster)'}, {'Has(Toast)', '~Has(Bread_In)'})
htn.add_operator('Fry_Egg', {'Has(Egg)', 'Has(Pan)'}, {'Has(Fried_Egg)'})
htn.add_operator('Brew_Coffee', {'Has(Coffee)', 'Has(Water)'}, {'Has(Coffee_Brewed)'})
htn.add_operator('Serve', {'Has(Toast)', 'Has(Fried_Egg)', 'Has(Coffee_Brewed)'}, {'Breakfast_Ready'})
htn.add_method('Make_Breakfast', {'Has(Bread)', 'Has(Egg)', 'Has(Coffee)'},
['Toast_Bread', 'Fry_Egg', 'Brew_Coffee', 'Serve'])
initial = {'Has(Bread)', 'Has(Egg)', 'Has(Coffee)', 'Has(Toaster)', 'Has(Pan)', 'Has(Water)'}
plan = htn.decompose('Make_Breakfast', initial)
print(f"HTN 计划: {[a.name for a in plan] if plan else '无解'}")2.4 偏序规划
2.4.1 最小承诺策略
偏序规划不强制指定行动的顺序，只在必要时才确定顺序关系。
python
class PartialOrderPlan:
def __init__(self, initial, goal, actions):
self.initial = initial
self.goal = goal
self.actions = actions
self.plan_steps = []
self.ordering = []
self.causal_links = []
self.open_preconds = set(goal)
def refine(self):
if not self.open_preconds:
return True
precond = self.open_preconds.pop()
for action in self.actions:
if precond in action.add_effects:
self.plan_steps.append(action)
self.open_preconds.update(action.preconds)
self.causal_links.append((action, precond))
if self.refine():
return True
self.plan_steps.pop()
self.open_preconds.add(precond)
return False
def get_plan(self):
return self.plan_steps if not self.open_preconds else None
pop = PartialOrderPlan(
initial={'At(Home)', 'Has(Keys)'},
goal={'At(Work)', 'Has(Keys)'},
actions=[
STRIPSAction('Drive', {'At(Home)', 'Has(Keys)'}, {'At(Work)', '~At(Home)'}),
STRIPSAction('Walk', {'At(Home)'}, {'At(Work)', '~At(Home)'}),
]
)
pop.refine()
plan = pop.get_plan()
print(f"偏序规划: {[a.name for a in plan] if plan else '无解'}")2.5 规划中的启发式
python
def delete_relaxation_heuristic(state, goal, actions):
relaxed_actions = []
for action in actions:
relaxed = STRIPSAction(action.name, action.preconds,
list(action.add_effects))
relaxed_actions.append(relaxed)
from collections import deque
frontier = deque([(set(state), 0)])
visited = {frozenset(state)}
while frontier:
current, cost = frontier.popleft()
if set(goal).issubset(current):
return cost
for action in relaxed_actions:
if action.is_applicable(current):
new_state = current | action.add_effects
if frozenset(new_state) not in visited:
visited.add(frozenset(new_state))
frontier.append((new_state, cost + 1))
return float('inf')
# 测试启发式
state = {'At(Home)', 'Has(Keys)'}
goal = {'At(Work)'}
h = delete_relaxation_heuristic(state, goal, problem.actions)
print(f"删除松弛启发式值: {h}")三、实战案例
2.1 案例一：物流规划
python
def create_logistics_problem():
actions = [
STRIPSAction('Load(P1,T1,Airport1)',
{'At(P1,Airport1)', 'At(T1,Airport1)'},
{'In(P1,T1)', '~At(P1,Airport1)'}),
STRIPSAction('Fly(T1,Airport1,Airport2)',
{'At(T1,Airport1)'},
{'At(T1,Airport2)', '~At(T1,Airport1)'}),
STRIPSAction('Unload(P1,T1,Airport2)',
{'In(P1,T1)', 'At(T1,Airport2)'},
{'At(P1,Airport2)', '~In(P1,T1)'}),
]
initial = {'At(P1,Airport1)', 'At(T1,Airport1)'}
goal = {'At(P1,Airport2)'}
return PlanningProblem(initial, actions, goal)
logistics = create_logistics_problem()
solution = forward_state_space_search(logistics)
print(f"物流规划解: {[a.name for a in solution] if solution else '无解'}")3.2 案例二：机器人装配规划
python
def create_assembly_problem():
actions = [
STRIPSAction('Pick(A)', {'At(Robot,A)', 'Free(Robot)'},
{'Holding(A)', '~Free(Robot)', '~At(Robot,A)'}),
STRIPSAction('Place(A,Base)', {'Holding(A)', 'At(Robot,Base)'},
{'On(A,Base)', 'Free(Robot)', '~Holding(A)'}),
STRIPSAction('Pick(B)', {'At(Robot,B)', 'Free(Robot)'},
{'Holding(B)', '~Free(Robot)', '~At(Robot,B)'}),
STRIPSAction('Place(B,A)', {'Holding(B)', 'On(A,Base)'},
{'On(B,A)', 'Free(Robot)', '~Holding(B)'}),
STRIPSAction('Move(A)', {'At(Robot,_)'}, {'At(Robot,A)', '~At(Robot,_)'}),
STRIPSAction('Move(B)', {'At(Robot,_)'}, {'At(Robot,B)', '~At(Robot,_)'}),
STRIPSAction('Move(Base)', {'At(Robot,_)'}, {'At(Robot,Base)', '~At(Robot,_)'}),
]
initial = {'At(Robot,A)', 'At(Robot,B)', 'Free(Robot)', 'At(Robot,Base)'}
goal = {'On(B,A)', 'On(A,Base)'}
return PlanningProblem(initial, actions, goal)
assembly = create_assembly_problem()
solution = forward_state_space_search(assembly)
if solution:
print(f"装配规划解 ({len(solution)} 步):")
for i, a in enumerate(solution):
print(f" {i+1}. {a.name}")四、本章小结
本章介绍了自动规划的核心概念和方法。经典规划使用 STRIPS 语言描述问题，通过前向搜索、后向回归或规划图来求解。HTN 规划通过任务分解处理复杂问题，偏序规划使用最小承诺策略减少搜索。
核心知识点回顾：
- STRIPS 语言用前提条件和效果描述行动
- 前向搜索从初始状态出发，后向回归从目标出发
- 规划图表示行动的并行性和互斥关系
- HTN 通过层次分解处理复杂任务
- 偏序规划推迟顺序决策
五、思考与练习
思考题
规划的复杂性：经典规划问题是 PSPACE 完全的，这意味着什么？在实际中我们如何应对？
不确定性规划：当行动效果不确定时（如"移动"可能失败），如何制定稳健的计划？
编程练习
实现 Graphplan：完整实现规划图构建和计划提取算法。
HTN 规划器：实现一个 HTN 规划器，用于解决"准备出门"的任务（找钥匙、穿鞋、开车等）。
调度问题：用规划方法解决作业车间调度问题。