《人工智能课件蔡自兴不全第6章》由会员分享，可在线阅读，更多相关《人工智能课件蔡自兴不全第6章（34页珍藏版）》请在金锄头文库上搜索。
1、第六章 规划系统,本章重点： 基于谓词逻辑规划的基本过程 用F规则求解规划序列,第六章 规划系统 6.1 规划的作用与任务,自动规划 是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。也即，规划是一个行动过程的描述。一个总规划可以含有若干个子规划。 自动规划作用 主要用来解决真实世界问题复杂问题（如机器人世界问题） ，与专家系统一样均属高级求解系统与技术。 自动规划策略 分解：将问题分解为若干子问题分别求解，再将每个解组合成完整的解 状态转换：每次转换状态时只计算发生变化的部分，其余部分状态不发生变化 ,第六章 规划系统 6.1 规划
2、的作用与任务,问题分解途径及方法 当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。 把单一的困难问题分割为几个有希望的较为容易解决的子问题，这种分解能够使困难问题的求解变得较为容易。,6.2 基于谓词逻辑的规划 6.2.1 规划世界模型的谓词逻辑表示,“神洲“号运载火箭已把机器人R送到火星进行探索，机器人正位于L3处，它要把位于工具箱T内的探测仪W取出并放到到探测架F（F上为空时才能放）上，以对火星地表进行探测，工具箱T和探测架F分别位于L1和L2处。为完成这个任务，需要规划机器人的这一行动过程。,6.2 基于谓词逻辑的规划 6.2.1 规划世界
3、模型的谓词逻辑表示 首先引入相关的谓词：,CLEAR(x): x上是空的 HANDEMPTY(x): x手中是空的 HOLDING(x, y): x手中拿着y ON(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 基于谓词逻
4、辑的规划 6.2.1 规划世界模型的谓词逻辑表示,这样，问题的初始状态就可以描述为： 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),6.2 基于谓词逻辑的规划 6.2.1 规划世界模型的谓词逻辑表示,规划的目的就是“找出”一系列的操作，并将这些“操作”告诉机器，机器就可以按预定的操作将初始状态转化为目标状态。 操作可以分为先决条件和行为动作两个部分，只有当
5、前状态的先决条件被满足时，才能进行相应的动作，同时使得当前状态转变到下一个状态。,6.3 STRIPS规划系统,STRIPS(STanford Research Institute Problem Solver)，即斯坦福研究所问题求解系统。 对于STRIPS来说，任何时候所存在的具体的突出的实际世界都由一套谓词演算子句来描述。 STRIPS是夏凯(Shakey)机器人程序控制系统的一个组成部分。这个机器人是一部设计用于围绕简单的环境移动的自推车，它能够按照简单的英语命令进行动作。,6.3 STRIPS规划系统,6.3.1 积木世界的机器人规划 1.积木世界的机器人的问题 设想有个积木世界和一
6、个机器人。世界是几个有标记的立方形积木，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，可以抓起积木块并移动积木从一处至另一处。,6.3.1 积木世界的机器人规划 1.积木世界的机器人的问题,机器人能够执行的动作： unstack(a,b)：把堆放在积木b上的积木a拾起。在进行这个动作之前，要求机器人的手为空手，积木a在积木b上，且积木a的顶上是空的。 stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住积木a，而且积木b顶上必须是空的。 ,6.3.1 积木世界的机器人规划 1.积木世界的机器人的问题, pickup(a)：从桌面上拾起积木a，并抓住它不
7、放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。 putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。,6.3.1 积木世界的机器人规划 1.积木世界的机器人的问题,在这个例子中积木和机器人状态： ON(a,b)：积木a在积木b之上。 ONTABLE(a)：积木a在桌面上。 CLEAR(a)：积木a顶上没有任何东西。 HOLDING(a)：机械手正抓住积木a。 HANDEMPTY：机械手为空手。,6.3.1 积木世界的机器人规划 1.积木世界的机器人的问题,现要求描述图(a)到图(b)所示布局。 图(a)布局可由下列谓词的合取表示： CLEAR(B)：积木B
8、顶部为空 ONTABLE(B)：积木B置于桌面上 CLEAR(C)：积木C顶部为空。 ON(C，A)：积木C堆在积木A上 ONTABLE(A)：积木A置于桌面上 HANDEMPTY：机械手为空手。 ,6.3.1 积木世界的机器人规划 1.积木世界的机器人的问题, 图(b)布局可由下列谓词的合取来表示： ON(B，C)：积木B堆在积木C上 ON(A，B)：积木A堆在积木B上 即： ON(B，C) ON(A，B),6.3.1 积木世界的机器人规划 2.用F规则求解规划序列,F规则：STRIPS规划系统的规则 F规则的组成： 先决条件 必须是逻辑上遵循状态描述中事实的谓词演算表达式。 删除表 当某条
9、规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。 添加表 当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。,例 堆积木的move(X,Y,Z) 动作（把物体X从物体Y上移到物体Z上）可以用F规则表示如下：,先决条件：CLEAR(X),CLEAR(Z)，ON(X,Y) 删除表： ON(X,Y) ，CLEAR(Z) 添加表： ON(X,Z)，CLEAR(Y),6.3.1 积木世界的机器人规划 2.用F规则求解规划序列,机器人的4个动作(或操作符)可用STRIPS形式表示如下： stack(X,Y) 先决条件：HOLDING(X)CLEAR(Y) 删除： HOLDIN
10、G(X)，CLEAR(Y) 添加： HANDEMPTY，ON(X，Y),6.3.1 积木世界的机器人规划 2.用F规则求解规划序列,机器人的4个动作(或操作符)可用STRIPS形式表示如下： unstack(X,Y) 先决条件：HANDEMPTYON(X，Y)CLEAR(X) 删除： HANDEMPTY ，ON(X，Y) 添加： HOLDING(X)，CLEAR(Y),6.3.1 积木世界的机器人规划 2.用F规则求解规划序列,机器人的4个动作(或操作符)可用STRIPS形式表示如下： pickup(X) 先决条件：ONTABLE(X)CLEAR(X)HANDEMPTY 删除： ONTABLE
11、(X)HANDENPTY 添加： HOLDING(X),6.3.1 积木世界的机器人规划 2.用F规则求解规划序列,机器人的4个动作(或操作符)可用STRIPS形式表示如下： putdown(X) 先决条件：HOLDING(X) 删除： HOLDING(X) 添加： ONTABLE(X)，HANDEMPTY,6.3.1 积木世界的机器人规划 2.用F规则求解规划序列,教材P217图示了这个问题的全部状态空间，并用粗线指出了从初始状态(用S0标记)到目标状态(用G标记)的解答路径。 从初始状态开始，正向地依次读出连接弧线上的F规则，就得到一个能够达到目标状态的动作序列于下： unstack(C,
12、A),putdown(C),pickup(B),stack(B,C),pickup(A),stack(A,B) 这个动作序列叫做达到这个积木世界机器人问题目标的规划。,6.4 STRIPS系统的组成及其规划过程,6.4.1 STRIPS系统的组成 世界模型：一阶谓词演算公式 操作符：F规则，包括先决条件、删除表和添加表 操作方法：应用状态空间表示，并进行中间结局分析 对于一个复杂问题，首先做出规划，即制定求解规划步骤，然后再执行。在执行过程中如出现问题，需要对没有执行的部分规划进行修改，再继续执行。,6.4.2 STRIPS系统的规划过程,每个STRIPS问题的解答，就是为某个实现目标的操作符
13、序列，也即达到目标的规划。 例 考虑STRIPS系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型如右图所示。,6.4.2 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值。 添加表：INR
14、OOM(ROBOT，r2)。,6.4.2 STRIPS系统的规划过程,设有两个操作符，即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)。)。,6.4.2 STRIPS系统的规划过程,这个问题的差别表如下表所示。 下表表示：针对差别，须采用标有“”
15、的操作。,6.4.2 STRIPS系统的规划过程,假定这个问题的初始状态M0和目标G0如下： M0：INROOM(ROBOT，R1)INROOM(BOX1,R2)CONNECTS(D1，R1，R2) G0：INROOM(ROBOT,R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2),采用中间结局分析方法来逐步求解这个机器人规划, do GPS的主循环迭代，until M0与G0匹配为止。 begin。 G0不能满足M0，找出M0与G0的差别。 尽管这个问题不能马上得到解决，但是如果初始数据库含有语句INROOM(BOX1，R1)，那么这个问题的求解过程就可以得到继续。 它
16、们的差别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，R2)
