{管理信息化OA自动化}南邮自动化人工智能8自动规划

《{管理信息化OA自动化}南邮自动化人工智能8自动规划》由会员分享，可在线阅读，更多相关《{管理信息化OA自动化}南邮自动化人工智能8自动规划（41页珍藏版）》请在金锄头文库上搜索。

1、第八章 自动规划,教学内容：介绍自动规划的基本概念和各种规划系统。 教学重点：机器人规划的作用与任务、积木世界的规划系 统、基于模拟退火算法的机器人局部路径规划。 教学难点：Strips规划系统。 教学方法：课堂教学为主，注意结合例子来说明抽象概念。 教学要求：本章为选修内容，掌握机器人规划的作用与任 务，并一般了解有哪几种规划方法。,第一节 自动规划概述,8.1.1 规划的概念和作用 1、规划的概念及作用 规划的概念：规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。 规划的作用：规划可用来监控问题求解过程，并能够在造成较

2、大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。,战略规划：就是组织制定长期目标并将其付诸实施。第一阶段确定目标；第二阶段制定规划。 城市规划：指城市政府为了实现一定时期内经济社会发展目标，确定城市性质，规模和发展方向，合理利用土地，协调空间布局和各项建设所作的综合部署和具体安排。 人生规划：根据社会发展的需要和个人发展的志向，对自己的未来的发展道路做出一种预先的策划和设计。包括健康规划，事业规划，情感规划，晚景规划。,子规划的分层结构例子,规划的作用：科学规划方法不仅对国家和社会贡献很大，对于个人学习和工作也极为有益。,8.1.2 规划的分类与问题分解途

3、径 1、规划的分类 (1): 按规划内容分 (2): 按规划方法分 (3): 按规划性质分 任务规划(高层规划) 路径规划(中层规划) 轨迹规划(底层规划),2、问题分解途径及方法 把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。 第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。 第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。,3、域的预测和规划的修正 (1) 域的预测 规划方法的成功取决于问题论域的另一特性-预测。如果通过在实际上执行某个操作序列来寻找问题的解答，那末在这个过程的

4、任何一步都能确信该步的结果。但对于不可预测的论域，最好能考虑可能的结果的集合，这些结果很可能按照它们出现的可能性以某个次序排列。然后，产生一个规划，并试图去执行这个规划。 (2) 规划的修正 如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。大多规则的执行主要是按目标定向模式工作的。在种模式下，规划系统从目标状态向可达到的初始状态进行搜索。,8.1.3 规划系统的任务与方法 在规划系统中，必须具有执行下列各项任务的方法： (1) 根据最有效的启发信息，选择应用于下一步的最好规则。 (2) 应用所选取的规则来计

5、算由于应用该规则而生成的新状态。 (3) 对所求得的解答进行检验。 (4) 检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。 (空端：即死端，指无法从它到达目标的端点。) (5) 检验殆正确的解答，并应用具体的技术使之完全正确。,下面讨论能够执行上述 5 项任务的方法。 1、选择和应用规则 在选择合适的应用规则时最广泛采用的技术是：首先要查出期望目标状态与现有状态之间的差别集合，然后辨别出那些与减少这些差别有关的规则。 2、检验解答与空端 当规划系统找到一个能够把初始问题状态变换为目标状态的操作符序列时，此系统就成功地求得问题的一个解答。 如果搜索过程是从初始状态正向推理的，那么

6、可以删去任何导致某种状态的路径，从这种状态出发是无法达到目标状态的。（空端） 如果搜索过程是从目标状态逆向推理的，那么当确信无法达到初始状态，或者搜索过程进展甚微时，可以终止该路径的搜索。,3、修正殆正确解 一个求解殆可分解问题的办法是：当执行与所提出的解答相对应的操作符序列时，检查求得的状态，并把它与期望目标加以比较。 修正一个殆正确的解答的较好办法是: 注意有关出错的知识，然后加以直接修正。 修正一个殆正确的解答的更好办法是: 实际上不是对解答进行全面的修正, 而是不完全确定地让它们保留到最后的可能时刻。,第二节 任务规划,8.2.1 积木世界的机器人问题 机器人问题既比较简单，又很直观。

7、在机器人问题的典型表示中，机器人能够执行一套动作。 在这个例子中机器人能够执行的动作举例如下： unstack(a,b)：把堆放在积木 b 上的积木 a 拾起。在进行这个动作之前，要求机器人的手为空手，而且积木 a 的顶上是空的。 stack(a,b)： 把积木a堆放在积木 b 上。动作之前要求机械手必须已抓住积木 a，而且积木 b 顶上必须是空的。 pickup(a)： 从桌面上拾起积木 a，并抓住它不放。在动作之前要求机械手为空手，而且积木 a 顶上没有任何东西。 putdown(a)： 把积木 a 放置到桌面上。要求动作之前机械手已抓住积木 a。,采用状态描述作为数据库的产生式系统是一种

8、最简单的问题求解系统。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操作和执行操作的结果，需要应用下列谓词： ON(a,b)： 积木 a 在积木 b 之上。 ONTABLE(a)： 积木 a 在桌面上。 CLEAR(a)： 积木 a 顶上没有任何东西。 HOLDING(a)： 机械手正抓住积木 a。 HANDEMPTY： 械手为空手。,举例：积木世界由一些有标记的立方形积木，互相堆迭在一 起构成；机器人有个可移动的机械手，它可以抓起积 木块并移动积木从一处至另一处。 提问：请同学就图8.1 积木世界的机器人问题应用谓词公式 的合取描述此目标为： ON(B，C)ON

9、(A，B)。 ? 初始状态的描述:,图8.1 积木世界的机器人问题,8.2.2 用F规则求解规划序列 采用 F 规则表示机器人的动作，这是一个叫做 STRIPS 规划系统的规则，它由 3 部分组成。 第一部分是先决条件。 为了使 F 规则能够应用到状态描述中去。 第二部分是一个叫做删除表的谓词。 当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。 第三部分叫做添加表。 当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。,对于堆积木的例子中 move 这个动作可以表示如下： move(x,y,z)： 把物体 x 从物体 y 上面移到物体 z 上面。 先决条件：C

10、LEAR(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) 先决条件：HANDEMPTYON(X，Y)CLEAR(X) 删除

11、表：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所示给出这个问

12、题的全部状态空间，并用粗线指出了从初始状态 (用S0标记)到目标状态 (用G标记) 的解答路径。,与习惯的状态空间图画法不同的是，这个状态空间图显出问题的对称性，而没有把初始节点S0放在图的顶点上。此外，要注意到本例中的每条规则都有一条逆规则，如图7.3 所示。,例: 积木世界机器人问题的状态空间 (见P216-217),图8.3 积木世界机器人问题的状态空间,沿着粗线所示的支路，从初始状态开始，正向地依次读出连接弧线上的 F 规则，就得到一个能够达到目标状态的动作序列于下：unstack(C,A),putdown(C),pickup(B)， stack(B,C),pickup(A),stac

13、k(A,B) 就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。,8.3.1 STRIPS系统的组成 STRIPS（Stanford Research Institute Problem Solver） 整个 STRIPS 系统的组成如下： (1) 世界模型。为一阶谓词演算公式。 (2) 操作符 (F规则)。包括先决条件、删除表和添加表。 (3) 操作方法。应用状态空间表示和中间-结局分析。 例如： 状态：(M，G)，包括初始状态、中间状态和目标状态。 初始状态：(M0，(G0) 目标状态：得到一个世界模型，其中不遗留任何未满足的目标。,8.2.3 STRIPS系统规划过程 每个 ST

14、RIPS 问题的解答为某个实现目标的操作符序列，即达到目标的规划。下面举例说明 STRIPS 系统规划的求解过程。 例1 考虑 STRIPS 系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型示于图8.4。,BOX1,机器人,箱子,r1,r2,d,BOX1,机器人,箱子,r1,r2,d,图8.4 STRIPS的一个简化模型,设有两个操作符，即 gothru 和 pushthru (“走过”和“推过”)，分别描述于下： OP1：gothru(d,r1,r2)； 机器人通过房间 r1 和房间 r2 之间的 d，即机器人从房间r1 走过门 d 而进入房间

15、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)