人工智能及其应用_自动规划修改教材

《人工智能及其应用_自动规划修改教材》由会员分享，可在线阅读，更多相关《人工智能及其应用_自动规划修改教材（18页珍藏版）》请在金锄头文库上搜索。

1、第八章 自动规划 8.1 机器人的规划与作用 8.2 积木世界的机器人规划 8.3 STREPS规划系统 8.4 具有学习能力的规划系统 8.5 分层规划 8.6 基于专家系统的机器人规划 8.1 机器人的规划与作用 v8.1.1规划的作用与问题分解途径 规划是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立 一个操作序列，直到求得目标状态为止。简而言之，规划是一个行动过程的描述。一个总规划 可以含有若干个子规划 。 v 1.规划的特性和作用 在日常生活中，规划意味着在行动之前决定行动的进程，或者说，规划这一词指的是在执 行一个问题求解程序中任何一步之前，计算该程序几步

2、的过程。 一个规划是一个行动过程的描述。它可以像百货清单一样的没有次序的目标表列；但是一 般来说，规划具有某个规划目标的蕴含排序。例如，对于大多数人来说，吃早饭之前要先洗脸 和刷牙或漱口。 一个机器人要搬动某工件，必须先移动到该工件附近，再抓住该工件，然后带着工件移动 。 许多规划所包含的步骤是含糊的。而且需要进一步说明。譬如说，一个工作日规划中有吃午 饭这个目标，但是有关细节，如在哪里吃，吃什么，什么时间去吃等等，都没有说明。与吃午 饭有关的详细规划是全日规划的一个子规划。大多数规划具有很大的子规划结构，规划中的每 个目标可以由达到此目标的比较详细的子规划所代替。 8.1 机器人的规划与作用

3、 v尽管最终得到的规划是某个问题求解算符的线性或分部排序，但是由 算符来实现的目标常常具有分层结构，如图所示的工作日规划就是一 例。 子规划的分层结构例子 8.1 机器人的规划与作用 v8.1.1规划的作用与问题分解途径 缺乏规划可能导致不是最佳的问题求解；例如有人由于缺乏规划 ，为了借一本书和还一本书而跑了两次图书馆。 v 此外，如果目标不是独立的，那么动作前缺乏规划就可能在实际 上排除了该问题的某个解答。例如，建筑一个变电所的规划包括砌墙 、安装变压器和铺设电缆线等子规划。这些子规划不是相互独立的， 首先必须铺设电缆，然后砌墙，最后进行变压器安装。如果缺乏规划 ，颠倒了次序，就建不成变电所

4、。 8.1 机器人的规划与作用 v8.1.1规划的作用与问题分解途径 规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错 。如果该问题求解系统不是问题求解环境中唯一的行动者，以及如果此环境 可能按照无法预计的方法变化，那么这种监控就显得特别重要。例如，考虑 某个在遥远星球上空运行的飞行器，它必须能够规划一条航线，然后，当发 现环境状态与预期不合时，就进行重新规划。 v 有关该环境状态的反馈与预期的规划状态进行比较，当两者存在差异时 ，就对此规划进行修正。规划的好处可归纳为简化搜索、解决目标矛盾以及 为差错补偿提供基础。 8.1 机器人的规划与作用 v8.1.1规划的作用与问题分解途

5、径 v 2.问题分解途径及方法 v 把某些比较复杂的问题分解为一些比较小的子问题的想法使我们应用规划方法 求解问题在实际上成为可能。有两条能够实现这种分解的重要途径。 v 第一条重要途径是，当从一个问题状态移动到下一个状态时，无需计算整个新 的状态，而只要考虑状态中可能变化了的那些部分。 v v 第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问 题，这种分解能够使困难问题的求解变得容易些。 8.1 机器人的规划与作用 v8.1.1规划的作用与问题分解途径 例如，要表示出八数码难题每走动一步后的状态如何变化是不难的，要 隐含地记录下具有适当变化的新状态也不需要做大量的工作。从

6、一个状态移 动到另一个状态的规则可以简单的描述为整盘棋如何从一种位置变换为另一 种位置，与其写出叙述把一个完整状态变换为另一个完整状态的规则，我们 宁愿只写出叙述该状态描述中发生变化的那部分的规则。而对于其余部分， 我们可以假定保持不变。 8.1 机器人的规划与作用 v8.1.1规划的作用与问题分解途径 3.域的预测和规划的修正 (1)域的预测 规划方法的成功取决于问题论域的另一特性-预测。如果我们通过在实际上执 行某个操作序列来寻找问题的解答，那末在这个过程的任何一步我们都能确信该步 的结果。但对于不可预测的论域，我们最好能考虑可能的结果的集合，这些结果很 可能按照它们出现的可能性以某个次序

7、排列。然后，我们产生一个规划，并试图去 执行这个规划。 (2)规划的修正 如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过 程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。大多 规则的执行主要是按目标定向模式工作的。这种模式下，规划系统从目标状态向可 达到的初始状态进行搜索。 8.2 积木世界的机器人规划 v 问题求解是一个寻求某个动作序列以达到目标的过程，机器人问题求解即寻求某个机 器人的动作序列(可能包括路径等)，这个序列能够使该机器人达到预期的工作目标，完成 规定的工作任务。 v 8.2.1积木世界的机器人的问题 机器人技术的发展为人工智能问题求解

8、开拓了新的应用前景，并形成了一个新的研究 领域-机器人学。许多问题求解系统的概念可以在机器人问题求解上进行试验研究和应用 。机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套 动作。 v 设想有个积木世界和一个机器人。世界是几个有标记的立方形积木(在这里假定为一样 大小的)，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可 以抓起积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下 8.2 积木世界的机器人规划 v8.2.1积木世界的机器人的问题 设想有个积木世界和一个机器人。世界是几个有标记的立方形积木(在这里假定为一样大

9、小的)，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可以抓起 积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下 unstack(a,b)：把堆放在积木b上的积木a拾起。在进行这个动作之前， 要求机器人的手为空手， 而且积木a的顶上是空的。 stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住 积木a，而且积木b顶上必 须是空的。 pickup(a)：从桌面上拾起积木a，并抓住它不放。在动作之前要求机械 手为空手，而且积木a顶 上 没有任何东西。 putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。 8

10、.2 积木世界的机器人规划 8.2.1积木世界的机器人的问题 机器人规划包括许多功能，例如识别机器人周围世界，表述动作规划， 并监视这些规划的执行。我们所要研究的主要是综合机器人的动作序列问题 ，即在某个给定初始情况下，经过某个动作序列而达到指定的目标。采用状 态描述作为数据库的产生式系统是一种最简单的问题求解系统。机器人问题 的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的 操作和执行操作的结果，我们需要应用下列谓词： 积木世界的机器人问题 8.2 积木世界的机器人规划 积木世界的机器人问题 CLEAR(B)：积木B顶部为空 CLEAR(C)：积木C顶部为空 ON(C，A)

11、：积木C堆在积木A上 ONTABLE(A)：积木A置于桌面上 ONTABLE(B)：积木B置于桌面上 HANDEMPTY：机械手为空手。 (a)所示为初始布局的机器人问题。这种布局可由下列谓词公式的合取来表示： ON(a,b)：积木a在积木b之上。 ONTABLE(a)：积木a在桌面上。 CLEAR(a)：积木a顶上没有任何东西。 HOLDING(a)：机械手正抓住积木a。 HANDEMPTY：机械手为空手。 8.2 积木世界的机器人规划 v8.2.1积木世界的机器人的问题 积木世界的机器人问题 CLEAR(B)：积木B顶部为空 CLEAR(C)：积木C顶部为空 ON(C，A)：积木C堆在积木

12、A上 ONTABLE(A)：积木A置于桌面上 ONTABLE(B)：积木B置于桌面上 HANDEMPTY：机械手为空手。 (a)所示为初始布局的机器人问题。这种布局可由下列谓词公式的合取来表示： 8.2 积木世界的机器人规划 v8.2.1积木世界的机器人的问题 积木世界的机器人问题 CLEAR(B)：积木B顶部为空 CLEAR(C)：积木C顶部为空 ON(C，A)：积木C堆在积木A上 ONTABLE(A)：积木A置于桌面上 ONTABLE(B)：积木B置于桌面上 HANDEMPTY：机械手为空手。 目标在于建立一个积木堆，其中，积木B堆在积木C上面，积木A又堆在积木B 上面，如图 (b)所示。

13、也可以用谓词逻辑来描述此目标为： ON(B，C)ON(A，B) 8.2 积木世界的机器人规划 8.2.2.用F规则求解规划序列 用F规则表示机器人的动作，这是一个叫做STRIPS规划系统的规则，它由 3部分组成。 第一部分是先决条件。为了使F规则能够应用到状态描述中去。这个先 决条件公式必须是逻辑上遵循状态描述中事实的谓词演算表达式。在应用F 规则之前，必须确信先决条件是真的。 F规则的第二部分是一个叫做删除表的谓词。当一条规则被应用于某个 状态描述或数据库时，就从该数据库删去删除表的内容。 F规则第三部分叫做添加表。当把某条规则应用于某数据库时，就把该 添加表的内容添进该数据库。对于堆积木的

14、例子中move这个动作可以表示如 下： 8.2 积木世界的机器人规划 表示move动作的搜索树 8.2.2.用F规则求解规划序列 move(x,y,z)：把物体x从物体y上面移到物体z上面 先决条件： CLEAR(x), CLEAR(z)， ON(x,y) 删除表：ON(x,y)，CLEAR(z) 添加表：ON(x,z)，CLEAR(y) 8.2 积木世界的机器人规划 8.2.2.用F规则求解规划序列 考虑上图中所示的例子，机器人的4个动作(或操作符)可用STRIPS形式表示如下： (1) stack(A,B) 先决条件和删除表：HOLDING(A)CLEAR(B) 添加表：HANDEMPTY

15、，ON(A，B) (2) unstack(A,B) 先决条件：HANDEMPTYON(A，B)CLEAR(A) 删除表：ON(A，B)，HANDEMPTY 添加表：HOLDING(A)，CLEAR(B) (3) pickup(A) 先决条件：ONTABLE(A)CLEAR(A)HANDEMPTY 删除表：ONTABLE(A)HANDENPTY 添加表：HOLDING(A) (4) putdown(A) 先决条件和删除表：HOLDING(A) 添加表：ONTABLE(A)，HANDEMPTY 8.2 积木世界的机器人规划 vunstack(C,A) vputdown(C) vpickup(B) vstack(B,C) vpickup(A) vstack(A,B)