第7章 自动规划系统

1、第7章 自动规划系统,课前思考 知识点 学习要求,课前思考,什么是规划？规划的作用是什么？ 基于谓词逻辑规划的基本过程怎样？ STRIPS系统的规划过程如何？ NOAH规划系统求解问题过程怎样？,知识点,规划相关概念 基于谓词逻辑的规划 STRIPS（斯坦福研究所问题求解系统）规划系统 NOAH规划系统,学习要求,掌握规划概念、作用与任务 了解各种规划系统,第7章 自动规划系统,7.1 自动规划概述 7.2 基于谓词逻辑的规划 7.3 STRIPS规划系统 7.4 分层规划,自动规划概述,自动规划是一种重要的问题求解技术，与一般问题求解相比，自动规划更注重于问题的求解过程，而不是求解结果。 规

2、划要解决的问题，如机器人世界问题，往往是真实世界问题，而不是比较抽象的数学模型问题。,规划的概念,规划是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。简而言之，规划是一个行动过程的描述。一个总规划可以含有若干个子规划。,规划的特性和作用,在日常生活中，规划意味着在行动之前决定行动的进程。 一个规划是一个行动过程的描述 。可以是没有次序的目标表列；一般来说，规划具有某个问题目标的蕴含排序。,规划的特性和作用,大多数规划具有很大的子规划结构，规划中的每个目标可以由达到此目标的比较详细的子规划所代替。,子规划的分层结构例子,规划的特性和作

3、用,规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。,规划的分类,按内容分 按方法分 非分层与分层、线性与非线性、同步与异步，基于消解原理的规划 基于演绎规则的规划等 按实质分 目标、任务、途径、代价,问题分解途径及方法,把比较复杂的问题分解为一些比较小的子问题。分解有两种重要途径。 第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。 第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。,域的预测和规划的修正,a)域的预测 我们最好能

4、考虑可能的结果的集合，这些结果很可能按照它们出现的可能性以某个次序排列。然后，我们产生一个规划，并试图去执行这个规划。 b)规划的修正 如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。,机器人规划系统的任务与方法,在规划系统中，必须具有执行下列各项任务的方法： （1）根据最有效的启发信息，选择应用于下一步的最好规则。 （2）应用所选取的规则来计算由于应用该规则而生成的新状态。 （3）对所求得的解答进行检验。 （4）检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。 （5）检验殆正确的解答，并应用

5、具体的技术使之完全正确。,机器人规划系统的任务与方法（续）,1、选择和应用规则 在选择合适的应用规则时最广泛采用的技术是：首先要查出期望目标状态与现有状态之间的差别集合，然后辨别出那些与减少这些差别有关的规则。,机器人规划系统的任务与方法（续）,2、检验解答与空端 当规划系统找到一个能够把初始问题状态变换为目标状态的操作符序列时，此系统就成功地求得问题的一个解答。 如果搜索过程是从初始状态正向推理的，那么可以删去任何导致某种状态的路径，从这种状态出发是无法达到目标状态的。 如果搜索过程是从目标状态逆向推理的，那么当确信无法达到初始状态，或者搜索过程进展甚微时，可以终止该路径的搜索。,机器人规划

6、系统的任务与方法（续）,3、修正殆正确解 执行与所提出的解答相对应的操作符序列时，检查求得的状态，并把它与期望目标加以比较。 修正一个殆正确的解答的较好办法是注意有关出错的知识，然后加以直接修正。,第7章 规划系统,7.1 规划的作用与任务 7.2 基于谓词逻辑的规划 7.3 STRIPS规划系统 7.4 分层规划,7.2 基于谓词逻辑的规划,用谓词逻辑来描述世界模型及规划过程的 一种规划方法，关键是对待求解问题的表示 1、规划世界模型的谓词逻辑表示 2、基于谓词逻辑规划的基本过程,1、规划世界模型的谓词逻辑表示,相关谓词,CLEAR(x):x上是空 HANDEMPTY(x):x手中是空 HO

7、LDING(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拿起,初始状态,AT(T, L1)IN(W, T)ISCLOSE(T) AT(F, L2)CLEAR(F)AT(R, L3) HANDEMPTY(R),目标状

8、态,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)

9、行为动作： 删除：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),2 基于谓词逻辑规划的基本过程,把问题分割成几个比较容易解决的子问题,子问题的规划,Plan1：

10、R从L3处走到工具箱T的旁边， Plan2：R打开工具箱T Plan3：R从工具箱中取出探测仪W， Plan4：R从工具箱T的旁边走到探测架F旁 Plan5：R把探测仪W放在探测架F上,第7章 规划系统,7.1 规划的作用与任务 7.2 基于谓词逻辑的规划 7.3 STRIPS规划系统 7.4 分层规划,7.3 STRIPS规划系统,1.积木世界的机器人规划 2. STRIPS规划系统,1.积木世界的机器人规划,机器人问题求解即寻求某个机器人的动作序列，这个序列能够使该机器人达到预期的工作目标，完成规定的工作任务。,1.积木世界的机器人的问题,在机器人问题的典型表示中，机器人能够执行一套动作,

11、机器人能够执行的动作,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之上。ONT

12、ABLE(a)：积木a在桌面上。CLEAR(a)：积木a顶上没有任何东西。HOLDING(a)：机械手正抓住积木a。HANDEMPTY：机械手为空手。,初始状态,CLEAR(B)：积木B顶部为空CLEAR(C)：积木a在桌面上。ON(C，A)：积木C堆在积木A上ONTABLE(A)：积木A置于桌面上ONTABLE(B)：积木B置于桌面上HANDEMPTY：机械手为空手,目标状态,ON(B，C)ON(A，B),用F规则求解规划序列,采用F规则表示机器人的动作，这是一个叫做STRIPS规划系统的规则 。它由3部分组成。 先决条件 删除表 添加表,用F规则求解规划序列,move(x,y,z)： 把物

13、体x从物体y上面移到物体z上面先决条件： CLEAR(x)，CLEAR(z)，ON(x,y) 删除表： ON(x,y)，CLEAR(y) 添加表：ON(x,z)，CLEAR(y),表示move动作的搜索树,机器人的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),机器人的4个动作用STRIPS形式表

14、示,(3)pickup(X) 先决条件：ONTABLE(X)CLEAR(X)HANDEMPTY删除表：ONTABLE(X)HANDENPTY添加表：HOLDING(X) (4)putdown(X) 先决条件和删除表：HOLDING(X)添加表：ONTABLE(X)，HANDEMPTY,能够达到目标状态的动作序列,unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B) 把这个动作序列叫做达到这个积木世界机器 人问题目标的规划,STRIPS规划系统,STRIPS(STanford Research Institute Pr

15、oblem Solver) 斯坦福研究所问题求解系统，是从被求解的问 题中引出一般性结论而产生规划的。,STRIPS系统的组成,STRIPS是由Fikes、Hart和Nilsson三人在1971及1972研究成功的，它是夏凯(Shakey)机器人程序控制系统的一个组成部分。 这个机器人是一部设计用于围绕简单的环境移动的自推车，它能够按照简单的英语命令进行动作。,STRIPS系统的组成,夏凯包含下列4个主要部分： (1)车轮及其推进系统； (2)传感系统，由电视摄象机和接触杆组成； (3)一台不在车体上的用来执行程序设计的计算机。它能够分析由车上传感器得到的反馈信息和输入指令，并向车轮发出使其推

16、进系统触发的信号 (4)无线电通讯系统，用于在计算机和车轮间的数据传送。,STRIPS系统的组成,STRIPS是决定把哪个指令送至机器人的程序设计。 该机器人世界包括一些房间、房间之间的门和可移动的箱子；在比较复杂的情况下还有电灯和窗户等。,STRIPS系统的组成,（1）世界模型：描述任何时刻的世界的数据库。是一阶谓词演算公式。 （2）操作符（F规则）：包括先决条件、删除表和添加表。 （3）操作方法：应用状态空间表示和中间结局分析。,系统的规划过程,（1）问题表示 （2）基于中间-结局分析方法的规划求解,（1）问题表示,STRIPS的一个简化模型,操作符,OP1：gothru(d,r1,r2)

17、 先决条件： INROOM(ROBOT,r1)CONNECTS(d,r1,r2) 删除表：INROOM(ROBOT，S)； 添加表：INROOM(ROBOT，r2)。,操作符,OP2： pushthru(b,d,r1,r2) 先决条件： INROOM(b,r1)INROOM(ROBOT,r1) CONNECTS(d,r1,r2) 删除表： INROOM(ROBOT，S)，INROOM(b，S)； 添加表： INROOM(ROBOT，r2),INROOM(b,r2)。,初始状态和目标状态,M0： INROOM(ROBOT，R1) INROOM(BOX1,R2) CONNECTS(D1，R1，R2

18、) G0： INROOM(ROBOT,R1) INROOM(BOX1，R1) CONNECTS(D1，R1，R2),(2)基于中间结局分析方法的规划求解,1.找出M0与G0的差别（ INROOM(BOX1，R1) ）,(2)基于中间结局分析方法的规划求解,2.选取操作符 OP2：pushthru(BOX1,d,r1,R1) 3.为OP2设置先决条件G1 INROOM(BOX1,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,R1),(2)基于中间结局分析方法的规划求解,应用置换r1=R2, d=D1变换G1为： INROOM(BOX1，R2) INROOM(ROBOT，R2)

19、 CONNECTS(D1，R2，R1),(2)基于中间结局分析方法的规划求解,4.重复第3步至第5步 找G1和M0的差别 INROOM(ROBOT，R2) 操作符为 OP1：gothru(d,r1,R2) OP1的先决条件G2：INROOM(ROBOT，R1)CONNECTS(d,r1,R2) 应用置换r1=R1和d=D1,(2)基于中间结局分析方法的规划求解,5.应用操作符得到中间状态M1、M2， 用OP1:gothru(D1,R1,R2) 删除表：INROOM(ROBOT，R1) 添加表：INROOM(ROBOT，R2)M1： INROOM(ROBOT，R2) INROOM(BOX1，R2

20、) CONNECTS(D1，R1，R2),(2)基于中间结局分析方法的规划求解,用OP2:pushthru(BOX1,D1,R2,R1) 删除表：INROOM(ROBOT，R2)， INROOM(BOX1，R2)添加表：INROOM(ROBOT，R1)， INROOM(BOX1，R1)M2： INROOM(ROBOT，R1) INROOM(BOX1，R1) CONNECTS(D1，R1，R2),(2)基于中间结局分析方法的规划求解,6. M2 = G0 end 得到的最后规划为 gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1),该问题的搜索图,该问题的与或树,第

21、7章 规划系统,7.1 规划的作用与任务 7.2 基于谓词逻辑的规划 7.3 STRIPS规划系统 7.4 分层规划,分层规划,为了有效地对问题进行求解，重要的是主要解答之前，能够暂时删去某些细节。然后设法填入适当的细节。 在ABSTRIPS系统(Sacerdoti,1974年)中，研究出一种较好的方法。这个系统实际上在抽象空间的某一层进行规划，而不管抽象空间中较低层的每个先决条件。,分层规划,1.长度优先搜索 2.NOAH规划系统,1.长度优先搜索,首先，只考虑可能具有最高临界值的先决条件， 第二步，用初步规划作为完整规划的一个轮廓，并 考虑下一个临界层的先决条件。用满足那些先决条件 的操作

22、符来证明此规划。 第三步，考虑越来越低层的临界先决条件，直至全 部先决条件均被考虑到为止。,1.长度优先搜索,重点：适当的临界值,2.NOAH规划系统,1、应用最小约束策略 一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。所需要的是某个能够发现哪些需要的操作符的规划过程，以及这些操作符间的任何需要的排序(例如，在能够执行某个已知的操作符之前，必须先执行其它一些操作符以建立该操作符的先决条件)。在应用这种过程之后，才能应用第二个方法来寻求那些能够满足所有要求约束的操作符的某个排序,2.NOAH规划系统（续）,问题求解系统NOAHSacerdoti在1975年提出和1977年进一步完善的正好能够进行此项工作，它采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。,NOAH规划系统例,书243页图7.11,2.NOAH规划系统（续）,2、检验准则 NOAH系统应用一套准则来检验规划并查出子规划间的互相作用。每个准则都是一个小程序，它对所提出的规则进行专门观测。准则法已被应用于各种规划生成系统。在NOAH系统中，准则被用来提出推定的方法