（计算机软件与理论专业论文）基于粗糙集的智能规划模型的研究.pdf

摘要 智能规划是人工智能一个重要的领域。 近年来， 有关智能规划的研究在问 题的描 述和问 题求解两方面得到了新的突破， 使得智能规划己 成为现在一个热门的人工智能 研究领域。 随 着智能规划从理论研究逐渐向 应用研究发展的 过程中， 人们发现经典的 智能规划根本无法满足实际应用的要求， 因为经典规划要求知识的完全性， 即要求状 态空间确定， 初始状态、 动作、 动作的结果状态、目 标状态己知; 而在实际应用中的 真实世界里具有许多不确定的因素。 所以 研究者们提出了不确定性规划来求解具有不 确定性的 规划问 题。 在不确定性规划问 题中的不确定性源主要有: 初始状态的不确定 和动作的不确定。 本文通过对不确定性规划的研究， 提出了一种新的不确定性: 初始对象的不确定， 也就是规划问题的初始对象集根据目 前己 知的知识是不精确、 不确定的。 一个规划问 题是由问 题的初始状态、 问 题的操作集合、 问 题的对象集合和问题的目 标状态组成的. 如果说规划问 题的对象集合不确定的 话， 则会导致智能规划的不确定。 本文提出了利用粗糙集理论来处理对象集合的不确定性， 在对粗糙集和智能规划 深入研究的基础上， 给出了 一系列的定义， 包括粗规划问 题、 可能的 初始状态、 可能 的目 标集合、 粗糙动作、 规划的上近似集和规划的下近似集的概念。 在一系列概念的 基础上给出了 粗规划问题的两种求解模型， 并提出基于规划图的粗规划算法， 包括粗 规划图的扩张算法和对粗规划图的搜索算法。 粗规划是一个全新的研究领域， 虽然粗糙集和智能规划是国内外研究的热点， 但 日 前国内 外还没有关于粗规划的 研究。 所以 本文的研究工作在理论上具有很大的学术 价值;而且在实际的应用中，它也有很好的应用前景。 关键词:人工智能;智能规划;粗糙集;粗规划 abs t r a c t n o w i n t e l l i g e n t p l a n n i n g i s a v e r y h o t b r a n c h i n a l . b e c a u s e o f i t s w i d e a p p li c a t i o n re s e a r c h e r s p a y m u c h a tt e n t i o n t o p l a n n i n g t e c h n o l o g y . r o u g h s e t t h e o ry i s a n e w m a t h e m a t i c a l a p p ro a c h t o i m p e r f e c t k n o w l e d g e . i n t h i s p a p e r , w e s t u d y r o u g h s e t t h e o ry d e e p l y i n o r d e r t o a p p l y i t t o i n t e l l i g e n t p l a n n i n g . w e s u r v e y t h e o r i g i n a n d d e v e l o p m e n t o f i n t e l l i g e n t p l a n n in g a n d i t s a p p l i c a t i o n s , b r i e fl y s t a t e t h e in 匆h p l a n m e t h o d s , a n d i m p r o v e t h e g r a p h p l a n a l g o ri t h m t h e d i s s e rt a t i o n s u g g e s t s a m e t h o d b a s e d o n ro u g h s e t s t h e o ry n a m e l y r o u g h p l a n n i n g a ft e r d e t a i l e d l y r e s e a r c h i n g t h e c h a r a c t e r s o f ro u g h s e t t h e o ry a n d c a r e f u l ly s t u d y i n g th e u n c e r t a i n ty i n i n t e l li g e n t p l a n n i n g . w e p u t f o r w a r d s o m e n e w b a s i c c o n c e p t s , i n c l u d e ro u g h p l a n n i n g p ro b l e m , p o s s i b l e i n i t i a l s t a t e , p o s s i b l e g o a l s e t , ro u g h a c t i o n , t h e l o w e r a p p r o x i m a t i o n o f a p l a n , t h e u p p e r a p p ro x i m a t i o n o f a p l a n e t c . a l s o t w o k i n d s o f r o u g h - s e t - b a s e d i n t e l l i g e n t p l a n n i n g m o d e l a r e p r o p o s e d i n t h i s p a p e r . f i n a l l y w e p ro p o s e a r o u g h p l a n n i n g a l g o r i t h m b a s e d o n p l a n n i n g g r a p h , i n c l u d e t h e a l g o r i t h m o f e x p a n d i n g ro u g h p l a n n i n g g r a p h a n d t h e a l g o r i t h m o f s e a r c h in g t h e ro u g h p l a n n i n g g r a p h . t h i s r e s e a r c h o n r o u g h i n t e ll i g e n t p l a n n i n g i s v e r y i m p o r t a n t b o t h t h e o r e t i c a l l y a n d p r a c t i c a l l y . k e y w o r d s : a i ; i n t e l li g e n t p l a n n i n g ; r o u g h s e t ; r o u g h i n t e ll i g e n t p l a n n i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示谢意。 学位论文作者签名:日期: 学位论文版权使用授权书 本学位论文作者完全了 解东北师范大学有关保留、使用学位 论文的规定，即:东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学 位 论 文 作 者 签名: .1 a 指导 教 师 签 名: 日期: .1k. 5 . 2 o 日期: 学位论文作者毕业后去向: 工作单位: 通讯地址: 电话: 邮编: 引言 在人工智能研究中， 智能规划 ( a 工p l a n n i n g ) 实际上就是一种问 题求解技术， 即从某个特定问题的初始状态出发， 发现一系列行为或构造一系列操作 ( 也有称之为 算子的) 步骤， 达到解决该问题的目 标状态。 在人工智能的研究中规划也是其较早的 研究领域之一， 它的研究起初源于问 题的求解， 由于其广泛的实用性， 受到研究者的 高 度重视。 人们对于它的研究可以 追溯到6 0 年代:1 9 5 7 年n e w e l l 和s i m o n 的 通用 问 题 求 解 程 序 ( g p s ) , g r e e n 的q a 3 系 统 ( 1 9 6 9 ) 0 1 9 7 1 年f i k e 和n i l s s o n 的s t r i p s 4 系统在智能规划领域中 具有划时代的 意义， 这使得规划可以 非常容易地进行描述和操 作，但由于受到当时客观条件的制约，该领域一直处于较为保守的状态;近几年来， 随着客观条件的改善， 世界上特别是一些发达国 家在此领域获得了长足的发展， 在国 防和空间 技术领域中得以 应用， 取得了巨 大的经济和社会效益， n a s a 于1 9 9 9 年在航 天器 d e e p s p a c e o n e ”中运用规划技术， 使得规划研究从实验室向 实际应用迈出了 重要的一步， 标志着规划的 研究步入了实用阶段， 在人工智能领域形成了智能规划这 一当前研究的热点， 但是在我国关于规划理论和应用的研究现在还处于初级阶段。 r o u g h 集 ( r o u g h s e t s ， 有的也称粗集、 粗糙集) 理论是波兰华沙理工大学科学 家p a w l a k 教授于2 0 世纪8 0 年代 ( 1 9 8 2 ) 提出的一种研究不完整、不确定知识和数 据的表达、 学习、 归纳的理论方法。 粗糙集理论将知识理解为对数据的划分， 每一被 划分的 集合称为概念。 粗糙集理论的主要思想是利用已 知的知识库， 将不确定或不精 确的知识用已 知的知识库中的知识来刻画。 它的一个突出 优点是具有很强的定性分析 能力， 即 不需要预先给定某些特征或属性的 数量描述， 如统计学中的概率分布、 模糊 集理论中的隶属度或隶属函数等， 而是直接从给定问题的描述集合出发， 通过不可分 辨关系和不可分辨类确定问题的近似域，找出问题中的内在规律。 本文首先对智能规划进行了概括地介绍，分析了目 前智能规划的研究现状和应 用情况， 然后深入了 地研究了粗糙集理论。 在对智能规划和粗糙集深入研究的基础上 提出了 基于粗糙集的智能规划模型。 本篇文章的结构如下: 第一章主要是对智能规划 进行了 概述; 第二章主要介绍了图规划方法和我对图 规划算法所做的若干研究工作; 第三章主要介绍了粗糙集理论的一些知识; 在第四章提出了基于粗糙集的智能规划研 究模型。 第一章智能规划概述 1 . 1 智能规划的墓本概念 规划过程是一种问题求解方法， 一个规划系统我们可以认为就是一个问题求解系 统， 若用它求解比 较复杂的问 题， 即可求得一个动作序列( 串行、 并行或串并行混合) ， 依次执行此动作序列可以完成某一特定的具体任务， 最终达到一个特定目 标。 在人工 智能的研究中规划是其较早的研究领域之一， 它的 研究可以 追朔到6 0 年代: 1 9 5 7 年 n e w e l l 和s i m o n 的问 题求解程序( g p s ) . g r e e n 的q a 3 系统 ( 1 9 6 9 ) ， 。 1 9 7 1 年f i k e 和n i l s s o n 的s t r i p s 系统12 1 在智能 规划领域中 具有划时 代的 意义， 这使得 规划可以 非常容易地进行描述和操作， 但由于受到当时客观条件的制约， 该领域一直处于较为 保守的 状态。 但是由 于其广泛的实用性， 受到 研究者的高度重视， 特别是近几年来， 随着客观条件的改善， 世界上特别是一些发达国家在此领域获得了长足的发展， 己 经 开发出来了获取和使用特定领域控制信息的有效方法，并且有了一些实用的规划器 ( p l a n n e r ) ， 它们能够在数分钟内 合成包括上百条动作的规划， 并且在国防和空间技 术领域中得以 成功地应用， 取得了巨 大的经济和社会效益， n a s a 于1 9 9 9 年在航天器 d e e p s p a c e o n e ” 中运用规划技术， 使得规划研究从实验室向 实际 应用迈出了 重要 的 一步， 标志着规划的研究步入了 实用阶段， 智能 规划己 经成为人工智能领域研究的 热点。 一方面， 智能规划是一个多领域交叉的 研究领域， 它涉及知识表达、知识推理、 非单调逻辑、 情景演算、 人机交互和知识挖掘等各个方面。 在人工智能领域， 规划目 前还没有一个统一的定义， m c d e r m o t t 和j a m e s h e n d e l e r 3 认为 “ 规划就是设计某个 ( 组) 实体 ( e n t i t y ) 的动作序列， 其结果被称之为规划解 ( p l a n ) 。 一个规划解实 质上就是一个动作序列， 此序列能够实 现某一目 标， 智能规划就是设计这个动作序列 的过程，也就是说它主要解决怎么样做，而不解决为什么。 2 一般地，我们在做规划之前，大多做以下的假设: 1 . 规划是动作的序列。 2 . 动作的执行前件是确定的。 3 . 动作的执行后件 ( 效果)是确定的。 通常， 我们把满足以 上假设的规划称之为“ 经典的规划” ( c l a s s i c a l p l a n n i n g ) , 例如地图着色问题、 积木世界问 题等都是经典的规划问题。 现在， 大多数研究者还在 采纳此假定， 但是由于现实世界的复杂性， 实际问题往往并不能满足上述条件， 因此 也有一部分人正在研究放宽此假定， 研究在环境不断变化情况下的规划问题， 不满足 此 假定的 规 划问 题 称之为“ 非 经典的 规 划” ( n o n c l a s s i c a l - p l a n n i n g ) . 由上面的讨论我们可以看到， 规划问题由 于其自 身的特点， 它至少包括三个部分: 初始状态、目 标状态和动作。 初始状态和目 标状态是规划问 题的 起点和终点， 动作是 可能由 初始状态到达目 标状态的一系列可以执行的动作。 初始状态和目 标状态属于状 态的描述， 一般用一阶逻辑或命题逻辑来表示。 动作 ( 也有叫操作的) 主要包括三部 分:动作名称、动作前件和动作后件。 q i a n g y a n g ， 把s t r i p s 规 划问 题定 义 为 一 个 三 元 组: ， 其 中， 工 n i t 是初始状态文字的集合，即 初始世界模型; g o a l 是目 标状态文字，即目 标状态 模型;0 是规划操作 ( 动作)的集合，也有的称之为域理论。 1 . 2 智能规划的发展 人们对智能规划的 研究已 经有半个世纪了， 最早可以 追朔到1 9 5 6 年n e w e l l . s h a w 和s i m o n 设计的 逻辑理论家 ( l o g i c t h e o r i s t ) 程序， 这个系统采用了启发式信息和 反向搜索技术，随后他们设计的g p s 系统把领域知识与一般的搜索控制信息相分离， 上述两个系统特别是g p s 在人工智能领域中具有非常重要的地位， 但它们还不是真正 面向规划问题研制的智能规划系统。 1 9 6 9 年g r e e n 通过归结定理证明的方法来进行规划求解， 并且设计了q a 3 系统w 这一系统被大多数的智能规划研究人员认为是第一个规划器， 原因就在于他是第一个 面向 现实规划问 题提出的 规划系统:1 9 7 1 年f i k e s 和n i l s s o n 设计的s t r i p s 系统1 j 在智能规划的 研究中具有重大的意义和价值， 他的突出 贡献是引 入了s t r i p s 操作符 的概念，使得原来很神秘的规划问 题求解变得明朗清晰起来;此后到 1 9 7 7 年先后出 现了h a c k e r , w a r p l a n , i n t e r p l a n , a b s t r i p s , n o a h , n o n l i n 等规划系统。 这个十 年时间人们研究智能规划的兴致比 较高， 普遍认为规划问题必须用定理证明的理论来 解决， 直到c h a p m a n 设计的规划系统t w e a k 出 现。 由 于c h a p m a n 的分析， 使人们认识 到简单地利用定理证明的方法来解决规划问 题是很难的，因此这以后到1 9 9 0 年间， 在人们发现新的求解方法之前， 对智能规划的研究陷入了低谷， 这期间仅有 s i p e , a b t w e a k和p r o d i g y 0 ) 等较少的智能规划器出 现。 1 9 9 2 年k a u t z 等把规 划问 题求 解转 化为可 满足 ( s a t ) 问 题2 u ， 一反定 理证明 式 求解方法， 利用在约束可满足问 题算法上的突破， 有效地解决了部分规划问 题。 后来， 基于 此 理论的b l a c k b o x 规划器(7 1 7 在 第一届 智能 规划器的比 赛 ( 参见附 录a ) 中 表现 了 非凡的 解决问 题能力， 一举夺魁， 开辟了 解决规划问 题的又一新途径。 1 9 9 5 年a v r i m b l u m 等 设 计的 图 规 划系 统g r a p h p l a n 3 第 一次 采 用图 的 方式 来 解决 规 划问 题， 并 且 提 出了用于规划的规划图的概念。 后来很多规划系统都借鉴了图规划系统的方法， 参加 第一届智能规划比赛的规划器除委内瑞拉的h s p 外， 其它四个规划器s g p , b l a c k b o x , i p p 和s t a n 都或多或少地采用了图 规划的某种 ( 些) 技巧，并且对图 规划做了 相应 的 扩充: s g p 加入了 用户互操作界面; b l a c k b o x 则综合了基于规划图的快速规划扩展 和基于 s a t的快速规划验证的优点;up扩充了图规划的问题描述语言，支持 a d l 规划描述语言， 它能够处理条件效果等， 这样它的 表达能力比图规划器要强大; s t a n 在减少搜索和构造规划图的费用上做了扩充. 这些规划算法都是部分序或非线性的通 用规划器，此次比赛表明部分序方法在规划求解中具有举足轻重的地位。 两年以后， 在第二届规划比 赛 ( 参见附录b ) 上， 部分序规划的思想得到了 进一步验证， 并且在 规划过程中规划知识被人们广泛关注。 在参加比 赛的十六种规划器中采用启发式知识 的有十一个， 并且采用启发式知识的 规划器比 没有采用启发式知识的规划器得到的规 划解效果好: 例如比赛评委评选出的最佳规划器t a l p l a n n e r 和f f ，以 及排名其次的 s t a n , h s p 2 , m i p s 和s y s t e m r 都是 采用启发 式知识的 规划器， 在 此次比 赛中 采用启 发式知识的规划器表现出很强的问题求解能力，而第一届比赛的冠军 b l a c k b o x ( g r a p h p l a n + s a t ) 则由 于没有采用启发式知识在此次比赛中表现不如人意。 综上所述，规划问 题求解从最初的定理证明方法到s t r i p s 方法是问 题求解方法 4 上的转变， 然后又发展了非线性规划器， 采用目 标导向的方式来生成规划: 一方面使 得规划的生成速度大大提高; 另一方面，由于是目 标导向的生成方式，因此生成规划 的质量比 较好。 现在人们又在此基础上加入了启发式信息， 进一步提高规划求解的效 率和质量。 1 . 3 规划问题描述语言 规划问题的定义是规划问题求解的前提， 如果一个规划问题不能通过规划语言来 表示， 则任何一个规划器都不能对它进行求解， 所以说规划语言的发展是智能规划发 展的 关 键。 1 9 7 1 年f i k e 和n i l s o n 的s t r i p s 系 统 在智能 规 划中 具 有 划时 代的 意 义， 因为它使得规划可以 非常容易地进行描述和操作。 但随着规划技术的应用， 人们发觉 s t r 工 p s表示的表达能力非常地有限，它不能 满足一些实际问 题的 模型化要求。 设计 一种能够刻划、模型化一个实际问 题的规划问 题定义语言成为了规划技术应用的关 键，1 9 9 6年 e . p e d n a u l t (9 ) 提出7动作描述语言一一a d l ( a c t i o n d e s c r i p t i o n l a n g u a g e ) , a d l 除了 具 有s t r 工 p s 的 表 达能 力 外， 还 能 表达 条 件效 果、 量 化 效 果 等 语 言 特征。 1 9 9 8 年d r e w m c d e r m o t t e 提出 了 规 划 领 域定 义 语言( p d d l ) ， 它 逐 渐 地 成 为 公 认的国际智能规划比 赛( i n t e r n a t i o n a l p l a n n i n g c o m p e t i t i o n , i p c ) 的标准。 p d d l 语言不仅给出了 规划问 题定义的语法，也从语义的角度给出了规划的定义。p d d l语 言的表达能力非常强， 能够刻画规划问 题的时间 和数值方面的属性， 超过了 现有的 规 划器所能处理的表达能力，给规划器的发展提出了挑战，指明了发展的方向。 规划语言也是规划领域的一种交流和沟通的标准， 对于不同的规划器我们可以 通 过它们对同一规划问题的处理来进行比较。 1 . 3 . 1 s t r i p s 表示 s t r 工 p s c21是一 个非 常 著 名的 规 划 器， 它 代 表“ 斯坦 福 研究 委员会问 题求 解 器” 造于2 0 世纪7 0 年代，用来控制不稳定的可动机器人。s t r i p s 系统在智能规划中具 有划时代的意义，因为它使得规划可以 非常容易地进行描述和操作。 规划问 题的一种简单的形式化方法是定义三个输入: 5 ( 1 ) 用某种形式语言对该领域的初始状态的描述; ( 2 ) 用某种形式语言对目 标的描述; ( 3 ) 可能被执行动作的 描述 ( 也用某种形式语言) ， 这个描述通常被称为域理论。 s t r i p s表示定义了“ 经典”的规划问 题， 它用一系列完整的基本字来描述域的 初始状态， 并且将目标定义为一个合取命题， 所有满足目标形式的域状态将被同等地 考虑。 在s t r i p s 表示中， 每个动作用一个合取前提和合取结果来描述， 它们定义了 从域到域的过渡函数。 动作能在满足前提公式的任何域w 中执行， 执行的结果通过描 述域w 状态， 为动作结果的合取依次地添加描述动作效果的实字， 除去过程中的矛盾 实字。 1 . 3 . 2动作描述语言a d l 采用s t r i p s 式语言描述的经典规划问 题具有一定的限制条件，即 动作的前 提是 命题的合取， 动作的结果也是命题的合取， 时间被离散地表示， 动作既不能创建新的 对象， 也不能消灭对象。 并且， 动作一旦执行， 其执行的结果是确定的。 这种规划描 述语言对有些问 题不能全面描述、 甚至对有些问 题根本就无法描述， 不能满足一些实 际问 题的 模型化需求， 所以 要解决此类现实问 题必须重新设计新的领域描述语言。 1 9 9 6年 e . p e d n a u l t f 提出7动作描述语言一一a d l ( a c t i o n d e s c r i p t i o n l a n g u a g e ) 。 a d l 所描述的操作对s t r i p s 进行t 扩展，除7 具有s t r i p s 的表达能力 外， 还能表达条件效果、 盆化效果等语言特征。 条件效果是动作描述中与上下文相依 赖的效果， 一般用w h e n 子句来表示。 w h e n 子句由 两部分构成:前提和结论， 动作执 行后， 只有w h e n 子句的前提也同时满足， 才生成结论中的结果;量化效果是允许在 动作的效果描述中具有存在量词和全称童词。 a d l 的扩展使得规划语言所能描述的问 题更多，解决了很多以前无法求解的问顾2a型。 1 . 3 . 3规划领城定义语言p d d l 智能规划的研究逐渐地从理论研究走向 实际 应用， 将规划技术运用到实际问 题领 域就涉及到一个不可避免的问 题:如何对一个实际问 题领域进行模型化并进行推理. 1 9 9 8 年， d r e w m c d e r m o t t 提出t 规 划领域定 义语言p d d l . 6 p d d l是一种以动作为中心的语言，它的实质是表达使用前件和后件来描述动作 的可使用性和效果的动作的语法标准。 一个规划问题由一个域描述和一个问题描述组 成。 同一个问题域可以 许多不同的问 题描述一起组成同一问 题域的不同规划问 题。 动 作的前件和后件表达成由谓词、项和逻辑连接词组成的逻辑命题。 p d d l i . 2 是1 9 9 8 年第一届国际智能规划比 赛使用的规划语言， 它只是简单地给 出了如何定义规划问题的域及规划问 题的语法标准， 并没有给出规划的语义。 p d d l i . 2 包含了s t r i p s 表示和a d l ，即使用s t r i p s 表示和a d l 能够表达的问题，则p d d l i . 2 也能表达该问题。 m a r i a f o x 它去掉了 表达能力 p d d li a n d d e r e k l o n g 12 于2 0 0 2 年的第三届规划器比 赛中提出了p d d l 2 . 1 , . 2 中不常使用的部分， 增加了数值表达、 规划尺度和持续动作等新的 。p d d l 2 . 1 的表达能力可以分为5 个层次，第一层是p d d l 2 . 1 的s t r i p s 部 分;第二层是数值表达部分:第三层是离散的持续动作:第四 层是连续的持续动作; 第5 层是p d d l 2 . 1 的所有扩展及能够支持自 发事件和物理过程模型化的附加组件。 它 的表达能力超出了目 前规划器所能处理的表达能力，给规划研究者们提出了新的挑 战。 p d d l 2 . 1 与p d d l 前面的 版本兼容. p d d l + 是对p d d l 2 . 1 的 第5 层的 描述，它引入了 两个附加的模型化部件: 过程 和事件。过程和事件的引入意味着那些用于持续动作来模型化的领域特点在 l e v e l 5 可以 使用由 起始点、 过程和结束点三部分组成的结构来进行模型化， 在起始点和结束 点可以运用动作或事件，也可以是活跃过程的效果导致一个数值到达关键闽值的点， 这称为s t a r t - p r o c e s s - s t o p 模型. 在p d d l + 的第5 层，动作具有瞬时的 效果， 它将 改变问题域中的逻辑状态， 动作可以 开始一个过程; 而一个过程在随着时间修改状态 的数值部分时 将保持一个状态的逻辑部分。 动作与过程的区别:动作导致状态转移， 而过程则不会导致状态转移; 动作与事件的区别: 问题域设计者在把它们标识为事件 来阻止规划器在提取一个规划时选择它们: 过程和事件的区别: 事件的数值后件中不 能有与时间相关的效果， 而过程的数值后件通常是与时间相关的效果。 一个过程可以 由一个动作或由出现在世界中的某一事件来结束。 p d d l 2 . 沙，保留 了p d d l 2 . 1 的 前 三 层 的 表 达 能 力， 新 增了 导 出 谓 词 和 初 始 化 时 间 命题两种表达能力。 1 . 4 规划的复杂度 虽然人们对规划问题的 研究已经五十多年了， 到目 前也已 经提出了各种各样的解 决方案， 但是由于规划问题是一个非常难解决的问题， 所以现在能够解决的规划问题 仍然是很有限的， 关于现实世界中的一些大而复杂的规划问题仍然没有能够很好地解 决，下面我们来看一看前人对于规划问题从理论上分析其计算复杂性的一些结论: 1 9 8 5 年j o h n c a n n y 证明了 形式化的s t r i p s 规划问 题是一个p s p a c e 完全问题;24 1 g u p t a a n d n a u于1 9 9 1 年证明:不论采取什么样的形式化系统， 积木世界问 题 总是n p 难题 ( n p - h a r d )【， ， . 领域相关的规划问 题至少是 n p完全的( c h e n o w e t h 1 9 9 1 6 ; g u p t a a n d n a u 1 9 9 2 t ， )。 领域无关的规划问 题是 p s p a c e完全问 题或更难( c h a p m a n 1 9 8 7 6 ; b y l a n d e r 1 9 9 1 1,11 )。 b e r n h a r d n e b e l 于1 9 9 4 年证明了 规 划问 题是n p 难题 ，. ， 。 s e l m a n 于1 9 9 4 年 进一 步 指出 : 类 似于 规 划的 问 题 是n p 完 全的 或 更 难的 ;19 ; 现在所能解决的规划问题还有很大的局限性， 也正因如此， 规划问 题的研究才具 有很大的挑战性，使得一些人工智能方面的研究者乐此不疲。 1 . 5 规划研究项目 和有关的会议情况 与规划相关的主要项目 ( 计划)情况: 1 )美国国 防 部高 级 研究 计划局d a r p a ( d e f e n s e a d v a n c e d r e s e a r c h p r o j e c t s a g e n c y ) 和r o m e 实验室的d a r p a - r o m e p l a n n i n g i n i t i a t i v e c a p r i ) 计划2 b ) 在1 9 9 1 年2 月该计划正式启动，主要针对军事中空军规划问 题进行研究， 现在 己 进行到第六阶段， 目 前为止总投资 额己 经超过7 千万美元， 同时该项计划也产生了 巨 大的社会经济效益， 据1 9 9 4 年美国政府的一份商业报告称: 仅后勤支援计划d a r t ( a r p i的一部分)这一子项目 在沙漠风暴行动中的应用价值就足以抵上政府在 a i / k b s 研究中过去3 0 年所投资的总额ca l 。 美国一流的科研机构和著名的公司都参加 了该计划，主要有:布朗大学 、卡乃基一 梅隆大学 、i s x公司 、k e s t r e l 学院 、 西北大学、洛氏国际 ( r o c k w e l l ) , s r i 国际 、斯坦福大学、夏威夷大学、马里兰大 学、俄勒冈大学和华盛顿大学等。 2 )欧洲p l a n e t 计划 ， 此项计划开始于 1 9 9 8 年 1 0月 1 号，是由e s p r i t 基金资助的，目 前已 经有 1 4 个国家共5 8 个高校、科研所和企业参加了 这一计划，在欧洲这是一个非常庞大的计 划， 投入了巨大的人力、 物力和财力，目 前参加的国家包括:比利时、塞浦路斯、 法 国、德国、希腊、 匈牙利、 意大利、 荷兰、 挪威、 葡萄牙、西班牙、瑞典、瑞士和大 不列颠联合王国。 这些国家著名的高等学府、科研机构大都参加了这一计划。 3 )美国国家航空和宇宙航行局也投入了大量的人力、物力，开展关于规划理论 及其应用的 研究，并且将之应用子宇宙飞 船等航空器上圈。 4 )英国的国家航空和宇宙航行局也赞助了e u m e t s a t 项目 4 3 这些项目 有力地推动了规划理论和应用的研究， 世界上关于智能规划的专题会议 等活动也渐渐地增多起来，目 前比 较重要的会议有:两年一届的a 工 p s 会议、 e c p 欧 洲规划会议、 美国国家航空和宇宙航行局举办的n a s a p s , i j c a i 中也有专门 针对规划 问题的专题讨论等等。 第二章规划图与人工智能规划 2 . 1 图规划 ( g r a p h p l a n )方法 1 9 9 5 年b l u m 和f u r s t t 3 提出 了 一种 基于规 划图 的 快速规划方 法一- 一 图 规 划， 其 代表有美国 卡乃基一 梅隆大学( c a r n e g i e m e l l o n u n i v e r s i t y ) 的图 规划器g r a p h p l a n ( b l u m和 f u r s t ) .德国的 i p p 、英国的 s t a n、美国盛顿大学 ( u n i v e r s i t y o f w a s h i n g t o n )的s g p ( d a n i e l s . w e l d 等) 。 先来介绍几个概念: 有 效( v a l i d 之 规 划 解: 规 划问 题的 一 个 有 效 规 划 解 是 一 个动 作的 集 合 和 对 每 一 个动作发生时间的指定。 规划图 ( p l a n n i n g g r a p h ) :是一个具有两类节点和三类边的有向、 分层图。 规 划图各层是命题层 ( p r o p o s i t i o n l e v e l s ) 和动作层( a c t i o n l e v e l s ) 交替出现的， 命题层包含命题节点( 标识为一些命题) ， 动作层包含动作节点 ( 标识为动作) 。 三类 边是前提条件边( p r e c o n d i t i o n e d g e ) ， 添加效果边( a d d e d g e ) 和删除效果边( d e l e t e e d g e ) .规划图的第一层是命题层， 包括规划问 题初始条件下的所有命题。 图 规划在两个阶段( p h a s e s ) 交替进行:图 扩展 ( g r a p h e x p a n s i o n )阶段和解提 取( s o l u t i o n e x t r a c t i o n ) 阶段。图 扩展阶段正向 扩展规划图直到目 标状态的所有命 题都出 现为止。 解提取阶段反向 搜索规划图以 求出 规划解。 如图2 -1 所示:黑圆点 代表命题节点，空白方框代表动作节点。 ， 二 沪 . 卜 一 、，- 二 、朴 图 2 - 1 这里以s t r 工 p s 规划问 题型 ( 动作的前件和后件都是确定的文字的合取) 为例， 结合图例大致介绍这一方法，为了 简化规划图的规模， b l u m和 f u r s t 定义了规划图 中节点的两元互斥关系，如图2 -2 所示: 第i 层两个动作实例 ( a c t i o n i n s t a n c e ) 满足以 下三者中的任意一个时，我们 称之为具有互斥关系: 后件 ( 效果)不一致 ( i n c o n s i s t e n t ) :一个动作的后件是另一个动作后件的否 定。 冲突( i n t e r f e r e n c e ) :一个动作删除另一个动作的前件。 竞争所需 ( c o m p e t i n g n e e d s ) : 两个动作具有i - 1 层互斥关系的前 件。 第i 层的两个命题 ( p r o p o s i t i o n s ) 具有互斥关系，当: 一个命题是另一个的否定或: 不一致支持 ( i n c o n s i s t e n t s u p p o r t ) : 获得此命题的所有动作 ( 方法) 都具有 互斥关系。 显然上述关系不具备传递性。 i n c o n s i s t e n t r ff -t sc o m p e ti n g n e e d s i n c o n s i s t e n t s u p p o rt 图2 -2 考虑以 下问 题: 给睡眠中的爱人准备一个惊喜， 要求把垃圾 ( g a r b a g e ) 带出 去， 做好正餐( d i n n e r ) ， 准备好一份礼物( p r e s e n t ) 。 初始条件:( a n d ( g a r b a g e ) ( c l e a n h a n d s ) ( q u i e t ) ) 目标:( a n d ( d i n n e r ) ( p r e s e n t ) ( n o t ( g a r b a g e ) ) ) 前件 ( c l e a n h a n d s ) c a r r y 后件( d i n n e r ) 前件 后件 : 前件 ( q u i e t ) :后件( p r e s e n t ) d o l l y : 前件 :后件 ( ) ( a n d ( n o t ( g a r b a g e ) ) ( n o t ( c l e a n h a n d s ) ) ) ( ) ( a n d ( n o t ( g a r b a g e ) ) ( n o t ( q u i e t ) ) ) :lkd且 作 oa or l日诀cw 图2 -3 图2 -3 是上述问 题的部分规划图， 我们注意到:动作c a r r y 与保持g a r b a g e 的 动作具有互斥关系，因为他们的后件不一致;d o l l y 与w r a p由于冲突而具有互斥关 系: 在第二层即命题层，q u i e t 与p r e s e n t 具有互斥关系。由 于在第二层已 经获得了 所有的子目 标，并且它们之间没有互斥关系，因此下面可以 进入图 规划的 第二阶段: 即解提取阶段。 依次考虑目 标的各个子目 标， 对第i 层的每一个子目 标， 图规划选择 第i - 1 层的获得此子目 标的动作a ， 此处选择是一个回溯点: 如果存在多于一个的动 作能够获得此目 标， 那么图规划为了 保证其完整性必须考虑所有的动作， 如果一个动 作a 与其他的已 经选择的动作是一致( c o n s i s t e n t ) 的， 那么图规划就继续进行其他的 子目 标， 否则如果没有这样的选择存在， 图 规划就回溯到前一个选择。 当图 规划找到 所有的实 现第i 层目 标的动作后， 它再把选择的动作的前件作为目 标， 依次进行， 直 到第零层，即初始条件为止，否则返回第一阶段继续进行图扩展阶段。 在上面的 例子中， 在第二层有三个子目 标: ，g a r b a g e 可有动作c a r r y 或d o l l y d 12 g a r b q u 泌 t 来获得; d i n n e r 可有c o o k 来实现; p r e s e n t 可有w r a p 来包扎好。 因此图 规划至少必 须考虑两个动作的 集合: c a r r y , c o o k , w r a p 和! d o l l y , c o o k , w r a p ， 但是这两个集合 都不一致，因为。 a r r y 和c o o k , d o l l y 和w r a p 是互斥的，因此解提取失败，图 规划 扩展规划图到第四层如图2 -4 所示， 然后经过解提取阶段获得解规划如图2 -5 所示。 d 1 2 3 4 黝黔豁 g a r b c le a n h q u ie t 笠 沮 c a rr 一犷 河 d a l d i n n er p re s e n t 图 2 -4 工 ， 万 d d l 图2 -5 己 经证明图规划算法是多项式时间的。 2 . 2 规划图的互斥延迟算法 我们利用相互独立集改进了建立规划图的算法， 改进的基本思想是: 在建立完一 动作列后， 查看该动作列中是否存在互斥关系， 并将没有互斥关系的动作归入一个集 合中 ( 称这样的一个集合叫相互独立集，即集合内的每个动作间没有相互排斥关系) 如果该动作列的相互独立集个数大于1 ， 则说明独立集间的动作有相互排斥关系。 为 了将这一组不可能在同一时间步内执行的动作拆分成多个时间步内完成. 我们引入了 延续时间步。 延续时间步的主要作用是延续动作的执行效果 ( 包括添加效果和删除效 果) ，因为相互独立集间动作不能在同一时间步同时执行，所以必须延续几个时间步 以便将多个独立集拆分开. 我们把非延续时间步称为扩张时间步， 为了区分这两种时 间步， 我们可以利用一个动态一维数组， 每添加一个时间步就增加一个元素， 扩张时 间步用 “ 1 ” 表示，延续时间步用 “ 0 ” 表示。 这样， 通过相互独立集的个数n ，我们 可以知道有几组动作相互排斥， 那么通过使用n o p 动作， 将接下来的命题列延续n - 1 个时间步，在延续时间步内不考虑可能新增加的动作( 即形成动作的前提在上一命题 列中 存在，且该动作在上一动作列中不存在) ，这样做的目的仅是为了将所有相互排 斥的动作组分开，放