（计算机软件与理论专业论文）一致性规划的实时并行化规划解算法研究.pdf

摘要 智能规划是人工智能的一个重要分支，它主要涉及战略或行动顺序的安排和 实现，在很多领域都有重要应用。而一致性规划是指处理初始条件和动作具有不 确定性的规划，它极大的扩展了规划的在现实中的应用能力，使得规划器更加适 合于处理现实世界中的问题。而目前主流的一致性规划系统都是将一致性规划问 题转换为信念状态空间上的搜索问题来进行求解，这样使得求解效率大大提高， 但只能得到非并行规划解。 本文根据一致性规划的特殊情况，引入了独立动作和新的交互作用定义，给 出了一致性规划中的并行动作生成规则。在一个使用了启发式信念状态搜索的高 效一致性规划系统c f f ( c o n f o r m a n tf a s t f o r w a r d ) 的基础上进行改进而设计了一 个规划系统c f f p ，使用递归的实时并行化算法来生成并行规划。并且对c f f 的 增强爬山算法和“有利动作”剪枝策略进行修改以帮助生成并行规划。该方法成 功的使得信念状态空间搜索算法可以生成并行规划，在求解效率和规划解质量上 找到了一个较好的平衡点，得到了较好的应用价值。 在c f f 的基础上，使用c 语言对该算法进行了实现，设计了可以实时生成 并行规划解的规划系统c f f p 。该系统可以求解一致性规划问题和经典规划问题， 找到时间步较少的次优规划解，提高了规划解质量。实验结果表明它比起能生成 最优并行规划的一致性析取规划系统来可以用很小的代价生成接近最优的一致 性并行规划解，对一致性问题的求解质量有较大的改进。 关键词：智能规划；一致性规划；信念状态空问搜索；并行规划 a b s t r a c t i n t e l l i g e n tp l a n n i n gi sa ni m p o r t a n tb r a n c ho fa r t i f i c i a li n t e l l i g e n c e ，w h i c hm a i n l v r e l a t e dt ot h ea r r a n g e m e n t sa n da c h i e v ea b o u ts e q u e n c eo fa c t i o n so rs t r a t e g i e s i t s i m p o r t a n ti nm a n ya p p l i c a t i o na r e a s c o n f o r m a n t p l a n n i n gi s t h ep l a n n i n gi n u n c e r t a i n t ya b o u tt h ei n i t i a ls t a t ea n da c t i o ne f f e c t s i tg r e a t l ye x t e n d st h ep l a n n i n g a p p l i c a t i o ni nt h er e a lc a p a c i t ya n dm a k ep l a n n e ri sm o r eu s e f u lf o ra c t u a lp r o b l e m s p r e s e n t l y , t h em a i ni d e ao fm o s ts t a t e o f - t h e a r tc o n f o r m a n tp l a n n e r si st ot r a n s f b 啪a c o n f o r m a n tp l a n n i n gp r o b l e mi n t oas e a r c hp r o b l e mi nt h es p a c eo fb r i e f s t a t e s t h i s m e t h o dg r e a t l yi m p r o v e dt h e e f f i c i e n c y , b u to n l yg e t st h en o n p a r a l l e lp l a n n i n g s o l u t i o n i nt h i sp a p e r , w ei n t r o d u c et h en e w d e f i n i t i o no f i n d e p e n d e n ta c t i o na n di n t e r a c t i o n g w e nt h er u l e st og e n e r a t ep a r a l l e la c t i o ni nc o n f o r m a n tp l a n n i n g w ed e s i g na s y s t e m c a l l e dc f f po nt h eb a s i so fa ne f f i c i e n tc o n f o r m a n tp l a n n e rc f ff c o n f o n 1 1 a n t f a s t - f o r w a r d ) c f f pg e n e r a t e sp a r a l l e lp l a n sb yu s i n gr e c u r s i o no n l i n ep a r a l l e l i z a t i o n o fp a r t i a lp l a n s a n dm o d i f yt h ee n f o r c e dh i l l c l i m b i n ga n d “h e l p f u la c t i o n s ，o f c f ft o h e l pg e n e r a t ep a r a l l e lp l a n n i n g t h i sm e t h o dm a k e st h eb e l i e fs t a t e s p a c e s e a r c ha l g o r i t h mc a ng e n e r a t e p a r a l l e lp l a n n i n g ，f i n d sab a l a n c eb e t w e e ns e a r c h e f f i c i e n c ya n ds o l u t i o nq u a l i t y w eh a v e d e v e l o p e d a no n l i n e p a r a l l e l i z a t i o np l a n n i n gs y s t e mc f f pb vc p r o g r a r n m m gl a n g u a g eb a s e do nt h ec f f t h es y s t e mi s c a p a b l eo fs o l v i n gt h e c o n f o r m a n tp l a n n i n gp r o b l e m sa n dc l a s s i c a l p l a n n i n gp r o b l e m s ，f i n dt h el e s s t i m e 。s t e pa p p r o x i m a t eo p t i m a ls o l u t i o n ，a n di m p r o v et h eq u a l i t yo fp l a n n i n gs o l u t i o n s t h ee m p i r i c a lr e s u l t ss h o wt h a ti tc a ng e n e r a t eg o o dp l a nc l o s et ot h eo p t i m a lp a r a l l e l p l a n n i n gb ys m a l lc o s tc o m p a r e dt oc f f k e yw o r d s ：i n t e l l i g e n c ep l a n n i n g ；c o n f o r m a n tp l a n n i n g ；h e u r i s t i cb e l i e fs t a t e s s e a r c h ；p a r a l l e lp l a n s n 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取 得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文 中作了明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：到竺丝 同期： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：剑芝五笙 指导教师签名： e t 期：型幽肛目同 期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 东北师范大学硕士学位论文 己i吉 丁i口 智能规划( i n t e l l i g e n tp l a n ) 是人工智能的一个重要分支，它主要涉及战略或行 动顺序的安排和实现，在很多领域都有着重要应用。在过去十多年中，智能规划 研究领域取得了巨大的突破，使得现代规划系统无论在规划求解规模上还是在规 划求解效率上都有数量级的提高。因此研究人员开始扩展智能规划系统的所能处 理问题的范围，其中一个重要的研究方向就是将智能规划系统所处理的问题从确 定性问题扩展到不确定性问题。其中，一致性规戈j j ( c o n f o r m a n tp l a n n i n g ) 是当前对 于不确定性问题的规划研究的一个重要方面。不仅陆续出现了多个一致性规划系 统，而且第六届国际智能规划竞赛( 6 t hi n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o n2 0 0 8 ， p c 0 8 ) 将一致性规划列为比赛的一个子类。 所谓一致性规划( c o n f o r m a n tp l a n n i n g ) 是指在处理具有不确定性的问题时生 成不依赖于感知信息的规划，执行该规划只要实际处于任何一个被允许的世界状 态中就能达到目标川。具体说来它是在初始条件和动作效果不确定的情况下进行 的规划任务，且在规划执行过程中智能体没有感知能力。不管我们从初始世界中 的哪个部分出发，动作中哪个效果被执行，智能体执行所生成的规划都能到达目 标( 所有的目标命题都为真) 。而众所周知，一致性规划问题可以转换为信念 状态空间上的搜索问题，并且信念状态空间中的元素是可能的世界状态的集合。 除了早期的c g p ( s m i t h & w e l d ，1 9 9 8 崎1 1 和s g p ( w e l d ， a n d e r s o n ， & s m i t h ， 1 9 9 8 哺1 1 ，目前几乎所有的一致性规划系统都使用了成熟的启发式在信念状态空间 中搜索规划。这样就非常成功的提高了一致性规划系统的规划求解规模和规划求 解效率，但是只能得到非并行规划。所谓并行规划是指智能规划系统所生成的规 划能在一个时间点执行多个动作。并行规划在效率和能力上要优于只能在一个时 问点执行单个动作的时序规划，主要有两个原因：一、由于几个相互独立的动作 可以在一个时间步内执行，规划的搜索过程中就可以不用考虑这几个动作之间的 顺序；二、规划的并行化使得规划的时间步减少了。 而目前的一致性规划系统所使用的信念状态空间搜索可以看成是状态空间 搜索的一种，而且状态空间搜索在并行规划生成上有个缺陷：在状态空间搜索中 直接生成并行规划会导致搜索的每一步都是在动作集合上进行的，它需要规划系 统在并行动作的所有可能子集上分支搜索，这样就以指数方式增加了分支因子。 目前普遍的看法是高效生成最优并行规划通过使用析取规划系统是唯一的办法， 状态空间搜索规划系统生成最优的并行规划几乎是不可能做到的。状态空间搜索 规划系统在生成并行规划上的缺陷在以前的文献中已经被提到过。其中h a s l u m 和g e f f n e r ( 2 0 0 0 ) 提出了h s p 术p 用以在状态空间上进行后向搜索来生成并行规 东北师范大学硕士学位论文 划。其后他们提出了t p 4 ( h a s l u m & g e f f n e r ，2 0 0 1 年p 1 ，其中除了增加行动的持 续外，也改进了h s p * p 的分支模式，使其向规划图的方向增加。但是他们的实 验结果表明这些改进在处理问题规模上比起规划图的变形上还是有着较大差距。 其后r o m e os a n c h e zn i g e n d a 和s u b b a r a ok a m b h a m p a t i ( 2 0 0 3 ) 在规划器a l t a l t p 瞳。 中提出了一种增量实时并行方法，它也是在状态空间上进行后向搜索来生成并行 规划。该方法选择一个最有可能的动作，然后贪婪的增加所有可行的动作来并行 化选定的搜索分支，并且用一个叫做p u s h u p 的规划压缩程序来弥补掉在并行化 过程中的贪婪特性导致的次最优化晗1 。但是以上方法都是在状态空间上进行后向 搜索来处理并行化，本文提出一种在信念状态空间上使用递归增量实时并行化的 方法进行前向搜索来生成并行规划。该方法是应用在一个高效的一致性规划系统 c f f ( c o n f o r m a n tf a s t f o r w a r d ) 【1 1 的基础上。c f f 是2 0 0 4 年b r a f m a n 和h o f f m a n n 在f f ( f a s t f o r w a r d ) 阻1 的基础上进行扩展以处理一致性问题的规划系统。c f f 巧 妙的利用c n f 公式来保存信念状态空间，节省了大量的空间，并相应的对f f 系统的核心技术：增强爬山算法( e n f o r c e dh i l l c l i m b i n g ) ，基于松弛规划解 ( r e l a x e d p l a n ) 的启发式函数和“帮助动作 剪枝策略( h e l p f u l a c t i o n s ) 进行修改以 处理一致性问题，使得该规划系统在r o v e r s 和l o g i s t i c s 等多个域上有着突出的 性能。 针对已有的并行规划系统中的处理局限性和现有的一致性规划器所采用的 信念状态空间搜索技术，在现有的一致性规划系统c f f 的基础上设计了新的一致 性并行规划器c f f p 。本文的主要工作为以下几个方面： 1 根据一致性规划的特殊情况，引入了独立动作和新的交互作用定义，给出 了一致性规划中的并行动作生成规则； 2 对c f f 的增强爬山算法和“有利动作”剪枝策略进行修改以生成并行规 划； 3 利用c 语言开发了c f f p 规划器，达到了较好的实验效果，c f f p 规划器可 以处理具有并行动作的一致性规划问题。 本文由以下六部分组成： 第一章智能规划概述，介绍智能规划的相关概念、发展历史、具体应用及主 流的智能规划方法。 第二章规划图及并行规划，介绍规划图所处理规划问题的问题描述，规划图 的相关概念、并行规划的相关概念及一致性规划中的并行规划定义。 第三章一致性规划，介绍一致性规划的相关概念、信念状态空间搜索的基本 思想和主流方法。 第四章一致性规划的实时并行化规划解算法( o p c p ) ，介绍o p c p 算法的基 本概念、基本步骤以及具体算法。 2 东北师范大学硕士学位论文 第五章c f f p 规划系统的设计与实现，介绍了系统的丌发环境、系统的功能 设计、系统的工作流程并且列举了实例及实验结果。 3 东北9 币范大学硕士学位论文 第一章智能规划概述 1 1 智能规划的相关概念 智能规戈1 ( i n t e l l i g e n tp l a n ) 是人工智能的一个重要分支，它主要涉及战略或行 动顺序的安排和实现，在很多领域都有重要应用，常见的是用于控制智能代理， 自主机器人和无人驾驶车辆。针对不同的应用，规划的定义也有所不同，a u s t i n t a t e 在m i t 的认知科学百科全书中给出的定义为“规划是一种在使用该规划前 对将来的行为生成表示( 可能是部分的) 的过程，用以驱动和控制该行为。这个过 程的结果一般是一个有着时态和其它约束的动作集合，可被一个智能体或多个智 能体执行。 智能规划不同于经典控制论和分类问题，它所生成的解决方案是复 杂的，未知的，并且只能在多维空间中被发现和优化。 在智能规划的发展过程中，由于早期规划器求解能力的不足和研究的方便， 为了简化规划问题，早期的规划研究一般都做出如下假设，满足以下假设的规划 问题被称作经典规划问题n 引： ( 1 ) 环境状态的改变完全是由智能体的动作效果造成的，排除了其他可能的 影响和干扰； ( 2 ) 智能体的动作效果是完全确定的； ( 3 ) 智能体能够感知环境和它的动作效果。 经典规划要求知识的完整性，即确定的初始状态、目标状态及动作效果， 但现实世界中对规划问题的知识描述是不完整的，存在很多不确定性因素，很多 时候初始状态和动作效果是不确定的。这些现实情况使得经典规划与现实的应用 之i 日j 存在着较大差距。而最近这些年来，由于规划器求解能力的增强和规划研究 的进一步深入，人们开始将规划研究扩展到非经典规划问题中。对于经典规划问 题的种种约束进行突破。其中的一个研究目标就是在具有不确定性的问题上进行 规划。 1 2 智能规划发展历史 对智能规划的研究开始于2 0 世纪6 0 年代，最早可以追溯到1 9 5 6 年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 系统把领域知识与一般的搜索控 制信息相分离。n e w e l l 和s i m o n 提出一般问题求解( g s p ) 后，规划作为一般 4 东北师范大学硕士学位论文 求解问题技术的一种类型( 另外两种是搜索和推理) 引起了许多研究者的注意。 它主要强调求解问题要有一个合理、周密的方案来有效地求解。但由于当时各种 条件限制，有很多人还仅把它当作一个搜索问题。1 9 6 9 年g r e e n 通过归结定理 证明的方法来进行规划求解，并且设计了q a 3 系统n 引。1 9 7 1 年f i k e 和n i l l s s o n 的s t r i p s 系统【1 4 j 在智能规划中具有划时代的意义，他的突出贡献是引入了 s t r i p s 操作符的概念。在s t r i p s 系统中，初始条件是一个用来描述世界的初 始状态命题集，算子描述可执行的合法动作，目标是希望在规划结束时为真的事 实。算子的前提条件是命题的合取式，算子的结果和添加( 经算子运算后为真的 命题) 列表、删除列表( 经算子运算后为假的命题) 相连。这使规划可以非常容 易地进行描述和操作，使得原来很神秘的规划问题求解变得明朗清晰起来。此后， 大多数的规划算法都是在s t r i p s 表达形式的基础做了进一步的扩充，如 w l k s a t p l a n ，w a t p l a n ，b l o c k b o x ，m i p s ，0 p l a n ，g r a p h p l a n ，i p p ，s h o p ， a l t a l t 等。1 9 9 1 年s o d e r l a n d 和w e l d 等人设计了世界上第一个完备、完全、 系统的非线形规划器引，奠定了现代非线形规划系统的基础。1 9 9 7 年a v r i mb l u m 等设计的图规划系统g r a p h p l a n n 刚第一次采用了图的方式来解决规划问题。规划 图实际上是前向状态空间搜索树的一种压缩表示方法，并使用互斥等动作之间的 关系信息有效的减少了规划解搜索的难度【1 7 1 。此后利用了规划图思想的其它算法 不断出现，为了提高规划系统的效率，很多规划系统都开始采用启发信息。启发 式搜索的基本思想是：人为给定一个评估函数，对每个搜索状态进行计算，得到 每个状态的值，从而决定哪个状态较好。采用启发式搜索比较成功的有： h s p , f f , l p g 等。其中规划系统h s p ( h e u r i s t i cs e a r c hp l a n n e r ) 剐在a i p s 0 0 的规划 大赛上取得了比较好的成绩，它的与领域无关的启发信息的抽取是基于实现目标 的动作数量，对要求解的问题p 放宽到一个比较简单的问题p ，抽取技术就是 基于p 来评估。规划系统f f ( f a s t - f o r w a r d ) 1 在a i p s 0 0 的规划大赛上取 得了冠军，它是在前向的状态空间搜索中使用了启发式信息。与h s p 不同的是 它主要是通过忽略动作的删除效果建立一个放松的规划图来获得评估函数的值。 而规划系统l p g ( l o c a ls e a r c hf o rp l a n n i n gg r a p h s ) n 卅在i p c 4 ( t h e4 t hi n t e r n 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 ) 获得了冠军，它的评估函数主要是通过建立一个规划图的 动作子图，然后计算修改动作子图的代价来获得的。 1 3 智能规划的应用 智能规划研究的主要目的就是为了在现实中进行有效利用，使得很多问题可 以高效解决。而随着目前智能规划研究的逐步发展，智能规划的应用的范围和所 起的作用也在不断扩大。但是由于通用规划器理论上的实践难度，目前的通用规 5 东北师范大学硕士学位论文 划器还无法直接在现实的问题中应用。目前人们对于智能规划的现实应用主要是 针对不同的现实问题来应用较有针对性的规划技术，研发出具体应用的专有规划 器，比较典型的有： 1 3 1 工厂生产规划中的应用 智能规划在工厂生产规划中的应用从智能规划的较早时期就开始应用了，它 主要是和调度结合在一起，处理的问题主要集中与将时间和生产资料等有限资源 分配到不同的规划步骤上进行推理。 其中爱丁堡大学开发的基于层次规划的规划器o - p l a n 在多个工厂都得到了 具体应用，比如普莱斯沃特豪斯公司的软件采购规划和美洲虎汽车的装配规划 程序。另外的一些规划和调度系统在工厂的生产安排中都有较好的应用和表现。 目前智能规划在智能化工厂中的应用比以往有所扩张旧”是它可以包括从生 产设计到生成产品监测生产的一系列过程，它不只包括单个企业，还可以处理多 个企业之间的关系，例如：供应链、工作流管理和虚拟企业。智能规划在工厂生 产中的应用有效提高了工厂的智能化水平，增强了工厂的生产效率和资源利用 率，达到了良好的经济效益。 1 3 2 航空航天中的应用 智能规划的一个重要应用领域是航空航天，在这个领域的应用已经有了较长 的历史，也得到了较大的投入和回报。较早的基于o - p l a n 的o p t i m u m - a i v 和 p l a n - e r s l 分别应用于欧洲空间署的太空飞船装配和观测规划。其后n a s a 在不 同的任务领域应用了多个规划器，包括：哈勃太空望远镜的观测规划，航天飞机 的着陆过程调度安排系统，远程空问通讯网络中的d p l a n 规划系统，用于视觉图 像的处理上的v i c a r 系统等等。n a s a 还在1 9 9 9 年5 月1 7 同通过d s l 太空飞船 成功地发射了p a x ( 深空探测规划系统) 。它由三个部分组成：基于约束的规划 和调度系统、智能执行系统和基于模型的证明( 鉴定) 及修复系统。另外一个在这 个领域较为有名的规划系统为a s p e n ( 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 g e n v i r o n m e n t ) 乜规划系统，它获得了1 9 9 9 年美国宇航局的软件比赛优秀奖并且 广泛应用在进行外太空任务的宇航器上，包括c i t i z e ne x p l o r e r 、m a r s 0 1 和d s t 等宇航器。a s p e n 结合了宇航器操作约束、飞行规范、宇航器硬件模型、科学 实验目标和操作过程来自动生成较低层次的宇航器操作序列。 由于航空航天的特殊性，智能规划在这个领域一直有着重要的应用，预计在 将来会有更加广泛的应用。 6 东北师范大学硕士学位论文 1 3 3 智能机器人中的应用 智能机器人的一种定义是：具有人类所特有的某种智能行为的机器。 关于智能机器人的研究和应用跨越了多个学科和大量的研究方向，而智能规 划在智能机器人的研究和应用主要涉及领域有： 1 路径规划：是指机器人从开始位置到达目标位置的控制机制并且要满足 一定的( 静态或动态) 约束。 2 感知规划：主要是有关如何采集外部和内部信息的规划，例如：辨别物 体确定机器人位置对环境的观察。 3 任务规划：跟传统的规划问题相似，不过更加注重时间和资源的分配在 动态的环境、不确定的或部分已知的状态下进行规划。 4 规划交流：多个机器人之间和人与机器人之间如何进行信息交换，包括 询问信息和反馈信息两大部分。 智能规划在机器人学领域中具体的应用方向包括：环境模型的描述，控制知 识表示，路径规划，任务规划，非结构环境下的规划，含有不确定性的规划，协 调操作( 运动) 规划，装配规划，基于传感信息的规划，任务协调与调度，制造( 加 工) 系统中机器人的调度。 1 3 4 其他的大量应用 ： 智能规划在众多不同的领域中都有着广泛的应用，例如：软件模块集成；测 试用例生成；互动决策支持；基于规划的数据库接口；w e b 服务；网络信息集成； 运输规划等等。 1 4 主流规划方法 早期的规划方法中偏序规划占据了支配地位，其后1 9 9 5 年b l u m 和f u r s t 提 出的图规划算法成为了一个突破，使得智能规划算法在效率上得到了较大的提 高。目前主流的智能规划方法主要可以分为以下几类： 第一类是基于图规划的规划方法，它的代表性规划系统有：g r a p h p l a n 、 b l a c k b o x 憎引、i p p 和l g p 。 第二类是基于启发式搜索的规划方法，它的代表性规划系统有：h s p 、f f 。 第三类是基于逐步细化的分层规划方法，它的代表性规划系统有： s h o p 2 2 6 1 。 第四类是将规划问题转化为约束可满足问题来求解的规划方法，它的代表 性规划系统有b l a c k b o x 。 7 东j l i j l 范大学硕士学位论文 第h 类是将规划问题转化为模型检测问题来求解的规划方法，它的代表性 规划系统有m i p s l 2 7 1 。 8 东北师范大学硕士学位论文 2 1 规划问题描述 第二章规划图及并行规划 规划问题的表示主要包括：状态、动作和目标。而要使用规划算法来处理规 划问题就必须要有一种有着足够强表达能力和足够宽表示范围的描述语言。在经 典规划问题上，主要使用的是s t r i p 语言，其后随着规划器能力和访问的提升又 有着较大扩展。目前的规划研究所使用的大部分语言在规划域定义语言p d d l 瞄3 1 中进行了系统化规范和定义。 规划图算法所处理的规划问题( p l a n n i n gp r o b l e m ) 可以定义为以下四个集合： 1 一个操作( o p e r a t o r s ) 的集合； 2 一个对象( o b j e c t s ) 的集合； 3 一个初始条件( i n i t i a lc o n d i t i o n s ) 的集合，其中每个元素都是一个命题； 4 一个目标( g o a l s ) 的集合，其中每个元素都是一个命题，而且要求规划结 束时，这些命题必须是真命题。 其中目前的规划器求解的时候大多把一个规划问题分为两个文件，一个为域 文件，主要包括操作的集合，如图2 1 描述了积木世界问题的操作集合： 图2 - 1 积木世界问题的操作集合 另外一个为问题文件，主要包括对象集合，初始条件集合和目标集合，如图 2 2 描述了问题的对象，初始条件和目标集合： 9 东北师范大学硕士学位论文 图2 - 2 积木世界问题的对象，初始条件和目标集合 以上两个图所描述的积木世界问题为例，此问题的四个集合相应为： 1 操作的集合：s t a c k ，u n s t u c k ，m o v e 。 2 对象的集合：a ，b ，c 。 3 初始条件的集合：o nca ，o n t a b l eb ，o n t a b l ea ，c l e a rc ，c l e a rb 。 4 目标状态的集合：o nab ，o nbc 。 2 2 规划图的相关概念 1 动作 一个完全实例化的操作叫做动作( a c t i o n ) 。这是由于规划图只能处理命题规 划问题，所以处理规划问题前需要将操作实例化为动作。如s t a c k 操作中s t a c ka c 就是动作；再如m o v e 是操作，而m o v ebc 就是动作。动作的执行是指：把动作 添加效果中的命题添加到环境中，把动作删除效果中的命题从环境中删除掉。规 划的任务就是在给定规划问题的初始条件之后，对对象实施一系列动作，使问题 目标得以实现。 2 n o o p 动作 对一个命题不做任何改变的特殊动作就称作n o o p 动作或f r a m e 动作。这是 由于规划图中需要一种表示非行动的方式，且该方式应该和正常动作一样表示。 也就是情景演算中框架公理在规划图中的等价表示。如上面积木世界问题中的： o n - t a b l eb 经过n o o p 操作后，命题仍为o n t a b l eb 。n o o p 动作在形式化上很 有用，它相当于数学加法中的0 ，乘法中的1 等等。 3 规划图 规划图是由两种结点交替出现、并由三种边所连接组成的图。 两种节点分别是命题结点( p r o p o s i t i o nn o d e ) 和动作结点( a c t i o nn o d e ) 。 三种边是前提条件边( p r e c o n d i t i o ne d g e ) 、添加效果边( a d de d g e ) 和删除效果 边( d e l e t ee d g e ) 。 4 规划图的“稳定” 在规划图扩张阶段，存在一个最小整数t ，如果对于任何正整数m ，l ，时 间步m 的命题集合与时间步, 的命题集合总相同，时间步m 与时间步n 的动作集 合也相同，而且互斥关系相同。在这种情况下，就称规划图从第咒时间步起已经 1 0 东北师范大学硕士学位论文 稳定。 5 有效规划 设有一个动作的集合，其中的每个动作都被指明其被执行的时问步；在同 一个时f b j 步中被执行的任何两个动作都是不互斥的，所有的问题目标在最后的时 间步均为真，那么，就称这个动作集合为一个有效规划( v a l i dp l a n ) 。 2 3 并行规划的相关概念 定义1 规划任务( p l a nt a s k ) ：一个规划任务p 是一个三元组( 0 ，i ，g ) ，其中 o 是动作的集合，i 是世界的初始状态，g 是目标的描述。 定义2 全序规划( t o t a l - o r d e rp la n ) ：给定一个规划任务p = ( o ，i ，g ) ，一个 全序规划是一个动作序列s = ，且可以另外使用元组 标记，其中1 j ，k n ，当且仅当j k 成立时a j _ a 。才成立。且从i 开 始执行该动作序列最后所到达的状态满足g 中的目标描述。 定义3 偏序规划( p a r t i a 卜o r d e rp l a n ) ：给定一个规划任务p = ( 0 ，i ，g ) ，一 个偏序规划是一个二元组s = a ，_ ，其中a 是动作集合o 的子集且 是a 上 的一个严格偏序关系。且对于一 的每个拓扑排序 ，从i 开始执行 a ，_ 最后所到达的状态都满足g 中的目标描述。 从以上定义可以看出，一个全序规划的动作必须以指定的顺序执行，而一个 偏序规划罩未排序的动作可以以任意的顺序执行。从这方面来看偏序规划似乎隐 藏的包括了并行规划的情况，但实际并非如此，虽然偏序规划里未排序的动作可 以以任意的顺序执行而该规划仍然有效，但如果这些未排序的动作同时执行则无 法保证该规划仍然有效。这是由于一个偏序规划实际上是一个全序规划集合的压 缩表示，它所包含的那些动作序列实际还是全序的。因此我们接下束介绍并行规 划的定义。 定义4 并行规划( p a r a l l e lp l a n ) ：给定一个规划任务p = ( 0 ，i ，g ) ，一个并行 规划是一个三元组s = a ， ，其中 a ，_ 是偏序规划且# 是a 上的一个 反自反对称关系，# 描述了动作间是否可以同时执行。 该定义隐含的表示了并行规划实际上是并不是一个动作的序列，而是一个动 作集合的序列。在给定的时间步上的那个动作集合中的动作可以同时执行，且同 时执行和以任意顺序执行得到的是一样的结果。因此我们开始考虑对于个时间 步上面的动作集合内的动作之间的关系，就引入了相互独立动作的定义。 定义5 相互独立动作( i n d e p e n d e n ta c t i o n s ) ：要使两个动作a 和a l 为相 互独立动作，当且仅当在一个状态s 同时执行两个动作和在同一个状态s 以任意 的线性化顺序执行动作都到达同一个状态s 4 l 。 东北师范大学硕士学位论文 该定义则隐含的表示了如果动作a 和a l 的执行中没有任何部分重复才可以 并行处理换句话说，就是两个动作的前提和效果之间没有交互作用。 定义6 交互作用( i n t e r a c t i o n ) ：两个动作a 和a l 之问没有交互作用的充 分条件为： ( ( p r e ( a ) + e f f e c t s ( a ) ) n ( p r e ( a 1 ) + e f f e c t s ( a 1 ) ) ) = o 因此，我们考虑在一个时间步内所能包含的动作集合时，只要求在动作之间 相互独立，也就是要求动作之间没有交互作用。但在一致性规划中情况有所不同， 为了使一致性规划能够在没有感知能力的情况下执行动作。规划系统引入了 g e n e r o u s 动作执行语义：假定在规划的执行过程中，动作有未满足的前提并不 导致规划失败而是忽略该动作。因此一致性规划系统在处理世界状态中的不确定 性中出现了一些前提有交集或效果有交集的动作，而且这些动作的并行执行到达 的信念状态和以这些动作的任意线性化顺序执行这些动作所到达的信念状态一 致。因此我们在算法中使用了另外一个更严格的充分条件，引入一个新的定义。 定义7 严格交互作用( s t r i c t l yi n t e r a c t i o n ) ：两个动作a 和a 1 之间没有 严格交互作用的充分条件为： ( ( c o n ( a 1 ) na d d ( a 2 ) ) u ( c o n ( a 1 ) nd e l ( a 2 ) ) u ( a d d ( a 1 ) nc o n ( a 2 ) ) u ( a d d ( a 1 ) nd e l ( a 2 ) ) u ( d e l ( a 1 ) n c o n ( a 2 ) ) u ( d e l ( a 1 ) na d d ( a 2 ) ) ) = a 该条件就是在前一个充分条件的基础上去除了添加效果的交集和删除效果 的交集。这是因为在信念状态空间搜索中两个动作有着同样的添加效果或同样的 删除效果并不影响两个动作的并行。 1 2 东北师范大学硕士学位论文 3 1 一致性规划概述 第三章一致小i q 止- 规划弟二早一烈。就刈 一致性规划( c o n f o r m a n tp l a n n i n g ) 是指在初始条件和动作效果不确定的情 况下进行的规划任务，且在规划执行过程中智能体没有感知能力。 在智能规划的发展过程中，由于规划器求解能力的不足和研究的方便，为了 简化规划问题，早期的规划一般都作出如下假设 ( 1 ) 环境状态的改变完全是由智能体( a g e n t ) 的动作效果造成的，排除了其他 可能的影响和干扰； ( 2 ) 智能体的动作效果是完全确定的； ( 3 ) 智能体能够感知环境和它的动作效果。 人们把具有上述假设的规划问题叫做经典规划问题。 最近这些年来，由于规划器求解能力的进步和规划研究的进一步深入，人们 开始将规划研究扩展到非经典规划问题中。对于经典规划问题的种种约束进行突 破。其中的一个研究目标就是在具有不确定性的问题上进行规划。 在不确定性上的规划是一个相当难的任务。在这样的问题上可分为两种情 况。如果智能体有感知能力，则可以使用可能性规：怠l j ( c o n t i n g e n tp l a n n i n g ) ，它所产 生的规划可以根据感知动作的结果有条件的执行确定的分支。而智能体没有感知 能力，则必须使用一致性规戈j j ( c o n f o r m a n tp l a n n i n g ) ，它产生的规划必须达到不管 实际的世界状态是哪种情况都能顺利到达规划目标1 5 。 目前可用的规划器在处理已知环境的规划任务时一般是离线的，也就是规划 解必须在被执行和评估前获得。而在处理动态未知环境的规划任务时一般是使用 在线修改策略，也就是规划解一般采用迭代实验和试错的方法来进行修正。而一 致性规划处理的规划问题稍有不同，它面对的环境虽然是未知的，但不是动态变 化的。因此它也是离线进行规划求解的，就是规划解必须在被执行和评估前获得。 一个典型的规划器一般接收3 个输入：世界初始状态的一个描述，想要达到 的目标的一个描述，一个可用动作的集合。这些输入一般用一个形式化语言来描 述，比如s t r i p s 。在一致性规划中，接收的3 个输入与经典的规划不同的是初始 状态的描述和可用动作的集合。世界的初始状态的描述中存在一些未知的状态， 而可用动作中存在一些不确定的效果。 1 3 东北师范大学硕士学位论文 3 2 一致性规划求解算法 实际上，一致性规划可以转换成在信念状态空间中的一个搜索问题，而这个 信念状态空间的元素是所有可能的世界状态的集合。这样的话，一个真实的世界 状态的不确定性就被转换成了在这一时刻所有可能的世界状态的集合【5 。经过这 样的转换以后，影响一致性规划能力和规划效率的主要有两方面：一个是信念状 态空间的表示，一个是信念状态空间中的搜索算法。由于随着不确定状态的增加， 信念状态空间随之发生指数爆炸，如果按经典规划的方法将其放入内存进行计算 的话，规划器只能处理非常小的一致性问题。因此目前一致性规划算法的发展变 化主要针对于信念状态空间的表示。 3 2 1 一致性图规划求解算法 最早的一致性规划器c g p 哺1 直接在规划图的基础上添加了处理不确定性的机 制来处理一致性问题，列举出所有的可能世界状态来表示初始状态的不确定性。 在列举出所有的可能世界状态后用图规划算法为每个可能的世界状态建立一个 独立的规划图。 如果c g p 在所有的规划图中都达到了目标状态，则开始试图提取一致性规划 解。在提取过程中还需要考虑不同世界状态的规划图之间的交互作用和这些规划 图中的命题和动作的互斥关系，因此效率较低。而且c g p 为每个可能的世界状态 建立一个独立的规划图占用了大量的存储空间，处理能力非常弱。 3 2 2 通用规划工具中的一致性规划算法 在2 0 0 0 年b o n e t 和g e f f n e r 的g p t ( g e n e r a lp l a n n i n gt 0 0 1 ) 凹1 是一个通用规划 框架，能够处理的规划问题包括：概率规划，一致性规划，条件规划以及条件 概率规划。它处理一致性规划的算法中直接用一个数据结构列出了所有可能的世 界状态，然后使用排序网络和公理剪枝方法来减少需要搜索的信念状态空间，其 后结合g p t 的启发式使用a 木算法搜索规划解。但是由于处理后的信念状态空间 还是相当的大，所以g p t 只能处理比较小的一致性规划问题。 3 2 3 基于模型检测的一致性规划算法 在2 0 0 1 年b e r t o l i 和c i m a t t i 的m b p ( m o d e lb a s e dp l a n n e r ) 船5 1 中，它使用二元 决策表b d d s ( b i n a r yd e c i s i o nd i a g r a m s ) 来表示信念状态空间。m b p 有两种不同 的方法用以搜索信念空间来求解一致性规划问题，一种是直接使用宽度优先搜索 1 4 东北师范大学硕士学位论文 算法，另外一种是使用了启发式的搜索算法。二元决策表的使用有效的节省了信 念状态空间，使得m b p 在处理一些一致性规划问题的时候取得较好的效果，但 是部分一致性规划问题使用二元决策表柬表示信念状态空间仍然占用了相当大 的空间，使得求解能力受到限制。 3 2 4 基于隐含信念状态表示的一致性规划算法 在2 0 0 4 年b r a f m a n 和h o f f m a n n 的c f f 使用了与其他一致性规划器不同的 方法来隐含的保存信念状态空间，为了节省空间，它并不直接保存所有的信念状 态，而是将所有信念状态保存为初始的信念状态加上到达目前信念状态的动作序 列。因此c f f 中整个信