（计算机软件与理论专业论文）可能性规划问题表示与求解研究.pdf

摘要 早期智能规划研究一直集中在经典规划领域，它假设动作是确定的、初始条 件是已知的、目标被定义为一些命题的集合。但很多实际问题并不满足这样的条 件，因此，一些学者开始尝试不确定规划的研究，其中绝大部分集中于概率规划 研究。然而，动作效果的概率在实际中很难获得，尤其是人工智能研究中的不确 定性通常是顺序的、定性的。一些研究认为，可能性理论更适用解决那些概率模 型无法解决或者概率信息很难获得的问题。 本文利用可能性理论提出了一种基于p d d l ( p l a n n i n gd o m a i nd e n n i t i o n l a n g u a g e ) 的可能性规划问题表示方法p o s s p d d l ，给出了基于可能性理论 框架下的定性决策理论和图规划算法的可能性规划求解方法可能性图规划， 设计并开发了可能性规划问题求解器p o s s g r a p h p l a n 。p d d l 是国际规划器大赛的 标准域定义语言，这使得p o s s p d d l 更具通用性和标准性。由于用可能性理论表 示动作效果和状态的不确定性更具优势，因此p o s s g r a p h p l a n 更适用于解决那些 概率模型无法解决或者很难获得概率信息的不确定规划问题。我们证明了应用可 能性图规划方法求解可能性规划问题得到的规划解是最优的。同时，我们用c 语 言在w i n d o w s 系统下实现了可能性图规划器，实验结果表明，可能性图规划方法 在问题求解能力和速度上的表现都较为突出。 关键词：可能性理论；可能性规划；定性效用理论；p d d l ；图规划 a b s t r a c t p l a n n i n gr e s e a r c hh a v eb e e nc e n t r a l i z i n gi nc l a s s i c a lp l a n n i n gp r o b l e m sb a s e d o nt 1 1 ea s s u m p t i o n st h a ta c t i o n sa r ed e t e t m i n i s t i c ，t h ei n i t i a is t a t ei s k n o 、na n dt h e g o a ii sd e 6 n e db yas e to ff i n a ls t a t e sf o re a r l i e ry e a r s h o w e v e r ，m o s tp r a c t i c a l p r o b l e m sd on o ts a t i s 矽t h e s ec o n d i t i o n so fc o m p l e t ea n dd e t e r m i n i s t i ci n f o m a t i o n 。i h e r e f o r e ，m a n yr e s e a r c h e r sh a v eb e e nt a k i n gu pw i t ht h es t u d yo fu n c e r t a i n t ! i ， p l a n n i n g m o s tr e s e a r c ho ni ta r ec e n t r a l i s e di np r o b a b i l i s t i cp i a n n i n gb a s e do nm d p m o d e l sa n dd y n a m i cp r o g r a m m i n go rs t a t e s p a c es e a r c hm e t h o d s b u tt r a n s i t i o n p r o b a b i l i t i e sf o rt h er e p r e s e n t a t i o no ft h ee f f e c t so fa c t i o n sa r en o ta v a i l a b l ee a s i l v e s p e c i a j j yj na ia p p 】j c a j o n sw h e r eu n c e n a j n 钞i so f 如no r d j n a l ，q u a j i t a t i v e 。af e w r e s e a r c h e r sh a v ea d v a n c e dt h eq u a l i t a t i v ev i e wo fd e c i s i o nm a k i n ga n dq u a l i t a t i v e v e r s i o n so fd e c i s i o nt h e o 叮a n dy e ts o m er e s e a r c h e r st h i n kp o s s i b i “t yt h a t t h e u n c e r | 组i n t yo ns 拓吐e sa n de f 诧c t so fa c t i o n si i e p r e s e n t e db yp o s s i b i l i t yd i s t r i b u t i o n si s m o 陀a d e q u a t et oc a s e si nw h i c hp r o b l e m sc a nn o tb er e s o i v e db yp r o b a b i i i t ym o d e l o rt h ep r o b a b i ji t i e sa r en o ta v a i l a b l e ，n o tr e h a b l e ，o r h a r dt 0o b t a i n w ei n t r o d u c eap o s s i b i i i s t i cp i a n n i n gp r e s e n t a t i o na p p r o a c hb a s e do np d d l ( p l a n n i n gd o m a i nd e f i n i t i o nl a n g u a g e ) n a m e dp o s s p d d l ，a n dp r o v j d ea n a l g o r i t h mi - e s o l v i n gp o s s i b i l i s t i cp i a n n i n gp r o b l e m sr e p r e s e n t e db yp o s s p d d l b a s e do ng r a p h p l a na n dq u a l i t a t i v eu t i l i t y t h e o 叫i nt h ef r a m e w o r ko fp o t h e o 眄， w h e r eb o t hp r e f b r e n c e sa n du n c e r t a i n t ya r eq u a l i t a t i v e w ea i s od e s i g na n d d e v e l o p p o s s i b i l i s t i cp l a n n i n gp r o b i e ms o l v e 卜p o s s g r a p h p l a n p o s s p d d li sm o r e u n i v e r s a la n dn o n n a lf o rp d d lh a sb e e nt h ec r i t e r i a p l a nd o m a i nd e f i n i t i o n i a n g u a g e a st h eu n c e r c a i n t ) ， o ns t a t e sa n de f f e c t so fa c t i o n sr e p r e s e n t e db y p o s s i b i i i t yd i s t r i b u t i o n si sw e l i - s u i t a b l ef o rc a s e si nw h i c ht h ep r o b a b j l i t i e sa r en o t a v a i l a b i e ，n o tr e i i a b l e ，o rh a r dt oo b t a i n ，o u ra p p r o a c hi sm o r ef i tf o rs o l v i n g u n c e n 面np l a n n i n gp r o b l e m s t h ee x p e r i m e n t ss h o wt h a t0 u ra l g o r i t h mh a se x c e l l e n t p e r f 0 肋a n c ej nt e 册so f s o j v j n ga b j j i t ya n de 炳c j e n c y 。 k e yw o r d s ：p o s s i b i l i s t i ct h e o 叫；p o s s i b i l i s t i cp l a n n i n g ；q u a l i t a t v i eu t i l i t y t h e o 叮； p l a n n i n gd o m a i nd e n n i t i o nl a n g u a g e ；g r a p h p i a n i i 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：之坠暑是 日期：守叼6 ，丛 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名夕耋2 主近 日 期：递& ：61 够 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 东北师范大学硕士学位论文 引言 早期智能规划研究一直集中在经典规划领域，它通常假设问题的动作是确定 的、初始条件是已知的、目标被定义为一些命题的集合。事实上，很多实际问题 并不满足这样的条件，因此，一些学者开始尝试不确定规划的研究，其中以概率 规划研究为主。目前大多数的概率规划研究都采用基于马尔可夫决策过程 ( m d p ) 、动态规划( d p ) 和状态空间搜索的方法n 叫。2 0 0 4 年，第四届国际规划器 大赛( i p c 4 ) 把p p d d l1 0 ( p r o b a b i l i s t i cp l a n n i n gd o m a i nd e f j n i t i o nl a n g u a g e ) 作 为概率规划的标准域定义语言，它促使了概率规划研究的爆炸式增长，概率规划 研究也因此取得了很大的进展哺叫制。 然而，动作效果的概率在实际中很难获得，尤其是人丁智能研究中的不确 定性通常是顺序的、定性的。因此b o u t i l i e r 等人提出了定性决策理论的概念，给 出了它的表示逻辑以及求解方法n5 蚓。目前有多种定性决策模型，它们中大部分 依赖顺序估价，还有一些基于公理化的通用定性概率。由于定性信息的存在， 一些模型为模型化偏好而特别设计，最著名的就是w a l d 的极大极小规则u 毛忸1 9 1 。 然而另外一些研究则认为，可能性理论更适用解决那些概率模型无法解决或者概 率信息很难获得的问题乜蚴1 。1 9 9 5 年，d u b o i s 和p r a d e 提出了基于可能性理论的 期望效用理论，在这个被称为定性效用理论的框架内，偏好和不确定性都是定性 的。他们建立了一个定性效用函数来表示可能性分布之间的偏好顺序，这些可 能性分布本身则满足一系列决策者的公理。这种定性决策理论的优势在于可能性 理论的核心是定性的，它只有极大( m a x ) 、极小( m i n ) 和反序( o r d e r - r e v e r s i n g ) 三 种操作。1 9 9 8 年，s a b b a d i n 等人将d u b o i s 和p r a d e 的理论扩展到多步决策并从乐 观和悲观两个角度给出了基于可能性理论的贝尔曼方程堙引。随后，s a b b a d i n 定义 了可能性马尔可夫决策过程框架，并将其扩展到无限h o r i z o n 和部分观察领域， 证明了定性的可能性效用可以调整定性标准和效果之间的平衡并证明了其是期 望效用的一利一特殊类型，同时，d u b o i s 等人也放松了效用值与不确定性之间可统 一衡量的假设乜“2 2 荆7 1 。 1 9 9 7 年，p e r e i r a 等人提出了可能性规划思想，给出了基于可能性理论的知识 表示和求解方法，该方法采用类s t 砌p s 表示和b u r i d a n 方法昭卫引。不论是从知 识表示的角度还是从规划方法的角度而言，该方法的性能都与现在的不确定规划 研究方法相差甚远。而此后，可能性规划的研究一直未取得任何的进展，其中一 个很大的原因是至今仍没有一个统一的、标准的可能性规划问题表示方法。 本文提出了一种基于p d d l 的可能性规划问题表示方法p o s s p d d l ，给 出了基于可能性理论框架下的定性决策理论和图规划算法的可能性规划求解方 东北师范大学硕士学位论文 法，同时，设计并开发了基于可能性图规划方法的规划器p o s s g r a p h p i a n 。p d d l 目前已成为国际规划器大赛的标准域定义语言，这使得p o s s p d d l 更具通用性和 标准性。图规划是现代规划研究方法中最让人兴奋和活跃的方法之一，该方法一 经提出就赢得了规划领域广泛的关注，目前已被扩展到各个规划领域乜f 艄副。我们 证明了基于图规划算法的可能性规划问题求解方法能够找到可能性规划问题的最 优解。实验结果也表明，p o s s g r a p h p l a n 在求解问题能力和速度 ：的表现都较为 突出。 本文的主要工作如下： ( 1 ) 提出了一种基于p d d l 的可能性规划问题表示方法_ p o s s p d d l 。根 据可能性理论，我们从语法和语义两个方面阐述了基于p d d l 的可能性规划问题 表示方法。p d d l 目前己成为国际规划器大赛的标准域定义语言，这使p o s s p d d l 更具通用性和标准性。 ( 2 ) 提出了基于可能性理论框架下的定性决策理论和图规划算法的可能性规 划求解方法可能性图规划。图规划方法在经典智能规划研究中具有重要的意 义，几乎所有的现代规划系统都或多或少地借鉴了图规划的方法。根据可能性理 论框架下的定性决策标准，我们将它扩展到了可能性规划领域以解决可能性规划 问题。 ( 3 ) 用c 语言在w i n d o w s 系统下实现了基于可能性图规划方法的可能性图规 划器p o s s g r a p h p l 粕。p o s s g r a p h p l 锄能够解决可能性规划问题，同时它也能够求 解确定性规划问题，只需对问题的参数进行简单地调整即可。 本文的主要结构如下： ( 1 ) 第一章智能规划 第一章主要介绍智能规划的研究现状、相关概念、发展历程、主要应用以及 知识表示等。 ( 2 ) 第二章基于可能性理论的定性决策理论 第二章主要介绍可能性理论的基本概念及基于可能性理论的定性决策标准。 ( 3 ) 第三章可能性规划问题表示 第三章提出了基于p d d l 的可能性规划问题表示方法p o s s p d d l ，根据 可能性理论，我们从语法和语义两个方面阐述了基于p d d l 的可能性规划问题表 示方法，它扩展了p d d l 表示来处理可能性规划的模型化问题。 ( 4 ) 第四章可能性规划问题求解 第四章给出了基于可能性理论框架下的定性决策理论和图规划算法的可能性 规划求解方法可能性图规划。根据可能性图规划求解规划问题的两个阶段， 我们给出了可以处理用p o s s p d d l 表示的不确定规划问题的算法，包括可能性规 划图扩展算法和可能性规划提取算法，同时，我们分析了可能性图规划方法求解 东北师范大学硕士学位论文 可能性规划问题时存在的搜索空间过大问题并据此给出了几种启发式，最后给出 了最优规划解定理及证明。 ( 5 ) 第五章规划器设计与实验结果分析 第五章主要介绍可能性图规划器p o s s g r a p h p l a n 的功能设计、实验结果以及 对实验结果的分析等。 3 东北师范大学硕士学位论文 第一章智能规划 智能规划( i n t e l l i g e n tp l a n n i n g ) 是一门涵盖知识表示、自动推理、非单调逻 辑、人机交互和认知科学等方面的多领域交叉性学科，是人工智能的重要研究领 域之一。智能规划问题是指“给定初始状态和目标条件，a g e n t 自动寻找一条从初 始状态出发满足目标条件的动作序列”。近年来，智能规划被广泛地应用于航空航 天、机器人控制、后勤调度、游戏角色设计和系统建模等领域中，带来了诸多成 果，例如海湾战争中的美军配备的动态分析和重规划工具d a i 玎，它使过去需要 几个星期才能完成的调度工作可以在几个小时内完成，为此美国国防部高级研究 计划局( d a a ) 称：“仅智能规划的这一项应用成果就足以补偿d a ) a 在人 工智能研究方面的近3 0 年的投资”。 近年来，智能规划研究受到了学者们的广泛关注。美国一流的科研机构如布 朗大学、卡耐基梅隆大学、斯坦福大学、华盛顿大学和著名的公司如i s x 公司等 都参加了美国国防部高级研究计划局d a p r a 和r o m e 实验室的a r p i 计划；美 国国家航空和宇宙航行局也开展了关于规划理论的研究，并且将之应用于宇宙飞 船等航空器上；欧洲也已经有1 4 个国家共5 8 个著名的高等学府、科研机构和企 业参加了欧洲p l a n e t 计划；英国的国家航空和宇宙航空局共同赞助了 e u m e t s a t 项目。这些科研机构和项目有力地推动了智能规划理论和应用的研 究。目前，在各种研究机构中，卡耐基梅隆大学、华盛顿大学、普度人学、斯坦 福大学、澳大利亚国立大学和美国国防部高级研究计划局等研究机构所做的工作 引领着智能规划最新的发展方向。 2 0 0 3 年，之前每两年举办一次的欧洲规划会议( e c p ) 和人工智能规划会议 ( a i p s ) 被合并为国际人工智能规划与调度会议( i n t e m a t i o n a lc o n f e r e n c eo na i p l a n n i n ga n ds c h e d u l i n g ，i c a p s ) ，该会议已经成为智能规划领域最权威的国际会 议之一。i c a p s 从1 9 9 8 年起每两年举办一次国际规划大赛( i n t e m a t i o n a lp l a n n i n g c o m p e t i t i o n ，i p c ) ，用于促进规划器系统的设计和研究，迄今已经举办了六届。 在近几年的人工智能国际联合会议( i n t e m a t i o n a lj o i n tc o n f e r e n c eo na n i f l c i a l i n t e i l i g e n c e ，i j c a i ) 、欧洲人工智能会议( n a t i o n a lc 0 n f e r e n c eo na r t i f i c i a l i n t e l l i g e n c e ，丸a i ) 、知识表示与推理国际会议( i n t e m a t i o n a lc o n f e r e n c eo nt h e p r i n c i p l e so fl o o w l e d g er e p r e s e n t a t i o na n dr e a s o n i n g ，l r ) 、不确定人工智能会议 ( c o n f e r e n c eo nu n c e n a i n 妙i na r t i f i c i a l i n t e l l i g e n c e ，u a i ) 等最权威的国际人工智 能学术会议上，智能规划都被作为一个重要讨论课题。同时，人工智能方而最重 要的刊物人工智能刊期( j o u m a lo f a r t i f i c i a l i n t e l i i g e n c e ，j a i ) 分别在1 9 9 5 年、 东北师范大学硕士学位论文 2 0 0 3 年、2 0 0 8 年三次用专刊的形式发表智能规划相关的研究成果。人工智能研究 期刊( j o u m a lo fa r t i f i c i a l i n t e l l i g e n c er e s e a r c h ，j a i r ) 、人工智能杂志( a r t i f i c i a l i n t e l l i g e n c em a g a z i n e ，a im a g a z i n e ) 也多次以专刊的形式发表智能规划竞赛中的 优秀论文。此外，人工智能通信( a r t i f i c i a li n t e l i i g e n c ec o m m u n i c a t i o n s ) 、理论计 算机科学( t h e o r e t i c a lc o m p u t e rs c i e n c e ) 等在国际上占有重要地位的计算机期刊 都刊载智能规划的理论研究及应用成果。 本章主要介绍智能规划的相关概念、发展历程、主要应用以及知识表示等内 容。 1 1 智能规划基本概念 智能规划研究最早出现在2 0 世纪6 0 年代，是人工智能较早的一个研究领域 之一，本节将介绍什么是智能规划及其相关的基本概念。 在清楚什么是智能规划之前，我们首先要清楚规划要解决什么样的问题。 通常规划问题的一种形式化方法( 即定义三个输入) 是： ( 1 ) 用某种形式语言描述的初始世界状态； ( 2 ) 用某种形式语言描述的a g e n t 目标； ( 3 ) 用某种形式语言描述的a g e n t 可能采用的动作，通常也叫域理论。 从上述定义可以看出，智能规划的任务实际上就是给定a g e n t 的初始状态、 目标状态以及可执行动作，找到一组动作，使a g e n t 在初始状态下以某种特定的 顺序执行这些动作a g e n t 就可以实现它的目标。以火箭运输为例，规划问题有三 个操作对象，分别是货物a 、货物b 和火箭r ，a g e n t 可执行动作有三个，分别是 将货物用火箭从此地运到彼地( m o v e ) 、装载货物( 1 0 a d ) 以及卸载货物( u n l o a d ) ， 规划问题的初始状态是货物a 和货物b 均在l o n d o n ，目标状态是货物a 和货物 b 均在p a r i s ，智能规划要做的就是在给定条件下寻找一个动作序列，使得a g e n t 在初始状态下执行这个动作序列能够到达目标状态。 一般地，如果a g n e t 在初始状态下执行一个动作序列，最后到达目标状态， 我们就称这个动作序列为规划，也称其为相应规划问题的一个规划解。智能规划 的目的就是找到这样能完成任务或实现目标的动作序列。换言之，智能规划就是 设计这个动作序列的过程，它强调问题该如何解决，而不关心为什么这样解决。 我们称一个可以给出满足规划问题要求的动作序列的应用软件为规划器。规划器 可以看成是一个问题求解系统，给定初始状态、目标状态及相关操作等信息，它 就可以给出满足上述定义的一个动作序列，即得到一个满足问题要求的规划。规 划器的输出是一系列动作，在任何域中从某个满足初始条件的状态开始执行这些 动作都能到达目标状态。 早期的规划研究对规划问题一般会做如下假设： 东北师范大学硕士学位论文 ( 1 ) 状态的改变完全由a g e n t 的动作效果实现； ( 2 ) a g e n t 的动作的效果是完全确定的； ( 3 ) a g e n t 能够感知环境和动作的效果。 我们把满足以上假设的规划问题称之为“经典规划”们问题，如地图着色问 题、积木世界问题等。事实上，这些假设是很绝对的，很多实际问题往往并不能 满足上述条件，因此一些学者正在致力于放松这些假设，研究环境动态变化f 的 规划问题。相应地，我们把不满足上述假设的规划问题称为“非经典规划”问题。 经典规划理论对规划问题做了一些假设，比如原子执行时间、确定的动作结 果、无外因事件等。实际上，这是一个抽象的形式化表示，它用表示域、目标、 行为的特定语言把一类规划问题参数化。一般来说，众多可表示域、目标和可能 动作的语言都有一定的表示范围，本文将在后续的章节中介绍这些语言。 1 2 智能规划的发展 智能规划研究始于2 0 世纪6 0 年代，是人工智能较早的一个研究领域之一， 起源于状态空间搜索、定理证明和控制理论的研究以及机器人技术、调度技术和 其他领域的实际需要，它的本质是利用程序来模拟人类解决问题的能力。 早期求解规划问题的方法就是将规划问题转化成搜索问题。第一个具有智能 意义的系统就是n e w e l l 、s h a w 和s i m o n 设计的逻辑理论家( l o g i ct 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 系统。 大多数的智能规划研究人员认为q a 3 才是真正意义上的第一个规划器，原因在于 它是第一个面向实际规划问题设计的规划系统。 1 9 7 1 年f i k e s 和n i l s s o n 设计并开发了s t r i p s 系统，它被认为是第一个主流 的规划器系统。作为s 刚的s h a k e y 机器人项目的规划模块，s t r i p s 系统的出现 在智能规划的研究中具有划时代的意义和价值。它的突出成绩是引入了s t r i p s 表示，使得原来很神秘的规划问题求解变得明朗清晰起来，它也开启了规划问题 描述形式化和趋于标准化的先河，之后的问题表示都是在s t r i p s 表示的基础上 进行扩展得来的。 问题描述上的发展也推动了规划研究的快速发展。1 9 7 7 年先后出现了 h a c k e r 、w a r p l a n 、n n t e r p l a n 、a b s t r j p s 、n o a h 、n o n l i n 等规划系 统。在这近十年里，智能规划研究成为人工智能研究的新热点，在此期间，学者 们普遍认为规划问题必须用定理证明的理论来解决，直到c h a p m a n 设计的规划系 6 东北师范大学硕士学位论文 统t w e a k 的出现。c h a p m a n 的分析使研究者认识到简单地利用定理证明的方法 来求解规划问题实际上是很困难的。同时，早期的规划系统多是在全序动作序列 上工作的，这种线性方法很快被a l l e nb r o w n 等人在h a c k 系统实验中证明是不 完备的，有时候甚至无法解决一些简单的问题，如s u s s m a n 不规则问题。此后到 1 9 9 0 年，在新的规划求解方法出现之前，智能规划的研究陷入低谷，这期间仅有 s i p e 、a b l w e a k 和p r o d i g y 阱1 等较少的智能规划器出现。 1 9 9 1 年s o d e r l a n d 和w | e l d 等人设计了世界上第一个完备的、系统的非线性规 划器s n l p 3 副，奠定了现代非线性规划系统的基础，偏序规划方法也随之统治了 多年的智能规划研究。1 9 9 2 年，p e n b e n h y 和w b l d 扩展了s t 砌p s 表示，同时基 于最小承诺的思想研究并设计了u c p o p 规划器m ，3 7 1 ，它在当时的经典规划领域中 的表现非常优异。 然而，即使是当时性能最好的偏序规划器u c p o p 也很难找到包含超过十几 步左右的规划。1 9 9 2 年k a u 亿等人将规划问题转化为约束可满足( s a t ) 问题m 来求解，开辟了求解规划问题的新途径。他们一反定理证明式的求解方法，利用 在约束可满足问题算法上的突破，有效地解决了很多规划问题。 1 9 9 5 年，b l u m 和f u r s t 等设计的g r a p h p l a n 系统使得智能规划研究领域又获 得了新的突破，该方法使用一个名为规划图的紧凑结构来表示状态空间，通过构 造和分析规划图的方式来求解规划问题。图规划思想的出现掀起了现代智能规划 系统研究的一个高潮，此后很多规划系统都或多或少地借鉴了图规划的方法。1 9 9 9 年，b l u m 和l a n g f i o r d 在图规划的框架下研究并设计了概论规划器啦! 。2 0 0 0 年， k a m b h a m p a t i 将规划图转化为对应的c s p ，并在图规划求解规划过程中应用c s p 的搜索技术以提高求解效率阳训。在这一阶段，规划研究中以图规划方法和基于s a t 的求解方法最为显著啪1 。基于s a t 和规划图的规划器b l a c k b o x h 们在第一届智能规 划器的比赛中表现出了突出的问题求解能力，夺得了那一届规划器大赛的冠军。 相对于早期的偏序规划系统，现代规划系统无论在求解速度还是在求解规模上均 有了几个数量级的提高。 1 9 9 8 年6 月在卡耐基一梅隆大学举行了第二届国际规划器大赛( i n t e m a t i o n a l p l a n n i n gc o m p e t i t i o n ，i p c ) 。规划器大赛统一了规划领域内一些标准问题的描述， 同时它也建立了问题域的标准描述方法，使得各种规划系统之间具有了可比性。 大赛每两年举行一次，它展示了规划研究的最新进展情况。如今已举行了五届国 际规划器大赛，每届都会有比较优秀的规划器出现，如h s p 、f f 、g r t 、a l t a l t 、 m e t r i c f f 、f a s td o w n w a r d s 、s g p l a n 、m a x p l a n 等h h 引。规划器大赛的举行极大地 推动了规划研究的发展，同时问题描述语言表达能力的刁i 断丰富给规划的发展指 明了方向也提出了更大的挑战。现在已有多种规划求解方法，它们各具特点和优 势，并且分别都得到了许多研究者的认可，目前规划方法的发展趋向于多种求解 方法的融合。 随着方法的改进和技术的成熟，规划器求解规划问题的能力和质量也相应提 东北师范大学硕士学位论文 高，研究者也从最初追求求解速度转而寻求提高规划器处理问题的能力和质量的 方法舯5 1 ，因此，智能规划研究的另一个发展趋势即研究非经典规划的知识表示 和求解方法。 1 3 智能规划的应用 从规划被当作一个研究问题提出到现在，已有四十多年。在这四十多年里， 规划研究经历了从简单到复杂、从理论到应用、从确定领域到不确定领域、从单 a g e n t 规划到多a g e n t 规划等过程。智能规划的研究对象和研究方法的成熟与发展， 使得它的应用逐渐走出实验室，它在自动化系统中的应用使得自动化系统的灵活 性、健壮性和适应性都得到了显著提高。目前智能规划主要应用在航空航天、机 器人、智能企业、商业软件、后勤调度、游戏角色设计和系统建模等领域，这里 我们只简单介绍其中的一部分应用。 1 3 1 航空航天领域中的应用 智能规划的一个重要的应用领域就是航天航空，其中取得最好成绩的是美国 宇航局的a s p d 、i ( a u t o m a t e ds c h e d u l i n ga n dp l a n n i n ge n v i r o n m e n t ) 规划系统矧。 a s p e n 获得了1 9 9 9 年美国宇航局软件比赛的优秀奖，并且被广泛应用在需要完 成外太空任务的宇航器上。 1 3 2 机器人领域中的应用 与其它规划研究领域的不同，机器人领域的规划研究主要集中在有噪音的环 境模型中。通常情况下，机器人通过感应器和交流信道得到的信息都存在噪音， 因此它需要将感应和执行整合起来进行规划。 目前主要研究包括： ( 1 ) 路径规划：研究机器人如何从初始位置走到目标位置且满足问题动态约 束的控制机制； ( 2 ) 感知规划：研究有关如何采集外部和内部信息的规划，例如，观察环境、 辨别物体以确定机器人位置等： ( 3 ) 任务规划：任务规划与传统的规划问题相似，但它更注重时间和资源的 分配以及在动态的、不确定的或仅有部分状态知识已知的环境下进行规 划； ( 4 ) 规划交流：研究多个机器人之问和人与机器人之问如何进行信息交换， 包括询问信息和反馈信息两大部分。 东北师范大学硕士学位论文 1 3 3 智能工厂中的应用 智能规划在智能化工厂中的应用啼 是指从生产设计到监测生产的一系列过 程，它不仅涉及单个企业，还可以处理多个企业之间的关系，例如供应链和虚拟 企业等。 例如在加工厂作业调度规划问题中，需要考虑如何在资源( 车床，刨床，钻床 等) 有限的情况下根据已知工件的加工顺序要求对整个车间的生产做出安排，使得 加工完所有工件所需的时间尽可能的少、每台机床的等待时间尽可能的短，即使 得工厂在同样资源条件下，因作业调度规划合理而增加生产能力，从而增加相应 的经济效益。 目前智能规划在智能工厂中的应用研究主要包括： ( 1 ) 生产流程规划：研究如何将一个生产要求转变为一组详细的操作指令。 很多基于知识工程的软件在这方面均取得了较好的成效，它们先将现实 生产流程转化为知识库中的信息，然后再根据相应的生产要求来转化具 体的操作； ( 2 ) 生产规划和调度：研究安排生产以满足客户的需求，即通常说的e i 冲作 业调度。 1 3 4 商业中的应用 智能规划在商业中的应用较为广泛。在商业规划中，问题的目标状态可以仅是 满足某个条件，而不是明确的命题。目前主要研究有： ( 1 ) 网络信息集成 网络信息集成钔是根据领域本体的内容，从互联网上采集信息并将信息集成 到领域本体中，其实质是为网络信息提供重新组织和理解的机制。目前的研究主 要集中在查询规划上，即把对信息对象框架的查询转化成只对信息源作访问的操 作序列。在规划的执行过程中，有时需要将信息源返回的结果合并起来分析，以 做出下一步的规划，即将两个残缺对象的属性值对集结合成一个属性值对集合， 合并的依据是信息源之间的相关链接。信息的合并是查询规划中的一个重要环节， 目前查询规划已经扩展到生物信息查询上。 ( 2 ) 运输规划 运输规划是指在物流应用问题中，根据动态的运输要求对一组交通工具进行 实时规划( 行程调整和计划安排) 。这些交通工具可以是在一个房子里的移动机器 人，或是在一个城市道路上的出租车，也可以是电梯( 经典的电梯问题) 。然而在 这个问题中存在着很多的制约条件使得运输规划变得复杂，例如时间限制、最终 期限、运输能力、行程时间以及资源优化等，而更多的是像交通状况、天气状况 以及车辆中途损坏等不可预测的事件。另外运输规划在有突发事件发生的大规模 9 东北师范大学硕士学位论文 运输调度中也有所应用呻1 ，比如短时蒯内的军事调度和部署。 1 4 规划域定义语言 规划域定义语言又可称为规划问题描述( 表示) 语言，是规划领域交流和沟通 的标准，同时它也是求解规划问题的前提，因此，规划域定义语言的发展是智能 规划发展的关键。对于不同的规划器，我们可以通过它们对同一种语言表示的规 划问题的处理来进行性能比较哺。随着规划技术的改进与成熟，规划器求解问题 的能力与质量也越来越高，可应用范围越来越广，这些都刺激了规划域定义语言 的不断丰富，反过来，表达能力不断丰富的语言也给规划发展指明了方向。1 9 7 1 年f i k e 和n i l s o n 的s t r i p s 系统在智能规划史上产生了划时代的影响，它使得规 划可以非常容易地进行描述和操作引。但随着规划技术在实际中的应用，研究者 发觉s t r i p s 表示的表达能力非常有限，它不能满足一些实际问题的模型化要求。 设计一种能够刻画和模型化一个实际问题的规划问题定义语言成为了规划技术应 用的前提。1 9 8 6 年e p e d n a u l t 提出了动作描述语言a d l 副( a c t i o nd e s c r i p t i o n l 龃g u a g e ) 。a d l 除了具有s t r j p s 的表达能力外，还能表达条件效果和量化效 果等语言特征。1 9 9 8 年d r e wm c d e m o t t 提出了规划域定义语言p d d l ( p l a n n i n g d o m a i nd e f i n i t i o nl 锄g u a g e ) 肺朋删，它从语法和语义两个方面给出规划问题的定 义。p d d l 的表达能力非常强，它能够刻画规划问题在时间和数值方面的属性， 能够表示问题的偏好，其目前的表达能力已超过现有的规划器所能处理的表达能 力。目前，p d d l 己成为国际智能规划比赛的标准域定义语言。 1 4 1s t r i p s 在规划史上，s t 对p s 系统是一个非常著名的规划器，而其之所以著名的主要 原因是引入了s t 对p s 问题描述方法。s t 黜p s 为了描述操作和世界模型，引入了 s t 刚p s 操作符的概念并发展成为s t 刚p s 问题描述语言，为规划提供了一种有效 的描述和操作规范。 在s t 刚p s 语言中，所有的操作和世界模型都采用一阶谓词演算公式来描述， 变量在使用之前都有辖域限制。它用一系列完整的基文字( g r o u n dl i t e r a l ) 描述域 的初始状态，目标被定义为一个合取命题( p r o p o s i t i o n a lc o n j u n c t i o n ) ，所有满足 目标形式的状态均被同等考虑。在s t 刚p s 表示中，每个动作用一个合取前提 ( c o n j u n c t i v ep r e c o n d i t i o n ，动作执行前必须满足的条件) 和合取效果( c o n j u n c t i v e e 疏c t ，动作执行完后可以保证为真的状态) 来描述，它们定义了从状态到状态的 过渡函数。动作能在满足其前提的任何状态中执行，动作的执行导致状态的转移， 即根据执行动作的效果向原状态中添加文字、除去过程中的矛盾文字，得到动作 执行后的新状态。 l o 东北师范大学硕士学位论文 我们前文谈到的火箭问题用s t r i p s 描述如图1 1 所示。 c i o m a i n ： ( d e f i n e ( o p e r a t o rm o v e ) ：p a r a m e t e r s ( ( r o c k e t ? r ) ( p l a c e ? f 幻m ) ( p l a c e ? t o ) ：p r e c o n d i t i o n ( ：a n d ( ：n e q ? f 而m ? t o ) ( a t ? r ? f r o m ) ( h a s - f u e l ? r ) ) ：e f 诧c t ( ：a n d ( a t9 r9 t o ) ( ：n o t ( a t9 r ? f 幻m ) ) ( ：n o t ( h a s f u e l ? r ) ) ) ) ( d e f i n e ( o p e “i t o ru n l o a d ) ) ：p a r a m e t e r s ( ( r o c k e t ? r ) ( p l a c e ? p ) ( c a 唱o ? c ) ) ：p r e c o n d i t i o n ( ：a n d ( a t ? r ? p ) ( i n ? c ? r ) ) ：e 疏c t ( ：a n d ( ：n o t ( i n ? c ? r ) ) ( a t ? c ? p ) ) ) ( d e f i n e ( o p e r a t o rl o a d ) ：p a r a m e t e r s ( ( r o c k e t ? r ) ( p l a c e ? p ) ( c a r g o ? ) ) ：p r e c o n d i t i o n ( ：a n d ( a t ? r ? p ) ( a t ? c ? p ) ) ：e 行e c t ( ：a n d ( ：n o t ( a t ? c ? p ) ) ( i n ? c ? r ) ) ) i n i t i a lc o n d i t i o n s ：a trl o n d o n ，a tal o