第11章 现实世界的规划与行动

第11章 现实世界的规划与行动

本章中我们将看到更有表达能力的表示和更具交互性的 Agent 结构是如何通向在现实世界中有用的规划器的。

前一章介绍了规划中的最基本概念、表示和算法。在诸如为宇宙飞船、工厂、军事行动的制订调度安排的现实世界任务中使用的规划器更加复杂；它们扩展了表示语言和规划器与环境的交互方式。本章将说明这是如何实现的。11.1 节扩展了经典规划语言来讨论有时间和资源约束的动作。11.2 节描述了分层次构建规划的方法。这允许人类专家告诉规划器他们知道如何求解问题。有效的规划构建也需要借用层次，因为规划器能在深入细节之前在抽象层次求解问题。11.3 节提出了能够处理不确定环境的、思考与执行能够交叠的Agent体系结构。11.4 节展示了当环境包含其他Agent时如何规划。

11.1 时间、调度和资源

经典规划表示讨论了做什么、按什么顺序，但它不能讨论时间：动作持续多久或者甚至动作何时发生。例如，第10章的规划器能为航班制定调度，哪架飞机分配到哪次航班，但我们实际上需要同时知道出发时间和达到时间。这是调度（scheduling）的主要问题。真实世界也有许多资源约束（resource constraints）；例如一个航班有有限数量的乘务员——同时一个航班的乘务员不能同时在另一个航班上。这一节讨论表示和求解问题的方法，包括时间和资源约束。

本节我们采用的方法是“无规划，后调度”：也就是说，我们把整个问题分解为一个规划阶段和一个接下来的调度阶段，在规划阶段选择动作，考虑次序约束，满足问题的目标，在调度阶段时间信息加入到规划中以满足资源和期限约束。

在真实世界的加工和逻辑设置中规划阶段经常是由人类专家来做的，这种方法很常见。第10章的自动方法能够用于规划阶段，只要它们生成正确性要求的具有最小次序约束的规划。GRAPHPLAN（10.3节）、SATPLAN（10.4.1节）以及偏序规划器（10.4.4节）能够胜任该任务；基于搜索的方法（10.2节）生成全序规划，但这些规划容易转换为具有最小次序约束的规划。

11.1.1 表示时间和资源约束

如 6.1.2 节所述，一个典型的车间调度问题（job-shop scheduling problem）由一组工作（jobs）组成，每个工作由一组具有次序约束的动作（actions）组成。每个动作有一个持续时间（duration）和一组动作所要求的资源约束。每个约束规定了一种资源（例如螺栓、扳

手、或导航仪）以及该资源的数量以及该资源是否是消耗品（例如螺栓不能再次使用）或可重用（例如一个航班使用一个导航仪，该航班使用结束后导航仪以后还能用）。具有负消耗的动作也能产生资源，包括加工、生长、再补给等动作。车间调度问题的解必须规定每个动作的开始时间，而且必须满足时间次序约束和资源约束。至于搜索和规划问题，可以根据一个代价函数来评估解；在具有非线性资源代价、时间相关延迟代价等时，这可能很复杂。为了简化，我们假设代价函数就是规划的全部时间，称为完工时间（makespan）。

图 11.1 给出了一个简单例子：一个组装两辆汽车的问题。该问题由两个工作组成，每一个形式为 [AddEngine, AddWheels, Inspect]，语句 Resources 声明有四种资源，给出开始时每种资源的数量：1 个引擎起重机、1 个车轮静电干扰、2 名检查员、500 个螺母。动作模式给出每个动作的时间和资源需求。当车轮加到汽车上时会消耗螺母，而其他资源在一个动作开始时被借用，动作结束后被释放。

Jobs({AddEngine1 <AddWheels1 <Inspect1},

{AddEngine2 <AddWheels2 <Inspect2})

Resources(EngineHoists(1), WheelStations(1), Inspectors(2), LugNuts(500))

Action(AddEngine1, DURATION:30,

USE:EngineHoists(1))

Action(AddEngine2, DURATION:60,

USE:EngineHoists(1))

Action(AddWheels1, DURATION:30,

CONSUME:LugNuts(20), USE:WheelStations(1))

Action(AddWheels2, DURATION:15,

CONSUME:LugNuts(20), USE:WheelStations(1))

Action(Inspecti, DURATION:10,

USE:Inspectors(1))

用数量表示资源——例如 Inspectors(2)，而不是用命名实体，如 Inspector( $ I_{1} $) 和 Inspector( $ I_{2} $)——是非常通用的、称为集成（aggregation）的技术的一个实例。集成的中心思想是：相对于手头的任务目标，当各单个对象无法区分时将它们组合成数量。在我们的组装问题中，哪位检查员检查汽车并不重要，因此不需要区分。（同样的思想在习题 3.9 的传教士与食人者问题中也是有效的。）集成对于降低复杂性是很关键的。当一个调度有 10 个并发的 Inspect 动作但只有 9 个检查员时，会发生什么。检查员表示为数量，马上会检测到失败，算法会回溯以尝试其他调度。如果检查员表示为个体，算法会回溯以尝试将检查员分配到动作的 10 种方法。

11.1.2 求解调度问题

我们从只考虑时间调度问题开始，忽略资源约束。为了最小化完工时间，我们必须找到所有动作与问题的次序约束一致的最早开始时间。将这些次序约束视为与动作相关的有向图是有帮助的，如图11.2。我们可以使用关键路径方法（critical path method）来确定每个动作可能的开始和结束时间。穿过表示偏序规划的图的一条路径是动作的线性次序，以

Start 开始，以 Finish 结束。（例如，图 11.2 中的偏序规划有两条路径。）

关键路径是时间跨度最长的路径；它是关键的是因为它决定了整个规划的时间长度——缩短其他路径并不会缩短整体规划，但延误关键路径上的任一动作的开始时间就会延长整个规划的时间。不在关键路径上的动作有个时间窗口，可在这个窗口里执行动作。用最早可能开始时间 ES 和最晚可能开始时间 LS 来指定这个窗口。LS-ES 被称为动作的松弛。在图 11.2 中我们可以看到整个规划需要 85 分钟，最顶上的工作中的每个动作有 15 分钟松弛，关键路径中的每个动作没有松弛（由定义）。所有动作的 ES 和 LS 时间一起构成问题的调度。

下面的公式可以作为 ES 和 LS 的定义以及计算它们的动态规划算法的轮廓。A 和 B 是动作， $ A \prec B $ 表示 A 在 B 之前：

$$ \begin{aligned}&ES(Start)=0\\&ES(B)=\max_{A\prec B}ES(A)+Duration(A)\\&LS(Finish)=ES(Finish)\\&LS(A)=\min_{B\succ A}LS(B)-Duration(A)\\ \end{aligned} $$

思路是我们从把 ES(Start)赋值为 0 开始。然后一旦我们得到一个动作 B，所有直接出现在 B 之前的动作的 ES 都已经赋过值，我们就可以设 ES(B)为那些直接前驱动作的最早完成时间的最大值，其中一个动作的最早完成时间定义为最早开始时间加上持续时间。这个过程重复进行直到每个动作被赋予一个 ES 值。LS 值用类似的方式计算，从 Finish 动作反向进行。

关键路径算法的复杂度仅仅是 O(Nb)，其中 N 是动作的个数，b 是进入或离开动作的最大分支因子。（为了了解这点，注意对每个动作的 LS 和 ES 只计算一次，每次计算最多在 b 个其他动作上迭代）。因此，给定一个动作的偏序，寻找最小持续时间调度的问题是很容易的。

数学上，关键路径问题容易求解是因为它们被定义为在开始和结束时间的线性不等式的合取。当引入资源约束，开始和结束时间上的约束将变得更复杂。例如，AddEngine 动作——在图11.2的相同时间开始——需要相同的EngineHoist，因此不能重叠。“不能重叠”约束是两个线性不等式的析取，每个可能的次序一个。引入析取使有资源约束的调度是NP难的。

图 11.3 给出具有最快完成时间的解，115 分钟。这比没有资源约束情况下的规划所需的 85 分钟长 30 分钟。注意，没有同时需要两个检查员的情况，因此我们可以马上将其中一个检查员放到更有益的位置。

具有资源约束的调度的复杂性在实践与理论中经常遇到。1963年提出的一个挑战性的问题——为有10台机器、10件工作每个工作100个动作的问题找出最优调度——23年里都没得到解决（Lawler等，1993）。尝试了很多方法，包括分支限界法、模拟退火法、tabu搜索、约束满足、以及第3第4章中的其他方法。一个简单但很流行的启发式是最小松弛算法：在每次迭代，它考虑那些前辈都已经被调度安排而自身尚未调度的动作，并调度具有最小松弛的那个行动作为最早可能开始的。然后它更新每个受到影响的动作的ES和LS时间，并重复进行。启发式是基于与约束满足中的最大约束变量启发式一样的原理的。在实际应用中它通常工作得很好，但是对于我们的装配问题它产生了一个130分钟的解，而不是图11.3中的115分钟的解。

目前为止，我们假设了动作集合和次序约束是固定的。这些假设下，每个调度问题有一个避免所有资源冲突的、无重叠次序的解，只要每个动作本身是切实可行的。然而，如果一个调度问题是非常难的，这样求解可能是不错的想法——重新考虑动作和约束，只要能够导致更容易的调度问题。因此，在构建偏序规划中通过考虑时间和重叠来结合规划与调度是合理的。第10章中的一些规划方法可以扩展后处理这些信息。例如，偏序规划器使用通过因果链检测冲突相同的方法可以检测到违反资源约束。这是目前一个活跃的研究领域。

11.2 分层规划

前面章节的问题求解与规划方法都有一组固定的原子动作，动作可以串成一个序列或分支网络；最新的算法可以生成含有几千个动作的解。

对于人脑执行的规划，原子动作是肌肉活动。我们大约有 $ 10^{3} $ 块肌肉需要触发（数下来有 639 块，但其中许多有多个子单元）；我们每秒可控制它们的活动 10 次；我们活着并苏醒的时间大约 $ 10^{9} $ 秒。因此人的一生有 $ 10^{13} $ 个动作。即使我们限制自身在更短的时间水平上规划——例如在夏威夷两个星期的假期——详细的发动机规划包含大约 $ 10^{10} $ 个动作。这比 1000 多很多。

为了建立这个间隙的桥梁，AI系统可能不得不做人类似乎在做的事情：在更高抽象层次上规划。夏威夷假期的合理规划可能是“去旧金山机场；搭乘夏威夷11号航班去檀香山；度假两周；搭乘夏威夷12号航班回到旧金山；回家。”给定这样的规划，动作“去旧金山机场”本身就可看作是一个规划任务，其解像“开车去长期停车场；停车；搭巴士去航站楼。”进而，其中每个动作又可以继续分解，直到无需生成马达控制序列就可执行的动作层次。

在这个例子中，我们看到规划可以发生在执行规划之前和执行过程之中；例如，我们可能会延迟考虑从长期停车场中的停车点到巴士站的路径规划，直到执行过程中发现了特定的停车点。因此，这个特定的动作在执行阶段之前都保持在抽象层次。11.3 节我们再讨论这个问题。这里，我们集中于层次化分解，这是处理复杂性的普及性的思想。例如，复杂软件是从子过程或对象类的层次开始创建的；部队是以单元的层次来操纵的；政府和公司有部门和子部门以及分部办公室。层次结构的好处是，在每一层，一个计算任务（军事任务，或行政职能）分解为下一层少量的活动，因而，对于当前问题找到安排这些活动的正确方式的计算代价较小。另一方面，非层次化的方法将一个任务分解为大量的单个行动；对于大规模问题，这完全是不切实际的。

11.2.1 高层动作

我们理解层次化分解所采用的形式来自层次任务网络（hierarchical task networks）或HTN规划领域。像在经典规划（第10章）中一样，我们假设完全可观察性、确定性以及一组可用的动作，现在称为基元动作（primitive actions），基元动作具有标准的前提-效果模式。关键的额外概念是高层动作（high-level action）或HLA——例如，前面例子中的动作“去旧金山机场”。每个HLA有一个或多个可能的细化 $ ^{1} $（refinement）动作序列，其中每个动作可以是一个HLA或一个基元动作（无细化）。例如动作“去旧金山机场”表示形式为Go(Home,SFO)，可以有两种可能的细化，如图11.4所示。同一图中给出了吸尘器世界的导航的递归细化：为了去目的地，先走一步，然后去目的地。

Refinement(Go(Home,SFO)).

STEPS: [Drive(Home,SFOLongTermParking),

Shuttle(SFOLongTermParking,SFO)])

Refinement(Go(Home,SFO)).

STEPS: [Taxi(Home,SFO)])

Refinement(Navigate({a,b}, [x,y]),

SECOND: a = x ∧ b = y)

STEPS: [])

Refinement(Navigate([a,b], [x,y]),

SECOND: Connected([a,b], [a-1,b])

STEPS: [Left, Navigate([a-1,b], [x,y]]))

Refinement(Navigate([a,b], [x,y]),

SECOND: Connected([a,b], [a+1,b])

STEPS: [Right, Navigate([a+1,b], [x,y]]))

...

这些例子表明高层动作和它们的细化体现了如何做事的知识。例如，Go(Home,SFO)的细化说，为了到达机场，你可以开车，或者乘的士；不要考虑买牛奶、坐下、移动座位到e4等。

一个只包含基元动作的 HLA 的细化被称为 HLA 的实现（implementation）。例如，吸尘器世界中，序列 [Right, Right, Down] 和 [Down, Right, Right] 都实现了高层动作 Navigate([1,3],[3,2])。高层规划（HLA 序列）的实现是每个 HLA 的实现的拼接。给定每个基元动作的前提-效果定义，很容易确定高层规划的给定实现是否能达到目标。那么，可以说，一个高层规划能从给定状态达到目标，如果它的至少一个实现能从那个状态达到目标。定义中的“至少一个”是关键的——不是所有的实现都需要达到目标，因为 Agent 会决定执行哪个实现。因此，HTN 规划中的可能实现集合——每一个可能有不同的输出——与非确定规划中的可能输出结果集合是不同的。那里，我们为所有输出结果需要一个规划工作，因为 Agent 不会选择输出结果；大自然会选择。

最简单的情况是一个 HLA 恰好有一个实现。这种情况下，我们能够从该实现的前提和效果中计算出这个 HLA 的前提和效果（参见习题 11.3），然后这个 HLA 本身就可看作是一个基元动作。可以证明合适的 HLA 集合能够导致盲目搜索的复杂度从搜索深度的指数量级降到搜索深度的线性量级，尽管设计这样的 HLA 集合本身可能是一个琐碎的工作。当 HLA 有多种可能的实现时，有两种选项：一种是在这些实现中搜索一个可以有效工作的实现，像 11.2.2 节一样；另一种是直接对 HLA 推理——不管实现的多样性——像 11.2.3 节解释的一样。后一种方法可以派生出可证明正确的抽象规划，无需考虑它们的实现。

11.2.2 搜索基元解

经常用单个的称为 Act 的顶层动作来表示 HTN 规划，目的是要找到达到目标的 Act 的实现。这完全是一般性的方法。例如，经典规划问题能够如此定义：对于每个基元动作 $ a_i $，提供 Act 的一个细化 $ [a_i, Act] $。这建立了 Act 的递归定义，允许我们增加动作。但我们需要一些停止递归的方法；我们的方法是通过为 Act 提供另一个细化，步骤列表为空，前提等

于问题的目标。这就是说，如果目标已经达到，那么实现就不需要做任何事。

这种方法导致一个简单算法：反复在当前规划中选择一个HLA，用它的细化替换它，直到规划达到目标。图11.5给出了基于宽度优先树搜索的一种可能实现。将规划视为其细化按深度次序进行嵌套，而不是一些基元步骤。不难设计出该算法的图搜索版本以及深度优先和迭代加深版本。

function HIERARCHICAL-SEARCH(problem,hierarchy) returns a solution, or failure

frontier←→ a FIFO queue with [Act] as the only element

loop do

if EMPTY?(frontier) then return failure

plan←→ POP(frontier) /* chooses the shallowest plan in frontier */

hla←→ the first HLA in plan, or null if none

prefix,suffix ← the action subsequences before and after hla in plan

outcome ← RESULT(problem.INITIAL-STATE, prefir)

if hla is null then /* so plan is primitive and outcome is its result */

if outcome satisfies problem.GOAL then return plan

else for each sequence in REFINEMENTS(hla, outcome, hierarchy) do

frontier ← INSERT(APPEND(prefix, sequence, suffix), frontier)

本质上，分层搜索的这种形式探索序列空间，这些序列遵守包含在HLA库中的如何做事的知识。许多知识是可以编码的，不仅在每个细化规定的动作序列中，而且在细化的前提中。在某些领域中，HTN规划器能够生成大型规划，只要很少的搜索。例如，O-PLAN（Bell和Tate，1985）结合HTN规划与调度，已经用于日立的生产规划。有350个不同的产品、35台组装机器以及2000多个不同操作的生产线是一个典型问题。规划器生成30天的调度，每天8小时轮换，涉及数千万个步骤。根据定义，HTN规划的另一个重要方面是层次化的结构；这通常使人类容易理解它们。

通过考查一个理想情况可以看到分层搜索的计算方面的好处。假设一个规划问题有一个解具有 $d$ 个基元动作。对于一个非层次化的、每个状态有 $b$ 个可用动作的前向状态空间规划器，代价是 $O(b^d)$，像第 3 章解释的一样。对于一个 HTN 规划器，让我们假设一个非常一般的细化结构：每个非基元动作有 $r$ 个可能的细化，每个细化有 $k$ 个动作。我们想知道这个结构有多少不同的细化树。现在，如果在基元层有 $d$ 个动作，那么在根下方的层数是 $\log_k d$，因此内部细化结点数是 $1+k+k^2+\cdots+k^{\log_k d-1}=(d-1)/(k-1)$。每个内部结点有 $r$ 个可能的细化，因此可构建出 $r^{(d-1)(k-1)}$ 可能的分解树。考查这个公式，我们发现 $h$ 和 $k$ 可以导致大量的节省：特别是，当 $b$ 和 $r$ 可比较时，代价是非层次化的代价的 $k$ 方根。小 $r$ 和大 $k$ 意味 HLA 的细化数量少，每个细化有一个长的动作序列（虽然长，但允许我求解任何问题）。这并不总是可能的：可用于大量问题的长动作序列是很宝贵的。

那么 HTN 规划的关键是构建含有实现复杂高层动作的已知方法的规划库。构建这个库的一个方法是从问题求解经验中学习。在从无到有构建一个规划的惨痛经验之后，Agent 可以将这个规划保存在库中，作为实现任务所定义的高层动作一种方法。这种方式下，随着时间推移，在老方法之上建立新方法，Agent 可以变得越来越有能力。这个学习过程的一个重要方面是泛化所构建的方法的能力，消除与问题实例相关的细节（例如，建筑者的姓名或一块陆地的地址），而只保留规划的关键元素。第19章描述了实现这种泛化的方法。

似乎难以想象，人类没有这样的机制也能如此有能力。

11.2.3 搜索抽象解

前一节的分层搜索算法将 HLA 一路细化为基元动作序列以确定一个规划是否可行。这违背通常的感觉：我们应该能够确信有两个 HLA 的高层规划

[Drive(Home, SFOLongTermParking), Shuttle(SFOLongTermParking, SFO)]

无需确定精确路径、停车点等等就能让我们到达机场。解似乎是明显的：写出HLA的前提-效果描述，就像基元动作那样。从描述，不难证明高层规划能达到目标。因此说，这是分层规划的圣杯，因为如果得到的高层规划可证明能达到目标，在高层动作的小搜索空间中工作，那么我们可以致力于这个规划，对这个规划的每一步进行细化。我们的搜索得到指数量级的缩减。这能够有效工作必须是这种情况：每个声明能达到目标的高层规划在早些定义的意义上实际也能达到目标：它至少有一个实现能达到目标。这个特性被称为是HLA描述的向下细化特性（downward refinement property）。

写出满足向下细化特性的 HLA 描述原理上是容易的：只要描述是真的，那么任何声明能达到目标的高层动作实际上能达到目标——否则，描述会为 HLA 所做的事情做出错误的声明。我们已经看到如何为只有恰好一个实现的 HLA 写出真描述（习题 11.3）；当 HLA 有多个实现时就会出现问题。我们如何描述可以用许多不同方法实现的一个动作的效果？

一个保守答案（至少对于所有前提和目标为正的问题）是只包含 HLA 的每个实现都会获得的正效果以及任意一实现的负效果。那么，向下细化特性将会得到满足。不幸的是，HLA 的这种语义太保守。再次考虑高层动作（HLA）Go(Home,SFO），它有两个细化，为了论证，假设一个总可以开车到机场并在机场泊车而乘的士需要现金（Cash）作为前提的简单世界。这种情况下，Go(Home,SFO)并不总是能让你到达机场。特别是，如果 Cash 为假，这个 HLA 动作会失败，因此不能将 At(Agent,SFO)插入到这个 HLA 的效果中。然而，这毫无意义；如果 Agent 没有现金（Cash），它将会自己驾车。要求一个效果对每个实现都成立等价于假设另一个人——一个对手——将会选择这个实现。它处理 HLA 的多个结果的方式就好像 HLA 是非确定性的行动，像 4.3 节一样。对于我们的情况，Agent 自己会选择这个实现。

程序语言领域已经创造了术语魔鬼非确定主义（demonic nondeterminism）——为对手做选择的情况，与术语纯洁非确定主义（angelic nondeterminism）相对——其中 Agent 自己做选择。我们借用这个术语来为 HLA 描述定义纯洁语义（angelic semantics）。理解纯洁语义需要的基本概念是一个 HLA 的可到达集（reachable set）：给定一个状态 s，一个 HLA 的到达集 h，记为 REACH(s,h)，是这个 HLA 的任一实现可到达的状态集合。核心思想是当 Agent 执行这个 HLA 时它可以选择停在可到达集的哪个元素；因此，有多种细化的一个 HLA 比细化数少一些的同一个 HLA 更强大。我们也可以定义一个 HLA 序列的可到达集。例如，一个序列 $ [h_1,h_2] $ 的可达到集是 $ h_1 $ 的可到达集中的每个状态下应用 $ h_2 $ 得到的可到达集的并集：

$$ \mathrm{REACH}(s,[h_{1},h_{2}])=\bigcup_{s^{\prime}\in\mathrm{REACH}(s,h_{1})}\mathrm{REACH}(s^{\prime},h_{2}) $$

给定这些定义，一个高层规划——HLA 的一个序列——达到目标，如果它的可到达集与目标状态集有交集。（将这与魔鬼语义的更强的条件对比，魔鬼语义中可到达集的每个成员必须是一个目标状态。）相反，如果可到达集与目标不相交，那么规划一定不会工作。图 11.6 阐述了这些思想。

可达到集的概念形成了一个简单算法：在高层规划中搜索，找出一个高层规划其可到达集与目标相交；一旦找到，算法就致力于那个抽象规划，因为知道这个规划管用，并致力于将这个规划进一步细化。我们后面将回到这个算法的事项；首先，我们考虑一个HLA的效果——每个可能初始状态的可到达集——是如何表示的问题。这与第10章的经典动作模式一样，我们表示每个流（fluent）的变化。将一个流视为一个状态变量。一个基元动作可以增加或删除一个变量或保持变量不变。（有了条件效果（参见第11.3.1节）），就有第四种可能性：将一个变量翻转到其对立面。）

在纯洁语义下的一个 HLA 可做更多：可以控制一个变量的值，根据选择的实现将变量设置为真或假。实际上，一个 HLA 对一个变量可以有九种不同的效果：如果变量开始为真，可以保持它一直为真、或把它一直变为假、或进行选择；如果变量开始为假，可以保持它一直为假、或把它一直变为真、或进行选择；每种情况下的三种选项可以任意组合，得到九种结果。概念上，这有一些挑战。我们将使用符号~表示“可能，如果 Agent 这样选择。”因此，效果 $ \tilde{+}A $ 表示“可能增加 $ A $”，也就是说，或者保持 $ A $ 不变，或者使其为真。类似地， $ \tilde{-}A $ 表示“可能删除 $ A $”， $ \tilde{\pm}A $ 表示“可能增加或删除 $ A $。”例如，具有如图 11.4 所示两种细化的 HLA 动作 Go(Home,SFO)可能删除 Cash，因此它应该具有效果 $ \tilde{-Cash} $。因此，我们看到 HLA 的描述原理上是可以从它们的细化描述中推导的——事实上，如果我们想要为真的 HLA 描述以使向下的细化特性保持，就要求如此。现在，假设 HLA 动作 $ h_1 $ 和 $ h_2 $ 具有如下模式：

$$ \begin{array}{l}Action(h_{1},PRECOND:\neg A,EFFECT:A\land\neg B)\\ Action(h_{2},PRECOND:\neg B,EFFECT:\neg A\land\pm C)\end{array} $$

也就是说，$h_1$ 增加 $A$ 而且可能删除 $B$，而 $h_2$ 可能增加 $A$ 而且完全控制 $C$。现在，如果初始状态只有 $B$ 为真，而且目标是 $A \land C$，那么序列 $[h_1, h_2]$ 达到目标：我们选择一个使 $B$ 为假的 $h_1$ 的实现，然后选择一个保持 $A$ 为真使 $C$ 为真的和 $h_2$ 的实现。

前面的讨论假设了一个 HLA 的效果——任何给定的初始状态的可到达集——可以通过描述对每个变量的效果来精确描述。如果这总是对的就好，但在很多情况下我们只能对

效果进行近似，因为一个 HLA 可能有无限多的实现，从而可能产生任意摇摆不定的可到达集——很像图 7.21 描述的摇摆信念状态问题。例如，我们说 Go(Home,SFO) 可能删除 Cash；也可能增加 At(Car,SFOLongTermParking)；但不能同时发生——实际上它只能取一个。与信念状态一样，我们可能需要写出近似描述。我们将使用两种近似：一个 HLA 动作 h 的乐观描述（optimistic description） $ REACH^{+}(s,h) $ 可能夸大可到达集，悲观描述（pessimistic description） $ REACH^{-}(s,h) $ 可能低估可到达集。因此，我们有

$$ \mathrm{R E A C H}^{-}(s,h)\subseteq\mathrm{R E A C H}(s,h)\subseteq\mathrm{R E A C H}^{+}(s,h) $$

例如，Go(Home,SFO)的乐观描述认为它可能删除 Cash，且可能增加 At(Car, SFOLongTermParking)。另一个好的例子是八码问题，有一半状态从任何给定状态是无法到达的（参见习题3.4）：Act的乐观描述可能包含整个状态空间，因为确切的可到达集是十分摇摆的。

使用近似描述，对一个规划是否达到目标的测试需要稍微修改。如果规划的乐观可到达集与目标不相交，那么这个规划是不能工作的；如果悲观可到达集与目标相交，那么这个规划是能够工作的（图11.7（a））。在精确描述下，一个规划或者工作或者不工作，但在近似描述下，就有中间状态：如果乐观集与目标相交，但悲观集与目标不相交，那么我们不能确定规划是否工作（图11.7（b））。当出现这种情况，通过细化规划可以消除这种不确定性。在人类推理中，这是常见的情形。例如，在前面提到的两星期夏威夷度假规划中，有人可能提出在七个岛上每个岛呆上两天。远见告诉我们这个雄心的规划需要细化，增加岛与岛之间交通的细节。

图 11.8 给出了具有近似纯洁描述的分层规划的一个算法。为了简化，我们遵守前面图 11.5 中使用整个规划，即在细化空间里的一个宽度优先算法。就像刚才解释的，该算法能够通过检测乐观与悲观可到达集与目标的交集来检测能够工作的规划和不能工作的规划。（给定每个步骤的近似描述，习题 11.5 覆盖了如何计算一个规划的可到达集。）当找到一个可工作的抽象规划，算法将原始问题分解为子问题，规划的每个步骤一个。通过复原一个经过规划的每个步骤的动作模式的保证可达到的目标状态，可以获得每个子问题的初始状态和目标。（参加 10.2.2 节讨论如何复原。）图 11.6（b）描述了基本思想：右边圆圈状态是保

证可达到的目标状态，左边圆圈状态是中间目标，通过复原经过最后动作的目标而获得。

function ANGELIC-SEARCH(problem, hierarchy, initialPlan) returns solution or fail

frontier ← a FIFO queue with initialPlan as the only element

loop do

if EMPTY?(frontier) then return fail

plan ← POP(frontier) /* chooses the shallowest node in frontier */

if REACH+(problem.INITIAL-STATE, plan) intersects problem.GOAL then

if plan is primitive then return plan /* REACH+ is exact for primitive plans */

guaranteed ← REACH-(problem.INITIAL-STATE, plan) ∩ problem.GOAL

if guaranteed # { } and MAKING-PROGRESS(plan, initialPlan) then

finalState ← any element of guaranteed

return DECOMPOSE(hierarchy, problem.INITIAL_STATE, plan, finalState)

hla ← some HLA in plan

prefix, suffix ← the action subsequences before and after hla in plan

for each sequence in REFINEMENTS(hla, outcome, hierarchy) do

frontier ← INSERT(APPEND(prefix, sequence, suffix), frontier)

function DECOMPOSE(hierarchy, so, plan, sf) returns a solution

solution ← an empty plan

while plan is not empty do

action ← REMOVE-LAST(plan)

s ← a state in REACH-(s_0, plan) such that s_f ∈ REACH-(s_i, action)

problem ← a problem with INITIAL-STATE = s_i and GOAL = s_f

solution ← APPEND(ANGELIC-SEARCH(problem, hierarchy, action), solution)

s_f ← s_i

return solution

能够致力于或拒绝高层规划的能力使 ANGELIC-SEARCH 比 HIERARCHICAL-SEARCH 具有计算优势，进而比普通的 BREADTH-FIRST-SEARCH 更有大量优势。例如，考虑一个大的吸尘器世界由矩形房间组成，房间之间有狭窄的通道相连。有一个 HLA 动作 Navigate（如图 11.4 所示）和一个 HLA 动作 CleanWholeRoom 是有意义的。因为在这个问题中有 5 个动作，因此 BREADTH-FIRST-SEARCH 的代价以 $ 5^{d} $ 增长，其中 d 是最短解的长度（大约是房间数的两倍）；这个算法甚至不能处理 $ 2 \times 2 $ 的房间数。HIERARCHICAL-SEARCH 高效一些，但仍然是指数级增长，因为它尝试与分层一致的所有打扫方法。ANGELIC-SEARCH 增长与房间数之间是近似线性的——它致力于一个好的高层序列，而剪掉其他选项。依次打扫每个房间不是什么难事：因为任务的层次结构这对人类来说是容易的。当我们想到人类求解八码问题这样的小型谜题是多难时，似乎人类解决复杂问题的能力很大程度上源于抽象和分解问题以消除组合的能力。

可以通过泛化可到达集的概念扩展纯洁方法找到最小代价解。不说一个状态可到达或不可到达，它有一个到达它的最高效方法的代价。（不可到达的状态的代价是∞。）乐观和悲观描述限定了这些代价的界。使用这种方法，纯洁搜索能够找到可证明最优的抽象规划，无需考虑它们的实现。同样的方法能够用于获得有效的在线搜索的分层前瞻（hierarchical lookahead）算法，以 LRTA $ ^{*} $的风格（图 4.24）。某种程度上，这种算法映射了在诸如夏威夷度假规划这样的任务中的人类的深思熟虑——对取舍的考虑最初是在长时间尺度上的抽象层完成的；规划的某些部分直到执行之前都是十分抽象的，例如怎样在 Molokai 度过两

天闲暇时光，另外一些部分规划得很细，例如要乘的航班和预订的旅馆——没有这些细化，就不能保证规划是可行的。

11.3 非确定性领域中的规划与行动

在本节，我们扩展规划以处理部分可观察的、非确定性的、未知的环境。第4章类似地扩展了搜索，这里的方法也是相似的：用于无观察的环境中的无传感器规划（sensorless planning）；用于部分可观察的、非确定性环境中的应急规划（contingency planning）；用于未知环境中的在线规划（online planning）和重新规划（replanning）。

虽然基本与第4章一样，还是有些明显差异。这是因为规划器处理因子表示而不是原子表示。对于不可观察的和部分可观察的环境，这影响了我们表示 Agent 的动作和观察的能力的方法以及表示信念状态（Agent 可在的可能物理状态的集合）的方法。我们也可以利用第10章给出的计算搜索启发式的领域无关的方法的优点。

考虑这个问题：给定一把椅子和一张桌子，目标是对其进行匹配——有相同颜色。初始状态我们有两罐颜料，但颜料和家具的颜色未知。只有桌子开始时在 Agent 的视线内：

$$ \begin{aligned}&Init(Object(Table)\land Object(Chair)\land Can(C_{1})\land Can(C_{2})\land InView(Table))\\&Goal(Color(Chair,c)\land Color(Table,c))\\ \end{aligned} $$

有两个动作：从颜料罐去掉盖子，使用打开的罐子中的颜料涂抹对象。动作模式很简单，有一个例外：我们允许前提和效果包含不属于动作变量列表中的变量。也就是说，Paint(x,can)不提到表示这个颜料罐中颜料的颜色 c。在完全可观察的情形下，这是不允许的——我们需要将动作命名为 Paint(x,can,c)。但在部分可观察的情形下，我们可能知道或不知道罐中的颜料颜色。（变量 c 是全称量化的，就像一个动作模式中的所有其他变量。）

Action(RemoveLid(can),

PRECOND: Can(can)

EFFECT: Open(can))

Action(Paint(x,can),

PRECOND: Object(x) \^Can(can) \^Color(can,c) \^Open(can)

EFFECT: Color(x,c))

为了求解部分可观察问题，当 Agent 执行规划时，它将需要对它将获得的感知进行推理。当 Agent 实际行动时，它的传感器将提供感知信息，但当它进行规划时，它将需要它的传感器模型。第4章中，这个模型是由一个函数给定的，PERCEPT(s)。对于规划，我们用一个新型的模式——感知模式（percept schema）——来扩展 PDDL：

Percept(Color(x,c),

PRECOND: Object(x) ^\InView(x)

Percept(Color(can,c),

PRECOND: Can(can) ^\InView(can) ^\Open(can)

第一个模式说，只要对象在视线内，Agent 将感知到这个对象的颜色（即，对于对象 x，Agent 将学习对于所有 c 的 Color(x,c) 的真值。）第二个模式说，如果打开的罐子在视线内，

Agent 将感知到罐子里颜料的颜色。因为这个世界里没有外在事件，对象的颜色将保持不变，即使它没有被感知到，直到 Agent 执行一个动作来改变对象的颜色。当然，Agent 将需要一个使对象（每次一个）进入到视线里的动作：

$$ \begin{aligned}&Action(LookAt(x),\\&\quad PRECOND:InView(y)\land(x\neq y)\\&EFFECT:InView(x)\land\neg InView(y))\end{aligned} $$

对于一个完全可观察的环境，对于每个流（fluent）我们将有一个没有前提的感知公理。另一方面，一个无传感器的 Agent 根本没有感知公理。注意，即使一个无传感器的 Agent 也能求解涂色问题。一个解是，打开任意一罐颜料，将其都用到椅子和桌子，这样就迫使它们变为同一颜色（即使 Agent 不知道颜色是什么）。

一个可能的具有传感器的规划 Agent 能够生成一个更好的规划。首先，观看桌子和椅子以获取它们的颜色；如果它们已经是同一颜色就结束。如果不是，看看颜料罐；如果罐子里的颜料与家具之一同色，就将该颜料用到另一件家具商。否则，使用任一颜色对两件家具涂色。

最后，一个在线规划 Agent 首先可生成一个可能的具有更少分支的规划——也许忽略任何颜料罐不与任何家具匹配的可能性——然后处理重新规划中出现的问题。它也处理它的动作模式的不正确性。一个可能的规划器简单假设一个动作的效果总是会达到——假设给椅子涂色是如此——一个重新规划的 Agent 将检查结果并制定额外的规划来修复任何不期望的失败，例如未涂色的区域或还能看到原始颜色。

现实世界中，Agent 使用方法的组合。汽车加工商销售备胎和气囊，这是设计来处理轮胎被刺穿或碰撞的可能规划分支的物理体现。另一方面，多数汽车司机从不考虑这些可能性；当问题发生时，他们的反应是重新规划。通常，Agent 只对有重要后果的、其发生几率不可忽略的意外情况进行规划。因此，一个考虑横穿撒哈拉沙漠的汽车司机应该为破胎制定显式地意外规划，而去超市行程需要更少的事先规划。我们接下来更详细地看看这三种方法。

11.3.1 无传感器规划

4.4.1 节介绍了搜索信念状态空间以找到无传感器问题之解的基本思想。无传感器问题到信念状态规划问题的转换与4.4.1节中的方法一样；主要差异是，潜在的物理转移模型由一组动作模式表示，信念状态可以用一个逻辑公式而不是一组显式枚举的状态表示。为了简化，我们假设潜在的规划问题是确定性的。

无传感器的涂色问题的初始信念状态可以忽略 InView 流，因为 Agent 没有传感器。另外，我们将 Object(Table)∧Object(Chair)∧Can(C₁)∧Can(C₂)作为给定的不发生变化的事实，因为在这个信念状态这些事实都成立。Agent 不知道罐子里颜料或对象的颜色，也不知道罐子是开着的还是盖上的，但知道对象和罐子有颜色：∇x⊃c Color(x,c)。在 Skolem 化以后，(参见第 9.5 节)，我们获得初始信念状态：

$$ b_{0}=Color(x,C(x)) $$

在有封闭世界假设（closed-world assumption）的经典规划中，我们假设一个状态中没

有提到的任何流（fluent）为假，但在无传感器的规划中我们需要切换到开放世界假设（open-world assumption），其中状态包含正流和负流，而且如果一个流不出现，它的值就是未知的。这样，信念状态恰好对应于满足公式的可能世界集合。给定这个初始信念状态，下面的动作序列是一个解：

$$ [R e m o v e L i d(C a n_{1}),P a i n t(C h a i r,C a n_{1}),P a i n t(T a b l e,C a n_{1})] $$

我们现在描述如何通过动作序列推进信念状态来证明最后的信念状态满足目标。

首先，注意到在一个给定的信念状态 b，Agent 能够考虑前提被 b 满足的任何动作（不能使用其他动作，因为转移模型不能定义前提可能不能满足的动作的效果）。根据公式（4.4），在确定性世界里给定一个可用动作更新信念状态 b 的通用公式如下：

$$ b^{\prime}=RESULT(b,a)=\{s^{\prime}\colon s^{\prime}=RESULT_{P}(s,a)\text{and}s\in b\} $$

其中 RESULT $ _p $ 定义了物理转移模型。我们暂且假设，初始信念状态总是文字的合取，即 1-CNF 公式。为了构建新信念状态 $ b' $，我们必须考虑当应用动作 a 时，b 中每个物理状态 s 中的每个文字 l 会发生什么。对于在 b 中真值已知的文字，在 b' 中的真值是由当前值、动作的增加列表和删除列表计算的。（例如，如果 l 是在动作的删除列表中，那么加入到 b 中。）在 b 中真值未知的文字又如何呢？有三种情况：

（1）如果动作增加 l，那么不管其初始值，在 b' 中 l 将为真。

（2）如果动作删除 l，那么不管其初始值，在 b' 中 l 将为假。

（3）如果动作不影响 l，那么 l 将保持它的初始值（是未知的），且不会出现在 b' 中。因此，我看到 b' 的计算几乎与公式（10.1）描述的可观察的情况是相同的：

$$ b^{\prime}=RESULT(b,a)=(b-DEL(a))\cup ADD(a) $$

我们不能使用语义集，因为（1）我们必须确保 $b'$ 不包含 $l$ 和 $-l$，（2）原子可以包含无界的变量。但 RESULT$(b,a)$ 的计算仍是从 $b$ 开始的，将 DEL$(a)$ 中出现的任何原子设置为假，将 ADD$(a)$ 中出现的任何原子设置为真。例如，如果我们将 RemoveLid(Can$_1$) 应用初始信念状态 $b_0$，得到

$$ b_{1}=Color(x,C(x))\land Open(Can_{1}) $$

当我们应用动作 Paint(Chair,Can_{1})时，前提 Color(Can_{1},c)被已知文字 Color(x,C(x))用绑定 $ \{x/Can_{1}, c/C(Can_{1})\} $ 满足，而新信念状态是

$$ b_{2}=Color(x,C(x))\land Open(Can_{1})\land Color(Chair,C(Can_{1})) $$

最后，我们应用动作 Paint(Table, Can $ _{1} $) 得到

$$ b_{3}{=}C o l o r(x,C(x))\land O p e n(C a n_{1})\land C o l o r(C h a i r,~C(C a n_{1}))\land C o l o r(T a b l e,C(C a n_{1})) $$

最后的信念状态将变量 c 绑定为 $ C(Can_1) $ 可满足目标 Color(Table.c) $ \land Color(Chair.c) $。

前面的更新规则的分析已经揭示一个非常重要的事实：定义为文字合取的信念状态家族在 PDDL 动作模式定义的更新下是封闭的。也就是说，如果信念状态开始是文字的合取，那么任何更新将得到文字的合取。这意味着在具有 n 个流的世界里，任何信念状态能够用规模为 $ O(n) $ 的合取表示。想到在这个世界里有 $ 2^{n} $ 个状态，这是结果还是让人舒适的。而且，信念状态（前面访问过的信念状态的子集或超集）的检验过程也是容易的，至少在命题逻辑的情况下是这样。

美中不足的是它只对这样的动作模式有效：前提得到满足的所有状态下具有相同的效果。这种特性能够保持1-CNF信念状态表示。一旦效果可以依赖于状态，流之间就引入了

依赖关系，1-CNF 特性也会丢失。例如，考虑第 3.2.1 节的简单吸尘器世界。令机器人位置流为 AtL 和 AtR，方格状态流为 CleanL 和 CleanR。根据问题的定义，动作 Suck 没有前提——总是可以做这个动作。困难的是它的效果依赖于机器人的位置。当机器人在 AtL，结果就是 CleanL。但当它在 AtR，结果就是 CleanR。对于这种动作，我们的动作模式将需要一些新东西：一个条件效果（conditional effect）。语法是“when condition: effect，”其中条件（condition）是一个要与当前状态比较的逻辑公式，而效果（effect）是一个描述结果状态的公式。对于吸尘器世界，我们有

Action(Suck, EFFECT: when AtL: CleanL $ \wedge $when AtR: CleanR)

当初始信念状态为真，结果信念状态就是 $ (AtL \land CleanL) \lor (AtR \land CleanR) $，不再在1-CNF 中（图 4.14 中能看到这样转移）。一般，条件效果可以导致信念状态里流之间的任意依赖，最坏情况下导致指数级规模大小的信念状态。

理解前提和条件效果之间的差异是很重要的。所有那些条件得到满足的条件效果应用它们的效果生成结果状态：如果没有条件得到满足，那么结果状态不发生变化。另一方面，如果一个前提没有得到满足，就不能应用这个动作，而结果状态是无定义的。从无传感器规划的角度来说，条件效果比不能应用的动作更好。例如，我们可以将 Suck 分裂为两个具有非条件效果的动作：

$$ \begin{aligned}&Action(SuckL,PRECOND:AtL;EFFECT:CleanL)\\&Action(SuckR,PRECOND:AtR;EFFECT:CleanR)\\ \end{aligned} $$

现在我们只有非条件模式，因此信念状态都保持在1-CNF里；不幸的是，我们不能在初始信念状态里确定SuckL和SuckR的可应用性。

似乎不可避免，不平凡的问题将导致信念状态的摆动，就像当我们考虑 wumpus 世界状态估计问题时遇到的情况一样（参见图7.21）。

将保守近似用于精确信念状态：例如，信念状态可以保持在1-CNF，如果它包含所有真值能确定的文字，且将其他文字视为未知。虽然这种方法是有道理的，它从不生成不正确的规划，但它是不完备的，因为对于在文字之间需要必要交互的问题它可能不能找到解。给个实例，如果目标是要机器人在一个干净的方格里，那么[Suck]就是一个解，但一个坚持1-CNF信念状态的无传感器Agent将不能找到这个解。

也许一个更好的解是找到一个动作序列使信念状态尽可能简单。例如，在无传感器的吸尘器世界，动作序列[Right,Suck,Left,Suck]生成如下的信念状态序列：

$$ \begin{aligned}&b_{0}=True\\&b_{1}=AtR\\&b_{2}=AtR\land CleanR\\&b_{3}=AtL\land CleanR\\&b_{4}=AtL\land CleanR\land CleanL\\ \end{aligned} $$

也就是说，Agent 能够求解这个问题，而 1-CNF 信念状态是保持的，即使一些序列（例如那些以 Suck 开始的序列）走到 1-CNF 之外。人类没有失去一般的教训：我们总是执行一些小动作（核实时间，摸摸口袋以确定车钥匙在，穿过一个城市时看马路标识）来消除不确定性并使我们的信念状态可操控。

对于不可操控的信念状态摇摆问题，有另一个十分不同的方法：不要为计算它们而烦

恼。假设初始信念状态是 $b_0$，我想知道动作序列 $[a_1,\cdots,a_m]$ 导致的信念状态。我们不显式地计算它，而是将它表示为 “$b_0$ then $[a_1,\cdots,a_m]$。” 这是一种偷懒但没有歧义的信念状态表示方法，而且十分简明——$O(n+m)$，其中 $n$ 是初始信念状态的规模（假设在 1-CNF 中），$m$ 是动作序列的最大长度。然而，作为一种信念状态表示，它有一个缺点：确定目标是否满足或一个动作是否可用可能需要很多计算量：

计算可以实现为一个蕴涵测试：如果 $ A_m $ 表示定义动作 $ a_1, \cdots, a_m $ 发生所需要的后继状态公理集——像在 10.4.1 节中为 SATPLAN 解释的一样——而且 $ G_m $ 断言目标在 $ m $ 个步骤后得到满足，那么如果 $ b_0 \land A_m \models G_m $ 规划就达到了目标，也就说，如果 $ b_0 \land A_m \land \neg G_m $ 不可满足。给定一个现代的 SAT 求解器，这可能会比计算完全信念状态快得多。例如，如果序列中没有动作在它的增加列表中有特定的目标流，求解器将会马上检测到这一点。如果缓冲信念状态的部分结果——例如已知为真或为假的流——来简化后面的计算，这也是有帮助的。

无传感器规划谜题的最后事项是指导搜索的启发式函数。启发式函数的含义与经典规划中是一样：从给定信念状态达到目标的代价的一个估计（可能是可接纳的）。使用信念状态，我们得到一个另外的事实：求解一个信念状态的任何子集必定比求解这个信念状态更容易：

$$ if b_{1}\underline{\subset}b_{2}then h^{*}(b_{1})\leq h^{*}(b_{2}) $$

因此，为一个子集计算的任何可接纳的启发式对于信念状态本身也是可接纳的。最明显的候选是 singleton 子集，即单个的物理状态。我们可以取在信念状态 b 中的状态 $ s_{1},...,s_{N} $ 的任意随机组合，应用第 10 章的任意可接纳的启发式 h，返回

$$ H(b)=\max\{h(s_{1}),\cdots,h(s_{N})\} $$

作为求解 b 的启发式估计。我们也可以将一个规划图用在 b 上：如果它是文字（1-CNF）的合取，简单地将这些文字设置为图的初始状态层。如果 b 不在 1-CNF 中，找到一起蕴涵 b 的文字集合也是可能的。例如，如果 b 是析取范式（DNF）的形式，DNF 公式的每个项是蕴涵 b 而且可以形成规划图初始层的文字的合取。像以前一样，我们可以取从每组文字获得的启发式的最大值。我们也能够使用不可接纳的启发式，例如忽略-删除-列表启发式，这在实践中好像工作得很好。

11.3.2 应急规划

在第4章中我们看到了应急规划（contingent planning）——带有基于感知的条件分支的规划生成——对于部分可观察或非确定性环境或同时是部分可观察和非确定性的环境是合适的。对于部分可观察的具有前面给出的感知公理的涂色问题，一个可能的应急规划如下：

$$ \begin{aligned}&[LookAt(Table),LookAt(Chair),\\&\quad if~Color(Table,c)\land Color(Chair,c)~then~NoOp\\&\quad else~[RemoveLid(Can_{1}),LookAt(Can_{1}),RemoveLid(Can_{2}),LookAt(Can_{2}),\\&\quad if~Color(Table,c)\land Color(can,c)~then~Paint(Chair,can)\\&\quad else~if~Color(Chair,c)\land Color(can,c)~then~Paint(Table,can)\\&\quad else~[Paint(Chair,Can_{1}),Paint(Table,Can_{1})]]]\end{aligned} $$

这个规划中的变量应该考虑用存在量词量化；第二行是，如果存在某个颜色 $c$ 是桌子的颜色和椅子的颜色，那么 Agent 不需要做什么就达到了目标。执行这个规划的时候，一个应急规划 Agent 可以保持其信念状态为一个逻辑公式，并且通过确定这个信念状态是否蕴涵这个条件公式或它的否定来评估每个分支条件。（确保 Agent 从不以条件公式真值未知的信念状态结束，这取决于应急规划算法）注意，使用一阶条件，公式可能不止以一种方式得到满足；例如，条件 Color(Table,c) ∧ Color(can,c) 可被 {can/Can₁} 和被 {can/Can₂} 满足，如果两个罐子里的颜色与桌子的颜色都相同。这种情况下，Agent 可以选择任何满足的代换来用于其余的规划。

像 4.4.2 节给出的一样，计算一个动作和接下的感知之后的新信念状态分两个阶段完成。第一个阶段在动作之后计算信念状态，就像无传感器 Agent 一样：

$$ \hat{b}=(b-\operatorname{DEL}(a))\cup\operatorname{ADD}(a) $$

其中，像以前一样，我们假设了一个用文字合取表示的信念状态。第二个阶段有一点技巧。假设接收到了感知文字 $ p_1 $，…， $ p_k $。有人可能觉得我们只是需要将它们加入到信念状态；实际上，我们也可以推断，用于感知的前提得到了满足。现在，如果一个感知 $ p $ 恰好有一个感知公理 $ \text{Percept}(p, \text{SECOND:}c) $，其中 $ c $ 是文字的合取，那么这些文字可以和 $ p $ 一起丢进信念状态。另一方面，如果 $ p $ 有不止一个感知公理，其前提根据预测的信念状态 $ \hat{b} $ 可能成立，那么我们不得不加进前提的析取。明显，这使信念状态在 1-CNF 之外，而且带来了与条件效果相同的复杂性，解的级别也是相同的。

给定计算精确或近似信念状态的一个机制，我们可以扩展信念状态上的 AND-OR 前向搜索（4.4 节）来生成应急规划。具有非确定性效果的动作——用动作模式的效果的析取来定义——稍作修改可以适应信念状态更新计算，而无须改变搜索算法 $ ^{1} $。对于启发式函数，无传感器规划建议的许多算法在部分可观察的、非确定性的情况下也是可用的。

11.3.3 在线重规划

想象在一个汽车厂观看一个点焊机器人。每辆汽车在流水线下经过时，机器人快速而准确的动作重复了一遍又一遍。尽管技术令人印象深刻，机器人可能似乎并不智能，因为动作是固定不变的、预先编程的序列；从任何有含义的角度，机器人显然不“知道它在做什么。”现在假设机器人正要进行点焊时松垮的车门脱落下来。机器人快速地将点焊器替换为一个钳子，拿起车门，检查擦痕，重新将门装到车上，向地面的检查员发送一封电子邮件，切换回点焊器，然后继续工作。突如其来，机器人的行为似乎是有意识的而不是机械的；我们假设这不是有一个巨大的、预先计算的应急规划引起的，而是产生于一个在线重新规划过程——这意味着机器人确实需要知道它正要做什么。

重新规划预先假设有某种形式的执行监控（execution monitoring）来确定是否需要一个新规划。当一个应急规划 Agent 对每个小的应急事件（例如天是否会塌到头顶上 $ ^{2} $）进行规

划感到厌烦的时候，这种需要就来了。

一个部分已构建出的应急规划的一些分支可以简单地就是重新规划（replan）；如果执行过程中达到这样的分支，Agent 转换到规划模式。像我们早些提到的一样，决定多少问题事先解决和多少问题留待重新规划，是具有不同代价和发生概率的可能事件之间的一个折中。没有人想让他们的汽车在撒哈拉沙漠中抛锚，只有那个时候才会想着要更多的水。

如果 Agent 的世界模型不正确，也需要重新规划。一个动作的模型可能缺失前提——例如，Agent 可能并不知道打开颜料罐盖子经常需要螺丝刀；模型可能缺失效果——例如，给对象涂色可能也会使地面涂上颜色；或者模型可能缺失状态变量——例如，前面给出的模型没有概念指出罐里有多少颜料，没有概念指出动作又是如何影响颜料多少的，没有概念要求颜料的容量不能为零。模型也可能没提供外来事件，例如某人敲击颜料罐。外来事件包括改变目标，例如增加要求，要求桌子和椅子不能涂成黑色。没有监控和重新规划的能力，如果 Agent 依赖于它的模型的绝对正确，那么它的行为很可能是脆弱的。

对环境监控到什么样的仔细程度，在线 Agent 可以有所选择。我们区分三个层次：

动作监控：在执行动作之前，Agent验证所有前提是否仍成立。

规划监控：在执行动作之前，Agent验证剩下的规划是否仍然会成功。

目标监控：在执行动作之前，Agent 检查是否有它可以尝试达到的更好的目标集。

在图 11.9 中，我们看到一个动作监控示意图。Agent 跟踪其原始规划 wholeplan，以及规划中还没有执行的部分，这部分用 plan 标示。在执行了规划的开始几步后，Agent 期望到状态 E 里去。但 Agent 观察到它实际上在状态 O 里。此时它需要修改规划，找到它可以回去的原始规划的某个点 P（P 可以是目标状态 G）。Agent 试图最小化规划的总体代价：修改的部分（从 O 到 P）假设后续部分（从 P 到 G）。

图 11.9 执行前，规划器得到一个为了从 S 达到 G 的规划，这里称为整体规划（whole plan）。Agent 执行规划步骤，直到它期望到状态 E 中，但观察到它实际上在 O 中。这时，Agent 重新规划，最小改动而且要继续达到 G

现在，我们回到实现椅子和桌子颜色匹配的问题实例。假设 Agent 得到这个规划：

[LookAt(Table), LookAt(Chair),

$$ \begin{aligned}&if Color(Table,c)\land Color(Chair,c)then NoOp\\&\quad else[RemoveLid(Can_{1}),LookAt(Can_{1}),\\&\quad if Color(Table,c)\land Color(Can_{1},c)then Paint(Chair,Can_{1})\\&\quad else REPLAN]]\\ \end{aligned} $$

现在，Agent 准备执行这个规划。假设 Agent 观察到桌子和颜料罐都为白色，而椅子为黑色。Agent 于是执行 $ \text{Paint}(\text{Chair},\text{Can}_1) $。这个时候，经典规划器将认为胜利完工了；规划已经被执行了。但一个在线执行检测 Agent 需要检查余下空规划的前提——桌子和椅子是相同的颜色。假设 Agent 察觉到它们的颜色不同——实际上，椅子现在是杂灰色，因为底层的黑色透过了刚涂的白色。Agent 需要在整体规划（whole plan）中计算出一个立志要达到的状态，另需要一个修复动作序列来达到这个状态。Agent 注意到当前状态与 $ \text{Paint}(\text{Chair},\text{Can}_1) $ 动作之前的前提是一样的，因此 Agent 选择空序列进行修复，使其规划为刚执行过的 $ [\text{Paint}] $ 序列。这个新规划执行，执行检测继续，Paint 动作重来一片。这个过程将循环，直到椅子完全涂为白色。但注意到这个循环是规划-执行-重规划的过程，而不是规划里的显式循环。也要注意到，原始规划不需要覆盖每个应急因素。如果 Agent 到达 REPLAN 步骤，它就可以产生一个新规划（也许涉及 $ \text{Can}_2 $）。

动作监控是执行检测的一种简单方法，但它有时可以得到不那么智能的行为。例如，假设没有黑色和白色颜料，Agent于是构建一个规划解决涂色问题，将椅子和桌子都涂为红色。假设颜料只够为椅子涂色。在动作检测下，Agent将着手将椅子涂成红色，然后发现颜料用完了，这样无法给桌子涂色，这时Agent将重新规划出一个修复——也许是将椅子和桌子都涂成绿色。只要当前状态属于剩余的规划不会再有效地工作的情况，一个规划监控Agent就可以检测到失败。这样就不会浪费时间将椅子涂成红色。通过检查整个剩余规划成功所需的前提，规划监控可以实现这一点——也就是规划中每个步骤的前提，剩余规划中另一个规划获得的前提除外。规划监控尽早结束注定失败的执行，而不是继续执行到失败真正发生 $ ^{1} $。规划监控也允许意外收获——偶然的成功。在Agent将椅子涂成红色的时候，如果有人一起来将桌子涂成红色，那么最后的规划前提得到满足（目标已经实现），Agent于是可以早早地收工。

不难修改规划算法，为规划中的每个动作注释上动作的前提，从而可以进行动作检测。进行规划检测稍微复杂一些。偏序和规划图规划器具有优势，它们已经建立起包含规划检测所需关系的结构。随着目标流经过规划得到回归，通过记账可以扩大扩展状态空间规划器带有必要的注释。

现在，我们已经描述了监控和重新规划的方法，我们要问，“这个方法能工作吗？”这是一个十分棘手的问题。如果我们的意思是，“我们能保证 Agent 总是能实现目标吗？”那么答案是否，因为 Agent 不经意地会达到一个无法修复的死胡同。例如，吸尘器 Agent 的自身模型可能是有缺陷的，它不知道它的电池会耗尽。一旦电池耗尽，它就无法修复任何规划。如果我们排除掉死胡同——假设从环境中的任何状态都有到达目标的规划——并且假设环境全然是非确定性的（给定执行尝试，这样的规划总是有某个成功的几率），那么 Agent 最终将到达目标。

当一个动作实际上不是非确定性的，而是依赖于 Agent 并不知道的某个前提的时候，麻烦就来了。例如，颜料罐有时是空的，因此用那个颜料罐涂色将没有效果。无论重试多

少次都改变不了 $ ^{1} $。一种解决方法是从一组可能的修复规划中随机选择一个规划，而不是每次都尝试同一个。这种情况下，打开另一个颜料罐的修复规划可能工作。一种更好的方法是学习一个更好的模型。每次预测失败就是一次学习机会；一个 Agent 应能修改它的世界模型以与它的感知相适应。从这时起，重规划器将能够获得接近根问题的修复，而不是碰运气选择一个好修复。第18和19章描述了这种学习。

11.4 多 Agent 规划

目前为止，我们假设只有一个 Agent 在感知、规划、行动。当环境中有多个 Agent 时，每个 Agent 面对一个多 Agent 规划问题（multiagent planning problem），每个 Agent 在其他 Agent 的帮助或阻碍下试图达到自身的目标。

在纯粹单 Agent 与真正多 Agent 情况之间是大范围的问题系列，呈现出对庞大 Agent 不同程度的分解。有多个可以并发操作的效应器的 Agent——例如人可以同时打字和说话——在处理效应器之间的正交互与负交互时需要进行多效应器规划（multieffector planning）来处理每个效应器。当效应器物理上分离（decouple）为独立的（detached）单元时——就像工厂里的一队装配机器人——多效应器规划就变为多体规划（multibody planning）。只要每个体收集的相关感知信息可以共用——无论是集中式的还是在各个体内——以形成对世界状态的公共估计，然后通知整个规划执行，多体问题就仍然是一个标准的单 Agent 问题；这种情况下，多体就像单体一样行动。当通讯约束使这不可能时，我们遇到有时称为分散规划（decentralized planning）的问题；也许这是一个不当的名称，因为规划阶段是集中式的，但执行阶段至少是部分分离的。这种情况下，每个体构建的子规划可能需要包含显式的与其他体的通讯动作。例如，覆盖一个大区域的多个巡逻机器人可能经常彼此失去无线电联络，当它们可以通讯的时候它们应该共享它们的发现。

当单个实体在执行规划的时候，实际上只有一个目标，所有体都必须共享这个目标。当多体是在执行它们各自规划的多个不同 Agent 时，它们可能仍然共享同样的目标；例如，两个人类网球手组成双打，他们共享的目标是赢得比赛。然而即使有共享目标，多体和多Agent 的情况是十分不同的。在多体机器人双打队中，一个单个规划指示哪个体去球场的哪个位置，以及指示哪个体将击球。另一方面，在多 Agent 双打队中，每个 Agent 决定自己做什么；没有协调方法，两个 Agent 都可能决定守住球场的同一区域，每个 Agent 也可能决定让给另一个 Agent 击球。

当然，多 Agent 问题的最清楚的情况是当各 Agent 具有不同目标的时候。网球比赛中，相对的两个队的目标是直接冲突的，导致第 5 章的零和情形。观众可以被视为 Agent，如果他们的支持或鄙视是个重要因素，而且可以被网球手的行为影响；否则，他们可以被当做大自然的一方面来对待——就像天气——假设网球手的意图对此并不关心 $ ^{2} $。

最后，一些系统混合了集中式与多 Agent 规划。例如，一个配货公司可以每天为其卡车和飞机的路线做集中式的离线规划，但某些方面留给可以对交通和天气做出响应的司机

和飞行员进行自治决策。某个程度上，公司和雇员的目标通过支付奖金（工资和奖励）也对齐了——这是一个真正多 Agent 系统的肯定标志。

多 Agent 规划中的事项可以粗略地分为两组。首先（11.4.1 节）涉及多个同步动作的表示和规划。其次（11.4.2 节）涉及真正多 Agent 环境中合作、协同和竞争。

11.4.1 多同步动作的规划

现在，我们将用相同的方法处理多效应器、多体以及多 Agent 环境，将它们一般性地标示为多行动者（multiactor）环境，使用通用术语行动者（actor）来覆盖效应器（effector）、体（body）以及 Agent。本节的目的是要想出如何定义转移模型、正确的规划以及多行动者环境的高效规划算法。一个正确的规划是一个如果被行动者执行就能达到目标的规划。（当然，在真正多 Agent 环境中，Agent 可能不同意执行任何特殊规划，但至少它们知道如果它们同意执行，什么规划将会工作。）为了简化，我们假设理想同步：每个动作需要的时间相同，而且联合规划中每个点的动作是同步的。

我们从转移模型开始；对于确定性的情况，就是函数 RESULT(s,a)。在单 Agent 环境中，对于一个动作也许有 b 个不同的选项；b 可以非常大，特别是对有许多对象起作用的一阶表示，但动作模式提供一个精确表示。在有 n 个行动者的多行动者环境中，单个动作 a 被联合动作 $ (a_{1}, \cdots, a_{n}) $ 替换，其中 $ a_{i} $ 是第 i 个行动者的动作。我们马上看到两个问题：首先，我们需要为 $ b^{n} $ 个不同的联合动作描述转移模型；其次，我们遇到分支因子为 $ b^{n} $ 的联合规划问题。

将各行动者一起放入一个具有巨大分支因子的多行动者系统中后，研究多行动者规划的主要焦点已经变成将各行动者分离（decouple）到可能的程度，这样，问题的复杂性以n线性地增长，而不是指数量级地增长。如果行动者不与另一个行动者交互——例如，n个行动者每个行动者玩单人跳棋——那么我们可以简单地求解n个独立问题。如果行动者是松耦合的（loosely coupled），我们可以得到接近指数量级的改进吗？当然，这是许多AI领域的一个中心问题。在CSP的上下文中，我们已经明显看到了这一点，在CSP中树一样的约束图生成高效的求解方法（第6.5节），以及在不相交模式库（disjoint pattern databases）（3.6.3节）和规划的加法启发式（10.2.3节）的上下文中。

松耦合问题的标准方法是假装问题是完全分离的，然后安排一些交互。对于转移模型，这意味着就像行动者独立行动一样写动作模式。我们现在看看网球双打问题中这是如何工作的。我们假设在游戏的某一点，两人的目的是将过来的球击回去，并确保至少有一人覆盖球网。多行动者定义的首轮传球像图11.10那样。在这个定义下，不难看出下面的联合规划（joint plan）可以工作：

PLAN 1:

$$ \begin{aligned}&A:\ [Go(A,RightBaseline),Hit(A,Ball)]\\&B:\ [NoOp(B),NoOp(B)]\\ \end{aligned} $$

然而，当一个规划让两个 Agent 在同一时间都击球的时候问题就来了。在真实世界中，这是不能工作的，但 Hit 的动作模式说球会被成功的击回。技术上，困难在于前提约束了动作可以被成功执行的状态，但没有约束其他可能搅局的动作。我们用一个新特征扩展动作

Actors(A, B)

Init(At(A, LeftBaseline) ∧ At(B, RightNet) ∧

Approaching(Ball, RightBaseline)) ∧ Partner(A, B) ∧ Partner(B, A)

Goal(Returned(Ball) ∧ (At(a, RightNet) ∨ At(a, LeftNet))

Action(Hit(actor, Ball)).

PRECOND:Approaching(Ball, loc) ∧ At(actor, loc)

EFFECT:Returned(Ball))

Action(Go(actor, to),

PRECOND:At(actor, loc) ∧ to ≠ loc,

EFFECT:At(actor, to) ∧ → At(actor, loc))

模式来解决这一点：一个并发动作（concurrent action）列表，说明哪些动作必须并发地执行或不能并发地执行。例如 Hit 动作可以描述为如下形式：

Action(Hit(a,Ball),

CONCURRENT: $ b \neq a \Rightarrow \neg Hit(b,Ball) $

PRECOND: Approaching(Ball,loc) $ \land $ At(a,loc)

EFFECT: Returned(Ball))

换句话说，Hit 动作只有在同一时间其他 Agent 没有发出 Hit 动作时，才会有它所说的效果。（在 SATPLAN 方法中，部分动作排斥公理将处理这一点。）对于某些动作，只有当另一个动作并发地发生时，才会获得期望的效果。例如，两个 Agent 要抬一个装满饮料的冰箱到球场：

Action(Carry(a,cooler,here,there),

CONCURRENT: b ≠ a ∧ Carry(b,cooler,here,there)

PRECOND: At(a,here) ∧ At(cooler,here) ∧ Cooler(cooler)

EFFECT: At(a,there) ∧ At(cooler,there) ∧ ¬At(a,there) ∧ ¬At(cooler,here))

有了这些动作模式，第10章中描述的任何规划算法可以稍加修改就可以生成多行动者规划。子规划之间的耦合是松散的——意味着在规划搜索中并发约束很少起作用——有人可能期望单Agent规划中得到的各种启发式在多行动者上下文中也是有效的。我们可以使用最近两章的细化——HTN、部分可观察、条件式、执行检测、重新规划——来扩展这种方法，但这超出了本书的范围。

11.4.2 多 Agent 规划：合作与协调

现在，我们考虑真正的多 Agent 环境，每个 Agent 制定自己的规划。开始，我们假设目标和知识库是共享的。有人可能认为这退化到了多体的情况——每个 Agent 简单地计算那个联合解并执行那个解的自己的部分。“那个联合解”中的“那个”有点误导。对于我们的双打问题，存在不止一个联合解：

PLAN 2:

A: [Go(A,LeftNet), NoOp(A)]

B: [Go(B,RightBaseline), Hit(B, Ball)]

如果两个 Agent 都同意规划 1 或规划 2，目标就可以实现。但如果 A 选择规划 2 而 B 选择规划 1，那么就没人去击球。相反，如果 A 选择 1 而 B 选择 2，那么两人都会去击球。Agent 可能意识到这一点，但它们如何协调以确保它们达成一致意见。

一种方法是联合行动之前进行协定（convention），一个协定是对联合规划进行选择的任何约束。例如，协定“守住你那边的球场”将排除规划1，使得两人都选择规划2。马路上驾驶员面临不要相互碰撞的问题；这部分通过采用协定解决：在多数国家是“走马路的右边。”；或者如果环境中的所有Agent都达成一致，“走左边”也会工作得同样好。类似的考虑应用到人类语言的发展，重要的事情不是每个个体应该说哪种语言，而是一个社区都说同一种语言。当协定广泛普及的时候，它们就称为社会法则（social laws）。

没有协定，Agent 可以用通讯来获得可行的联合规划的公共知识。例如，一个网球手可以大喊“我的！”或“你的！”来指示一个首选的联合规划。我们在第22章会更深地覆盖通讯机制，在那里我们观察到通讯不一定会涉及口头上的交换。例如，一个网球手可以将一个首选的联合规划传递给另一人，只需要执行这个规划的第一部分就可以传递。如果Agent A奔向球网，那么Agent B被迫回到底线击球，因为规划2是唯一的从A奔向球网开始的联合规划。这种协调方法有时称为规划识别（plan recognition），当单个动作（或短的动作序列）足够无歧义地确定一个联合规划时，这种协调方法是有效的。注意，与竞争Agent 通讯可以工作得与合作Agent一样好。

通过进化过程也可以形成协定。例如，吃种子的收割期蚂蚁是社交生物，是从不太社交的黄蜂进化而来的。蚁群执行精心设计的联合规划，没有任何集中控制——蚁王的工作是复制，不是做集中规划——每个蚂蚁有非常有限的计算、通讯和存储能力（Gordon，2000，2007）。蚁群有许多角色，包括内部工人、巡逻者以及食物搜寻者。每只蚂蚁根据它观察到的局部条件选择执行一个角色。例如，搜寻者离开巢穴，搜寻种子，一旦找到种子就立马带回。这样，搜寻者返回巢穴的速率就是今天食物的可得性的估计。如果速率高，其他蚂蚁会放弃它们现在的角色，变为觅食者的角色。蚂蚁们看似对角色的重要性有一个协定——搜寻者是最重要的——而且蚂蚁将容易切换到更重要的角色，而不容易切换到不重要的角色。有一些学习机制：蚁群在其数十年的生命中学习制定更成功的、深谋远虑的行动，即使各个蚂蚁只活一年时间。

合作多 Agent 行为的最后一个例子出现在鸟群的结队行为中。我们可以得到一个鸟群的合理模拟，如果每个鸟 Agent（有时称为 bold）观察到离它最近的鸟的位置然后选择飞行方向和加速度来最大化下面这三个量的加权和：

（1）凝聚（cohesion）：向邻居的平均位置更靠近的正分数。

（2）分离（separation）：与任何邻居都靠得太近的负分数。

（3）对齐（alignment）：向邻居的平均飞行方向更靠近的正分数。

如果所有的鸟 Agent(boid)都执行这个策略，鸟群呈现出涌现行为（emergent behavior），像一个假刚性体一样飞行，具有大约为常量的密度，不会随着时间而散开，偶尔做出俯冲动作。你可以在图 11.11（a）中看到一个静态图像，将其与图 11.11（b）中的实际鸟群对比。对于蚂蚁而言，没有必要每个 Agent 都具有一个模拟其他 Agent 动作的联合规划。

最困难的多 Agent 问题涉及与自己的团队合作以及与对手团队竞争，都没有集中式的控制。我们在机器人足球或图 11.11（c）的 NERO 这样的游戏中看到这一点，在其中，两

个软件 Agent 团队竞争占据对高楼的控制。到现在为止，这些环境中的高效规划方法——例如，利用松耦合——还在初始阶段。

11.5 本章小结

本章处理了真实世界的规划和行动的一些复杂因素。要点是：

许多行动消耗资源，诸如钱、汽油或原材料。把这些资源看作池中的数值度量是方便的，胜过试着去推理（比如说）世界上每个单个的硬币和钞票。行动能够产生和消耗资源，通常在尝试进一步细化之前检验偏序规划对资源约束的满足性是便宜和有效的。

● 时间是一种最重要的资源。它能被专门的调度算法处理，或者调度可与规划结合。

分层任务网络（HTN）规划允许 Agent 以高层动作（high-level action, HLA）的形式从领域设计者处获得建议，高层动作可以由底层动作序列以不同方式实现。HLA 的效果可以用纯洁语义定义，允许不考虑低层实现就可导出可证明正确的高层规划。HTN 方法可以构建许多真实应用所需要的非常大的规划。

标准规划算法假设有完备的和正确的信息以及确定性的和完全可观察的环境。许多领域违反这个假设。

应急规划允许 Agent 在执行过程中感知世界，以决定沿着规划的哪个分支。某些情况下，无传感器的或一致性的规划可以用来构建一个不需要感知就可以工作的规划。一致性和应急规划都可以在信念状态空间中搜索而构建。信念状态的高效表示或计算是关键问题。

在线规划 Agent 使用执行监控和从不期望的情形中恢复所需要的修复中的粘接，不期望的情形可能是由于非确定性的动作、外在的事件、或不正确的环境模型。

当环境中有其他 Agent 合作或竞争时，多 Agent 规划是必要的。如果两个 Agent 要对执行哪个联合规划达成共识，可以构建联合规划，但必须有某种形式的协调。

本章扩展了经典规划来覆盖非确定性环境（在这个环境里，动作的结果是非确定性的），但不是规划的最终内容。第17章描述随机环境中（在这个环境里，动作的结

果具有概率）的技术：马尔科夫决策过程、部分可观察的马尔科夫决策过程以及博弈理论。第21章中，我们证明强化学习允许Agent学习如何根据过去的成功与失败而行动。

参考文献与历史注释

DEVISER（Vere，1983）第一个处理了具有时间约束的规划。Allen（1984）和 Dean 等（1990）在 FORBIN 系统中讨论了在规划中的时间的表示。NONLIN+（Tate 和 Whiter，1984）和 SIPE（Wilkins，1988,1990）能够对有限资源分配给不同规划步骤进行推理。O-PLAN（Bell 和 Tate，1985）——一个 HTN 规划器——对时间与资源约束具有统一的一般表示。除了课本中提到的在日立（Hitachi）的应用，O-PLAN 还被用于在 Price Waterhouse 的软件采购规划，以及在 Jaguar Cars 的汽车后桥的装配规划。

SAPA（Do 和 Kambhampati，2001）和 T4（Haslum 和 Geffner，2001）两个规划器都用于具有精密启发式的前向状态空间搜索，以处理具有延迟和资源的动作。或者使用表达能力强的动作语言，但用人类所写的专门领域的启发式来引导它们，ASPEN（Fukunaga 等，1997）、HSTS（Jonsson 等，2000）和 IxTeT（Ghallab 和 Laruelle，1994）就是这样做的。

一些混合规划与调度的系统已经部署到了实际场合：ISIS（Fox等，1982；Fox，1990）已经用于在Westinghouse的加工车间的调度，GARI（Descotte和Latombe，1985）对机械构件的加工与构建进行规划，FORBIN用于工厂控制，NONLIN+用于海军后勤规划。我们决定将规划和调度作为两个不同的问题提出；（Cushing等，2007）证明了这会导致某些问题的不完备性。航空领域的调度有很长的历史。T-SCHED（Drabble，1990）用于UOSAT-II卫星的任务命令序列的调度。OPTIMUM-AIV（Aarup等，1994）和PLAN-ERSI（Fuchs等，1990）都基于O-PLAN，在欧洲宇航局分别被用于航天器组装和观测规划。SPIKE（Johnston和Adorf，1992）在NASA用于哈勃太空望远镜的观测规划，而航天飞机地面处理调度系统（Deale等，1994）对加工车间的多达16000个换班进行调度。远程Agent（Muscettola等，1998）变为第一个自治规划器-调度器来控制航天器，当它1999年随外层空间探测器飞行时。太空应用推动了资源分配算法的发展；参见Laborie（2003）和Muscettola（2002）。调度方面的文献在一篇经典综述论文（Lawler等，1993）、最近的一本书（Pinedo，2008）和一本编辑的手册（Blazewicz等，2007）中有所阐述。

STRIPS 程序中学习 macrops（宏算子，macro-operators）的能力由一系列基元步骤组成——可以认为是层次化规划的第一个机制（Fikes 等，1972）。层次化也用于 LAWALY 系统（Siklossy 和 Dreussi，1973）。ABSTRIPS 系统（Sacerdoti，1974）引入了抽象层次（abstract hierarchy）的思想，允许高层规划忽略低层动作的前提，以导出工作规划的通用结构。Austin Tate 的博士学位论文（1975b）以及 Earl Sacerdoti（1977）的工作发展了现代形式的 HTN 规划的基本思想。Yang（1990）讨论使 HTN 规划更高效的动作的特性。Erol、Hendler 和 Nau（1994,1996）提出了一个完整的层次分解规划器，给出了纯 HTN 规划器的一些复杂结果。我们对 HLA 和纯洁语义的论述归功于 Marthi 等（2007,2008）。Kambhampati 等（1998）提出了一种方法，其中分解就规划细化的另一种形式，类似于非层次偏序规划的细化。

从 STRIPS 中的宏算子开始，层次规划的目标之一是以泛化规划的形式重用前面的规划经验。第 19 章将详细描述的基于解释的学习（explanation-based learning）技术，已经在一些系统中用作对以前计算出的规划进行泛化的手段，包括 SOAR（Laird 等，1986）和 PRODIGY（Carbonell 等，1989）。另一个可选方法是用原始形式存储以前计算出的规划，然后通过对原始问题进行类推，复用它们以求解新的、类似的问题。这是被称为基于案例的规划（case-based planning）领域采用的方法（Carbonell，1983；Alterman，1988；Hammond，1989）。Kambhampati（1994）认为基于案例的规划应该作为一种细化规划的形式来分析，并为基于案例的偏序规划提供了一个形式化的基础。

早期规划器缺乏条件和循环，但有的能够强制性地形成一致性规划。Sacerdoti 的 NOAH 在 “钥匙和箱子” 问题的求解中使用强制，这是规划器对初始状态知之甚少的挑战性规划问题。Mason（1993）主张在机器人规划中感知经常能够也应该能够被省略，并描述了一个无传感器的规划，它能根据一个倾斜行动序列把一件工具移到一个指定的位置，而不管初始位置在哪里。

Goldman 和 Boddy（1996）为无传感规划器引入了术语一致性规划（conformant plan），注意到无传感规划通常是有效的，即使 Agent 有传感器。第一个相当高效的一致性规划器是 Smith 和 Weld（1998）的一致性图规划器（CGP）。Ferraris 和 Giunchiglia（2000）以及 Rintanen（1999）独立开发了基于 SATPLAN 的一致性规划器。Bonet 和 Geffner（2000）描述了一个基于信念状态空间启发式搜索的一致性规划器，利用了 20 世纪 60 年代首先为部分可观察马尔可夫决策过程或称 POMDP（参见第 17 章）发展出来的思想。

当前有三种一致性规划的主流方法。前两个使用信念状态空间中的启发式搜索：HSCP（Bertoli 等人，2001a）使用二元决策表（BDD）表示信念状态，而 Hoffmann 和 Brafman（2006）用 SAT 求解器采用了计算前提和目标测试的懒惰方法。第三种方法主要由 Jussi Rintanen（2007）拥护，将整个无传感器的规划问题形式化为一个量化的布尔公式（QBF，quantified Boolean formula），并使用通用目标 QBF 求解器求解。当前的一致性规划器比 CGP 快 5 个数量级。2006 年国际规划比赛中一致性规划跟踪的获胜者是 $ T_0 $（Palacios 和 Geffner，2007），它使用信念状态空间的启发式搜索，通过定义覆盖条件效果的导出文字，使得信念状态表示很简单。Bryce 和 Kambhampati（2007）讨论了如何泛化一个规划图来为一致性规划和应急规划生成好的启发式。

文献中对术语 “条件（conditional）” 和 “应急（contingent）” 规划有些混淆。我们遵循 Majercik 和 Littman（2003），使用 “条件（conditional）” 表示根据世界的实际状态而具有不同效果的一个规划（或动作），使用 “应急（contingent）” 表示智能体可以根据感知结果选择不同动作的一个规划。在 Drew McDermott（1978a）发表的有影响力的论著《规划与行动》后，应急规划的问题得到了更多关注。

本章描述的应急规划方法是基于 Hoffmann 和 Brafman（2005）的，并受 Jimenez 和 Torras（2000）以及 Hansen 和 Zilberstein（2001）开发的有环与或（AND-OR）图高效搜索算法影响。Bertoli 等（2001b）描述了 MBP（Model-Based Planner），它使用二元决策图来进行一致性和应急规划。

回顾一下，现在有可能考察主要经典规划算法是如何通向涉及不确定性领域的扩展版本的。信念状态空间的快速前向启发式搜索导致对信念空间的前向搜索（Bonet 和 Geffner，

2000; Hoffmann 和 Brafman, 2005); SATPLAN 导致随机 SATPLAN（Majercik 和 Littman, 2003）以及使用量化布尔逻辑的规划（Rintanen, 2007）；偏序规划导致 UWL（Etzioni 等, 1992）和 CNLP（Peot 和 Smith, 1992）；GRAPHPLAN 导致了传感器 GRAPHPLAN（SGP）（Weld 等, 1998）。

具有执行监控的第一个在线规划器是 PLANEX（Fikes 等，1972），它与 STRIPS 规划器一起工作来控制机器人 Shakey。NASL 规划器（McDermott，1978a）将规划问题简单处理为一个对复杂动作的规范与执行问题，因此执行与规划是完全统一的。SIPE（交互规划和执行监控的系统）（Wilkins，1988,1990）是系统地处理重新规划问题的第一个规划器。它已经应用于几个领域的演示项目中，包括对航空母舰飞行甲板操作的规划和一个澳大利亚啤酒厂的加工车间调度，以及规划多层建筑的建造（Kartam 和 Levitt，1990）。

在20世纪80年代中期，对规划系统运行时间缓慢的悲观导致了反射式Agent的提出，称为反应式规划（reactive planning）系统（Brooks，1986；Agre和Chapman，1987）。PENGI（Agre和Chapman，1987）能够用结合了对当前目标及Agent内部状态的“可视化”表示的布尔电路玩一个（完全可观察的）视频游戏。“通用规划”（Schoppers，1987，1989）是作为反应式规划的一种查找表方法发展出来的，但是结果却变成了对马尔可夫决策过程（第17章）中已长期使用的策略的思想的再发现。一个通用规则（或策略）包含从任何状态到在该状态中应该采用的行动的映射。Koenig（2001）综述了在线规划技术，他所用的名称是以Agent为中心的搜索（Agent-Centered Search）。

近年来多 Agent 规划迅速进入大众化，虽然它的确有很长的历史。Konolige（1982）在一阶逻辑内提供了多 Agent 规划的形式化方法，而 Pednault（1986）给出了一个 STRIPS 风格的描述。联合意图的概念来自对通讯活动的研究工作（Cohen 和 Levesque，1990；Cohen 等人，1990），如果 Agent 准备执行一个联合规划则此概念是关键的。Boutilier 和 Brafman（2001）论述了如何修改偏序规划来适应多行动者（multiactor）环境。Brafman 和 Domshlak（2008）设计了一个多行动者规划算法，如果耦合度（可以由 Agent 间交互图的树宽部分测量）是有界的，其复杂度就随行动者数量而线性变化。Petrik 和 Zilberstein（2009）提出了一种基于双线性规划的方法，好于我们在本章所说的覆盖集方法。

我们几乎略过了多 Agent 规划协商的研究工作的表面。Durfee 和 Lesser（1989）讨论了如何通过协商在 Agent 中分摊任务。Kraus 等（1991）描述了玩 Diplomacy（外交）游戏的系统，这是一个需要协商、联盟形成以及欺诈的棋盘游戏。Stone（2000）显示了 Agent 如何在机器人足球赛的竞争的、动态的和部分可观察的环境中作为队友进行合作。在后来的论文中，Stone（2003）分析了两个竞争的多 Agent 环境——RoboCup（机器人足球比赛）以及 TAC（基于拍卖的贸易 Agent 比赛）——发现我们当前理论上非常好的方法计算上的不可操作性导致许多多 Agent 系统是用专门方法设计的。

Marvin Minsky（1986,2007）在他的有高度影响的理论 Society of Mind 中，提出人类思维是有 Agent 集成而来的。Livnat 和 Pippenger（2006）证明了，对于最优路径发现问题，限定总的计算资源，一个 Agent 的最佳体系结构是子 Agent 的集成，每一个都试图优化自己的目标，每个目标都与另一个目标冲突。

11.4.2 节的 bold 模型（机器鸟模型）归功于 Reynolds（1987），他因为在影片《蝙蝠侠归来》（Batman Returns）中把此模型应用到企鹅群而赢得了奥斯卡奖。Bryant 和 Miikkulainen

（2007）描述了 NERO 游戏以及学习策略的方法。

多 Agent 系统的最新书籍包括 Weiss（2000a）、Young（2004）、Vlassis（2008）以及 Shoham 和 Leyton-Brown（2009）写的书。每年还会有一个自治 Agent 与多 Agent 系统年会（AAMAS）。

习题

11.1 我们目前为止所考虑的目标都要求规划器在一个时间步让世界满足目标。不是所有的目标可以如此表示：你通过将一个枝形吊灯抛向空中不会达到将它悬挂在地面上方的目的。更严重的是，你不想你的航天器生命支持系统只供一两天氧气。当 Agent 的规划使一个状况从一个给定状态开始得以连续维持，就能实现维护目标（maintenance goal）。描述如何扩展本章的形式体系来支持维护目标。

11.2 你有一些卡车来运输一些包裹。每个包裹开始在网格地图的某个位置，要运到某个目的地。每辆卡车通过向前和转弯动作直接控制。为这个问题构造出一层高层动作。你的构造编码了关于解的什么知识？

11.3 假设一个高层动作刚好可用一个基元动作序列实现。给定完整的细化层次和基元动作模式，给出一个计算它的前提和效果的算法。

11.4 假设一个高层规划的乐观可到达集是目标集的超集；这个规划是否达到了目标，是否能做出任何结论？如果悲观可到达集与目标集不相交呢？请解释。

11.5 写一个算法，利用初始状态（由一组命题文字描述）和 HLA 序列（每个 HLA 由前提以及乐观和悲观可到达集的纯洁规范定义），计算序列的可到达集的乐观和悲观描述。

11.6 在图 11.2 中，我们显式了如何通过为 DURATION、USE、CONSUME 使用不同的域来描述调度问题中的动作。现在假设我们想结合调度与非确定性规划（要求非确定性的条件效果）。考虑每个域，解释它们是否应该维持不同的域，或是它们是否应该变为动作的效果。这三个域每个给出一个实例。

11.7 标准程序设计语言中的某些操作可以作为改变世界状态的行动而建立模型。例如，赋值操作改变一个内存位置的内容，而打印操作改变输出流的状态。一个由这些操作组成的程序也可以被认为是一个规划，它的目标由程序的规格说明给出。因此，规划算法可以被用来构造一个实现给定规格的程序。

a. 写出赋值算符（将一个变量的值赋给另一个变量）的动作模式。记住初始值将被覆盖！

b. 说明对象创建如何被用于产生通过使用一个临时变量交换两个变量值的规划的规划器所使用。

11.8 假设动作 Flip 总是改变变量 L 的真值。通过使用带有条件效果的动作模式，说明如何定义这个动作的效果。证明，尽管使用条件效果，一个 1-CNF 信念状态表示在一次 Flip 后仍然是 1-CNF 的。

11.9 在积木世界中，为了适当地保持 Clear 谓词，我们被迫引入了两个动作模式 Move 和

MoveToTable。说明使用单个行动如何用条件效果表示这两种情况。

11.10 真空吸尘器世界中 Suck 动作例示了条件效果——哪个方格变得干净取决于机器人在哪个方格。你能想出一个新的命题变量集，定义真空吸尘器世界的状态以使 Suck 有一个非条件描述吗？用你的命题写出 Suck，Left 和 Right 的描述，并证明它们足以描述世界的所有可能状态。

11.11 找到一块合适的脏地毯，没有障碍物，用真空吸尘器打扫它。尽可能正确地画出真空吸尘器采取的路径。参考本章讨论的规划形式来解释它。

11.12 对于上一道习题中的药物治疗问题，增加一个 Test 动作，当 Disease 为真以及任何情况下都有感知效果 Known(CultureGrowth)时它有条件效果 CultureGrowth。图示一个解决问题并最小化使用 Medicare 动作的条件规划。

【译注：11.12题提到“上一道习题”，这里的“上一道习题”应该是：

考虑下列问题：一个病人到达诊所，其症状可能是脱水（dehydration）或者疾病 D 引起的（但并非两者都是病因）。有两种可能的行动：Drink（喝水），无条件治愈脱水，以及Medicate（药物治疗），可以治愈疾病 D，但是如果当病人脱水时服用会产生不希望的副作用。用 PDDL 写出问题描述，并图示解决问题的无传感规划，通过枚举所有相关的可能世界。

在本书第2版中有这一道题，而在第3版中没有这道题，可能是作者遗漏了。