第六章 规划系统.doc

第六章 规划系统自动规划是一种重要的问题求解技术，与一般问题求解相比，自动规划更注重于问题的求解过程，而不是求解结果。此外，规划要解决的问题，如机器人世界问题，往往是真实世界问题，而不是比较抽象的数学模型问题。与前几章介绍的求解技术相比,自动规划系统与专家系统均属高级求解系统与技术。在本章我们专门研究规划系统求解问题,至于专家系统也将于第八章着重介绍。 6.1 规划的作用与任务 6.1.1.规划的概念 规划是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。简而言之，规划是一个行动过程的描述。一个总规划可以含有若干个子规划。 6.1.2.规划的作用与问题分解途径1.规划的特性和作用 在日常生活中，规划意味着在行动之前决定行动的进程，或者说，规划这一词指的是在执行一个问题求解程序中任何一步之前，计算该程序几步的过程。一个规划是一个行动过程的描述。它可以像百货清单一样的没有次序的目标表列；但是一般来说，规划具有某个规划目标的蕴含排序。例如，对于大多数人来说，吃早饭之前要先洗脸和刷牙或漱口。又如，一个机器人要搬动某工件，必须先移动到该工件附近，再抓住该工件，然后带着工件移动。 许多规划所包含的步骤是含糊的。而且需要进一步说明。譬如说，一个工作日规划中有吃午饭这个目标，但是有关细节，如在哪里吃，吃什么，什么时间去吃等等，都没有说明。与吃午饭有关的详细规划是全日规划的一个子规划。大多数规划具有很大的子规划结构，规划中的每个目标可以由达到此目标的比较详细的子规划所代替。尽管最终得到的规划是某个问题求解算符的线性或分部排序，但是由算符来实现的目标常常具有分层结构，如图6.1所示的工作日规划就是一例。图 6.1 子规划的分层结构例子 缺乏规划可能导致不是最佳的问题求解；例如有人由于缺乏规划，为了借一本书和还一本书而跑了两次图书馆。此外，如果目标不是独立的，那么动作前缺乏规划就可能在实际上排除了该问题的某个解答。例如，建筑一个变电所的规划包括砌墙、安装变压器和铺设电缆线等子规划。这些子规划不是相互独立的，首先必须铺设电缆，然后砌墙，最后进行变压器安装。如果缺乏规划，颠倒了次序，就建不成变电所。规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。如果该问题求解系统不是问题求解环境中唯一的行动者，以及如果此环境可能按照无法预计的方法变化，那么这种监控就显得特别重要。例如，考虑某个在遥远星球上空运行的飞行器，它必须能够规划一条航线，然后，当发现环境状态与预期不合时，就进行重新规划。有关该环境状态的反馈与预期的规划状态进行比较，当两者存在差异时，就对此规划进行修正。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。2.问题分解途径及方法把某些比较复杂的问题分解为一些比较小的子问题的想法使我们应用规划方法求解问题在实际上成为可能。有两条能够实现这种分解的重要途径。第一条重要途径是，当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。 例如，一个机器人从一个房间走动到另一个房间这并不改变两个房间内门窗的位置。当问题状态的复杂程度提高时，框架(画面)问题(研究如何决定哪些事物是变化的以及哪些是不变的问题)就变得越来越重要。要表示出八数码难题每走动一步后的状态如何变化是不难的，要隐含地记录下具有适当变化的新状态也不需要做大量的工作。从一个状态移动到另一个状态的规则可以简单的描述为整盘棋如何从一种位置变换为另一种位置，不过，如果我们考虑引导一个机器人围绕着原来的房子移动的问题，那么情况就要复杂得多。一个单一的状态描述就会十分庞大，因为它必须描述房子中的每个物体是在什么地方以及该机器人是在哪里。对机器人部件的某个给定动作只改变整个状态的一个小部分。如果该机器人推移一张桌子横过房间，那么这张桌子和桌面上的所有物体的位置就要发生变化，而房间内其它物体的位置并不发生变化。与其写出叙述把一个完整状态变换为另一个完整状态的规则，我们宁愿只写出叙述该状态描述中发生变化的那部分的规则。而对于其余部分，我们可以假定保持不变。 第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题，这种分解能够使困难问题的求解变得容易些。 虽然这样做有时是可能的，但往往是不可能的。替代的办法是，可以把许多问题看做几乎可分解的问题，即意味着它们可以被分割为只有少量互相作用的子问题。例如，假设我们要把某个房间里的所有家具都搬出去。这个问题可被分解为一个较小问题的集合，其中每个子问题只包括把一件家具移出该房间。在每个子问题中，如考虑搬动抽屉，可以单独地从每件家具找到位置，不过，如果在长沙发椅后面有个书架，那么在搬动书架之前，我们必须先把长沙发椅搬开。要解决这种准可解问题，我们希望有一种方法能够允许我们应用我们已经研究过的技术对每个子问题分别求解，然后记下这些子问题间可能出现的互相作用，并对它们加以适当处理。 曾经提出过几种进行这两类分解的方法。这些方法主要包括把原问题分解为适当的子问题的方法以及在问题求解过程中发现子问题时记录和处理子问题间的互相作用。这些方法就是规划的方法。当描述计算机问题求解的特性时，规划和行动之间的区别有点减少，因为除了规划之外，计算机实际上很少能够做更多其它的事。举例来说，在求解15数码难题时，我们实际上所做的是概括求解此问题时计算机可能生成某个规划的途径。对于这样的15数码难题，规划和行动之间的区别是不重要的。不过，在其它情况下，区别可能起关键作用。在求解15数码难题时，计算机可能用人们实际上采用的同样方法去为解答寻找一个规划。人们试图解答此问题时所采用的方法是走动棋盘上的棋子。如果在真实世界中的解答步骤是不可忽略的或非进行不可的，那么，规划就变得非常重要。尽管现实世界的步骤可能是无法改变的，但是这些步骤的计算机模拟都是可以改变的。所以，我们可以在允许回溯的模拟世界中寻找一个完整的解答以避开真实世界的约束，而且只有在找到一个解答之后，才走出到执行规划的世界里去。3.域的预测和规划的修正 (1)域的预测 规划方法的成功取决于问题论域的另一特性-预测。如果我们通过在实际上执行某个操作序列来寻找问题的解答，那末在这个过程的任何一步我们都能确信该步的结果。但对于不可预测的论域，我们最好能考虑可能的结果的集合，这些结果很可能按照它们出现的可能性以某个次序排列。然后，我们产生一个规划，并试图去执行这个规划。(2)规划的修正如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。大多规则的执行主要是按目标定向模式工作的。在种模式下，规划系统从目标状态向可达到的初始状态进行搜索。6.2. 基于谓词逻辑的规划 基于谓词逻辑的规划是用谓词逻辑来描述世界模型及规划过程的一种规划方法，它在人工智能中有着广泛的应用。作为问题求解的一种方法，和其它问题求解方法一样，首先要解决的就是待求解问题的表示，为此我们先从问题的表示谈起。6.2.1 规划世界模型的谓词逻辑表示为更清楚地阐明问题，我们举一个机器人的例子来说明：现在是2010年，中国神洲号运载火箭已把机器人R送到火星进行探索，机器人正位于L3处，它要把位于工具箱T内的探测仪W取出并放到到探测架F（F上为空时才能放）上，以对火星地表进行探测，工具箱T和探测架F分别位于L1和L2处，如图6.2所示。为完成这个任务，需要规划机器人的这一行动过程。首先引入相关的谓词： CLEAR(x):x上是空的HANDEMPTY(x):x手中是空的HOLDING(x, y):x手中拿着yON(x, y):x在y之上NEAR(x, y):x在y的附近IN(x, y):x在y中AT(x, y):x在y处（上）ISCLOSE(x):x处于关闭状态ISOPEN(x):x处于打开状态OPEN(x, y):x把y打开CLOSE(x, y):x把y关闭GOTO(x, y):x走到y的旁边PICKDOWN(x, y, z):x把y放在z上PICKUP(x, y):x把y拿起图 6.2 机器人规划世界这样，问题的初始状态就可以描述为：AT(T, L1)IN(W, T)ISCLOSE(T)AT(F, L2)CLEAR(F)AT(R, L3)HANDEMPTY(R)目标状态：AT(T, L1)IN(W,T)ISOPEN (T)AT(F, L2)ON(W, F)NEAR(R, F)HANDEMPTY(R) 一般来说，如果问题可解的话，在经过一系列的操作后，都可以把其初始状态转化为目标状态，从而实现问题的求解。规划的目的就是找出这一系列的操作，然后把这些操作告诉机器，机器就可以按预定的操作完成相应的任务。操作可以分为先决条件和行为动作两个部分，只有当前状态的先决条件被满足时，才能进行相应的动作，同时使得当前状态转变到下一个状态。对于上面给出的例子，其基本操作为： OP1：OPEN(x, y)先决条件：NEAR(x, y)ISCLOSE(y)行为动作：删除：ISCLOSE(y)OP2：CLOSE(x,y)先决条件：NEAR(x, y)ISOPEN(y)行为动作：删除：ISOPEN(y)添加：ISCLOSE(y)OP3：GOTO(x, y)先决条件：NEAR(x, y)行为动作：删除：NEAR(x,y)添加：NEAR(x, y)OP4：PICKDOWN(x, y, z)先决条件：NEAR(x,z)HOLDING(x,y)CLEAR(z)行为动作：删除：CLEAR(z)HOLDING(x, y)添加：ON(x, z)OP5：PICKUP(x, y)先决条件：NEAR(x,z)IN(y,z)ISOPEN(z)HANDEMPTY(x)行为动作：删除：IN(y, z)HANDEMPTY(x)添加：HOLDING(x, y)IN(x,z)当然，还可以进一步的规划，但这里作为命题逻辑规划方法的一个例子，为了突出关键事件状态的变迁，我们对操作行为做了简化，希望读者能从这个例子中体会到这种规划方法的基本原理。另外，上述操作的先决条件也不是唯一的，在此我们对每一种操作仅列出一个先决条件。 6.2.2 基于谓词逻辑规划的基本过程上已述及，规划的目的就是找到能把初始状态转变为目标状态的操作序列。为此，我们可以运用上节介绍的问题分解途径的第二种方法来规划，即把问题分割成几个有希望的较为容易解决的子问题。依据这种思想，上述的规划问题就可以依序转化为下列几个子问题的规划：Plan1：机器人R从L3处走到工具箱T的旁边，其先决条件假设为S1；Plan2：机器人R打开工具箱T，其先决条件假设为S2；Plan3：机器人R从工具箱中取出探测仪W，其先决条件假设为S3；Plan4：机器人R从工具箱T的旁边走到探测架F的旁边，其先决条件假设为S4；Plan5：机器人R把探测仪W放在探测架F上，其先决条件假设为S5；至此机器人R的任务完成。这一过程可用图形简单表示如图6.3所示： 图 6.3 机器人搬出探测仪的规划过程于是，我们很容易给出用谓词逻辑描述的机器人规划序列：初始状态：AT(T,L1)IN(W,T)ISCLOSE(T)AT(F,L2)CLEAR(F)AT(R,L3)HANDEMPTY(R)OP3OP3：GOTO(R, T)注：AT(R, L3)满足NEAR(R, T)，且HANDEMPTY(R)，故GOTO(R, T)的先决条件被满足中间状态 1：AT(T,L1)IN(W,T)ISCLOSE(T)AT(F,L2)CLEAR(F)NEAR(R,T)HANDEMPTY(R) Plan2OP1：OPEN(R, T)注：OPEN(R, T) 的先决条件NEAR(R, T)ISCLOSE(T)被满足中间状态 2：AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,T)HANDEMPTY(R)Plan3OP5：PICKUP(R, W)注：PICKUP(R, W) 的先决条件NEAR(R, T)IN(W,T)ISOPEN(T)HANDEMPTY(R)被满足中间状态 3：AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,T)HOLDING(R,W)Plan4OP3：GOTO(R, F)注：AT(R, L1)满足NEAR(R, T)，且HOLDING(R, W)，故GOTO(R, T)的先决条件被满足中间状态 4：AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)CLEAR(F)NEAR(R,F)HOLDING(R,W)Plan5OP5：PICKDOWN(R, W, F)注：先决条件NEAR(R, F)HOLDING(R, W)CLEAR(F)被满足目标状态：AT(T,L1)IN(W,T)ISOPEN(T)AT(F,L2)ON(W,F)NEAR(R,F)HANDEMPTY(R) 从上面这一例子可以看出，规划是行动过程的描述，是问题求解的行为序列；同时亦了解到了规划的基本原理和方法，这为学习以下几节乃至后续章节的内容奠定了基础。6.3. STRIPS规划系统 在前面两节中，我们已经介绍了规划的一些基本概念和原理，在此基础上，本节进一步研究更为完整的规划-规划系统。6.3.1 积木世界的机器人规划问题求解是一个寻求某个动作序列以达到目标的过程，机器人问题求解即寻求某个机器人的动作序列(可能包括路径等)，这个序列能够使该机器人达到预期的工作目标，完成规定的工作任务。1.积木世界的机器人的问题机器人技术的发展为人工智能问题求解开拓了新的应用前景，并形成了一个新的研究领域-机器人学。许多问题求解系统的概念可以在机器人问题求解上进行试验研究和应用。机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套动作。设想有个积木世界和一个机器人。世界是几个有标记的立方形积木(在这里假定为一样大小的)，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下： unstack(a,b)：把堆放在积木b上的积木a拾起。在进行这个动作之前，要求机器人的手为空手，而且积木a的顶上是空的。stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住积木a，而且积木b顶上必须是空的。pickup(a)：从桌面上拾起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。机器人规划包括许多功能，例如识别机器人周围世界，表述动作规划，并监视这些规划的执行。我们所要研究的主要是综合机器人的动作序列问题，即在某个给定初始情况下，经过某个动作序列而达到指定的目标。采用状态描述作为数据库的产生式系统是一种最简单的问题求解系统。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操作和执行操作的结果，我们需要应用下列谓词： ON(a,b)：积木a在积木b之上。ONTABLE(a)：积木a在桌面上。CLEAR(a)：积木a顶上没有任何东西。HOLDING(a)：机械手正抓住积木a。HANDEMPTY：机械手为空手。图 6.4 积木世界的机器人问题 图6.4(a)所示为初始布局的机器人问题。这种布局可由下列谓词公式的合取来表示： CLEAR(B)：积木B顶部为空CLEAR(C)：积木a在桌面上。ON(C，A)：积木C堆在积木A上ONTABLE(A)：积木A置于桌面上ONTABLE(B)：积木B置于桌面上HANDEMPTY：机械手为空手。目标在于建立一个积木堆，其中，积木B堆在积木C上面，积木A又堆在积木B上面，如图6.4(b)所示。也可以用谓词逻辑来描述此目标为：ON(B，C)ON(A，B)2.用F规则求解规划序列采用F规则表示机器人的动作，这是一个叫做STRIPS规划系统的规则，它由3部分组成。第一部分是先决条件。为了使F规则能够应用到状态描述中去。这个先决条件公式必须是逻辑上遵循状态描述中事实的谓词演算表达式。在应用F规则之前，必须确信先决条件是真的。F规则的第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。F规则第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。对于堆积木的例子中move这个动作可以表示如下： move(x,y,z)：先决条件：删除表：添加表：把物体x从物体y上面移到物体z上面。CLEAR(x),CLEAR(z)，ON(x,y)ON(x,y)，CLEAR(y)ON(x,z)，CLEAR(y) 图 6.5 表示move动作的搜索树 如果move为此机器人仅有的操作符或适用动作，那么，可以生成如图6.5所示的搜索图或搜索树。下面我们更具体地考虑图6.4中所示的例子，机器人的4个动作(或操作符)可用STRIPS形式表示如下： (1) stack(X,Y)先决条件和删除表：HOLDING(X)CLEAR(Y)添加表：HANDEMPTY，ON(X，Y)(2) unstack(X,Y)先决条件：HANDEMPTYON(X，Y)CLEAR(X)删除表：ON(X，Y)，HANDEMPTY添加表：HOLDING(X)，CLEAR(Y)(3) pickup(X)先决条件：ONTABLE(X)CLEAR(X)HANDEMPTY删除表：ONTABLE(X)HANDENPTY添加表：HOLDING(X)(4) putdown(X)先决条件和删除表：HOLDING(X)添加表：ONTABLE(X)，HANDEMPTY假定目标为图6.4(b)所示的状态，即ON(B，C)ON(A，B)。从图6.4(a)所示的初始状态描述开始正向操作，只有unstack(C,A)和pickup(B)两个动作可以应用F规则。图6.6所示给出这个问题的全部状态空间，并用粗线指出了从初始状态(用S0标记)到目标状态(用G标记)的解答路径。与习惯的状态空间图画法不同的是，这个状态空间图显出问题的对称性，而没有把初始节点S0放在图的顶点上。此外，要注意到本例中的每条规则都有一条逆规则。沿着粗线所示的支路，从初始状态开始，正向地依次读出连接弧线上的F规则，我们就得到一个能够达到目标状态的动作序列于下：unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B)就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。6.3.2 STRIPS系统规划STRIPS(STanford Research Institute Problem Solver)，即斯坦福研究所问题求解系统，是从被求解的问题中引出一般性结论而产生规划的。我们先从系统的组成讲起，然后再讨论系统的规划。1.STRIPS系统的组成STRIPS是由Fikes、Hart和Nilsson三人在1971及1972研究成功的，它是夏凯(Shakey)机器人程序控制系统的一个组成部分。这个机器人是一部设计用于围绕简单的环境移动的自推车，它能够按照简单的英语命令进行动作。夏凯包含下列4个主要部分： (1)车轮及其推进系统；(2)传感系统，由电视摄象机和接触杆组成；(3)一台不在车体上的用来执行程序设计的计算机。它能够分析由车上传感器得到的反馈信息和输入指令，并向车轮发出使其推进系统触发的信号；(4)无线电通讯系统，用于在计算机和车轮间的数据传送。STRIPS是决定把哪个指令送至机器人的程序设计。该机器人世界包括一些房间、房间之间的门和可移动的箱子；在比较复杂的情况下还有电灯和窗户等。对于STRIPS来说，任何时候所存在的具体的突出的实际世界都由一套谓词演算子句来描述。例如，子句INROOM(ROBOT，R2)在数据库中为一断言，表明该时刻机器人在2号房间内。当实际情况改变时，数据库必须进行及时修正。总起来说,描述任何时刻的世界的数据库就叫做世界模型。控制程序包含许多子程序，当这些子程序被执行时，它们将会使机器人移动通过某个门，推动某个箱子通过一个门，关上某盏电灯或者执行其它的实际动作。这些程序本身是很复杂的，但不直接涉及问题求解。对于机器人问题求解来说，这些程序有点像人类问题求解中走动和拾起物体等动作一样的关系。上一节已介绍过STRIPS系统F规则(即操作符)的组成。整个STRIPS系统的组成如下：(1)世界模型。为一阶谓词演算公式；(2)操作符(F规则)。包括先决条件、删除表和添加表；(3)操作方法。应用状态空间表示和中间结局分析。例如：状态：(M，G)，包括初始状态、中间状态和目标状态。初始状态：(M0，(G0)目标状态：得到一个世界模型，其中不遗留任何未满足的目标2.系统的规划过程(1)问题的表示每个STRIPS问题的解答为某个实现目标的操作符序列，即达到目标的规划。下面举例说明STRIPS系统规划的求解过程。考虑STRIPS系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型示于图6.7。设有两个操作符，即gothru和pushthru(走过和推过)，分别描述于下：OP1：gothru(d,r1,r2)机器人通过房间r1和房间r2之间的d，即机器人从房间r1走过门d而进入房间r2。先决条件：INROOM(ROBOT，r1)CONNECTS(d,r1,r2)；机器人在房间r1内，而且门d连接r1和r2两个房间。图 6.7 STRIPS的一个简化模型 删除表：INROOM(ROBOT，S)；对于任何S值。添加表：INROOM(ROBOT，r2)。OP2：pushthru(b,d,r1,r2)机器人把物体b从房间r1经过门d推到房间r2。先决条件：INROOM(b,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,r2)删除表：INROOM(ROBOT，S)，INROOM(b，S)；对于任何S。添加表：INROOM(ROBOT，r2),INROOM(b,r2)。这个问题的差别表如表6.1所示。 表 6.1 差别表假定这个问题的初始状态M0和目标G0如下：M0：INROOM(ROBOT，R1)INROOM(BOX1,R2)CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)(2)基于中间结局分析方法的规划求解下面，采用中间结局分析方法来逐步求解这个机器人规划。 do GPS的主循环迭代，until M0与G0匹配为止。 begin。 G0不能满足M0，找出M0与G0的差别。尽管这个问题不能马上得到解决，但是如果初始数据库含有语句INROOM(BOX1，R1)，那么这个问题的求解过程就可以得到继续。GPS找到它们的差别d1为INROOM(BOX1，R1)，即要把箱子(物体)放到目标房间R1内。 选取操作符：一个与减少差别d1有关的操作符。根据差别表，STRIPS选取操作符为：OP2：pushthru(BOX1,d,r1,R1) 消去差别d1,为OP2设置先决条件G1为：G1：INROOM(BOX1,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,R1)这个先决条件被设定为子目标，而且STRIPS试图从M0到达G1。尽管G1仍然不能得到满足，也不可能马上找到这个问题的直接解答。不过STRIP发现：如果 r1=R2, d=D1，当前数据库含有INROOM(ROBOT，R1)那么此过程能够继续进行。现在新的子目标G1为：G1：INROOM(BOX1，R2)INROOM(ROBOT，R2)CONNECTS(D1，R2，R1) GPS(p)；重复第3步至第5步，迭代调用，以求解此问题。 步骤3：G1和M0的差别d2为 INROOM(ROBOT，R2)即要求机器人移到房间R2。步骤4：根据差别表，对应于d2的相关操作符为 OP1：gothru(d,r1,R2)步骤5：OP1的先决条件为：G2：INROOM(ROBOT，R1)CONNECTS(d,r1,R2)步骤6：应用置换式r1=R1和d=D1，STRIPS系统能够达到G2。 把操作符gothru(D1,R1,R2)作用于M0，求出中间状态M1： 删除表：INROOM(ROBOT，R1)添加表：INROOM(ROBOT，R2)M1：INROOM(ROBOT，R2)INROOM(BOX1，R2)CONNECTS(D1，R1，R2)把操作符pushthru应用中间状态M1，删除表：INROOM(ROBOT，R2)，INROOM(BOX1，R2)添加表：INROOM(ROBOT，R1)，INROOM(BOX1，R1)得到另一中间状态M2为：M2：INROOM(ROBOT，R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)M2 = G0 end。由于M2与G0匹配，所以我们通过中间结局分析解答了这个机器人规划问题。在求解过程中，所用到的STRIPS规则为操作符OP1和OP2，即gothru(D1,R1,R2),pushthru(BOX1,D1,R2,R1)中间状态模型M1和M2，即子目标G1和G2，如图6.6所示。从图6.6可见，M2与图6.7的目标世界模型G0相同。因此，得到的最后规划为OP1，OP2，即gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1)这个机器人规划问题的搜索图见图6.8，与或树见图6.9。 图 6.8 机器人规划例题的搜索图 图 6.9 机器人规划例题的与或图 6.4 分层规划 要求解困难的问题，一个问题求解系统可能不得不产生出冗长的规划。为了有效地对问题进行求解，重要的是在求得一个针对问题的主要解答之前，能够暂时删去某些细节。然后设法填入适当的细节。早期的办法(Fikes,1971年)涉及宏指令的应用，它由较小的操作符构成较大的操作符。不过，这种方法并不能从操作符的实际描述中消去任何细节。在ABSTRIPS系统(Sacerdoti,1974年)中，研究出一种较好的方法。这个系统实际上在抽象空间的某一层进行规划，而不管抽象空间中较低层的每个先决条件。6.4.1 长度优先搜索问题求解的ABSTRIPS方法是比较简单的。首先，全面求解此问题时只考虑那些可能具有最高临界值的先决条件，这些临界值反映出满足该先决条件的期望难度。要做到这一点，与STRIPS的做法完全一样，只是不考虑比最高临界值低的低层先决条件而已。完成这一步之后，应用所建立起来的初步规划作为完整规划的一个轮廓，并考虑下一个临界层的先决条件。用满足那些先决条件的操作符来证明此规划。在选择操作符时，也不管比现在考虑的这一层要低的所有低层先决条件。继续考虑越来越低层的临界先决条件的这个过程，直至全部原始规划的先决条件均被考虑到为止。因为这个过程探索规划时首先只考虑一层的细节，然后再注意规划中比这一层低一层的细节，所以我们把它叫做长度优先搜索。显然，指定适当的临界值对于这个分层规划方法的成功来说是至关重要的。那些不能被任何操作符满足的先决条件自然是最临界的。例如，如果试图求解一个涉及机器人绕着房子内部移动的问题，而且考虑操作符PUSHTHRUDOOR，那么存在一个大得足以能够让机器人通过的门这一先决条件是最高临界值，因为在正常情况下，如果这个先决条件不是为真，那么将一事无成。如果我们有操作符OPENDOOR，那么打开门这一先决条件就是较低的临界值。要使分层规划系统应用类似STRIPS的规划进行工作，除了规划本身之外，还必须知道可能出现在某个先决条件中的每项适当的临界值。给出这些临界值之后，就能够应用许多非分层规划所采用的方法来求解基本过程。6.4.2 NOAH规划系统1.应用最小约束策略一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。所需要的是某个能够发现哪些需要的操作符的规划过程，以及这些操作符间的任何需要的排序(例如，在能够执行某个已知的操作符之前，必须先执行其它一些操作符以建立该操作符的先决条件)。在应用这种过程之后，才能应用第二个方法来寻求那些能够满足所有要求约束的操作符的某个排序。问题求解系统NOAHSacerdoti在1975年提出和1977年进一步完善的正好能够进行此项工作，它采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。图6.10说明NOAH系统如何求解图6.4所示的积木世界问题。图6.10中所用的操作符STACK与至今我们使用过的操作符有点不同：如果提供了任何两个物体顶上均为空的条件，那么操作符STACK就能够把其中任一个物体放置在另一个物体(包括桌子)上。STACK操作还包括拾起要移动的物体。 图 6.4 积木世界的机器人问题 这个问题求解系统的初始状态图如图6.10A所示。第一件要做的事是把这个问题分成两个子问题，如图图6.10B所示。这时，问题求解系统已决定采用操作符STACK来达到每个目标，但是它们还没有考虑这些操作符的先决条件。标记有S的节点表示规划中的一个分解，它的两个分量都一定要被执行，但其执行次序尚未决定。标记有J的节点表示规划的一个结合，两个分开的规划在此回复到一起。在下一步(即第3层)，考虑了STACK的先决条件。在这个问题表示中，这些先决条件只是两个有关积木必须顶部为空。因此，此系统记录下操作符STACK能够被执行前必须满足的先决条件。这一点如图6.10C所示。这时，该图表明操作符有两种排序：要求只有一个(即在堆迭前必须完成清顶工作)，而关系暂不考虑(即有两种堆迭法)。2.检验准则现在，NOAH系统应用一套准则来检验规划并查出子规划间的互相作用。每个准则都是一个小程序，它对所提出的规则进行专门