（计算机软件与理论专业论文）领域无关规划器预处理的研究与实现.pdf

领域无关规划器预处理的研究与实现 专业：计算机软件与理论 硕士生：余剑锋 指导教师：吴向军副教授 摘要 在智能规划的研究上，存在领域相关和领域无关两个方向的研究，其中，领 域无关规划是研究的热点和难点。长期以来，由于领域无关规划器很难充分利用 特定研究领域的专家信息，领域无关规划器效率很难提高。但许多研究学者的研 究和实践都表明，领域知识是提高规划器效率的关键所在。在规划前，进行有效 的领域知识分析、提取和表示，不仅可以提高规划效率，而且还能扩大规划器解 决问题的能力，因此，对规划器预处理系统的研究成为拽划技术之后的另一个研 究热点。 本文对这些问题进行了研究，设计并实现了领域无关规划器预处理系统 d z m ，论文的贡献主要在于： ( 1 ) 对领域信息的组织、存取机制进行了优化： ( 2 ) 把较复杂的a d l 领域问题转换为常用的s 嘲p s 领域问题； ( 3 ) 分析领域动作，在s 1 榭p s 和a d l 描述范围内，采用自动化推导策 略，自动挖掘黪含的领域规则，进而表示为有效的领域约束知识。在 规划过程中利用这些领域约束知识，能有效地指导规划器的规划，消 减无意义的状态，减少搜索空间，提高规划效率； 通过实验数据表明，d k e m 在处理一些领域问题时表现出色，体现了它的 理论价值和应用价值。 关键词：智能规划预处理系统p d d l 领域规则领域约束知识 2 0 0 5 中山大学硕士毕业论文 颁域无关规划器预处理的研究与实现余剑锋 1 1 a e ：s t u d ya n di m p i e m e n 删o no ft h ep 旧p r o c e s s o ro f d o m a i n i n d e p e n d e n tp l a n n e r m a j o r ：c o m p u t e rs o f t w a r e & t h e o r y n a m e ：y uj i a n f e n g s u p e r v i s o r ：w ux j a n g j u n a b s t r a c t w i t h i na i p i a n n i n g t h e r eh a v e t r a d j 茜o n a y b e e n t w ot 1 e m e s 。 d o m a i n d e p e n d e mp l a n n i n ga n dd o m a i n i n d e p e n d e n tp i a n n l n g 廿1 el a t t e ri s t h eh o ta n dd i f 竹c u l tt o p i c hi sd i f 厅c u i t ，b ri o n gt i m ef o rd o m a i n - j n d e p e n d e n t p l a n n e r st ot a k ea d v a n t a g eo fd o n 谊n - s p e c i f i ci n f o r 兀湖o n ，w h i c hr e s u l t si nt h e d i 俏c u i t y t oi m p r o v et h e 鲥i c i e n c yo f p i a n n e r s a tt h es a m et i m e ，t h e r e a r c h e sm a n yr e s e a r c h e 飓a 阳e n g a g i n ga n da p p c a 矗o n ss h o wt h a t d o m a l n - s p e c i f i ck n o w i e d g ei st h ek e yt ot h ee 师c i e n c yo fp i a n n e r s b 确r e p e 巾r m n g a l p l 锄n i n g ， t h e卸a i y s i s 。e ) c t r a c t i n g绷dr e l ) r e 州n go f d o m a i n - s p e c i 套ck n 讲j i i e d g en a to n i ym 科i m p r o v et h e 嘶c l e n 斜o fp l a n n e r s ， b u ta i “剧e n p o w 射t h ec 印酬咐t o p r o m e m s t h er 鹋翩i r c ho n p i a n n e 沼p 他p r e s s 饼b e 幻o m e s 蕾i o 枷e rh o tt o p i ca f t e rp i a n n i n gs e 甜c h t e c h n o i o g i e s i nt h l st h e s i s ，w es t u d i e dt h e s ep r o b 恼m sa n dd j g n e dap 怕p r o s s o ro f d o m a n - i n d e p e n d e n tp i a n n e ln a m e i yd k 日啊h e r ea m 廿1 em a n n t n b u 旧o n s ( 1 ) 1 - oo 叫m i z et h eo 叼a n i z a 珏o n a n da c s sm e c h a n i s mo fp n m a l d o m a j n s p e c 埔ci n 蕾d n 嘣i o nw h i c hi si n p u t 刚- r i t od k e m ( 2 ) t r 鲫g f o r mt h ea d lp r o b i e m st os t r i p sp r o b i e m s ( 3 ) w 胁i nt h es t r l p s & a d l ，d k e mp e m r 鹏a n 醐a l y s i st od o m i n a c 舾o n s w h i c h na u t o m a a c a i l ye x t r a c ti m p i i c j td o m a i n - s p e c i f i c c o n s 订a i n tk n o w l e d g e t h ek n a w i e d 9 0i su s e dt o 鲥i c i e n 柚yg u i d et h e p i a n n i n g ，e 村m i n a 船n gs o m em e a n i n g l e s ss t a t e sa n dr e d u c i n gt h e n u m b e ro fs e a r c hs p a c e 。t oi m p r o v et h ee 竹i c i e n c yo fp i a n n j n g n 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 d k 日d e m o n s t r a t e de x c e p 髓o n a ip e 哟r m a n c ei ns o m ed o m a i n si no u r e x p er _ m e n t w et h i n kt h a td k e mi sm o r ev a l u a b i ei nt h e o r ya n di np r a c t j c e k e yw o r d s ：a ip i a n n i n g p r e - p r o c e s s o lp i a n n i n gd o m a i nd e 啊n i t i o nl a n g u a g e d o m a i ni a w s 。d o m a i n s p e c i 啊ck n o w l e d g e - - 1 1 概述 第一章引言 智能规划是人工智能研究领域近年发展起来的一个热门分支，理论研究和实 际应用都成为人工智能当前研究的热点。智能规划是指在行动前设计好操作步 骤，它是一种问题求解技术。智能规划在机器人、智能工厂、商业应用，如：智 能网络信息集成和智能小区、智能交通、物流运输和工作流等方面都有着非常广 阔的应用前景。 一个典型的智能规划器包含两部分：预处理和规划，因此，要进行智能规划 就必须设计好规划器的预处理系统，也即对所研究问题的领域知识进行读取、组 织和存储，并以有效的形式表示出来，以便规划器能利用这些信息进行高效的规 划。而要使得领域无关规划器能处理更多大型、复杂的领域问题，就必须有一定 的策略处理并组织好输入的领域信息，设计好规划器的预处理部分。 通用规划系统是为了解决通用规划问题而设计的。但长期以来，通用规划系 统很难做到把所有问题的领域知识都利用起来，因此，通用规划器在具体的应用 下效率很难提高。另一方面，许多研究专家学者都认为，领域知识能提高规划系 统的表达能力和求解效率。多伦多大学的f a h i e mb a c c h u s 教授认为：充分利用 领域知识或结构，能改进解决通用问题的性能御。又如，英国s l 限t h d y d e 大学 的t m ，一个独立的领域分析工具，成功应用于规划器s r a n ，并表现出了优异 的规划性能( 4 ) 四。t l p | 朗规划器( b a c c h u s & k a b a n 拍2 0 ) 和_ f a l p i a n 规划器 ( d o h e n y & - ( v a m s 订o m1 9 9 9 ) 利用领域控制知识进行规划，都表现出了非常不错 的问题求解性能。因此，领域分析技术成为紧随规划技巧之后的另一个提高规划 器表达能力、求解效率以及通用性的关键技术。由自动规划和调度国际会议 ( i c a p s ) ”) 主办的国际规划竞赛出台的规划领域定义语言( p d d l ) ，为规划的研究 和发展起到了很大的推动作用。p d d l 规范消除了以往即使是同一个问题，规划 描述也不统一的现象，使得各种规划器有了统一的交流、比较平台。为领域无关 规划器预处理的研究和实现，起到了很大的作用。 同时，进行领域无关规划预处理的研究还有许多成熟理论的支持，例如： 成熟的l e x 和w 屺c 词法语法分析技术； 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 人工智能理论；知识的表示和推理、状态空间搜索技术； 以及数据结构等计算机基础理论的支持，使得本方向的研究具有很强的科学 性。因此，总的来说，用自动推导领域约束知识的思路来设计规划器预处理系统 有着很好的意义。 1 2 智能规划器预处理系统的研究现状 规划器预处理系统是规划器的一部分，因此，要研究规划器的预处理系统， 就要先了解规划器的研究情况。 智能规划( a ip i a n n i n g ) 是人工智能一个比较新的热点研究领域，对智能规划 的研究，主要还是在国外，国内比较少。在国外，有两年一次的国际规划竞赛 ( i p c - i n t e m 觚o na | p i 钔n i n gc o m p 酬a o n ) ，主要是由自动规划和调度国际会议 ( 1 c a p s - i m e m a 旧o n a ic o n f e r e n o na u t d m a t e dp l a n n j n ga n ds c h e d u i i n g ) 圭 办。i 雪际规划竞赛从1 9 驰年开始举行第一次竞赛，至今已经举行了四次竞赛。 l c a p s 的下一次竞赛预定在今年举行，名称为国际知识工程竞赛 ( 1 k e c - i n t e m a 髓o n 刮k n 0 1 一e d g ee n g i n e e r n gc o m p e 砒i o n ) f 。 每届国际规划竞赛都吸引了很多国家的参赛队伍参加，这些规划器大部分都 采用甩c c + + 实现并运行在u n i ) ( u n u x 环境下。比较这些规划器的预处理系 统，我们发现：规划器的预处理流程框架基本都是一样的。先看看规划器的流程 框架，如图1 1 所示。 图1 - 1 中“规划”前的流程即是预处理系统的流程。 领域模型的定义和问题实例是以一定的格式存储在文件上的，目前为规范的 p d d l 格式，预处理系统采用l e x 和c c 词法语法分析技术，对领域模型定 义和问题实例的合法性、有效性进行验证( s y n 协i ) ( c h e c l ( i n g ) ，并在l e x 和w 屺c 产生的c 和h 程序中实现存储原始的领域信息( g e n e 限日n gp a 阽et r sf o ri e g a i p d d ls y n 缸) 。这个过程，大部分的规划器处理都大同小异，区别在于随后对读 取的这些原始领域信息的进一步处理。 在每届参与竞赛的这些规划器中，我们选择了二个被认为比较好的规划器预 处理系统来分析和比较，它们代表了当前智能规划器预处理系统的最新研究成 果。它们分别是：f f 的预处理系统以及s _ r a n 的预处理系统t l m 。 2 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 分析命令行输入的参数 j r 读取领域模型文件信息并存储 读取问题实例文件信息并存储 上 1 分析所读取的领域信息，并进行适当的 l 转换和优化；同时建立辅助数据结构。 上 i 对原始领域信息进行分析、推导，挖掘 i并有效表示领域知识 上 规划 i 结果输出 上 【 结束 j f f 的预处理系统 图1 1 智能规划器规划流程 f f 是德国f r e j b u r g 大学的h o f f m 鲫n 设计的，h o f f r 舱n n 也参与了i p 尸的 设计。f f 参与了2 0 年和2 2 年的国际规划竞赛，并获得很好的成绩：在 2 0 0 0 年的国际规划竞赛中获得突出表现奖( 0 i 心协n d i n gp e 哟r 眦n c e ) ，在2 0 0 2 年的国际规划竞赛中获得最高表现奖pp e r f ；o r m e r ) 。f f 的规划策略采用局部 搜索技术( l o c a is e a r c l lt o p o i o g y ) ，作者本人的p h d 论文( u t j i i z i n gp r o b i e m s o i v i n gs i r u c h j r ei nh a m l n g ：al a is e a r c ha p p f o h ) 获得e c c a i 的2 0 0 2 年人工智能论文奖，这充分表现了f f 规划策略的先进性。h 砷f m 锄n 还主持了 2 0 0 4 年国际规划的经典规划部分的竞赛。 f f 的局部搜索技术其实是在规划中采用了较好的启发函数：针对研究领域 的众多问题进行分析，并总结这些问题的共性( 经验性的总结) ，从而根据这些总 2 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 结，设计启发函数。这个启发函数表现了卓越的性能，使得它在众多的规划器中 脱颖而出。要进一步了解f f 的相关信息，请参考【1 2 】。 t l m t i m t y p ei n f e r e n c em o d u i e ，类型推导模块，是英国s c r a l h c i y d e 大学s p g 专家组研究的领域无关规划器预处理系统。t i m 最初从领域无关规划器s _ r a n 中 分离出来，成为独立于任何规划方法的系统。s t a n 参与了1 9 9 8 年和2 0 0 0 年 的国际规划竞赛，并表现出优异的性能。t i m 的两位主要设计者f o x 和l o n g 还主持了2 0 0 2 年的国际规划竞赛( i p c 3 ) 。 t l m 被称为是领域无关的自动化领域分析工具。t i m 可以从所读取的原始领 域模型和问题实例信息中，根据领域中对象间的功能关系，提取类型结构( t y p e s t u c t u r e ) 信息，进而分析出隐含其中的状态常量( s 哺ei n v a n a n t s ) ，这些信息在 规划中被有效使用，能改善规划器的性能f 3 7 ) 楫8 ) 。这种技术也被称为状态分析技 术( 蝴ea n 剐y s i s ) 。下面是t | m 的处理流程描述： ( 1 ) 根据领域模型描述中的a c i i o n s 定义，构造属性关联结构( p r o p e 哪 r e i a 吐n gs i r u c t u r e p r s ) ( 2 ) 根据属性关联结构，构造转换规则( 1 伢钔s i t i o nr u i e ) ( 3 ) 根据转换规则的前件和后件，划分属性空间：p r o p e n ys p e s 和 a t 晡b u 协s 钟嘴s ( 4 ) 分析初始状态，为问题实例描述中的对象( o b l e 指派类型附p e s ) ( 5 ) 推导状态常量( s 吼ei n v a n a n 哟 目前，t l m 的研究集中在识别通用类型结构，因为这样的类型结构能被分离 为子问题( s u b _ p m b i e m s ) ，并能被子问题解决机制s p e c i a i i s e d l v e r s ) 更好地解 决( 这些子问题机制往往是比较成熟和高效的) 。例如可在不同位置移动对象的问 题等。这样，当领域信息被规划器预处理系统处理后，规划器将根据问题类型的 不同而采用不同的规划机制进行规划，从整体上提高规划器的效率。 从所选的二个规划器预处理系统的机制来看，要提高规划器的通用性和效 率，就必须对领域问题进行多方面的研究，总结共性，使得规划器能更充分的利 用到领域的专家知识，这样才能提高规划器整体性能。 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现 余剑锋 1 3 本文任务 本文的核心任务是：优化输入的原始领域信息组织和存取机制，并采用自动 推导领域规则，进而表示为有效的领域约束知识的技术，设计领域无关规划器的 预处理系统( p r e p r o c e s s o r ) ，本文任务描述如下： 研究国内外智能规划技术的研究进展情况，并展望前景； 研究目前比较优秀的规划系统所采用的预处理技术，特别是规划领域分 析技术( p i a n n i n gd o m a i na n a l y s i s ) ； 学习和借鉴前人优秀的设计思路，并结合本人知识和想法，改进预处理 系统，并用创新观点，设计新的处理方法：在通用规划器下，能根据规 划器读取的原始领域信息，自动分析、提取隐含的领域规则，进而表示 为有效的领域约束知识。； 编写程序实现规划器预处理系统，并用实验方法进行验证； 总结研究工作； 1 4 论文创新点 普遍认为：挖掘领域知识是提高规划系统效率的关键部分，但如何在通用规 划器中挖掘随机输入的领域知识，成为研究的难点。尽管如此，许多专家和研究 学者都对这一问题进行了积极的研究，例如英国s t 嘣时1 d y d e 大学设计的领域无 关规划器预处理系统t m ，德国f 怕i b u r g 大学的f f 规划器预处理系统等。本文 从设计优秀的预处理系统出发，设计并实现了领域无关规划器预处理系统 d k e m ，主要创新点主要体现在： 改进规划领域信息的组织、存取方式提高效率； 从通用的思路出发，结合当前p d d l 标准，使得该通用规划器的预处理 系统能把用特殊格式描述的问题，如a d l 领域问题，转化为常用的 s t r l p s 领域问题来处理，扩大预处理系统的处理能力； 借鉴领域相关规划器的优点，设计通用规划器的预处理系统，使其也能 根据所读取的原始领域信息，自动挖掘出该领域的领域约束知识，从而 更有效地指导规划器的规划； 2 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 结合当前智能规划研究的两种方法：逻辑方法和s t r l p s 方法( 即程序方 法) 的优点进行研究； 1 5 本文结构安排 本文主要是设计一个能自动推导领域约束知识的领域无关规划器的预处理 系统，与其它规划器的预处理系统部分相比有自己独特的地方：不仅对领域信息 组织、存取机制做了优化，而且还能根据读取的原始领域信息，自动推导隐含的 领域约束知识，并用数学的方法给予了证明，最后，结合实验数据对方法的有效 性、价值性进行了分析。 首先，文章介绍了智能规划的基本概念，包括智能规划的基本思想、基本技 术、经典规划系统以及智能规划研究进展情况，接着开始进入主题部分： 介绍智能规划的问题表示形式： 设计领域无关规划器预处理系统的流程框架，并对各个流程部分进行了 较为详细的分析； 介绍如何对领域信息的组织、存取方式进行优化： 如何对所读取的原始领域信息推导出隐含的领域约束知识； 设计程序并用实际领域数据进行验证，对结果数据进行分析； 总结和展望； 使得领域无关规划器也能像领域相关规划器样：能充分利用领域知识进行 规划，是本文预处理系统d k e m 设计的最高目标。 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现 余剑锋 第二章智能规划概述 人工智能的研究更多的是结合具体领域进行的，主要研究领域有专家系统， 机器学习，模式识别，自然语言理解，自动定理证明，自动程序设计，机器人学， 博弈，智能决定支持系统和人工神经网络。而智能规划是人工智能研究领域近年 来发展起来的一个热门分支，理论研究和实际应用都成为人工智能当前的热点。 目前，智能规划跟其他人一些工智能技术一样，因为智能机器人还没出现， 现在大多都是出于实验室研究阶段，进行得比较好的应用就是美国宇航局里用在 宇宙空间探测上的机器人。目前也有一些其他的应用，例如物流调度、车间生产 安排等，但这些都是智能规划的基本应用，离智能规划的实质应用能力还有很长 一段距离。我们相信，随着机器人的出现，随着国际竞赛的越来越完善，智能规 划在未来几年中的研究会越来越热，从理论研究到实际应用的步伐会越来越快。 本章主要介绍智能规划的基本思想、基本技术、经典的智能规划系统以及智 能规划的最新研究进展情况。 2 1 智能规划基本思想 规划，在我们日常生活中的理解就是：在做菜件事或行动前，对闯题及要采 取的处理方式进行预先的分析并制定相应的计划。例如一个软件项目，第一步是 进行需求调研，接着进行系统设计，再到编码、测试、发布等。又如，给你一个 排列比较零乱的魔方，你总可以在魔方的游戏规则范围内，依据一定的步骤，把 魔方排列到目标状态。总之，规划就是提前策划好，并形成一个可以实施的计划、 步骤。恰当的规划，可以节省时间、人力、物力和财力，提高工作效率，有时甚 至可以找到问题的最优解。 在人工智能的研究范围中，智能规划( a lp i 钟n i n g ) 实际上就是一种问题求解 技术，即从某个特定问题的初始状态出发，发现一系列行为或构造一系列动作步 骤，达到解决该问题的目标状态。规划系统的研究起初源于问题的求解，但是后 来规划研究比起一般的问题求解更注重解决具体的实际问题，而不单单是抽象的 数学模型，因此近年来，智能规划重新得到人工智能研究学者们的重视，成为目 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现 余剑锋 前人工智能领域里极其活跃的研究方向之一。 智能规划与调度和最优搜索技术相关联，研究的主要问题是：给定一个问题 的初始状态，规划器如何选择达到指定目标的一组规划动作。在求解的过程中， 一般使用所谓的“目的手段”分析法( m e a n s - e 几d sa na i y s j s ) ，逐步比较并设法缩 小当前状态与目标状态的差别，最后达到目标状态。或者采用简化问题目标的方 法，把目标不断分解成容易解决的子目标，逐步搜索，最后确定出操作序列。 智能规划首先要对研究的领域进行建模：把问题进行抽象化，并提取出该类 问题的一般共性一领域模型。领域模型一般包括：该领域模型所采用的问题描述 能力( 即r e q “r e m e n t s ，在稍后描述) 、研究对象的类型付p e 、c o n s t a n t ) ，领域模 型抽象的谓词( p r e d i c a t e ) 一表示研究领域对象的状态，以及在这个模型内可以执 行的动作( a 酬o n ) 。然后根据这个模型衍生具体的问题一问题实例。这种机制类 似于我们比较熟悉的模扳机制。智能规划器正是在基于领域模型和问题实例的环 境下进行规划的。 例如，在积木块世界( 引o c k w o r i d ) ，模型认为所有的积木块都是一样的：都 是o b j e c t ，在这个世界里，抽象出五个谓词来表示积木块世界所处的状态： o n 伏舯一积瘩瑰柱积木块y 的上面： 。 0 o 堞限b l l ：一秘术抉x 在地板上； c 岬o q | - 糯拳块嚣士箍悬空的；。 洲d e m 剐雕一糨棚l 筝是空的l h o l d 聃g l p q 一机械筝豢着积术块x ； 积木块世界是研究如何从一个状态转换到另一个状态的，在这个过程中，积 木块的移动假定是由机械手完成的，谓词h a n d e m p l y 和h o l d i n g 用来表示 机械手的状态。 在积木块世界，机械手可以使用的动作( a c l i o n ) 相应的有四个： ，1 ，：， ：。 。： ： p 孵峰9 p 鳓曼鹅爨i i 媾x 扶撼板点攀起；一：。一。u 一0 _ j j j = jj ；j ： p 雌尊删懒_ 端秣婊x 藏到地板上_ ：i 。o ： u n 嫩蝴妻黼壤x 鼹积术搀y 点耪聋 j 0。0 。 蹴蝴薹斓蔫蠛。必遗鞫被未块y 上叠一；。1 ，： 在这个模型下，假如有积木块a 、b 、c ，a 在b 的上面，b 、c 在地板上， 2 5 中山大学硕士毕业论文镬域无关规划器预处理的研究与实现余剑锋 则我们可以这样定义问题实例： o n ( a ，b ) ，c l e a r ，o n t a b l e ( b ) 。o n t a b l e ( c ) ，c l e a r ( c ) 又如，积本块a 、b 、c 、d ，a 在地板上，同时a 上面是空的；b 在地板上， c 在b 的上面，d 在地板上，同时d 上面是空的，可以描述如下： o n t a b l e ，c l e a r ( a ) ，o n ( c ，b ) ，c l e a r ( c ) ，o n t a b l e ( d ) ，c l e a r ( d ) 这样，在一个领域模型下，可以非常灵活地衍生出与实际相符合的问题实例， 从而为研究提供了科学的方法。 在规划领域，目前存在两种传统的方法c 9 ) ： 领域无关规划 领域无关规划是指，规划器的规划方法不依赖于某个或某些特定的领域。这 种方法的规划动作与规划的基本原理相关。典型地如搜索技巧，搜索控制策略以 及处理结果的表达等。在规划过程中，还涉及不确定性、资源、时间、函数独立 等其它一系列问题。 领域相关规划 即规划在某些特殊领域的应用，这种方法将在复杂领域建模的基础上，使用 丰富的领域知识进行规划。典型的相关问题包括：知识的获取和表达，以及在规 划和推理的过程中，专家控制知识的灵活应用等问题。 在实际应用中，规划和调度经常是交叉的，而且适合某一领域的技术也适合 另一领域。规划和调度是为达翌l 某些目标，在执行前选择执行动作的一种方式。 从a i 的角度看，规划主要是选择动作和安排动作执行的顺序，而调度则主要指 为选择的动作分配时间和资源。a i 规划和调度的重点在于领域知识的运用。 2 2 智能规划基本技术 许多技术被用来解决规划问题，对规划问题的研究也产生了不少具有良好性 能的规划系统。 h a f i r 舱n n 在m o d e mh a m i n gt e c h n i q u e s l ) 中认为，按照技术发展的 时间分，智能规划技术可以分为三种：1 9 弱年前的技术、1 9 9 5 年到2 0 0 0 年的 基于图规划的技术，以及2 0 0 0 年后的基于启发式搜索的技术。同时认为，规划 其实又可分成两类：最小化规划和可满足规划。而在美国n i l sj n s s o n 的 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 芦删自c ia ii m e g e n c e 中总结了几种基于逻辑的规划方法：s t r l p s 规划、层 次规划。针对规划求解方式，规划技术又可分为两种：前向状态空间搜索技术以 及以目标为导向的规划技术。而又有文章指出，智能规划技术可分为：基于逻辑 的规划、基于操作的规划、非层次规划、层次规划、图规划和基于s 卢丁的规划 等等。下面介绍几种主要的技术。 ( 1 ) 图规划 1 9 9 5 年，由b l u m 和f u r s t 引进了一个使用与众不同的方法来求解规划问题 的规划系统：图规划。它的基本思想是：用一种可达性( r e a c h a b i t y ) 的分析来排 除许多不相容的动作序列以及组合。从初始条件出发，图规划排列出第一步、第 二步、第三步等等可能实现的命题集合。对于第一步来说，这个集合必须囊 括在从初始条件到下一步可达状态中所有成立的命题。同样的，对于第二步来说， 集合必须囊括在从第一步到下一步可达状态中所有成立的命题。 但是，并非所有这些命题都是相容的，即使我们允许动作并行，也不是所有 可达的命题能够同时成立。因此，图规划在不相容的动作之间和不相容命题之间 定义了互斥关系( 咖t e x ) 。两个动作a 、b 被标记成互斥，当它们中的一个删除 了另一个的前提或者增加效果( 被称为妨碍) ，或者a 的一个前提节点和b 的一个 前提节点被标记成互斥( 被称之为需求竞争) 。当实现它们的所有动作都彼此互斥 时，两个命题被标记成互斥。 采用图规划的系统有： g 陀p h p l 钔【b i u m & f u r s t 。9 5 l ，b i a c k b o xl k a u 垃& s e i m a n ，9 6 l ，i p p 【k o e h i e r e t a i 。9 7 】，s 1 _ a n 【f o x & l o n g ，9 8 】，t g p 【s m m & w e i d ，9 9 】等。1 9 年的国际规 划竞赛，除了一个外，其他的规划器都使用了图规划技术。 大致来说，使用图规划所能解决的规划问题不能超过5 0 个动作。图规划技 术也能解决量化条件效果和a d l 语言的其他一些特性。最近越来越的研究工作 正努力地使在图规划中考虑非常有限的时间处理和数值的运算。 ( 2 ) 基于启发函数的规划 目前的规划系统为了提高效率，几乎都采用了启发信息。启发式搜索的基本 思想是：人为地给定一个评估函数，对于每个搜索状态进行计算，得到每个状态 的值，从而决定哪个状态好。 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 启发式搜索可利用与问题有关的信息进行搜索，将知识或经验与搜索相结 合，从而达到减少搜索量，提高搜索效率的目的。但在当前智能规划研究中，设 计领域无关规划器的启发函数是一个难点。 ( 3 ) 层次规划 以n o a h 为代表的层次规划方法思想是：首先勾画出一个完整但又比较粗 略的规划解，然后逐步细化、逐步明确，直到足以具体完成整个规划的各步操作。 层次规划方法实际上是把不同性质的问题放在不同层次上加以考虑。 n o a h 系统所代表的层次规划方法从规划的总体过程来说，是构造性的， 这一特点的好处有很多。首先，由于每一级规划都是通过对子目标的并行操作形 成的，这样就降低了问题的复杂性。而且，逐级生成规划，便于及早发现、解决 子目标的冲突现象，加上“最小约定”策略的使用，避免了非层次规划中的回溯， 搜索工作量有所下降。另外，在规划的实际执行过程中，如果出现意外情况，只 需从相应的规划层次入手，予以修改，方便了规划的监控。最后，各级规划实际 上都是详略程度不同的规划解的表示，这在规划系统的应用中也是很有意义的。 ( 4 ) 基于前向状态空闯搜索的规划 对规划问题最显而易见的解决办法就是前向状态空间搜索( f s s f o r w a r d s t a t es p a s e 删，规划器由初始条件组成的状态出发，选择所有前提在当前 初始状态空间中都能够得到满足的动作，日案件动作执行后的正效果。删除动作 执行后负效果，从而构造出一个新的状态集。这样的过程每次查看目标状态要求， 不断向目标状态靠近，直到所有的目标都实现为止。 前向状态空间搜索的难度在于：对于任何一个状态可用的动作数是非常大 的，这导致了搜索空间的急剧膨胀。为了使得f s s 搜索成功地进行，就必须在 搜索过程中加入启发式引导，只扩展小部分的搜索状态空间。因此，大多数规划 器都使用了各自不同的搜索策略。例如，在各届国际规划竞赛中都表现的比较好 的f f ( f a i s t f o r w a r d ) 利用在放宽了的规划图中，把从当前状态到目标状态的步长 作为它的启发函数值。而在2 0 日2 年的国际规划竞赛中获得“d i 鲥n g u _ s h e d p e r f o r m a n o f t h e f i r s t o r d 甜”称号的l p g ，它的目标函数中则考虑了并行动 作的个数和整个规划执行的时间。当然也有一些例外的情况，如b a c c h u s 使用 时态逻辑中的公式来表达与领域有关的知识来引导状态空间的搜索，而g e 什n e r 2 0 0 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 自动地从一个简化了的状态空间的初次搜索中获取有用的启发式引导。这两个规 划器的速度比较快，但是得出来的规划解的步数要比其他规划系统的解长的多。 ( 5 ) 以目标为导向的规划 到最近为止，大部分对于经典规划问题的研究工作集中在以目标为导向的向 后搜索的构造规划，它的基本思想是：选择一个能够实现目标之一的动作，把这 个动作加入到当前的规划中。目标被从当前的集台中删除，取代它的是所选择动 作的前提条件集，规划再在这个新的目标中选择动作。这个过程不断的被重复， 直到这样的目标集成为初始条件的状态子集为止，规划完成。与前向状态空间搜 索一样，这种方法也是比较简单的，只要在规划中保持全序的动作就可以了。但 如果动作只是部分序的，那么就要增加一些防护方法来看那些没有排序的动作是 否相互干扰。 不少的策略被用来完成上面所说的防护工作，其中使用最广泛的就是由 m c a i e s t e r 提出的因果链接法( u s 刮一l i n k ) 。沿着规划的顺序，一组因果链接被 用来指示某些动作之间必须保持的命题。因此，当一个动作被加到规划中并建立 了新的予目标时，相应的因果链接就要加入，使得子目标在创建它的动作和需要 这个予目标的动作之间被保持。因果链接还必须在规划中定期的检查，以确认没 有什么其他的动作破坏它们如果这样的威胁发生，那么附加的捧序约束就要加 到这些动作中以消除这些威胁。 使用这些方法的规划器被称为部分序因果链接规划器f p a 哺a 10 r d 刨c a u s 酣 u n kp i a n n e r 一筒称p o c l ) ，例如u c p o p ，能够处理带有量化条件效果的动作 以及a d l 语言的一些其它特性。但是，不幸的是，这类规划器不能处理带有大 量动作的规划问题。 2 3 智能规划的应用研究进展 虽然国内的人工智能研究也是如火如荼，但对智能规划的研究却比较少，而 在这方面，国外却有很多著名的学术机构、组织和会议。例如l c a p s ( 1 著名的国 际规划竞赛l p c ，从19 年开始，每隔两年举行一次国际性的规划竞赛，吸引 了一大批专家参与，不仅使得规划器有了统一的比较、交流平台，更重要的是吸 引了更多的研究学者，促进了对智能规划的研究，缩短了智能规划从理论到实际 2 0 0 5 中山大学硕士毕业论文领域无关规划嚣预处理的研究与实现 余剑锋 应用的时间，使得对智能规划展现出非常好的前景。国际规划竞赛已经成为智能 规划权威的非赢利性组织机构，代表了智能规划最新、最前沿的研究和方向，因 此，要了解智能规划的应用研究进展，就是要了解国际规划竞赛。 国际规划竞赛( i p c i n t e m a t i o n a ip i a n n i n gc o m p e t i t i o n ) ，由自动规划与调 度国际会议( i c a p s ) 举办。旨在建立一个规划器能够进行比较、交流的平台，同 时收集智能规划研究领域数据。使得正在从事或想了解智能规划的研究学者能了 解、下载当前这个领域的研究问题数据。国际规划竞赛更重要的目的是：通过这 样的竞赛，凸现智能规划研究的焦点问题，指明研究难点和方向，同时通过建立 规范的领域定义语言，结合实际的研究和应用，缩小智能规划从理论到实际应用 的距离。 国际规划竞赛从1 9 9 8 年开始，每两年举行一次。1 9 9 8 年第一次国际规划 竞赛l p c i ( 5 ) 在卡乃基梅隆大学举行，有五个规划器参与了竞赛，它们分别是： 美国的b i k b o x 、s g p ，德国的i p p ，委内瑞拉的h s p 以及英国的s t a n 。上 述规划系统除了s g p 用l i s p 语言实现外，其他都用g c + + 实现。按照描述问 题域的语言，把参赛问题分成两类：s t 刚p s 问题类和a d l 问题类，所有规划 器都参与了s t r i p s 问题类的竞赛，其中l p p 和s g p 还参与了a d l 问题类的 竞争。这次大奏最重要的贡献是：建立了第一个版本的规划领域定义语言 p d d l - p i 舯n i n gd o m 踟nd 酾n i 怕nl a n g u 妁e ，结束了长期来规划器即使是同样 的研究问题，因为描述方式不同而没办法进行统一比较、评价的局面，向智能规 划统一比较、交流迈出了很重要的一步。 加0 0 年的国际规划竞赛i p c 2 ( 4 ) ，吸引了1 6 个规戈| j 器参与角逐。此次竞赛 分两组进行：全自动s t r i p s & a d l 规划器( f u i i ya u t o m a t e ds t r l p sa n da d l p i a m 删，参与此类型竞赛的规划器有：f f 、g r t 、s y s t e mr 等十二个规划系 统；以及允许手工参与调节的规划竞赛，有s h o p 、s y s t e mr 、p b r 、_ a l p l a n n e r 等八个规划系统参与。本次竞赛的研究热点集中在数值变量( n u m e r i c v a i u e d v a r i a n e s ) 和可持续动作( d u 例o n 剐a c l i o n s ) 上面。部分序规划的思想和规划知识 在规划中的重要作用得到了验证。 2 2 年第三届国际规划竞赛i p c 3 锄，吸引了1 4 支参赛的规划器：f f 、l p g 、 m i p s 、s h o p 2 、i ) ( t e l t 、s a p a 、s e m s y n 、s i m p i e p l a n n e r 、& e a 、t a l p i a n n e r 、 2 5 中山大学硕士毕业论文领域无关规划器预处理的研究与实现余剑锋 t l p l 卸、t p 4 、t p s y s 和v h p o p 。与上届一样，这次竞赛也是分为全自动和 允许手动调节两组进行。由于p d d l 不能对持续动作和持续资源消耗进行建模， 因此，大赛对p d d l 进行了修改和扩展，修改后的p d d l 称之为p d d l 2 1 。根 据p d d l 描述能力的几个层次分成五级：第一级即a d l 类型的规划；第二级在 第一级的基础上增加了数字变量；第三级在第二级的基础上增加了带持续特性的 构造类型；第四、五级由于没有在大赛中使用，被称之为p d d l + ，它是对建立 复杂的、持续离散的实时系统的建模能力的描述，旨在促进智能规划的进一步研 究。本次竞赛热点问题集中在带时间特性的问题和带数值属性的问题领域 ( t e m p o r a la n dm e t r i cd o m a i n s ) 。 2 0 0 4 年的国际规划竞赛l p c 4 髑，无论从数量还是质量上都以往规划竞赛有 了显著提高，大概有2 0 个规划器参与了竞赛。竞赛以p d d l 2 1 为基础：一样 采用三级规划一a d l 、n u m e r i c 锄dd u r 酣o n 刮p i a n n j n g ，但同时又对p d d l 进 行了扩展，第一次增加了导出谓词( d e n v e dp r e d i c a 协s ) 和带时间属性的初始化文 字( t i m e di n j 日a ii i t e 例s ) ，形成p d d l 2 2 规范。d e r i v e dp 怕d i c a t e s 是指其值的订u e 或伺s e 不受任何a c l i o n 的影响，而是通过规划领域的其他谓词，经过一个推导 规则直接推导出来的。例如，在积木块世界，积木块x 在积木块y 的上方可表 示为：a b o v e 。y ) ，它是这样推导出来的： 什o n y ) 0 r ( e 砌s bz ：o n ) ( ，刁a n da b a 垤( z ，y ) ) 廿1 e na b o v e ( x ，y ) 含义：如果x 在y 的上面，或者存在另一个积木块z ，x 在z 的上面，z 在y 的上方，则在y 的上方。 即是说a b o v e ( x ，y ) 值的真假只受o n p ( y 或e ) ( i s t sz ：o n 代z ) a n d a b o 垤y ) 值真假的影响，而不受其他动作的直接影响。d e n v e dp 怕d i c a t 鹋不 能出现在a c t i