第八章 机器人规划
8.1 机器人规划的作用与任务
8.2 积木机器的机器人规划
8.3 STRIPS规划系统
8.4 具有学习能力的规划系统
8.5 基于专家系统的机器人规划
8.6 小结
2
8.1 机器人规划的作用与任务
8.1.1 规划的作用与问题分解途径
?规划的概念及作用
?规划的概念
规划 是一种重要的问题求解技术，它
从某个特定的问题状态出发，寻求一系列
行为动作，并建立一个操作序列，直到求
得目标状态为止 。
图 8.1 子规划的分层结构例子
工 作 日 规 划
上午子规划 中午子规划 下午子规划
吃夹心面包 阅读 写作 回家去上班 阅读文章
3
?规划的作用
规划 可用来监控问题求解过程，并能够在造成较
大的危害之前发现差错。 规划的好处可归纳为简化
搜索、解决目标矛盾以及为差错补偿提供基础。
?问题分解途径及方法
把某些比较复杂的问题分解为一些比较小的子问
题。有两条能够实现这种分解的重要途径。
?第一条重要途径 是当从一个问题状态移动到下一
个状态时，无需计算整个新的状态，而只要考虑
状态中可能变化了的那些部分。
?第二条重要途径 是把单一的困难问题分割为几个
有希望的较为容易解决的子问题。
8.1自动规划的作用与任务
4
8.1.2 机器人规划系统的任务与方法
? 在规划系统中，必须具有执行下列各项任务的方法：
?根据最有效的启发信息，选择应用于下一步的最好规则。
? 应用所选取的规则来计算由于应用该规则而生成的新状
态。
? 对所求得的解答进行检验。
? 检验空端，以便舍弃它们，使系统的求解工作向着更有
效的方向进行。
? 检验殆正确的解答，并应用具体的技术使之完全正确。
8.1自动规划的作用与任务
5
8.2 积木世界的机器人规划
8.2.1 积木世界的机器人问题
积木世界由一些有标记
的立方形积木，互相堆
迭在一起构成；机器人
有个可移动的机械手，
它可以抓起积木块并移
动积木从一处至另一处。
C
B A
机械手
6
? 在这个例子中机器人能够执行的动作举例如下：
? unstack(a,b),把堆放在积木 b上的积木 a拾起。在进行这
个动作之前，要求机器人的手为空手，而且积木 a的顶上
是空的。
? stack(a,b),把积木 a堆放在积木 b上。动作之前要求机械
手必须已抓住积木 a，而且积木 b顶上必须是空的。
? pickup(a),从桌面上拾起积木 a，并抓住它不放。在动
作之前要求机械手为空手，而且积木 a顶上没有任何东西。
? putdown(a),把积木 a放置到桌面上。要求动作之前机械
手已抓住积木 a。
8.2 积木世界的机器人规划
7
研究内容 是综合机器人的动作序列，即在某个给定
初始情况下，经过某个动作序列而达到指定的目标。
机器人问题的状态描述和目标描述均可用谓词逻辑
公式构成：
?ON(a,b),积木 a在积木 b之上。
?ONTABLE(a)：积木 a在桌面上。
?CLEAR(a),积木 a顶上没有任何东西。
?HOLDING(a),机械手正抓住积木 a。
?HANDEMPTY：机械手为空手。
8.2 积木世界的机器人规划
8
图 8.4(a)所示为初始布局的机器人问题。
目标在于建立一个积木堆，其中，积木 B堆在积木
C上面，积木 A又堆在积木 B上面，如图 8.4(b)所示。
C
B A
机械手
A
B
C
机械手
（ a）初始布局 （ b）目标布局
图 8.4 积木世界的机器人问题
8.2 积木世界的机器人规划
9
初始布局可由下列谓词公式的合取来表示：
?CLEAR(B),积木 B顶部为空
?CLEAR(C),积木 C顶部为空
?ON(C,A)：积木 C堆在积木 A上
?ONTABLE(A),积木 A置于桌面上
?ONTABLE(B)：积木 B置于桌面上
?HANDEMPTY,机械手为空手
8.2 积木世界的机器人规划
10
8.2.2 用 F规则求解规划序列
STRIPS规划系统的规则由 3部分组成：
?第一部分是 先决条件 。
?第二部分是 一个叫做删除表的谓词 。
?第三部分 叫做添加表 。
8.2 积木世界的机器人规划
11
?例,表示堆积木的例子中 move这个动作，如下所示：
move(x,y,z)：把物体 x从物体 y上面移到物体 z上面。
先决条件, CLEAR(x),CLEAR(z),ON(x,y)
删除表, ON(x,z),CLEAR(z)
添加表, ON(x,z),CLEAR(y)
?如果 move为此机器人仅有的操作符或适用动作，那
么，可以生成如图 8.5所示的搜索图或搜索树。
CLEAR(X)
CLEAR(Z)
ON(X,Y)
ONTABLE(Y)
ONTABLE(Z)
CLEAR(X)
CLEAR(Y)
ON(X,Z)
ONTABLE(Y)
ONTABLE(z)
move(X,Y,Z)
图 8.5 表示 move动作的搜索树
8.2 积木世界的机器人规划
12
机器人的 4个动作 (或操作符 )可用 STRIPS形式表示如下：
? stack(X,Y)
先决条件和删除表, HOLDING(X)∧ CLEAR(Y)
添加表, HANDEMPTY,ON(X,Y)
? unstack(X,Y)
先决条件, HANDEMPTY∧ ON(X,Y)∧ CLEAR(X)
删除表, ON(X,Y),HANDEMPTY
添加表, HOLDING(X),CLEAR(Y)
? pickup(X)
先决条件, ONTABLE(X)∧ CLEAR(X)∧ HANDEMPTY
删除表, ONTABLE(X)∧ HANDENPTY
添加表, HOLDING(X)
? putdown(X)
先决条件和删除表, HOLDING(X)
添加表, ONTABLE(X),HANDEMPTY
8.2 积木世界的机器人规划
13
从初始状态开始，正向地依次读出连接弧线上
的 F规则，我们就得到一个能够达到目标状态的动作
序列（如图 8.6中粗线所示）于下：
{unstack(C,A),putdown(C),pickup(B),stack(B,C),
pickup(A),stack(A,B)}
就把这个动作序列叫做达到这个积木世界机器
人问题目标的规划。
8.2 积木世界的机器人规划
14
8.3 STRIPS规划系统
?STRIPS的介绍
STRIPS是由 Fikes,Hart和 Nilsson3人在 1981及
1982研究成功的，它是夏凯 (Shakey)机器人程序控制
系统的一个组成部分。
?STRIPS系统组成
?世界模型,为一阶谓词演算公式；
?操作符 (F规则 ),包括先决条件、删除表和添加表；
?操作方法,应用状态空间表示和中间 -结局分析。
15
8.4 具有学习能力的规划系统
? PULP-Ⅰ 机器人规划系统
PULP-Ⅰ 机器人规划系统是一种具有学习能力的
系统，它采用管理式学习，其作用原理是建立在类
比 (analogue)的基础上的。
? STRIPS的弱点
需要极其大量计算机内存和时间等。
应用具有学习能力的规划系统能够克服这一缺点。
16
8.4.1 PULP-Ⅰ 系统的结构与操作方式
?PULP-Ⅰ 系统的结构
“字典” 是英语词
汇的集合。
“模型” 部分包括模型世界 物体现有状态的事实。
“过程” 集中了予先准备好的过程知识。
“方块” 集中了 LISP程序，它配合“规划”对“模型”
进行搜索和修正。
SENEF
程序 规划与学习
字典 模型 过程 方块
响应
输入
图 8.14 PULP-Ⅰ 系统的总体结构
8.4 具有学习能力的规划系统
17
?PULP-Ⅰ 系统的操作方式
PULP-Ⅰ 系统具有两种操作方式：
?学习方式
在学习方式下，输入
至系统的知识是由操作人
员或者所谓“教师”提供
的。图 8.15表示出在学习
方式下的系统操作。
存储
任务分析
方块
匹配
过程
分解
学习教师
输入任务知识 响应
图 8.15 学习方式下 PULP-Ⅰ 系统的结构
8.4 具有学习能力的规划系统
18
?规划方式
当某个命令句子
送入系统时，
PULP-Ⅰ 就进入
规划方式。上图
表示 PULP-Ⅰ 系统在
规划方式下的结构。
检索
混合规划
方块
目标检
验匹配
单一规划
规划
输入命令 响应
过程模型
图 8.16 规划方式下 PULP-Ⅰ 系统的结构
8.4 具有学习能力的规划系统
19
8.5 基于专家系统的机器人规划
?机器人规划专家系统就是用专家系统的结构和技
术建立起来的机器人规划系统 。
?管理式学习能力的机器人规划系统的不足：
? 表达子句的语义网络结构过于 复杂。
?与复杂的系统内部数据结构有关的是，
PULP-Ⅰ 系统具有许多子系统。而且需要
花费大量时间来编写程序。
? 尽管 PULP-Ⅰ 系统的执行速度要比 STRIPS
系列快得多，然而它仍然不够快。
20
8.5.1系统结构和规划机理
?系统结构及规划机理
机
器
人
用
户
机
器
人
专
家
知
识
用
户
接
口
知识库
推理机
控制
策略
工具
专家系统
知识获取
说明与分析
问题输入或
新情况描述
回答问题或
建议与解释
图 8.20 机器人规划专家系统的结构
21
?基于规划的机器人规划专家系统由 5个部分组成，
如图 8.20所示。
?知识库
?控制策略
?推理机
?知识获取
?解释与说明
?基于规则的专家系统的目标就是要通过逐条执行
规则及其有关操作来逐步地改变总数据库的状况，
直到得到一个可接受的数据库 (称为目标数据库 )为
止。
8.5 基于专家系统的机器人规划
22
?任务级机器人规划三要素
?任务规划是机器人高层规划最重要的一个方
面，它包含下列 3个要素：
?建立模型
建立机器人工作环境的世界模型。
?任务说明
?程序综合
任务级机器人规划的最后一步是综合机械
手的程序。
8.5 基于专家系统的机器人规划
23
8.6 小结
本章在说明了机器人规划的作用和任务后，主要
讨论了几种机器人规划的方法：
?规划演绎法。
?逻辑演算和通用搜索法
?具有学习能力的规划系统
?基于专家系统的规划
值得指出,第一，机器人规划已发展为综合应用
多种方法的规划。第二，机器人规划方法已广泛
应用于图象处理、计算机视觉等各领域。第三，
机器人规划尚有一些进一步研究的问题，如多机
器人协调规划和实时规划等。
8.1 机器人规划的作用与任务
8.2 积木机器的机器人规划
8.3 STRIPS规划系统
8.4 具有学习能力的规划系统
8.5 基于专家系统的机器人规划
8.6 小结
2
8.1 机器人规划的作用与任务
8.1.1 规划的作用与问题分解途径
?规划的概念及作用
?规划的概念
规划 是一种重要的问题求解技术，它
从某个特定的问题状态出发，寻求一系列
行为动作，并建立一个操作序列，直到求
得目标状态为止 。
图 8.1 子规划的分层结构例子
工 作 日 规 划
上午子规划 中午子规划 下午子规划
吃夹心面包 阅读 写作 回家去上班 阅读文章
3
?规划的作用
规划 可用来监控问题求解过程，并能够在造成较
大的危害之前发现差错。 规划的好处可归纳为简化
搜索、解决目标矛盾以及为差错补偿提供基础。
?问题分解途径及方法
把某些比较复杂的问题分解为一些比较小的子问
题。有两条能够实现这种分解的重要途径。
?第一条重要途径 是当从一个问题状态移动到下一
个状态时，无需计算整个新的状态，而只要考虑
状态中可能变化了的那些部分。
?第二条重要途径 是把单一的困难问题分割为几个
有希望的较为容易解决的子问题。
8.1自动规划的作用与任务
4
8.1.2 机器人规划系统的任务与方法
? 在规划系统中，必须具有执行下列各项任务的方法：
?根据最有效的启发信息，选择应用于下一步的最好规则。
? 应用所选取的规则来计算由于应用该规则而生成的新状
态。
? 对所求得的解答进行检验。
? 检验空端，以便舍弃它们，使系统的求解工作向着更有
效的方向进行。
? 检验殆正确的解答，并应用具体的技术使之完全正确。
8.1自动规划的作用与任务
5
8.2 积木世界的机器人规划
8.2.1 积木世界的机器人问题
积木世界由一些有标记
的立方形积木，互相堆
迭在一起构成；机器人
有个可移动的机械手，
它可以抓起积木块并移
动积木从一处至另一处。
C
B A
机械手
6
? 在这个例子中机器人能够执行的动作举例如下：
? unstack(a,b),把堆放在积木 b上的积木 a拾起。在进行这
个动作之前，要求机器人的手为空手，而且积木 a的顶上
是空的。
? stack(a,b),把积木 a堆放在积木 b上。动作之前要求机械
手必须已抓住积木 a，而且积木 b顶上必须是空的。
? pickup(a),从桌面上拾起积木 a，并抓住它不放。在动
作之前要求机械手为空手，而且积木 a顶上没有任何东西。
? putdown(a),把积木 a放置到桌面上。要求动作之前机械
手已抓住积木 a。
8.2 积木世界的机器人规划
7
研究内容 是综合机器人的动作序列，即在某个给定
初始情况下，经过某个动作序列而达到指定的目标。
机器人问题的状态描述和目标描述均可用谓词逻辑
公式构成：
?ON(a,b),积木 a在积木 b之上。
?ONTABLE(a)：积木 a在桌面上。
?CLEAR(a),积木 a顶上没有任何东西。
?HOLDING(a),机械手正抓住积木 a。
?HANDEMPTY：机械手为空手。
8.2 积木世界的机器人规划
8
图 8.4(a)所示为初始布局的机器人问题。
目标在于建立一个积木堆，其中，积木 B堆在积木
C上面，积木 A又堆在积木 B上面，如图 8.4(b)所示。
C
B A
机械手
A
B
C
机械手
（ a）初始布局 （ b）目标布局
图 8.4 积木世界的机器人问题
8.2 积木世界的机器人规划
9
初始布局可由下列谓词公式的合取来表示：
?CLEAR(B),积木 B顶部为空
?CLEAR(C),积木 C顶部为空
?ON(C,A)：积木 C堆在积木 A上
?ONTABLE(A),积木 A置于桌面上
?ONTABLE(B)：积木 B置于桌面上
?HANDEMPTY,机械手为空手
8.2 积木世界的机器人规划
10
8.2.2 用 F规则求解规划序列
STRIPS规划系统的规则由 3部分组成：
?第一部分是 先决条件 。
?第二部分是 一个叫做删除表的谓词 。
?第三部分 叫做添加表 。
8.2 积木世界的机器人规划
11
?例,表示堆积木的例子中 move这个动作，如下所示：
move(x,y,z)：把物体 x从物体 y上面移到物体 z上面。
先决条件, CLEAR(x),CLEAR(z),ON(x,y)
删除表, ON(x,z),CLEAR(z)
添加表, ON(x,z),CLEAR(y)
?如果 move为此机器人仅有的操作符或适用动作，那
么，可以生成如图 8.5所示的搜索图或搜索树。
CLEAR(X)
CLEAR(Z)
ON(X,Y)
ONTABLE(Y)
ONTABLE(Z)
CLEAR(X)
CLEAR(Y)
ON(X,Z)
ONTABLE(Y)
ONTABLE(z)
move(X,Y,Z)
图 8.5 表示 move动作的搜索树
8.2 积木世界的机器人规划
12
机器人的 4个动作 (或操作符 )可用 STRIPS形式表示如下：
? stack(X,Y)
先决条件和删除表, HOLDING(X)∧ CLEAR(Y)
添加表, HANDEMPTY,ON(X,Y)
? unstack(X,Y)
先决条件, HANDEMPTY∧ ON(X,Y)∧ CLEAR(X)
删除表, ON(X,Y),HANDEMPTY
添加表, HOLDING(X),CLEAR(Y)
? pickup(X)
先决条件, ONTABLE(X)∧ CLEAR(X)∧ HANDEMPTY
删除表, ONTABLE(X)∧ HANDENPTY
添加表, HOLDING(X)
? putdown(X)
先决条件和删除表, HOLDING(X)
添加表, ONTABLE(X),HANDEMPTY
8.2 积木世界的机器人规划
13
从初始状态开始，正向地依次读出连接弧线上
的 F规则，我们就得到一个能够达到目标状态的动作
序列（如图 8.6中粗线所示）于下：
{unstack(C,A),putdown(C),pickup(B),stack(B,C),
pickup(A),stack(A,B)}
就把这个动作序列叫做达到这个积木世界机器
人问题目标的规划。
8.2 积木世界的机器人规划
14
8.3 STRIPS规划系统
?STRIPS的介绍
STRIPS是由 Fikes,Hart和 Nilsson3人在 1981及
1982研究成功的，它是夏凯 (Shakey)机器人程序控制
系统的一个组成部分。
?STRIPS系统组成
?世界模型,为一阶谓词演算公式；
?操作符 (F规则 ),包括先决条件、删除表和添加表；
?操作方法,应用状态空间表示和中间 -结局分析。
15
8.4 具有学习能力的规划系统
? PULP-Ⅰ 机器人规划系统
PULP-Ⅰ 机器人规划系统是一种具有学习能力的
系统，它采用管理式学习，其作用原理是建立在类
比 (analogue)的基础上的。
? STRIPS的弱点
需要极其大量计算机内存和时间等。
应用具有学习能力的规划系统能够克服这一缺点。
16
8.4.1 PULP-Ⅰ 系统的结构与操作方式
?PULP-Ⅰ 系统的结构
“字典” 是英语词
汇的集合。
“模型” 部分包括模型世界 物体现有状态的事实。
“过程” 集中了予先准备好的过程知识。
“方块” 集中了 LISP程序，它配合“规划”对“模型”
进行搜索和修正。
SENEF
程序 规划与学习
字典 模型 过程 方块
响应
输入
图 8.14 PULP-Ⅰ 系统的总体结构
8.4 具有学习能力的规划系统
17
?PULP-Ⅰ 系统的操作方式
PULP-Ⅰ 系统具有两种操作方式：
?学习方式
在学习方式下，输入
至系统的知识是由操作人
员或者所谓“教师”提供
的。图 8.15表示出在学习
方式下的系统操作。
存储
任务分析
方块
匹配
过程
分解
学习教师
输入任务知识 响应
图 8.15 学习方式下 PULP-Ⅰ 系统的结构
8.4 具有学习能力的规划系统
18
?规划方式
当某个命令句子
送入系统时，
PULP-Ⅰ 就进入
规划方式。上图
表示 PULP-Ⅰ 系统在
规划方式下的结构。
检索
混合规划
方块
目标检
验匹配
单一规划
规划
输入命令 响应
过程模型
图 8.16 规划方式下 PULP-Ⅰ 系统的结构
8.4 具有学习能力的规划系统
19
8.5 基于专家系统的机器人规划
?机器人规划专家系统就是用专家系统的结构和技
术建立起来的机器人规划系统 。
?管理式学习能力的机器人规划系统的不足：
? 表达子句的语义网络结构过于 复杂。
?与复杂的系统内部数据结构有关的是，
PULP-Ⅰ 系统具有许多子系统。而且需要
花费大量时间来编写程序。
? 尽管 PULP-Ⅰ 系统的执行速度要比 STRIPS
系列快得多，然而它仍然不够快。
20
8.5.1系统结构和规划机理
?系统结构及规划机理
机
器
人
用
户
机
器
人
专
家
知
识
用
户
接
口
知识库
推理机
控制
策略
工具
专家系统
知识获取
说明与分析
问题输入或
新情况描述
回答问题或
建议与解释
图 8.20 机器人规划专家系统的结构
21
?基于规划的机器人规划专家系统由 5个部分组成，
如图 8.20所示。
?知识库
?控制策略
?推理机
?知识获取
?解释与说明
?基于规则的专家系统的目标就是要通过逐条执行
规则及其有关操作来逐步地改变总数据库的状况，
直到得到一个可接受的数据库 (称为目标数据库 )为
止。
8.5 基于专家系统的机器人规划
22
?任务级机器人规划三要素
?任务规划是机器人高层规划最重要的一个方
面，它包含下列 3个要素：
?建立模型
建立机器人工作环境的世界模型。
?任务说明
?程序综合
任务级机器人规划的最后一步是综合机械
手的程序。
8.5 基于专家系统的机器人规划
23
8.6 小结
本章在说明了机器人规划的作用和任务后，主要
讨论了几种机器人规划的方法：
?规划演绎法。
?逻辑演算和通用搜索法
?具有学习能力的规划系统
?基于专家系统的规划
值得指出,第一，机器人规划已发展为综合应用
多种方法的规划。第二，机器人规划方法已广泛
应用于图象处理、计算机视觉等各领域。第三，
机器人规划尚有一些进一步研究的问题，如多机
器人协调规划和实时规划等。
