第八章机器人规划

第八章机器人规划8.1

机器人规划的作用与任务

8.2积木机器的机器人规划8.3STRIPS规划系统8.4具有学习能力的规划系统8.5基于专家系统的机器人规划8.6小结自动规划是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。也即，规划是一个行动过程的描述。一个总规划可以含有若干个子规划。自动规划作用主要用来解决真实世界问题复杂问题（如机器人世界问题），与专家系统一样均属高级求解系统与技术。自动规划策略

①分解：将问题分解为若干子问题分别求解，再将每个解组合成完整的解②状态转换：每次转换状态时只计算发生变化的部分，其余部分状态不发生变化→8.1

机器人规划的作用与任务

8.1.1 规划的作用与问题分解途径

规划的概念及作用规划的概念

规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。

图8.1子规划的分层结构例子工作日规划上午子规划中午子规划下午子规划吃夹心面包阅读写作回家去上班阅读文章规划的作用规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。问题分解途径及方法把某些比较复杂的问题分解为一些比较小的子问题。有两条能够实现这种分解的重要途径。第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。8.1.2 机器人规划系统的任务与方法在规划系统中，必须具有执行下列各项任务的方法：根据最有效的启发信息，选择应用于下一步的最好规则。应用所选取的规则来计算由于应用该规则而生成的新状态。对所求得的解答进行检验。检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。检验殆正确的解答，并应用具体的技术使之完全正确。8.1.3规划世界模型的谓词逻辑表示

"神洲"号运载火箭已把机器人R送到火星进行探索，机器人正位于L3处，它要把位于工具箱T内的探测仪W取出并放到到探测架F（F上为空时才能放）上，以对火星地表进行探测，工具箱T和探测架F分别位于L1和L2处。为完成这个任务，需要规划机器人的这一行动过程。首先引入相关的谓词：

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拿起这样，问题的初始状态就可以描述为：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)

规划的目的就是“找出”一系列的操作，并将这些“操作”告诉机器，机器就可以按预定的操作将初始状态转化为目标状态。操作可以分为先决条件和行为动作两个部分，只有当前状态的先决条件被满足时，才能进行相应的动作，同时使得当前状态转变到下一个状态。8.2积木世界的机器人规划

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(a)所示为初始布局的机器人问题。目标在于建立一个积木堆，其中，积木B堆在积木C上面，积木A又堆在积木B上面，如图8.4(b)所示。CBA机械手ABC机械手（a）初始布局（b）目标布局图8.1积木世界的机器人问题初始布局可由下列谓词公式的合取来表示：CLEAR(B)：积木B顶部为空CLEAR(C)：积木C顶部为空ON(C，A)：积木C堆在积木A上ONTABLE(A)：积木A置于桌面上ONTABLE(B)：积木B置于桌面上HANDEMPTY：机械手为空手图(b)布局可由下列谓词的合取来表示：ON(B，C)：积木B堆在积木C上ON(A，B)：积木A堆在积木B上即：ON(B，C)∧ON(A，B)

STRIPS(STanfordResearchInstituteProblemSolver)，即斯坦福研究所问题求解系统。对于STRIPS来说，任何时候所存在的具体的突出的实际世界都由一套谓词演算子句来描述。STRIPS是夏凯(Shakey)机器人程序控制系统的一个组成部分。这个机器人是一部设计用于围绕简单的环境移动的自推车，它能够按照简单的英语命令进行动作。8.2.2 用F规则求解规划序列STRIPS规划系统的规则由3部分组成：

F规则的组成：先决条件必须是逻辑上遵循状态描述中事实的谓词演算表达式。删除表当某条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。添加表当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。例：表示堆积木的例子中move这个动作，如下所示：move(x,y,z)：把物体x从物体y上面移到物体z上面。先决条件：CLEAR(x),CLEAR(z)，ON(x,y)删除表：ON(x,z)，CLEAR(z)添加表：ON(x,z)，CLEAR(y)如果move为此机器人仅有的操作符或适用动作，那么，可以生成如图8.5所示的搜索图或搜索树。CLEAR(X)CLEAR(Z)ON(X,Y)ONTABLE(Y)ONTABLE(Z)CLEAR(X)CLEAR(Y)ON(X,Z)ONTABLE(Y)ONTABLE(z)move(X,Y,Z)图8.2表示move动作的搜索树机器人的4个动作(或操作符)可用STRIPS形式表示如下：

stack(X,Y)

先决条件和删除表：HOLDING(X)∧CLEAR(Y)

添加表：HANDEMPTY，ON(X，Y)

unstack(X,Y)

先决条件：HANDEMPTY∧ON(X，Y)∧CLEAR(X)

删除表：ON(X，Y)，HANDEMPTY

添加表：HOLDING(X)，CLEAR(Y)

pickup(X)

先决条件：ONTABLE(X)∧CLEAR(X)∧HANDEMPTY

删除表：ONTABLE(X)∧HANDENPTY

添加表：HOLDING(X)

putdown(X)

先决条件和删除表：HOLDING(X)

添加表：ONTABLE(X)，HANDEMPTY教材P217图示了这个问题的全部状态空间，并用粗线指出了从初始状态(用S0标记)到目标状态(用G标记)的解答路径。从初始状态开始，正向地依次读出连接弧线上的F规则，我们就得到一个能够达到目标状态的动作序列（如图8.3中粗线所示）于下：{unstack(C,A),putdown(C),pickup(B),stack(B,C),pickup(A),stack(A,B)}就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。8.3STRIPS规划系统STRIPS的介绍

STRIPS是由Fikes、Hart和Nilsson3人在1981及1982研究成功的，它是夏凯(Shakey)机器人程序控制系统的一个组成部分。STRIPS系统组成世界模型：为一阶谓词演算公式；操作符(F规则)：包括先决条件、删除表和添加表；操作方法：应用状态空间表示和中间-结局分析。8.3.1STRIPS系统的组成世界模型：一阶谓词演算公式操作符：F规则，包括先决条件、删除表和添加表操作方法：应用状态空间表示，并进行中间—结局分析对于一个复杂问题，首先做出规划，即制定求解规划步骤，然后再执行。在执行过程中如出现问题，需要对没有执行的部分规划进行修改，再继续执行。8.3.2STRIPS系统的规划过程每个STRIPS问题的解答，就是为某个实现目标的操作符序列，也即达到目标的规划。例考虑STRIPS系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型如右图所示。

设有两个操作符，即gothru和pushthru(“走过”和“推过”)：OP1：gothru(d,r1,r2)机器人通过房间r1和房间r2之间的d，即机器人从房间r1走过门d而进入房间r2。先决条件：INROOM(ROBOT，r1)∧CONNECTS(d,r1,r2)；即：机器人在房间r1内，而且门d连接r1和r2两个房间。删除表：INROOM(ROBOT，S)；对于任何S值。添加表：INROOM(ROBOT，r2)。设有两个操作符，即gothru和pushthru(“走过”和“推过”)：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)。)。这个问题的差别表如下表所示。下表表示：针对差别，须采用标有“×”的操作。假定这个问题的初始状态M0和目标G0如下：M0：INROOM(ROBOT，R1)∧INROOM(BOX1,R2)∧CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)∧INROOM(BOX1，R1)∧CONNECTS(D1，R1，R2)

采用中间结局分析方法来逐步求解这个机器人规划

①doGPS的主循环迭代，untilM0与G0匹配为止。②begin。③G0不能满足M0，找出M0与G0的差别。尽管这个问题不能马上得到解决，但是如果初始数据库含有语句INROOM(BOX1，R1)，那么这个问题的求解过程就可以得到继续。它们的差别d1：INROOM(BOX1，R1)，即要把箱子(物体)放到目标房间R1内。④选取操作符：一个与减少差别d1有关的操作符。根据差别表，STRIPS选取操作符为：OP2：pushthru(BOX1,d,r1,R1)⑤消去差别d1，为OP2设置先决条件G1为：INROOM(BOX1,r1)∧INROOM(ROBOT,r1)∧CONNECTS(d,r1,R1)这个先决条件被设定为子目标。STRIP发现：若r1=R2,d=D1，当前数据库含有INROOM(ROBOT，R1)那么此过程能够继续进行。现在新的子目标G1为：G1：INROOM(BOX1，R2)∧INROOM(ROBOT，