989426-人工智能基础-第五章

第五章 自动规划
规划是人类生产和社会活动的重要形式。 规划旨在为活动实体（人、组织、机器）设计合理的行为——按时间顺序
的活动序列。 从知识工程的角度，自动规划是综合和构造型问题求解任务。 规划问题处理的对象是动作，而约束动作的主线是时间顺序。 经典的自动规划技术：
经典规划技术的发展， 规划的基本概念， 早期的自动规划技术， 部分排序规划技术；
积木块世界中有三个积木块：A、B、C， 机器人只有一个机器手，且每次只能拿起一个积木块。
1 状态
在一个给定的时间点对于世界的一个快照。 二元约束T——描述某个状态S下关于世界的特性， 特性用谓词公式加以表示——On、Clear和Table。 积木块世界的某个状态S1（见图5.2）：
{T(On(A，B), S1), T(On(B,C), S1), T(Clear(A), S1), T(Table(C), S1)} 目标状态的非唯一性。
T(On(x, y), s) ∨ T(Clear(x), s) ∨ T(Clear(y), Do(U(x, y), s))}
而相应于 U(x, y)的一条框架公理的子句则表示为：
T(On(u, v), s) ∨ (u ≠ x) ∨ T(On(u, v), Do(U(x, y), s))
若将 u ≠ x 视为作一个附加检查，则该子句简化为：
指出动作（操作符实例）执行的条件，
指出执行后新成立的事实（状态特性描述），
未指出操作前后保持不变的事实（事物间的关系）。
图5.3例，规划结果的执行，事实Clear(A)和
Table(C)始终不变。 [U(A, C), S(B, C), S(A, B)]
框架公理：
刻画一个状态描述中不由动作改变的方面；
T(On(u, v), s) ∨ T(On(u, v), Do(U(x, y), s))
Green 方法的应用:
1） 例 1（图 5.4(a)）
初始状态 So:{ T(Clear(A), So),
T(On(A, B), So),
T(On(B, C), So),
T(Table(C), So)}
目标状态ρ: {T(Table(A),ρ)} Goal(ρ)
Do: A X S S， A和S分别指示动作集和状态集； Do(a. s)指示下一状态。
2 动作
关于操作符的规则——形式地描述操作符的激活条件和其执行对于世界的 影响：
U: T(On(x, y), s) ∧ T(Clear(x), s)
T(Table(x), Do(U(x, y), s))∧T(Clear(y), Do(U(x, y), s))；
NOAH系统和目标回归方法——开拓了基于部分计划集的搜索技术， 能解决所有的经典规划问题——通过层次规划和非线性规划， 未得到广泛的应用——大量实际规划问题并不遵从经典规划问题的假设。
开拓非经典的实际规划问题（八十年代中期后）：
为消除规划理论和实际应用间存在的差距， 部分排序规划技术仍是开发规划新技术的基础。
（x）（s）{T(Table(x), s) (y)T(On(x, y), s)}
例子：
检查规划过程中的中间状 态是否为不合法状态，支 持搜索路径的修剪。
（y）（s）{T(Clear(y), s) (x)T(On(x, y),s)}
（x）（y）（z）（s）{T(On(x, y), s) ∧ y ≠ z T(On(x, z), s)}
1 GPS
U(x,y) S(x,y) M(x,y,z)
基本方法——针对规划的目标状态与初始状
Clear( y ) √
态间的差别来寻找能直接消除差别的动作：
Table( x ) √
建立领域相关的程序去检查状态差别，
On(x, y)
设计操作符-差别表去记载各操作符能消除的差别。
积木块世界动作规划例（自己看）。
研究新的方法——不求助于显式表示的框架公理，也能解决框架问题。 5 计划
规划的结果，表示为动作序列γ； γ∈Γ， Ω|= Do(γ, σ), 使得ρ= Do(γ, σ)。
图5.3规划问题推导出的动作序列： γ= [U(A, C), S(B, C), S(A, B)]。
5.1.3.早期的自动规划技术
“框架”的取名——来自对动画片制作的比拟：
动画片往往若干个画面具有相同的背景，只需
制作不同的前景；
关于操作符的规则定义——制作动画片的前景，
背景用所谓的框架公理加以表示。
Unstack操作符的框架公理，参见书上
指示积木块世界的相应属性在U操作执行的前后保持不变。
4 框架问题
利用框架公理的优缺点： 使规划系统仅用简单的推理机制（例如归结反演），就能实现自动规 划； 大量框架公理的引入将使规划效率大幅度下降； 所需框架公理的数目是状态特性描述谓词的个数与操作符个数的乘积。
Do(S(A, B), Do(S(B, C), Do(U(A, C), s))）
把单一动作从动作序列中分离出来加以处理， 应用于Green方法
3 数据库（也称知识库）
规划的初始状态 目标状态 操作符 逻辑操作公理：
逻辑操作公理： （P）(s){T(P, s) T(P, s)} （P）（Q）（s）{T(P ∨ Q, s) (T(P, s) ∨ T(Q, s))}
证明过程（其中 Ans(a)用于指示动作序列 a 的提取）：
（γ）Goal(Do(γσ))
1、{Goal(Do(a, So)), Ans(a)}; (a)Goal(Do(a, So))
2、{T(Table(A), Do(a, So)), Ans(a)};与“T(Table(A), ρ)∨Goal(ρ)”
On(x, z)
√√ √
缺点——难以解决子问题具有交互作用的复杂问题： 要消除的各个差别往往并非独立，具有一定的交互作用；
依赖大量启发式知识的引入。
2 Green方法
基于状态演算的规划器，格林（Green），1969年，为仿真机器人构造动作计划。
基本方法：
从计划存在语句（γ）Goal(Do(γσ))出发，证明存在一个正确的计划γ，
差别的消除只有通过执行适当的动作来实现。 启发式知识：
预测动作序列的长度， 抑制框架公理的应用（优先使用相应于操作符规则的子句）， 及时实现状态同一（框架公理的主要用处）， 及时发现和修剪不可达状态。
积木块世界动作规划例： 参见书上
规划过程用花括号收集归结式， 谓词公式间的逗号隐含着“析取”。
T(Clear(u), s) T(Clear(u), Do(U(x, y), s))
4 框架问题
T(Table(u), s) T(Table(u), Do(U(x, y), s)) T(On(u, v), s) ∧ u ≠ x
操作符的规则定义具有不完备性：
T(On(u, v), Do(U(x, y), s))
S: T(Table(x), s)∧T(Clear(x), s)∧T(Clear(y), s)∧x ≠ y
T(On(x, y), Do(S(x, y), s))；
关于操作符M的规则留给读者自行建立。
[U(A, C), S(B, C), S(A, B)]
动作序列——规划的结果，以方括号括起，称为动作块（图5.3）。
5、{Ans(U(A, B))}; 与初始状态描述 T(Clear(A), So)归结
规划的结果是由单一动作构成的动作块[U(A, B)]。注意，规划过程用花括号收集
归结式，谓词公式间的逗号隐含着“析取”。
1） 例 2（图 5.4(b)） 证明过程： 1、{Goal(Do(a, So), Ans(a)}; 2、{T(Table(B), Do(a, So)), Ans(a)}; 3、{T(Table(B), Do(c, Do(b, So))), Ans([b, c])}; 令 a = b.c(或[b, c]), 应用 5.1.2 节中的动作块公理 4、{T(On(B, y), Do(b, So)), T(Clear(B), Do(b, So), Ans([b, U(B, y)])); 与相应于 U(x, y)规则的前一子句归结，且有 B/x, U(B, y)/c, Do(b, So)/s 5、{T(On(B, y), Do(U(x, B), So)), T(On(x, B), So), T(Clear(x), So), Ans([U(x, B), U(B, y)])}; 与相应于 U(x, y)规则的后一子句归结， 且有 B/y, U(x, B)/b, So/s 6、{T(On(B, y), So), T(On(x, B), So), T(Clear(x), So), Ans([U(x, B), U(B,y)])}; 应用相应于 U(x, y)框架公理的子句作归结，实现状态同一(使花括弧中的状态描 述相应于同一状态，Do（U(x, B), So）指示了 So 的下一状态)。 7、{T(On(x, B), So), T(Clear(x, So), Ans([U(x, B), U(B, C)]); 与初始状态描述 T(On(B, C),So)归结，且有 C/y 8、{T(Clear(A, So), Ans([U(A, B), U(B, C)]); 与初始状态描述 T(On(A, B), So)归结， 且有 A/x 9、{Ans([U(A, B), U(B, C)])}; 与初始状态描述 T(Clear(A), So)归结
5.1.2. 规划的基本概念
总体描述：
用状态空间表示法来描述规划： 设计一个动作序列（也称为动作块），使得通过执行该动作序列，可以将 系统从初始状态转变为目标状态。
自动规划系统由规划器和执行器二个部分构成（图5.1）。 引入五个方面的基本概念：状态、动作、数据库、框架问题和计划。 玩具世界——积木块世界中的机器人动作规划：
将二元约束T中的状态特性 描述化简为仅是原子谓词