动机
一批效果有用的行动,尚未构成计划。每个行动开始时前提必须成立,之后的行动也不能破坏较后步骤需要的事实。同一批行动换个次序,就可能由成功变失败。规划因此既要找谁产生事实,也要保护事实到使用之时。
状态空间搜索每步承诺一个完整后继状态;计划空间搜索则细化行动出现及次序约束,把暂不重要的顺序押后决定。一个偏序可同时表示多个合法顺序,但其因果承诺要仔细验证。没有指定先后,并不自动表示能在物理上同时执行。
本节沿用有限、确定、正前提 STRIPS,再给两套有明确假设的完备算法:有限状态图的广度优先搜索,以及在指定行动数上界内完备的偏序细化。
定义
定义 6.1.1
(STRIPS 规划问题与状态转移)
设有限命题集 、初始状态 、正目标 及有限基项行动集 。行动有正前提、互斥的加入与删除集;可用时后继为 。最短长度结果假设每个行动成本为一。可能状态至多 个,其中一些根本不可达。
定义 6.1.2
(行动出现与偏序计划)
行动出现指某一个特定步骤,同一基项行动可在计划出现多次。偏序计划含有限出现、严格无环先后关系,以及两特殊步:Start 加入恰好 且无前提;Finish 以前提 作检查且无效果。Start 先于 Finish 及所有普通步,普通步先于 Finish。线性化是延伸所有先后约束的全序。
定义 6.1.3
(因果链接、威胁与开放条件)
因果链接 声称 建立 所需的 ,且中间保持它。要求 、、。步骤 若删除 ,而次序未强制 或 ,便威胁此链接。两种排除把删除者放在受保护区间之外。尚无支持链接的前提出现,称为开放条件。不能用 :行动后才产生的效果不能支持自己行动前的前提。
定义 6.1.4
(完整受保护计划)
完整受保护计划没有开放条件,所有链接均无威胁,且次序无环。它是可验证证书,但可有多余行动或链接;最小性另论。其语义只保证合法顺序执行,不包含持续时间、同时动作及资源容量。
定理/命题
定理 6.1.5
(有限状态图上的最短长度完备搜索)
由 广度优先搜索,产生每个可用基项行动,并在入队时只记录每个状态一次,便会终止。若目标可达,返回行动数最少的计划;否则报失败。状态键必须保留所有会影响可用性及效果的事实。
定理 6.1.6
(受保护计划与有界细化完备性)
完整受保护计划的每个线性化都可执行并达到 。对有限上界 ,下述穷尽细化程序会终止,且恰在存在至多 个普通行动的有效计划时成功。完整性要求尝试每种行动指定、支持者及相容威胁解法;一条贪心细化路径不足。
证明思路
证明
(广度优先次序与最短路径)
广度优先先把 入队、标为已访。反复取最早入队状态,检查目标,并计算每个可用行动的后继。后继未访才入队,同时标记并保存前驱状态与行动;取出目标时倒追前驱重建序列,队列空则失败。
按图距离归纳,距离 的状态必先于新发现距离 的状态取出。若某可达状态遗漏,取它最短路的前驱,前驱已被生成,最后合法行动便会生成它,矛盾。故首个取出的目标距离最小。最多 个状态入队,加上每步有限工作,便证终止。
证明
(受保护计划的可靠性)
偏序可靠性取任一线性化,依步骤归纳。下一步 的每个前提 均有较早 的支持链接。Start 建立相应初始事实,普通支持者执行后建立加入效果;所有会删 的其他步均被安排在 之前或 之后,所以没有中途删除。故执行 前 仍真,所有前提都成立。套到 Finish 即得所有目标。
证明透视
因果链接证明一段区间内的持续性
支持者只证事实在某时成立,威胁保护则证它在使用前不被破坏,缺一不可。可靠性不要求所有事实永远保持,只保护计划真正需要的各个时间区间。这比一句含糊的“行动不会互相影响”更准确。
有界程序如下。对每个 建立 个标记普通出现,穷举把基项行动指定给它们的所有方式。先加 Start、Finish 的基本次序,把普通步全部前提及 Finish 目标放入开放议程。选 ,对所有能加入 且不是 的出现 (包括 Start)分支,加 及链接,再移除该开放条件;次序成环便丢弃分支。对威胁 ,再分别尝试 或 ,同样弃环。继续至条件与威胁清空,或所有分支失败。
证明
(有界细化的终止性与完备性)
指定方式与前提出现均有限。每次选支持者永久减一个开放条件,每次解威胁加入一个先前未被强制的先后关系,且不再撤除。步骤对有限,所以每枝长度及分支数均有限,穷尽程序终止。成功分支的拓扑序由可靠性给可执行计划。
要证完整,假设有 不超 的有效序列,某种指定必包含恰好这些出现。每个前提选最近的较早加入者,若从初始一直保持则选 Start。有效性保证有支持者,且中间没有删除;若有重加者,它才是更近支持者。每个威胁依见证序列放在支持前或使用后。所有约束均符合该序列,故不成环,此枝会完成。上界不可略: 为三的失败只否定三步内计划,不否定更长计划。
例题详解
例题 6.1.7
(最短计划可先破坏已达目标)
初始 表示有蛋糕,目标 要求有蛋糕且吃过。Eat 要求 ,加入 ,删 ;Bake 无前提,只加入 。空计划与任何单步都失败。Eat 再 Bake 依次得 、,两步成功。Bake 再 Eat 则最后删掉 而失败。已为真的目标可能必须暂时放弃。
例题 6.1.8
(威胁解法决定有用次序)
用 Start 支持 Eat 的 ,Eat 支持 Finish 的 ,Bake 支持 Finish 的 。Eat 删 ,威胁 Bake Finish。Finish 在 Eat 前不合法,只能令 Eat 在 Bake 前,得成功序列。若试以 Start 直接支持 Finish 的 ,Eat 的两种排除都违反 Start、Finish 基本次序,此枝应失败。
概念视角组合
计划是一组线性延拓
受保护计划描述的是一整组动作序列:可执行的次序恰是延拓优先关系的全序,即该偏序的线性延拓。在蛋糕计划中,“先吃后烤”的约束只留下一个序列。若有 个普通步骤而彼此没有约束,便有 个序列,受保护计划保证它们全部有效。每多一条因果或威胁约束,就减少一部分这种灵活性。
例题 6.1.9
(独立子目标不用任意排序)
初始 。A 要求 并加 ,B 要求 并加 ,皆不删事实,目标 。由 Start 各支持 ,A、B 各支持 Finish 的目标,便得无须比较 A、B 的完整计划。A,B 与 B,A 都合法。但单一机器可能有未建模共享资源禁止重叠,两个合法顺序不等于可同时做。
常见错误
反例模式
有用行动可破坏彼此前提
初始 。A 要求 ,加 并删 ;B 要求 并加 ,目标 。Start B 被 A 威胁,只能令 B 先于 A,因 A 不能先于 Start。A 再 B 会在 B 的前提失败。因此只有行动名称集合不足以证计划。
常见错误
(把删除集当作全部变化)
框架问题在此模型内有局部答案:删除集外事实保持。但这依赖描述已包含所有相关变化。若开锁通过间接机制关掉警报,而警报影响未来,就要把效果表示出来,或明订扩充语义推导;规划器不会自动发现物理定律。
常见错误
(只对直接边检查威胁)
威胁检查必须使用传递关系。若多条约束已蕴涵 ,即使没有直接边也已排除威胁;多步隐藏环同样无效。需要可达性或拓扑检查,不能只看新边两端。
常见错误
(把完备性当作对真实任务的保证)
完备性亦假设相关行动全部已基项化并生成;缺少行动库可令真实有解而模型失败。信息收集、不确定性、时间及资源都是此模型外的重要问题。
总结
广度优先给有限完备基准及最短行动数。因果链接说谁建立所需事实,威胁解决保护它到使用。穷尽有界细化之所以完备,是因每个界内有效见证都有相容分支。次序、持续性及模型充分性,各自需要论证。
练习
练习 6.1.10
(在蛋糕例题中列出由 可达的所有状态,并说明广度优先搜索只保存状态而非每段行动历史,为何不失完整性。)
核心
解答(3)
- 1
列出可达状态
在 时 Bake 不改变状态,Eat 得 。由 出发,Bake 得 ,Eat 不可用。由 出发,Eat 回到 ,Bake 不变。可达状态为 、 与 。
- 2
论证状态已足够
关键一步
两段历史若终于同一状态,之后可行的延续完全相同,因为可用性与效果只依赖状态。
依据: 状态包含全部可用性及效果的信息。
- 3
保留首段历史
保留广度优先搜索到达每个状态的首段历史,就保留了到该状态的最短路径,所以丢弃其后的历史既不损失完整性,也不损失最短长度。
练习 6.1.11
(对常见错误的例子,给出成功的受保护计划的全部因果链接及一个线性化,并指出威胁及唯一一致的解法。)
核心
解答(3)
- 1
列出因果链接
使用 Start B、Start A、A Finish 及 B Finish。
- 2
找出威胁及解法
关键一步
A 删除 ,所以威胁链接 Start B。A 先于 Start 不可能,因为 Start 先于所有步骤,所以只剩 B 先于 A。A 的删除不威胁它自己的入链接,因为前提先测、效果后施。
依据: A 删除 ,而 B 需要来自 Start 的 。
- 3
写出一个线性化
合法顺序 B,A 同时达成 和 。
练习 6.1.12
(设 是链接,而相异的删除步 已被约束为 。证明两种一般威胁解法都不能成功。更换因果链接后,什么新支持可能修复计划?)
综合证明
解答(3)
- 1
尝试第一种解法
解法 要加到已有的约束 之上。
- 2
尝试第二种解法
关键一步
解法 要加到已有的约束 之上。两种解法各自形成两条约束的环,所以两枝都被弃去。
- 3
考虑修复
∎若有行动 能在 与 之间重新加入 ,把链接换成 便可能修复支持,条件是 本身的前提有支持,且所有新威胁都获解决。这是选新支持者的另一枝,不是忽略旧威胁。
练习 6.1.13
(若有界细化程序在 穷尽所有分支都失败,证明了什么?说明递增上界一般为何只给半判定程序,以及在本节假设下,有限状态搜索为何有更强的、会终止的判定程序。)
综合
解答(3)
- 1
说明失败证明了什么
在穷尽生成且检查正确的前提下,它否定零、一、二个普通行动的所有计划,但不能否定更长的计划。
- 2
描述半判定程序
逐一尝试递增的有限上界,若有有限计划就终会找到,但若无计划,单凭此法没有停止准则。
- 3
与有限状态搜索比较
广度优先搜索穷尽有限状态图,因此能证明失败。事实上,任何可达目标都有至多 步的简单状态路径,用此上界也能有限穷尽,只是成本通常极大。
依据: 在有限命题的假设下,状态图是有限的。