人工智能-第9章-智能规划9

人工智能第9章智能规划ch9.5-9.719.5分层任务网络规划处理复杂软件的一个最普遍的想法是分层分解。复杂软件从子程序或对象类的层次体系创建出来。军队作为单位的等级体系而运转，政府和企业有部门、子部门和分支办公室的分层体系。层次结构的关键好处是，在层次的每一层上，一个计算作任务、军事任务或管理功能都被还原为下一个较低层次的少量行动，所以对当前问题寻找正确的方法来安排这些行动的计算消耗是小的。2在另一方面，非层次方法将一个任务还原为大量单个行动；对大规模问题，这是完全不切实际的。在最好情况下——当高层的解总有令人满意的低层实现时——分层方法能够产生线性时间而不是指数时间的规划算法.3本节描述基于分层任务网络或缩写为HTN的规划方法。这个方法将来自偏序规划的思想和众所周知的“HTN规划”领域的思想结合在一起，在HTN规划中，用来描述问题的初始规划被视为对需要做什么的非常高层的描述——例如，建造一幢房屋，通过应用行动分解来改进规划。每个行动分解将一个高层行动还原为一个低层行为的偏序集。因此，行动分解包含了关于如何实现行动的知识。4例如，建造一幢房屋可以还原为获得一张许可证、雇佣一名承包人、进行建筑、付钱给承包人（图9-5显示了这样的一个分解）。过程继续进行直到规划中只剩下原始行动。典型地，原始行动是那些Agent能够自动执行的行动。对一名一般的承包人而言，“安置景观美化”可能是原始的，因为它只涉及叫来景观美化承包人，对于景观美化承包人，诸如“在这里种植杜鹃花”这样的行动可能被认为是原始的。56在纯“HTN”规划中，规划只由相继的行动分解产生。因此，HTN将规划视为使行动描述更具体化的过程，而不是（如同状态空间和偏序规划中的情况那样）一个从空行动开始构建行动描述的过程。7这表明每个STRIPS行动描述都能够被转变成一个行动分解，且偏序规划可以被看成纯HTN规划的一种特殊情况，然而对于特定任务——尤其是“新颖”的合取式目标——纯HTN规划的视点相当不自然，这样我们更喜欢用混合方法，除了建立开放条件和通过添加定序约束解决冲突的标准操作外，行动分解被用作偏序规划中的规划改进8将HTN规划看作偏序规划的扩展具有额外的优点，我们可以使用相同的符号约定而不是引入一个全新的集合。我们从更详细地描述行动分解开始。然后我们解释必须如何修改偏序规划算法以处理分解。最后我们讨论完备性、复杂度和实用性的问题。9行动分解方法的一般描述被存储在规划库中，它们被从库中抽取出来并被实例化以满足正在被构建的规划的需求。每个方法是一个形如Decompose(a,d)的表达式。这表明行动a能够被分解为规划d，它被表示为一个偏序规划。10建造一幢房子是一个精细而具体的例子，所以我们将用它来说明行动分解的概念。图9-5描绘了将BuildHouse（制造房屋）行动分解成4个低层行动的可能分解。下面是显示了领域的一些行动描述，以及BuildHouse的分解出现在替代库中的样子，规划库中也许存有其他可能的分解。11Action(BuyLand,PRECOND:Money,EFFECT:Land∧~Money)Action(GetLoan,PRECOND:GoodCredit,EFFECT:Money∧Mortage)Action(BuildHouse,PRECOND:Land,EFFECT:House)Action(GetPermit,PRECOND:Land,EFFECT:Permit)Action(HireBuilder,EFFECT:Contract)12Action(HireBuilder,EFFECT:Contract)Action(Construction,PRECOND:Permit∧Contract,EFFECT:HouseBuild∧~Permit)Action(PayBuilder,PRECOND:Money∧HouseBuild,EFFECT:~Money∧House∧~Contract)13Decompose(BuildHouse,Plan(Steps:{S1:GetPermit,S2:HireBuilder,S3:Construction,S4:PayBuilder},ORDERINGS:{Start,Start},LINKS{,,,,,,,,,}))14Action(Construction,PRECOND:Permit∧Contract,EFFECT:HouseBuild∧~Permit)Action(PayBuilder,PRECOND:Money∧HouseBuild,EFFECT:~Money∧House∧~Contract)Decompose(BuildHouse,Plan(Steps:{S1:GetPermit,S2:HireBuilder,S3:Construction,S4:PayBuilder},1516分解的Start行动为那些在规划中没有其他行动提供前提的行动提供所有前提。我们称这此为外部前提。在我们的例子中，分解的外部前提是Land和Money。类似地，作为Finish的前提的外部效果，是所有那些在规划中未被其他行动否定的行动效果。在我们的例子中，BuildHouse的外部效果是House和~Money。某些HTN规划器也区分诸如House的初级效果和诸如~Money的次级效果。只有初级效果才可能被用来获得目标，而两种类型的效果都可能引进与其他行动冲突，这能极大地缩小搜索空间。17分解应该是行动的一个正确实现，如果已知a的前提，规划d对于获得a的效果的问题是一个完备且一致的偏序规划，则规划d正确地实现了行动a。显然，如果分解是运行一个可靠偏序规划器的结果，那么它是正确的。18一个规划库对任何给定高层行动能够包含几种分解。例如，BuildHouse可能有另一种分解，它描述了Agent是如何空手用石头和泥炭建造房子的。每个分解应该是一个正确规划，但是它能够在高层行动描述以外附加的前提和效果。例如，图9-5的BuildHouse的描述需要除Land以外的Money，并有效果~Money。在另一方面，自己建造的选项不需要钱（Money）但是的确需要准备提供Rocks（石头）和Turf（泥炭），能够导致BadBack。19给定一个高层行动，比如BuildHouse，可能存在几种可能的分解，在它的STRIPS行动描述中隐藏那些分解的某些前提和效果是不可避免的，高层行动的前提应该是其分解的外部前提的交集，它的效果应该是分解的外部效果的交集。换个角度说，高层前提和效果保证是每个原始实现的真值前提和效果的子集。20信息隐藏的两种其他形式应该被注意到，第一，高层描述完全忽视了分解的所有内部效果。例如，我们的BuildHouse分解包含时序的内部效果Permit（许可证）和Contract（合同）。第二，高层描述没有详细说明行动“内部”的时间区间，在其间高层前提是必须成立的效果，例如，Land（土地）前提必须只能为真（在我们非常近似的模型中）直到GetPermit（得到许可证）完成。只有在

PayBuilder（支付施工人员）完成之后House才为真。21如果要用分层规划减小复杂度，这种类型的信息隐藏是根本的。我们需要能够对高层行动进行推理而不需要实现的种种细节。然而，有必须负担的代价。例如，一个高层行动的内部条件和另一个的内部行动之间可能存在冲突，但是没有办法从高层描述检测它。这个问题对HTN规划算法有重要含义。简而言之，尽管原始行动可以被规划算法视为点事件，高层行动仍然具备时序范围，在这范围内各种事情都可能发生。229.6非确定性规划到目前为止，我们只考虑了经典规划领域。它们是完全可观察的、静止的和确定性的。此外，我们已经假设行动描述是正确而且完备的。在这些情况下，Agent能够先规划，然后“闭上眼睛”执行规划。另一方面，在一个不确定的环境中，Agent必须用它的感知来发现当执行规划时发生了什么，以及当一些意外的事情发生时对规划可能进行的修改或替换。

23Agent不得不处理不完备和不正确的信息。不完备性的产生是因为世界是部分可观察的、非确定性的，或者两者都是。例如，通往办公室储备间的门可能锁着也可能没锁：如果它被锁着的话，我的一把钥匙可能打得开也可能打不开门；我可能知道也可能不知道在我的知识里的这种不完备性。因此，我的对世界的模型是不充分的，不过是正确的。24另一方面，不正确性的产生是因为世界不必匹配我的世界模型。例如，我可能相信我的钥匙能够打开储备间，但是如果门锁已经被更换，那么我就是错误的。没有处理不正确信息的能力，一个Agent最终将像蜣螂一样缺乏智能，这种甲虫会努力地用粪球来堵住它的窝，即使在粪球已经从它的掌握中拿走以后。25获得完备或正确的知识的可能性取决于世界有多少不确定性。在有界不确定性的条件下，行动能够有不可预知的效果，但是可能效果可以在行动描述公理中列出。例如，当我们掷硬币时，说“结果会是正面(Heads)或背面(Tails)”是合理的。通过使规划能够在所有可能的环境中都可行，Agent可以应付有界不确定性。另一方面，在无界不确定性的条件下，可能的前提或效用集要么是未知的，要么太大而不能完全枚举。26这是在类似驾驶、经济规划和军事战略这样的非常复杂或动态领域中的状况。只有当Agent准备好修改它的规划和／或知识库时，它才能处理无界不确定性。无界不确定性与通过列举现实世界行动的所有前提而获得预期效果的不可能性有密切的关系。27有四种处理不确定性的规划方法。前面两种适合有界不确定性，后面两种适合无界不确定性：1.无传感规划2．条件规划3．执行监控和重新规划4．持续规划28无传感规划也称为一致性规划，这种方法构造无感知地执行的标准串行规划。无传感规划算法要确保规划在各种可能环境中获得目标，不管真实的初始状态和实际的行动结果是什么。无传感规划依赖于强制——世界能够被强制进入一个给定状态的思想，即使当Agent只有关于当前状态的部分信息时。强制并不总是可能的，所以无传感规划常常并不实用。29条件规划也称为偶发性规划，这种方法通过对可能出现的不同的偶发性构造具有不同分支的条件规划来处理有界不确定性。正如经典规划中那样，Agent先规划，然后执行产生的规划。Agent通过在规划中包含感觉行动以测试合适的条件，从而找出应该执行哪部分规划。例如，在机场运输领域，我们可以有“检查SFO机场是否在运转。如果是，飞往那里；否则，飞往Oakland”的规划30执行监控和重新规划在这种方法中，Agent能够使用前述的任何一种规划技术(经典的、无传感器的或条件的)来构造一个规划，但是它也用执行监控来判断规划是不是当前实际情景的预定措施或者需要被修改。当出现错误时，发生重新规划。按这种方式，Agent能够处理无界不确定性。例如，即使重新规划Agent没有预见到SFO被关闭的可能性，但是当这发生时它能认识到这种情景并再次调用规划器寻找一条到达目标的新路径。31持续规划迄今为止我们所看到的所有规划器都被设计用于获得一个目标然后停止。一个持续规划器被设计成终生持续的。它能处理环境中的不可预料的情况，即使这些发生在Agent构造规划的过程当中。它通过目标形式化也能处理目标的放弃和附加目标的创建。32下面考虑一个例子来阐明各种类型Agent之间的不同。问题是这样的：给定初始状态，有一把椅子、一张桌子和几罐油漆，在每件物品都不知道颜色的情况下，获得椅子和桌子有相同颜色的状态。经典规划Agent不能处理这个问题，因为初始状态不是完全指定的——我们不知道家具是什么颜色的。33无传感规划Agent必须找到一个在执行规划期间不需要任何传感器的规划。解是能够打开任何油漆并把它用于椅子和桌子上，这样强制它们成为同一种颜色（即使Agent不知道是什么颜色）。当命题是代价昂贵的或不可能感知的时候，强制是最合适的。例如，医生经常开广谱抗菌素，而不是使条件规划：先进行血液测试，然后等着结果出来，再开更特效的抗菌素。他们之所以这么做是因为执行血液测试涉及的延迟和开销通常太大。34条件规划Agent能够产生一个更好的规划：首先感觉桌子和椅子的颜色；如果它们已经是同样的，那么规划完成。如果不是，感觉油漆罐上的标签：如果有一个罐的颜色跟其中一件家具的颜色一样，那么把这罐油漆用到另一件家具上。否则，用任何一种颜色来漆两件家具。35重新规划Agent能够产生和条件规划器相同的规划，或者它能在最初产生更少的分支，在执行期间需要时再填入其他分支。它也能处理其行动描述的不正确性。例如，假设Paint(obj,color)行动被相信有确定性的效果Color(obj,color)。条件规划器只是假设一旦行动被执行，效果就会发生，但是重新规划Agent要检验效果，如果它不正确（可能是因为Agent粗心而错过了一点），那么它能重新规划再漆这一点。持续规划Agent，除了处理不可预料的事件外，能够适当地修改规划，如果把“在桌子上用餐”添加到目标中，那么油漆规划必须被推迟。36在真实世界中，Agent使用这些方法的组合。汽车制造厂商出售备用轮胎和保险气囊，这是设计用于处理刺破或碰撞的条件规划分支的实际体现；另一方面，许多汽车驾驶员从来没有考虑过这种可能性，所以他们对刺破和碰撞的反应就如同重新规划Agent。一般而言，Agent只为那些具有重要后果和不可忽略出错机会的偶发事件构造条件规划。因此，一个期望横穿撒哈拉沙漠旅行的汽车驾驶员会仔细地考虑汽车抛锚的可能性，而去超市的旅行则需要较少的预先规划。379.7多Agent规划

9.7.1合作：联合目标和规划9.7.2多Agent规划9.7.3协调机制9.7.4竞争38到目前为止，我们已经处理了单Agent环境，在其中我们的Agent是独处的。当环境中有其他Agent时，我们的Agent能够简单地将它们包含在它的环境模型中，而不必改变它的基本算法。然而在很多情况下，这将导致较差的性能，因为对付其他Agent跟对付自然环境是不一样的。特别地，自然环境(人们假设)对Agent的意图不感兴趣，然而其他Agent不是这样的。本节引入多Agent规划来处理这些情况。39多Agent环境可以是合作的或者竞争的。我们从一个简单的合作例子开始：网球双打的团队规划。可以构造指定团队内每个队员行动的规划；我们将描述有效地构造这类规划的技术。有效的规划构造是有用的，但是并不保证成功：Agent不得不同意使用同样的规划！这需要某种形式的协调，可能通过通信获得。409.7.1合作：联合目标和规划参加一个网球双打团队的两个Agent有赢得比赛的联合目标，这带来各种子目标。让我们假设在游戏中的某一点，它们有联合目标，将击给它们的球打回去并确保它们中至少有一个防守网前。我们可以把这个观念表示为一个多Agent规划问题，描述如下：41Agents(A,B)

Init(At(A,[Left,Baseline])∧At(B,[Right,net])∧Approaching(Ball,[Right,Baseline]))∧Partner(A,B)∧Partner(B,A)

Goal(Returned(Ball)∧At(agent,[x,Net]))

Action(Hit(agent,Ball)PRECOND:Approaching(Ball,[x,y])∧At(agent,[x,y])∧Partner(agent,partner)∧~At(partner,[x,y]), EFFECT:Returned(Ball)) Action(Go(agent,[x,y]),PRECOND:At(agent,[a,b]),EFFECT:At(agent,[x,y])∧~At(agent,[a,b]))42这种符号表示引入了两个新特征。第一，Agent(A,B)声明有两个AgentA和B，它们参与规划。(对于这个问题，对手不是被考虑的Agent。)第二，每个行动明确地将Agent作为一个参数，因为我们需要记录是哪个Agent完成的。多Agent规划问题的一个解是由每个Agent的行动组成的联合规划。如果当每个Agent都执行它分配到的行动时目标能够实现，那么这个联合规划是一个解。43下面的规划是网球问题的一个解：如果两个Agent有相同的知识库，并且如果这是惟一的解，那么每件事都很好：Agent能够各自决定解，然后联合执行它。

PLAN1：A：[Go(A,[Right,Baseline]),Hit(A,Ball)]B：[NoOp(B)，NoOp(B)]44对于Agent，还有另一个和第一个规划同样满足目标的规划：

PLAN2：

A：[Go(A,[Left,Net]),NoOp(A)]B：[Go(B,[Right,Baseline]),Hit(B,Ball)]45如果A选择规划2，B选择规划1，那么没有人会把球打回去。相反，如果A选择1，B选择2，那么它们可能互相碰撞，仍然没有人把球打回去，网前也会保持无保护状态。因此，存在正确的联合规划并不意味着目标会实现。Agent需要一个协调的机制来达到相同的联合规划：此外，某个特定的联合规划将被执行，在Agent中这应该是常识。469.7.2多Agent规划本节集中在正确联合规划的构建上，暂时推迟协调问题。我们称这为多Agent规划；它本质上是面对单个集中Agent的规划问题，它能够指示几个物理实体中每一个的行动。在真正的多Agent情况下，它使得每个Agent能够计算出如果联合执行将会成功的可能联合规划是什么。47我们进行多Agent规划的方法是基于偏序规划的，假设环境是完全可观察的，以保持事物的简单性。有一个不会在单Agent情况下出现的附加情况：环境不再是真正静态的，因为当任何特定的Agent正在深思时，其他Agent可能行动。因此，我们需要关注同步。为了简单起见，我们假设每个行动需要花费等量的时间，而且联合规划中每一点的行动是同时发生的。48在时间的任何一点，每个Agent刚好执行一个行动(可能包含NoOp)。同时发生的行动集被称为联合行动。例如，具有两个AgentA和B的网球域的一个联合行动是<NoOp(A)，Hit(B,Ball)>。一个联合规划由联合行动的偏序图组成。例如，网球问题的规划2可以表示为这个联合行动序列：<Go(A,[Left，Net)),Go(B,(Right,Baseline])><NoOp(A),Hit(B,Ball)>49我们能够用常规的POP算法进行规划，应用于所有可能联合行动的集合。惟一的问题是这个集合的大小：有10个行动和5个Agent，我们得到105个联合行动。正确地指定每个行动的前提和效果是乏味的，而且用如此大的一个集合进行规划是无效率的。50一个替代方法是通过描述每个单独的行动如何与其他可能行动互相影响来隐含地定义联合行动。这会变得简单，因为大部分行动独立于大部分其他行动；我们只需要列出少数几个真正相互作用的行动。我们可以扩充通常的STRIPS或ADL行动描述来做到，通过使用一个新特征：并发行动表。这与行动描述的前提相似，除了不再描述状态变量之外，它描述的行动一定是或一定不是并发执行的。51例如，Hit行动可以被描述如下：Action(Hit(A,Ball),CONCURRENT:~Hit(B,Ball)PRECOND:Approaching(Ball,[x,y])∧At(A,[x,y]))EFFECT：Returned(Ball))这里，我们得到了禁止并发性约束，在执行Hit行动期间不能有另一个Agent的其他Hit行动。52我们也可以要求并发行动，例如当需要两个Agent运送装满饮料的冷却器到网球场时。这个行动的描述说明AgentA不能执行一个Carry(运送)行动，除非另一个AgentB正在同时执行对同一个冷却器的Carry行动：

Action(Carry(A,cooler,here,there), CONCURRENT:Carry(B,cooler,here,there) PRECOND:At(A,there)∧At(cooler,there)∧Cooler(cooler) EFFECT:At(A,there)∧At(cooler,there)∧~At(A,here)∧~At(cooler,here)用这种表示，创建一个非常接近于POP偏序规划器的规划器是可能的。53有3点不同：

(1)除了时序关系之外，我们允许A=B和，分别意味着“并发的”和“之前或并发”。

(2)当一个新行动需要并发行动时，我们必须用规划中新的或已经存在的行动来实例化那些并发行动。

(3)禁止并发行动是一个约束的附加来源。每个约束必须通过对冲突行动的前后顺序加以约束来解决。549.7.3协调机制一组Agent能够确保在一个联合规划上取得一致的最简单方法是在参加联合行动之前采用公约。公约是在对联合规划的选择之上的任何约束，超过“如果所有Agent都采用则联合规划必须运转”的基本约束。例如，公约“坚守球场上你的那一侧”会引起双打伙伴选择规划2，而公约“一个参赛者总是待在网前”会导致它们选择规划1。一些公约，如在道路的某一侧驾驶，是如此广泛地被采用以至它们被认为是社会法律。人类的语言也可以被视为公约。55前一段落中的公约是领域特定的，并且能通过对行为描述进行约束以排除违反公约的情况来实现。一个更加一般的方法是使用领域无关的公约。例如，如果每个Agent运行具有相同输入的同一个多Agent规划算法，它能遵循“执行第一个找到的可行联合规划”的公约，确信其他Agent也会做出相同的选择。一个更鲁棒但是更昂贵的策略是产生所有的联合规划，然后挑选一个，比如说，其印刷表示是按字母排序的第一个。56公约也会通过进化的过程出现。例如，群居昆虫群体执行非常精细的联合规划，这被群体内个体的共同基因构造所推动。一致性也能通过公约的偏差会减少进化适应性的事实而被增强，所以任何可行的联合规划都能够变成稳定的均衡。将相似的考虑应用到人类语言的发展上，其中重要的事情不是每个个体该说哪种语言，而是所有个体说同一种语言的事实。最后一个例子出现在鸟类的群居行为中。57我们能够得到一个合理的模拟，如果每个鸟类Agent(有时称为机器鸟，或写为bird)用某种组合方法来执行下面的3条规则：(1)分离性：当你开始变得太近时，飞行远离邻居；(2)凝聚性：飞向邻居的平均位置；(3)列队性：飞向邻居的平均方向(朝向)。如果所有的鸟执