南邮自动化人工智能8自动规划

第八章自动规划教学内容：引见自动规划的根本概念和各种规划系统。教学重点：机器人规划的作用与义务、积木世界的规划系统、基于模拟退火算法的机器人部分途径规划。教学难点：Strips规划系统。教学方法：课堂教学为主，留意结合例子来阐明笼统概念。教学要求：本章为选修内容，掌握机器人规划的作用与任务，并普通了解有哪几种规划方法。第一节自动规划概述8.1.1规划的概念和作用1、规划的概念及作用规划的概念：规划是一种重要的问题求解技术，它从某个特定的问题形状出发，寻求一系列行为动作，并建立一个操作序列，直到求得目的形状为止。规划的作用：规划可用来监控问题求解过程，并可以在呵斥较大的危害之前发现过失。规划的益处可归纳为简化搜索、处理目的矛盾以及为过失补偿提供根底。战略规划：就是组织制定长期目的并将其付诸实施。第一阶段确定目的；第二阶段制定规划。城市规划：指城市政府为了实现一定时期内经济社会开展目的，确定城市性质，规模和开展方向，合理利用土地，协调空间规划和各项建立所作的综合部署和详细安排。人生规划：根据社会开展的需求和个人开展的志向，对本人的未来的开展道路做出一种预先的谋划和设计。包括安康规划，事业规划，情感规划，晚景规划。子规划的分层构造例子规划的作用：科学规划方法不仅对国家和社会奉献很大，对于个人学习和任务也极为有益。8.1.2规划的分类与问题分解途径1、规划的分类(1):按规划内容分(2):按规划方法分(3):按规划性质分义务规划(高层规划)途径规划(中层规划)轨迹规划(底层规划)2、问题分解途径及方法把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。第一条重要途径是当从一个问题形状挪动到下一个形状时，无需计算整个新的形状，而只需思索形状中能够变化了的那些部分。第二条重要途径是把单一的困难问题分割为几个有希望的较为容易处理的子问题。3、域的预测和规划的修正(1)域的预测规划方法的胜利取决于问题论域的另一特性--预测。假设经过在实践上执行某个操作序列来寻觅问题的解答，那末在这个过程的任何一步都能确信该步的结果。但对于不可预测的论域，最好能思索能够的结果的集合，这些结果很能够按照它们出现的能够性以某个次序陈列。然后，产生一个规划，并试图去执行这个规划。

(2)规划的修正假设规划在执行中失败了，那么就需求对它进展修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必需被执行的理由。大多规那么的执行主要是按目的定向方式任务的。在种方式下，规划系统从目的形状向可到达的初始形状进展搜索。8.1.3规划系统的义务与方法在规划系统中，必需具有执行以下各项义务的方法：(1)根据最有效的启发信息，选择运用于下一步的最好规那么。(2)运用所选取的规那么来计算由于运用该规那么而生成的新形状。(3)对所求得的解答进展检验。(4)检验空端，以便舍弃它们，使系统的求解任务向着更有效的方向进展。(空端：即死端，指无法从它到达目的的端点。)(5)检验殆正确的解答，并运用详细的技术使之完全正确。下面讨论可以执行上述5项义务的方法。1、选择和运用规那么在选择适宜的运用规那么时最广泛采用的技术是：首先要查出期望目的形状与现有形状之间的差别集合，然后区分出那些与减少这些差别有关的规那么。2、检验解答与空端当规划系统找到一个可以把初始问题形状变换为目的形状的操作符序列时，此系统就胜利地求得问题的一个解答。假设搜索过程是从初始形状正向推理的，那么可以删去任何导致某种形状的途径，从这种形状出发是无法到达目的形状的。〔空端〕假设搜索过程是从目的形状逆向推理的，那么当确信无法到达初始形状，或者搜索过程进展甚微时，可以终止该途径的搜索。3、修正殆正确解一个求解殆可分解问题的方法是：当执行与所提出的解答相对应的操作符序列时，检查求得的形状，并把它与期望目的加以比较。修正一个殆正确的解答的较好方法是:留意有关出错的知识，然后加以直接修正。修正一个殆正确的解答的更好方法是:实践上不是对解答进展全面的修正,而是不完全确定地让它们保管到最后的能够时辰。第二节义务规划8.2.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：械手为空手。举例：积木世界由一些有标志的立方形积木，相互堆迭在一起构成；机器人有个可挪动的机械手，它可以抓起积木块并挪动积木从一处至另一处。提问：请同窗就图8.1积木世界的机器人问题运用谓词公式的合取描画此目的为：ON(B，C)∧ON(A，B)。?初始形状的描画:图8.1积木世界的机器人问题8.2.2用F规那么求解规划序列采用F规那么表示机器人的动作，这是一个叫做STRIPS规划系统的规那么，它由3部分组成。第一部分是先决条件。为了使F规那么可以运用到形状描画中去。第二部分是一个叫做删除表的谓词。当一条规那么被运用于某个形状描画或数据库时，就从该数据库删去删除表的内容。第三部分叫做添加表。当把某条规那么运用于某数据库时，就把该添加表的内容添进该数据库。对于堆积木的例子中move这个动作可以表示如下：

move(x,y,z)：把物体x从物体y上面移到物体z上面。

先决条件：CLEAR(x),CLEAR(z)，ON(x,y)

删除表：ON(x,y)，CLEAR(z)

添加表：ON(x,z)，CLEAR(y)假设move为此机器人仅有的操作符或适用动作，那么，可以生成如以下图所示的搜索图或搜索树：8.2表示move动作的搜索树下面更详细地思索图8.1中所示的例子，机器人的4个动作(或操作符)可用STRIPS方式表示如下：

(1)stack(X,Y)

先决条件和删除表：HOLDING(X)∧CLEAR(Y)添加表：HANDEMPTY，ON(X，Y)(2)unstack(X,Y)

先决条件：HANDEMPTY∧ON(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

假定目的为8.1所示的形状，即ON(B,C)∧ON(A,B)从图8.1〔a〕所示的初始形状描画开场正向操作，只需unstack(C,A)和pickup(B)两个动作可以运用F规那么。图8.3所示给出这个问题的全部形状空间，并用粗线指出了从初始形状(用S0标志)到目的形状(用G标志)的解答途径。与习惯的形状空间图画法不同的是，这个形状空间图显出问题的对称性，而没有把初始节点S0放在图的顶点上。此外，要留意到本例中的每条规那么都有一条逆规那么，如图7.3所示。例:积木世界机器人问题的形状空间(见P216-217)图8.3积木世界机器人问题的形状空间沿着粗线所示的支路，从初始形状开场，正向地依次读出衔接弧线上的F规那么，就得到一个可以到达目的形状的动作序列于下：

｛unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B)｝就把这个动作序列叫做到达这个积木世界机器人问标题的的规划。

8.3.1STRIPS系统的组成STRIPS〔StanfordResearchInstituteProblemSolver〕整个STRIPS系统的组成如下：(1)世界模型。为一阶谓词演算公式。(2)操作符(F规那么)。包括先决条件、删除表和添加表。(3)操作方法。运用形状空间表示和中间-结局分析。例如：形状：(M，G)，包括初始形状、中间形状和目的形状。初始形状：(M0，(G0))目的形状：得到一个世界模型，其中不遗留任何未满足的目的。8.2.3STRIPS系统规划过程

每个STRIPS问题的解答为某个实现目的的操作符序列，即到达目的的规划。下面举例阐明STRIPS系统规划的求解过程。例1思索STRIPS系一致个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始形状和目的形状的世界模型示于图8.4。BOX1机器人箱子r1r2dBOX1机器人箱子r1r2d图8.4STRIPS的一个简化模型设有两个操作符，即gothru和pushthru(“走过〞和“推过〞)，分别描画于下：OP1：gothru(d,r1,r2)；机器人经过房间r1和房间r2之间的d，即机器人从房间r1走过门d而进入房间r2。先决条件：机器人在房间r1内，而且门d衔接r1和r2两个房间。INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；删除表：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)。例:采用中间-结局分析方法来逐渐求解机器人规划(见P219-221)差别表假定这个问题的初始形状M0和目的G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)假定这个问题的初始形状M0和目的G0如下：

M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)

G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)BOX1机器人箱子R1R2DBOX1机器人箱子R1R2D图8.4STRIPS的一个简化模型基于中间结局分析方法的规划求解:采用中间结局分析方法来逐渐求解这个机器人规划：

①doGPS的主循环迭代，untilM0与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，M2与目的世界