经典的规划
##### 特征
完全可观测:Fully Observable
唯一已知初始状态:a unique known initial state
静态环境:static environments
确定性动作:deterministic actions
每次仅一个动作:can be taken only one at a time
单一智能体 a single agent
规划问题的难度取决于以下问题
| Properties 特性 | Questions 问题 |
|---|---|
| actions | 确定还是非确定性问题？是否持续一段时间，可并发执行还是串行 |
| state variables状态变量 | 离散还是连续 |
| 初始状态 | 有限还是任意多 |
| 目标 | 要达到指定的目标状态？/要最大化回报函数 |
| 智能体 | 仅一个angent还是多个/合作还是单人做 |
问题求解与规划Agent的比较
| 问题求解Problem-solving Agent | 规划智能体Planning Agent | |
|---|---|---|
| state(初始/目标) | Atomic representation原子表示 | Factored representation 因子表示 (变量的集合) |
| Action | Instantiated actions | Actions schemas 动作模式，使用PDDL规划定义语言 |
| Heuristic | Domain-specific领域特定启发发 | Domain-independent领域无关启发法 |
PDDL语言
PDDL定义规划语言中的三要素
1.状态：
表示为变数的合取，是一种conjunction of fluents的形式(从一个变化关系到另一种变化关系)
2.动作：
用一组动作模式描述，隐式定义函数，是一种action schema
3.目标
使用文件的合取，一个基本的命题，conjunction of literals
实例 航空运货
1.问题 from SFO to JFK从旧金山到纽约机场
2.动作
Load、unload、fly
3.谓词Predicates
In(c,p)获取在飞机内
At(x,a)获取在机场内
简单的例子
Solution解答
能够达到目标的动作序列
[Load(C1,P1,SFO),Fly(P1,SFO,JFK),Unload(C1,P1,JFK),Load(C2,P2,JFK),Fly(P2,JFK,SFO),Unload(C2,P2,SFO)]
错误的动作
不能从起飞的地方飞到起飞的地方
Fly(P1,JFK,JFK)
矛盾的作用
一个获取在一个
At(P1,JFK)^~At(P1,JFK)
经典规划搜索
1.前向计算搜索
2.反向状态空间搜索
3.启发式搜索
将规划问题视作一个图，其中节点表示状态、边为动作，寻找一条连接初始状态到达目标状态的路径
问题的简化方式:增加边、状态抽象(多个节点组成在一起)
图规划算法
规划问题转化
1.布尔可满足规划
2.一阶逻辑推理的规划
一阶逻辑中的情景演算，用来设计动态域的表示和推理。
3.将规划化作约束满足的规划
约束可满足和布尔可满足有一定的共性，其对调度问题很有效，将有界的问题进行编码为CSP，还可以将规划图编码为CSP
4.将规划问题化作精进的规划
全序规划是由严格的动作序列组成，该问题忽略了许多子问题是独立的事实。
经典规划的局限性
经典规划可以表示做什么？按什么顺序做?等问题，但是对于动作持续多长时间、什么时候发生？这样的问题不能描述。
分层规划
多智能体规划
多个agent与单个agent之间的比较问题
多个agent之间设计的特性
机器人中的规划问题
多个agent规划之间涉及的组件
协商规划问题
决策理论规划
马尔科夫决策过程
经典规划与MDP的比较
MDP问题的优化与效用
值迭代
策略迭代
