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

1、第八章第八章 自动规划自动规划8.1 机器人的规划与作用机器人的规划与作用8.2 积木世界的机器人规划积木世界的机器人规划 8.3 STREPS规划系统规划系统8.4 具有学习能力的规划系统具有学习能力的规划系统8.5 分层规划分层规划8.6 基于专家系统的机器人规划基于专家系统的机器人规划8.1 机器人的规划与作用机器人的规划与作用v8.1.1规划的作用与问题分解途径规划的作用与问题分解途径 规划是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立规划是一种问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。简而言之，

2、规划是一个行动过程的描述。一个总规划一个操作序列，直到求得目标状态为止。简而言之，规划是一个行动过程的描述。一个总规划可以含有若干个子规划可以含有若干个子规划 。v1.1.规划的特性和作用规划的特性和作用 在日常生活中，规划意味着在行动之前决定行动的进程，或者说，规划这一词指的是在执在日常生活中，规划意味着在行动之前决定行动的进程，或者说，规划这一词指的是在执行一个问题求解程序中任何一步之前，计算该程序几步的过程。行一个问题求解程序中任何一步之前，计算该程序几步的过程。 一个规划是一个行动过程的描述。它可以像百货清单一样的没有次序的目标表列；但是一一个规划是一个行动过程的描述。它可以像百货清单

3、一样的没有次序的目标表列；但是一般来说，规划具有某个规划目标的蕴含排序。例如，对于大多数人来说，吃早饭之前要先洗脸般来说，规划具有某个规划目标的蕴含排序。例如，对于大多数人来说，吃早饭之前要先洗脸和刷牙或漱口。和刷牙或漱口。 一个机器人要搬动某工件，必须先移动到该工件附近，再抓住该工件，然后带着工件移一个机器人要搬动某工件，必须先移动到该工件附近，再抓住该工件，然后带着工件移动。动。 许多规划所包含的步骤是含糊的。而且需要进一步说明。譬如说，一个工作日规划中有许多规划所包含的步骤是含糊的。而且需要进一步说明。譬如说，一个工作日规划中有吃午饭这个目标，但是有关细节，如在哪里吃，吃什么，什么时间去

4、吃等等，都没有说明。与吃午饭这个目标，但是有关细节，如在哪里吃，吃什么，什么时间去吃等等，都没有说明。与吃午饭有关的详细规划是全日规划的一个子规划。大多数规划具有很大的子规划结构，规划中吃午饭有关的详细规划是全日规划的一个子规划。大多数规划具有很大的子规划结构，规划中的每个目标可以由达到此目标的比较详细的子规划所代替。的每个目标可以由达到此目标的比较详细的子规划所代替。8.1 机器人的规划与作用机器人的规划与作用v尽管最终得到的规划是某个问题求解算符的线性或分部排序，但是由尽管最终得到的规划是某个问题求解算符的线性或分部排序，但是由算符来实现的目标常常具有分层结构，如图所示的工作日规划就是一算

5、符来实现的目标常常具有分层结构，如图所示的工作日规划就是一例。例。子规划的分层结构例子子规划的分层结构例子 8.1 机器人的规划与作用机器人的规划与作用v8.1.1规划的作用与问题分解途径规划的作用与问题分解途径 缺乏规划可能导致不是最佳的问题求解；例如有人由于缺乏规划，缺乏规划可能导致不是最佳的问题求解；例如有人由于缺乏规划，为了借一本书和还一本书而跑了两次图书馆。为了借一本书和还一本书而跑了两次图书馆。v 此外，如果目标不是独立的，那么动作前缺乏规划就可能在实际此外，如果目标不是独立的，那么动作前缺乏规划就可能在实际上排除了该问题的某个解答。例如，建筑一个变电所的规划包括砌墙、上排除了该问

6、题的某个解答。例如，建筑一个变电所的规划包括砌墙、安装变压器和铺设电缆线等子规划。这些子规划不是相互独立的，首安装变压器和铺设电缆线等子规划。这些子规划不是相互独立的，首先必须铺设电缆，然后砌墙，最后进行变压器安装。如果缺乏规划，先必须铺设电缆，然后砌墙，最后进行变压器安装。如果缺乏规划，颠倒了次序，就建不成变电所。颠倒了次序，就建不成变电所。8.1 机器人的规划与作用机器人的规划与作用v8.1.1规划的作用与问题分解途径规划的作用与问题分解途径 规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。如果该问题求解系统不是问

7、题求解环境中唯一的行动者，以及如果此环错。如果该问题求解系统不是问题求解环境中唯一的行动者，以及如果此环境可能按照无法预计的方法变化，那么这种监控就显得特别重要。例如，考境可能按照无法预计的方法变化，那么这种监控就显得特别重要。例如，考虑某个在遥远星球上空运行的飞行器，它必须能够规划一条航线，然后，当虑某个在遥远星球上空运行的飞行器，它必须能够规划一条航线，然后，当发现环境状态与预期不合时，就进行重新规划。发现环境状态与预期不合时，就进行重新规划。v 有关该环境状态的反馈与预期的规划状态进行比较，当两者存在差异时，有关该环境状态的反馈与预期的规划状态进行比较，当两者存在差异时，就对此规划进行修

8、正。规划的好处可归纳为简化搜索、解决目标矛盾以及为就对此规划进行修正。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。差错补偿提供基础。8.1 机器人的规划与作用机器人的规划与作用v8.1.1规划的作用与问题分解途径规划的作用与问题分解途径v 2.2.问题分解途径及方法问题分解途径及方法v 把某些比较复杂的问题分解为一些比较小的子问题的想法使我们应用规划方法把某些比较复杂的问题分解为一些比较小的子问题的想法使我们应用规划方法求解问题在实际上成为可能。有两条能够实现这种分解的重要途径。求解问题在实际上成为可能。有两条能够实现这种分解的重要途径。v 第一条重要途径是，当从一个问题状

9、态移动到下一个状态时，无需计算整个新第一条重要途径是，当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。的状态，而只要考虑状态中可能变化了的那些部分。 v v 第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题，这种分解能够使困难问题的求解变得容易些。题，这种分解能够使困难问题的求解变得容易些。 8.1 机器人的规划与作用机器人的规划与作用v8.1.1规划的作用与问题分解途径规划的作用与问题分解途径 例如，要表示出八数码难题每走动一步后的状态如何变化是不难的，例

10、如，要表示出八数码难题每走动一步后的状态如何变化是不难的，要隐含地记录下具有适当变化的新状态也不需要做大量的工作。从一个状态要隐含地记录下具有适当变化的新状态也不需要做大量的工作。从一个状态移动到另一个状态的规则可以简单的描述为整盘棋如何从一种位置变换为另移动到另一个状态的规则可以简单的描述为整盘棋如何从一种位置变换为另一种位置，与其写出叙述把一个完整状态变换为另一个完整状态的规则，我一种位置，与其写出叙述把一个完整状态变换为另一个完整状态的规则，我们宁愿只写出叙述该状态描述中发生变化的那部分的规则。而对于其余部分，们宁愿只写出叙述该状态描述中发生变化的那部分的规则。而对于其余部分，我们可以假

11、定保持不变。我们可以假定保持不变。 8.1 机器人的规划与作用机器人的规划与作用v8.1.1规划的作用与问题分解途径规划的作用与问题分解途径 3.3.域的预测和规划的修正域的预测和规划的修正 (1)(1)域的预测域的预测 规划方法的成功取决于问题论域的另一特性规划方法的成功取决于问题论域的另一特性-预测。如果我们通过在实际上执预测。如果我们通过在实际上执行某个操作序列来寻找问题的解答，那末在这个过程的任何一步我们都能确信该步行某个操作序列来寻找问题的解答，那末在这个过程的任何一步我们都能确信该步的结果。但对于不可预测的论域，我们最好能考虑可能的结果的集合，这些结果很的结果。但对于不可预测的论域

12、，我们最好能考虑可能的结果的集合，这些结果很可能按照它们出现的可能性以某个次序排列。然后，我们产生一个规划，并试图去可能按照它们出现的可能性以某个次序排列。然后，我们产生一个规划，并试图去执行这个规划。执行这个规划。(2)(2)规划的修正规划的修正如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。大多程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。大多规则的执行主要是按目标定向模式工作的。这种模式下，规划系统从目标状态向可

13、规则的执行主要是按目标定向模式工作的。这种模式下，规划系统从目标状态向可达到的初始状态进行搜索。达到的初始状态进行搜索。 8.2 积木世界的机器人规划积木世界的机器人规划v问题求解是一个寻求某个动作序列以达到目标的过程，机器人问题求解即寻求某个机问题求解是一个寻求某个动作序列以达到目标的过程，机器人问题求解即寻求某个机器人的动作序列器人的动作序列( (可能包括路径等可能包括路径等) )，这个序列能够使该机器人达到预期的工作目标，完成，这个序列能够使该机器人达到预期的工作目标，完成规定的工作任务。规定的工作任务。v8.2.18.2.1积木世界的机器人的问题积木世界的机器人的问题 机器人技术的发展

14、为人工智能问题求解开拓了新的应用前景，并形成了一个新的研究机器人技术的发展为人工智能问题求解开拓了新的应用前景，并形成了一个新的研究领域领域-机器人学。许多问题求解系统的概念可以在机器人问题求解上进行试验研究和应用。机器人学。许多问题求解系统的概念可以在机器人问题求解上进行试验研究和应用。机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套动机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套动作。作。v设想有个积木世界和一个机器人。世界是几个有标记的立方形积木设想有个积木世界和一个机器人。世界是几个有标记的立方形积木( (在这里假定为一样在这里

15、假定为一样大小的大小的) )，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下以抓起积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下 8.2 积木世界的机器人规划积木世界的机器人规划v8.2.18.2.1积木世界的机器人的问题积木世界的机器人的问题 设想有个积木世界和一个机器人。世界是几个有标记的立方形积木设想有个积木世界和一个机器人。世界是几个有标记的立方形积木( (在这里假定为一样大在这里假定为一

16、样大小的小的) )，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可以抓，它们或者互相堆迭在一起，或者摆在桌面上；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下起积木块并移动积木从一处至另一处。在这个例子中机器人能够执行的动作举例如下 unstack(a,bunstack(a,b) )：把堆放在积木：把堆放在积木b b上的积木上的积木a a拾起。在进行这个动作之前，拾起。在进行这个动作之前， 要求机器人的手为空手，要求机器人的手为空手， 而且积木而且积木a a的顶上是空的。的顶上是空的。stack(a,bsta

17、ck(a,b) )：把积木：把积木a a堆放在积木堆放在积木b b上。动作之前要求机械手必须已抓住上。动作之前要求机械手必须已抓住 积木积木a a，而且积木，而且积木b b顶上必顶上必 须是空的。须是空的。pickup(apickup(a) )：从桌面上拾起积木：从桌面上拾起积木a a，并抓住它不放。在动作之前要求机械，并抓住它不放。在动作之前要求机械 手为空手，而且积木手为空手，而且积木a a顶上顶上 没有任何东西。没有任何东西。putdown(aputdown(a) )：把积木：把积木a a放置到桌面上。要求动作之前机械手已抓住积木放置到桌面上。要求动作之前机械手已抓住积木a a。8.2

18、积木世界的机器人规划积木世界的机器人规划8.2.18.2.1积木世界的机器人的问题积木世界的机器人的问题 机器人规划包括许多功能，例如识别机器人周围世界，表述动作规划，机器人规划包括许多功能，例如识别机器人周围世界，表述动作规划，并监视这些规划的执行。我们所要研究的主要是综合机器人的动作序列问题，并监视这些规划的执行。我们所要研究的主要是综合机器人的动作序列问题，即在某个给定初始情况下，经过某个动作序列而达到指定的目标。采用状态即在某个给定初始情况下，经过某个动作序列而达到指定的目标。采用状态描述作为数据库的产生式系统是一种最简单的问题求解系统。机器人问题的描述作为数据库的产生式系统是一种最简

19、单的问题求解系统。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操作和执行操作的结果，我们需要应用下列谓词：作和执行操作的结果，我们需要应用下列谓词： 积木世界的机器人问题积木世界的机器人问题 8.2 积木世界的机器人规划积木世界的机器人规划积木世界的机器人问题积木世界的机器人问题 CLEAR(B)：积木：积木B顶部为空顶部为空 CLEAR(C)：积木：积木C顶部为空顶部为空 ON(C，A)：积木：积木C堆在积木堆在积木A上上 ONTABLE(A)：积木：积木A置于桌面上置于桌面上 ONTABLE(

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

21、木世界的机器人的问题积木世界的机器人的问题 积木世界的机器人问题积木世界的机器人问题 CLEAR(B)：积木：积木B顶部为空顶部为空 CLEAR(C)：积木：积木C顶部为空顶部为空 ON(C，A)：积木：积木C堆在积木堆在积木A上上 ONTABLE(A)：积木：积木A置于桌面上置于桌面上 ONTABLE(B)：积木：积木B置于桌面上置于桌面上 HANDEMPTY：机械手为空手。：机械手为空手。(a)(a)所示为初始布局的机器人问题。这种布局可由下列谓词公式的合取来表示：所示为初始布局的机器人问题。这种布局可由下列谓词公式的合取来表示： 8.2 积木世界的机器人规划积木世界的机器人规划v8.2.

22、18.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)所示。也可以用谓词逻辑来描述此

23、目标为：所示。也可以用谓词逻辑来描述此目标为：ON(B，C)ON(A，B)8.2 积木世界的机器人规划积木世界的机器人规划8.2.2.8.2.2.用用F F规则求解规划序列规则求解规划序列 用用F F规则表示机器人的动作，这是一个叫做规则表示机器人的动作，这是一个叫做STRIPSSTRIPS规划系统的规则，它规划系统的规则，它由由3 3部分组成。部分组成。 第一部分是先决条件。为了使第一部分是先决条件。为了使F F规则能够应用到状态描述中去。这个先规则能够应用到状态描述中去。这个先决条件公式必须是逻辑上遵循状态描述中事实的谓词演算表达式。在应用决条件公式必须是逻辑上遵循状态描述中事实的谓词演算

24、表达式。在应用F F规则之前，必须确信先决条件是真的。规则之前，必须确信先决条件是真的。 F F规则的第二部分是一个叫做删除表的谓词。当一条规则被应用于某个规则的第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。状态描述或数据库时，就从该数据库删去删除表的内容。 F F规则第三部分叫做添加表。当把某条规则应用于某数据库时，就把该规则第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。对于堆积木的例子中添加表的内容添进该数据库。对于堆积木的例子中movemove这个动作可以表示如这个动作可以表示如下：下： 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.8.2.2.用用F F规则求解规划序列规则求解规划序列考虑上