（计算机软件与理论专业论文）基于conant领域的一种规划策略.pdf

摹- pc o n f o r m a n t 领域的一种规划策略摘要 论文题目： 专业： 硕士生： 指导教师： 基于c o n f o r m a n t 领域的一种规划策略 计算机软件与理论 许鸿宇 吴向军副教授 摘要 智能规划是近几年人工智能领域中的一个研究热点，由于在工业实践以及理 论研究有着非常重要的地位，智能规划受到越来越多的学者关注。本文的研究是 针对智能规划中一种不确定性规划- - - c o n f o r m a n t 规划进行研究的。确定性是一种 对客观世界简单化的描述，而生活中许多问题都具有其不确定性，传统经典的智 能规划模型已经不能满足现实世界的需求，不确定性规划的出现使得智能规划领 域更加贴近于现实。 本文先对现有的智能规划策略进行研究，发现该策略针对确定性领域。主体 以领域知识的提取策略为出发点，先把其问题描述的不确定性信念状态转换成为 经典的确定性描述，然后深入研究c o n f o r m a n t 规划中的规划树结构及其信念状 态间的关系，提出一种基于c o n f o r m a n t 规划的规划策略，从而扩展了其规划求 解的能力。另外，本文采取了一种特殊的数据结构一规划树来存储规划信息，通 过候选谓词的选择指导规划，同时也从崭新的角度提出一种规划求解策略。该策 略在处理确定性规划的同时，能更好地兼容处理c o n f o r m a n t 规划。 最后本文通过实验来展示该规划策略的扩展求解能力。本文在给出的规划策 略基础上，采用c 语言进行实现，设计了智能规划系统c o n f o r m a n t s b s ，并用国 际智能规划大赛中的比赛用例对系统进行了验证。实验证明规划系统 c o n f o r m a n t s b s 能有效地求解c o n f o r m a n t 规划，在求解效率和求解质量上都有着 一定的优势。 关键字：智能规划，c o n f o r m a n t 规划，信念状态，规划树 基于c o n f o r m a n t 领域的一种规划策略 a b s t r a c t t i t l e ：a p l a n n i n gs t r a t e g yb a s e d o nc o n f o r m a n tp l a n n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：h o n g y ux u s u p e r v i s o r ：a s s o c i a t ep r o f x i a n g j u nw u 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 r e s e a r c hh o ts p o to fa r t i f i c i a li n t e l l i g e n c ei nr e c e n ty e a r s a sp l a n n i n gh a sav e r yi m p o r t a n tp o s i t i o ni ni n d u s t r i a lp r a c t i c ea n dt h e o r e t i c a l r e s e a r c h , a ni n c r e a s i n gn u m b e ro fs c h o l a r sc o n c e r n e da b o u ti t t h i st h e s i si sa i m e da t t h eu n c e r t a i n t yp a r to fp l a n n i n g ，w h i c hi sn a m e da sc o n f o r m a n tp l a n n i n g d e t e r m i n a b i l i t yi sas i m p l i s t i cd e s c r i p t i o no ft h eo b j e c t i v ew o r l d h o w e v e r , w i t h t h e u n c e r t a i n t i e so ft h ep r o b l e m si no u rl i v e s ，t h et r a d i t i o n a lm o d e lo fp l a n n i n gc a nn o l o n g e rm e e tt h en e e d s a sar e s u l t ，t h eu n c e r t a i n t yp l a n n i n gw h i c hm a k e sp l a n n i n g c l o s e rt ot h er e a l i t yi sa t t r a c t i n gm o r ea n dm o r ea t t e n t i o n t h i st h e s i s f i r s t l ya n a l y z e st h ee x i s t i n gp l a n n i n gs t r a t e g yw h i c hi s f o rt h e d e t e r m i n i s t i cp l a n n i n g ，a n dt h em e t h o do fe x t r a c t i n gd o m a i nk n o w l e d g ei sp r e s e n t e d t oe x p a n dt h ep r o b l e ms o l v i n gc a p a c i t y , i nt h es t r a t e g yo ft h i st h e s i sf o rc o n f o r m a n t p l a n n i n g ，t h eb e l i e fs t a t ei sf i r s t l yt r a n s f o r m e dt ot h ec l a s s i cd e t e r m i n i s t i ct y p e a f t e r t h a t ，t h eu s a g eo fp l a n n i n gt r e ea n dt h er e l a t i o na m o n gb e l i e fs t a t e sa r ea n a l y z e d a n d f i n a l l y , t h ep l a n n i n gs t r a t e g yb a s eo nc o n f o r m a n tp l a n n i n g i s p r e s e n t e d ，w h i c h i m p r o v e st h ep r o b l e ms o l v i n ga b i l i t y , c o m p a r i n gw i t hs t e p b y s t e p i nt h i st h e s i s ， p l a n n i n gt r e ei su s e df o rs t o r i n gi n f o r m a t i o n a n dc a n d i d a t ep r e d i c a t es e l e c t i o ni s u s e dt od i r e c tt h ep l a n n i n gp r o c e d u r e ，w h i c hp r e s e n t sas t r a t e g yf r o mad i f f e r e n t p e r s p e c t i v e t h es t r a t e g yc a nn o to n l yd e a lw i t hd e t e r m i n i s t i cp l a n n i n gb u ta l s o b e a b l et oh a n d l et h eu n c e r t a i n t yp a r tb e t t e r t h el a s tp a r to ft h i sp a p e rp r e s e n t st h er e s u l t so fo u re x p e r i m e n tt op r o v et h e p r o c e s s i n gc a p a c i t yo fm ym e t h o d b a s e do nt h eg i v e np l a n n i n gs t r a t e g y , ap l a n n i n g s y s t e mn a m e dc o n f o r m a n t s b si sd e s i g n e du s m gc a n dt h et e s t i n gd o m a i ni nt h e i 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 ni s u s e dt ov e r i f yc o n f o r m a n t s b s i nt h e i 基丁c o n f o r m a n t 领域的一种规划策略a b s t r a c t e x p e r i m e n t ，c o n f o r m a m s b si sp r o v e dt oh a v eap l a n n i n gw i t hh i g hq u a l i t ya n d e f f i c i e n c y k e yw o r d s ：i n t e l l i g e n tp l a n n i n g 、c o n f o r m a n tp l a n n i n g 、b e l i e fs t a t e 、p l a n n i n gt r e e i v 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 许多呜孑 日期：矽孵岁月1 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 l 夕 玎 基于c o n f o r m a n t 领域的一种规划策略第1 章引言 第1 章引言 1 1 智能规划的历史和现状 智能规划一直是人工智能研究热点之一，也是人工智能领域中最早受关注的 方向之一。1 9 5 7 年，n e w e l l 和s i m o n 提出了第一个规划系统g e n e r a lp r o b l e m s o l v e r t u ( 简称g p s ) ，并在后来由e r n s t 和n e w e l l 改进。它彻底地模仿人类的行 为，把包含有g p s 结构的任务独立系统和包含有领域知识的系统分离开来，并 利用暴力搜索和启发信息来搜索问题空间。虽然从理论上讲，g p s 可以解决大部 分甚至是所有规划问题，但是搜索效率过低和繁琐的操作限制了它的应用。1 9 6 9 年，g r e e n 提出了基于定理证明的规划系统q a 3 1 2 ，但由于当时定理证明技术不 够先进，q a 3 没有得到进一步的发展。 1 9 7 1 年，斯坦福研究所的f i k e 和n i l s s o n 设计出了s t r i p s 规划系统1 3 ，历 史上具有里程碑意义的规划系统之一，其中的思想和方法至今仍被众多学者沿用 和借鉴。在s t r i p s 域中，状态和动作都是公式的集合，状态的改变通过动作在 状态中增加和删除公式来实现。这个理论的提出使得原来神秘的智能规划问题的 描述变得规范了，很大程度上推动了智能舰划的研究。在接着的十年内，学者们 研究智能规划的热情比较高涨，相继出现a b s t r i p s 、p l a n e xm a c r o p s 、 h a c k e r 、w a r p l a n ，h e a r s a yi i ，i n t e r p l a n ，n o a h ，r e p l a n n i n g 、 m o l g e n 、n o n l i n 等规划系统。这个时期内，学者们普遍认为智能规划问题 都可以用定理证明的方法来解决，直至2 0 世纪8 0 年代中期c h a p m a n 设计的 t w e a k t 4 】规划系统的出现。c h a p m a n 详细分析了利用定理证明解决智能规划问 题的方法，提出了著名的模态真值标准( m o d a lt r u t hc r i t e r i o n ) 理论，令人们认识 到用定理证明方法来解决规划问题是十分有难度的。在往后的几年内，智能规划 领域进入了短暂的低潮。 进入2 0 世纪9 0 年代，三项技术的相继提出让智能规划研究进入高潮。1 9 9 1 年，s s o d e r l a n d 和d w e l d 等人设计的非线性规划系统s n l p t 5 1 ，奠定了非线性 规划方法的基础。1 9 9 2 年，k a u t z 和s e l m a n 提出用可满f f ：( s a t ) 方法【6 】来求解智 基于c o n f o r m a n t 领域的一种规划策略第l 章引言 能舰划问题，展现了解决规划问题新的思路；它把规划问题公式化为一个命题可 满足问题，并通过约束可满足问题求解算法的突破来解决智能规划问题。在随后 的第一届规划系统大赛上，基于该思想的规划系统b l a c k b o x 7 1 凭借着出色的效率 夺得冠军。1 9 9 5 年，a l b l u m 和m l f u r s t 教授提出了一种强大的可达搜索空 间一规划图以及相应的图规划技术f 8 1 。该方法对后来的研究产生了十分深远的影 响，很多学者都在此基础上研究智能规划问题的求解并提出相应改进，例如 i p p 9 、s t a n 和l p g t l 0 1 。图规划技术引起了学者广泛关注的一个原因是其性能 较先前的规划空间规划系统有显著的改进，另一个更重要的原因是图规划结构具 有很大的可扩展内涵，为学者的研究提供了一条宽广的道路。 19 9 8 年，b l a ib o n e t 和h e c t o rg e f f n e r 提出了启发式搜索技术【1 1 】，其主要思 想是在求精、分支、剪枝和选择子程序有效地组织搜索空间并引导搜索的进行， 从而提高程序搜索效率。在1 9 9 9 年的人工智能规划会议( a i p s 9 9 ) 上，b o n e t 和 g e f f n e r 设计的h s p 1 1 】规划系统详细地阐述了基于距离估计的启发信息在规划中 的作用，并取得了骄人的成绩。另外，那些采用了启发技术的规划系统总体表现 要明显优于其他规划系统。h o f f m a n n 受到启发技术的启发，设计了快速前向规 划系统f f t l 2 l 。它通过计算启发估值h ，并对当前状态的后续状态进行剪枝，同 时对爬山算法进行修改使之避免陷入局部最小值。在第二届规划系统比赛中，十 六个参赛的规划系统中就有十一个采用启发技术，包括被评为最佳的t a l p l a n n e r 和f f ，以及排名其次的s t a n 、h s p 2 、m i p s t b 】。 最近几年，学者们对智能规划的研究已经深入到其他领域，其中最主要的一 个领域就是不确定性领域，如概率规划和c o n f o r m a n t 规划。2 0 0 4 年，概率规划 领域成为第四次规划系统大赛中的正式比赛领域；而在第五次规划系统大赛【1 4 】 中，c o n f o r m a n t 规划也成为其中一个比赛项目，由此可见不确定性规划受到越来 越多的关注。 截至2 0 0 8 年末，规划系统大赛已经举行了六届，每次给智能规划研究带来 新的视角和方法。由于智能规划有着其广阔的应用，它将仍是人工智能领域研究 热点之一。 2 基于c o n f o r m a n t 领域的一种规划策略第1 章引言 1 2 智能规划的应用 智能规划主要应用于机器人系统、智能企业和商业系统，特别是在国防和空 间技术上得以应用，能使自动化系统的灵活性、健壮性得到提高。1 9 9 9 年，n a s a 在航天器深度空间一号( d e e ps p a c el ，d s i ) t 1 5 1 中使用了智能规划技术，是智能规 划走向实际运用的里程碑。d s l 中有一套基于趟技术的软件系统一r a ，它用于 规划、执行和监控航天器的行为。r a 具有健壮的意外处理机制，并和地面控制 进行交互。地面控制发送作业后，r a 能将其分解为基本的航天操作指令；也可 以发送规划目标，r a 会产生一个规划并自动执行。美国宇航局在同期开发了 a s p e n t l 6 1 ( 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 ) 任务规划：与传统的规划问题类似，不过更加着重研究时问和资源的分 配，在动态的环境、不确定的或部分已知状态的条件下的规划。 ( 2 ) 路径规划：指在机器人从一个初始位置如何走到目标位置，同时要满足 动态约束。 ( 3 ) 感知规划：主要研究如何采集外部和内部信息，例如：辨别物体、确定 机器人所在位置、对所处环境的感知等等。 ( 4 ) 通信规划：主要研究多个机器人之间、人与机器人之间的信息交换，包 括询问信息和反馈信息两大部分。 在企业生产过程中，智能规划也有着重要作用。例如在工厂作业调度安排问 题上，利用工厂有限的生产资源，满足已知的约束条件，合理安排工厂各部分的 工作顺序，从而使得工厂高效运转，获得更大的效益。企业生产规划主要有两方 面：流程规划和调度安排规划。流程规划是指把工厂的某项生产任务转化为一系 列的生产工作指令；调度安排规划是指根据客户要求交货的时间来安排工厂生 3 基于c o n f o r m a n t 领域的一种规划策略第1 章引言 产，从而达到按时出货的目的，这也就是我们常说的e r p 作：、l k 调度。 在商业领域，智能规划得到更广泛的应用。i b m 公司的d i s c o v e r y l i n k 系统就 是基于查询规划而开发出来的。查询规划是数据采集规划的一种，数据采集规划 是指根据所需领域的内容，从特定的途径，如网络，收集信息并合成后加入到该 领域中，其实质是把利用机制把信息进行重新组织和理解。调度规划也是智能规 划应用的一个主要方面。美国联邦太平洋铁路( u n i o np a c i f i cr a i lr o a d ，u p r r ) 公 司拥有三万一千多英里的铁路线，覆盖太平洋沿岸2 4 个州。u p r r 手工进行了部 分铁路规划的编制，但是效率十分低下，造成了巨大浪费。1 9 9 6 年1 月，m u r p h y 等人为u p r r 设计了一套铁路自动调度系统( r a i lt r a i ns c h e d u l e r , r t s ) ，根据需要 产生高效而低费用铁路规划。u p r r 每年因此节省了5 0 万美金。 1 3 智能规划系统的分类 智能规划系统的分类根据标准的不同而不同，我们介绍其中一种划分方法： 经典规划和非经典规划。下面我们先介绍八个在规划模型上的假谢1 7 1 ，令是一 个状态转移系统： 假设a 0 ( 有限的) ：系统的状态是一个有限集合。 假设a i ( 完全可观察的) ：系统是完全可观察的，即系统中的状态在任何时 刻都是可以认识的。 假设a 2 ( 确定的) ：系统是确定性的，即如果一个动作是可以应用于状态， 那么它应用于该状态后，系统将处于单一的状态中。 假设a 3 ( 静态的) ：系统不受外部事件的影响，并将保持不变，除非有明确 的控制转换发生。 假设a 4 ( 受限的目标) ：规划系统只求解显示的受限目标，不考虑其他状态约 束，如系统规划要求避免某个状态，或者满足某个状态顺序。 假设a 5 ( 线性序列) ：规划出来的问题解是一个线性序列。 假设a 6 ( 忽略时间) ：系统中的状态和动作都没有时间概念，动作和事件都是 瞬时的状态转换；规划目标没有时间约束。 假设a 7 ( 脱机规划) ：规划系统只按照任务的初始状态和目标状态进行规划， 4 基于c o n f o r m a n t 领域的一一种规划策略第l 章引言 忽略状态转移系统当前发生的变化。 满足上述八个a 0 a 7 限制的状态转移系统被称为受限的状态转移系统。经 典规划是指基于受限的状态转移系统的规划。 状态空间【1 7 1 和规划空间f 1 7 1 是经典规划两个经典的搜索空间。状态空间搜索算 法对状态空间的子集进行搜索：每个结点对应着一个状态，每条弧对应着一个状 态转换，规划求解就是搜索到从初始状态空间到目标状态空间的路径。规划空间 和状态空间的不同在于：搜索空间和对规划求解的定义。规划空间的搜索空间结 点是部分具体化的规划，弧是结点的求精操作，规划的过程就是从空的规划结点 出发，然后进行逐步求精，最后达到满足目标的规划结点。在规划空间中，规划 被定义成一个具有变量绑定约束和顺序约束的操作集合，它不一定对应一个动作 序列。规划过程有两个操作：( 1 ) 选择动作；( 2 ) 对选择的动作进行排序。 非经典规划是指规划问题不满足上述八个a 0 ，a 7 限制。在现实世界中，一 个动作执行后，效果可能是不确定的；在执行过程中，可能会遇到外部事件的干 扰。因此非经典规划能更好地刻画客观世界。概率规划就是非经典规划研究热点 之一，它主要描述动作执行后，会以一定的概率产生效果的规划问题。 在概率积木块世界中，执行一个p i c k u p 动作，会有7 5 的几率成功，还有 2 5 的几率失败，物体会从手中掉到桌面。形式语言定义如图1 1 ( ：a c t i o np i c k - u p ：p a r a m e t e r s ( ? bl ? b 2 一b l o c k ) ：p r e c o n d i t i o n ( a n d ( n o t ( = ? b l ? b 2 ) ) ( e m p t y h a n d ) ( c l e a r9 b 1 ) ( o n ? b l ? b 2 ) ) ：e f f e c t ( p r o b a b i l i s t i c 3 4 ( a n d ( h o l d i n g ? bd ( c l e a r ? b 2 ) ( n o t ( e m p t y h a n d ) ) ( n o t ( c l e a r ? b 1 ) ) ( n o t ( o n ? b l ? b 2 ) ) ) 1 4 ( a n d ( c l e a r9 b 2 ) ( o n - t a b l e9 b 1 ) ( n o t ( o n ? b l ? b 2 ) ) ” ) 图1 1 概率积木块世界动作p i c k - u p 的形式语言定义 下面我们简单介绍一下近二十年内几种不同策略的智能规划系统。 5 基于c o n f o r m a n t 领域的种规划策略第1 章引言 1 3 1 基于可满足性( s a t ) 问题的规划系统 基于s a t 的规划系统主要思想是将规划问题表示为可满足性问题，把规划问 题对应于一个著名问题，该著名问题已经有成熟的求解方法，只要把著名问题的 解映射到原规划问题即可。具体的步骤主要有： 采取种方法将规划问题转换为一个命题公式 对命题公式的变量进行赋值，通过可满足判定过程来判定公式是否可满足， 并在从该赋值抽取出规划问题的解 在第一步中需要用到编码方法，而编码方法的不同将影响命题变量和可满足 性问题子旬的数量，进而影响着了可满足判定过程和整个规划系统的求解效率。 一般我们所说的编码包括两个方面：动作编码和框架公理编码。动作编码一般有 四种：位编码、正则编码、简单操作分裂编码和重载操作分裂编码；框架公理也 有两种：经典框架公理和解释框架公理。表1 1 【1 7 】是不同编码方式在最坏情况下 所得公式的长度 表1 1 集中不同编码的长度 动作框架公理变量数 经典 o ( n lf i iall 0 9 2la i ) 位编码 解释 o ( - ifi iail o g 穸la1 ) 经典 o ( n l f i l a i ) 正则编码 解释 o ( n i f i la l + ，z l 彳1 2 ) 经典 0 ( - lf i ial 以+ 聆lal 掣i ) 简单操作分裂 解释 o ( nl ，f 甜+ 行( 1ala 0 ) 2 ) 经典 o ( n lf i iai4 + 聆iai 管) 重载操作分裂 解释 o ( n lfi ( 1 么i4 ) 2 + ，lifi l 么l 硝1 ) 表1 1 中刀是规划步数；iel 是状态谓词数；ifh p i ldl4 ，其中lp i 是谓 词符号数，ldl 是常量数，4 是谓词最大元的数目；ial 是基动作数； 6 基于c o n f o r m a n t 领域的一种规划策略 第1 章引言 iai - - - t0i idi4 ，ld l 是操作数，鸽是操作最大元的数目 这种类型的规划系统主要有hk a u t z 等人开发的b l a c k b o x l 7 1 18 1 。 1 3 2 基于图规划技术的规划系统 这种规划系统主要依赖被称为规划图的结构。规划图是这样的一种结构：( 1 ) 它有两种类型结点：状态结点和动作结点。( 2 ) 有三种类型的弧：前提条件弧、 正效果弧和负效果弧。前提条件弧是从状态结点出发指向动作结点，意思是该状 态结点是动作的前提条件；正效果弧和负效果弧都是从动作结点指向状态结点， 意思是该状态结点是动作的正或负效果。( 3 ) 两种关系：状态互斥关系和动作互 斥关系。互斥关系描述了两种状态或动作不能同时出现。 在第0 层瓯是规划问题的初始状态集合。第1 层有两个子层：动作层4 和状 态层s ；如果动作的前提都在氐中，那么就加该动作到动作层4 中；墨是& 和4 动作正效果的并集。重复上述过程，并在同时记录下每层的互斥关系，直至目标 状态出现在s 层中并且它们不互斥，即开始由后向前的规划图搜索过程。若成功 则结束；否则继续扩展规划图。 搜索规划图解从s 层开始，层中的目标状态为蜀，然后在4 中搜索能到达 的非互斥动作的子集合q ，以q 的前提作为新的目标状态岛一。进行搜索，以此类 推。若在第j 层中搜索失败则回溯到第j + l 层。成功到达瓯层，那么动作集序列 就是所求的规划解。 采用该策略的规划系统比较多，而且效率都比较高：有ab l u m 和mf u r s t 开发的g r a p h p l a n 8 1 ，hk a u t z 等人开发的b l a c k b o x t 7 1 1 1 8 1 ，jk o e h l e r 设计的i p p t g l ， ag e r e v i n i 和is e r i n a 设计的l p g 1 0 】【1 9 l ( l o c a ls e a r c hf o rp l a n n i n gg r a p h s ) ，mf o x 和dl o n g 的s t a n ( s t a t ea n a l y s i s ) 。 1 3 3 启发式搜索规划系统 几乎所有规划问题的求解都涉及抽象搜索过程，而求精、分支、剪枝和终止 是抽象搜索过程的四个步骤，不过对于不同类型规划，可能会有所改变。启发式 搜索主要利用放宽原问题约束的原则，利用启发式信息指引搜索的方向。启发式 7 基于c o n f o r m a n t 领域的一种规划策略第1 章引言 信息有时是针对不同规划领域设计的，那么它们是领域无关的；大部分的启发式 信息都是针对某个特定的领域，他们是领域相关的，而往往这种启发式信息会带 来效率的巨大提高。 启发搜索有几种搜索方向：前向搜索、后向搜索和前后向相结合搜索。它可 以和状态搜索空间、规划搜索空间或规划图搜索空间相结合，而启发式搜索的精 髓就在于启发函数f ( s ) 的设计，其好坏直接影响着搜索算法的效率。现在常用 的启发式函数是厂( s ) = g ( s ) + w h ( s ) ，其中g ( s ) 是已消耗的成本，w 是比例系数， 可根据实际情况设计，办( s ) 是启发估值函数，是当前状态结点s 到目标结点的距 离估值。如果乃( s ) 是所有从s 结点出发的可达解的最小值矿( s ) 的下界，即 h ( s ) 矿( s ) ，该启发估值函数是可纳的。如果启发搜索算法的估值函数是可纳 的，那么它可以保证得出最优解。下面我们介绍几种启发式估值函数： ( 1 ) 和估值法 办( s ) = 一办( p ) ( 1 1 ) 其中初始化所有命题p ，如果是初始状态，则未0 ，否则为o o 。对于每个动 作a 的正效果p ，修改它的估值矗( p ) = m i n h ( p ) ，l + h ( p r e c o n d ( a ) ) ) 。 ( 2 ) 最大估值法 办( s ) = m a x p 。，厅( p ) ( 1 2 ) 由于和估值法忽略了状态直接的联系，它的估值大于矿岱) ，因此它是不可纳 的；而最大估值法只考虑其中一个最大值，满足办( s ) 矿 ) 的条件，因此是可 纳的。 ( 3 ) 和互斥估值法 郴) = 坳) i f p , q 嘶岿栖斥 ( 1 3 ) 由于和估值法忽略了命题之间的关系，从而导致效果不理想，我们参考图规 划技术中互斥关系的思想，在和估值法中加入了命题之间静态互斥关系。当两个 命题不能同时出现在同一个可达状态，我们称之为静态互斥。和互斥估值法是规 划系统h s p r 的标准工作环境的默认值。 另外还有和估值调整2 m 法，层设置估值法( s e t l e v e lh e u r i s t i c ) ，组合估值法 8 基于c o n f o r m a n t 领域的一种规划策略第1 章引言 等等。 启发式策略的规划系统在第二届规划系统大赛上表现出色，而第一届冠军 b l a c k b o x 则由于没有用到启发式策略而表现不佳。采用启发式策略的规划系统 有：jh o f f m a n 开发的f f l l 2 l ( f a s tf o r w a r d ) 矛t lm e t r i c f f ，hg e f f n e r 和bb o n e t 设 计的h s p 1 l 】【2 0 1 ( h e u r i s t i cs e a r c hp l a n n i n g ) 希1 h s p r ，ag e r e v i n i 和is e r i n a 的 l p g l l o 】【1 9 1 ，k a m b h a m p a t i 的a l t a l t ( al i t t l eo f t h i sa n da l i t t l eo f t h a t ) 等。 1 3 4 基于模型检测的规划系统 基于模型检测的规划系统大多采取类似二元判定图b d d ( b i n a r yd e c i s i o n d i a g r a m ) t 2 l 】的结构和符号模型检测技术，把规划求解对应于在一个有限状态自动 机中寻找一条从初始状态到目标状态的路径，自动机的状态转换对应于在一个规 划状态执行一个动作，然后对自动机进行搜索。其中规划问题的表示对求解策略 有着很重要的影响，一些经典规划系统引入了b d d 结构及其先进技术，取得了 不同程度效率的提高。 基于模型检测技术的规划系统在很多实际应用中都可以处理不确定性问题， 因为其解的搜索是对状态集和状态转换集进行的，而不是对于单一状态。它具有 坚实的理论基础和广阔的应用前景，采取模型检测技术的规划系统有：j e n s e n 和 v e l o s o 设计的u m o p t 2 2 i t 2 3 j ( u n i v e r s a lm u l t i a g e n to b d d b a s e dp l a n n e r ) ，b e r t o l i 和 c i m a t t i 开发的m b p 2 4 l ( m o d e lb a s e dp l a n n e r ) 。 除此之外，几种常见类型的规划系统主要有：基于时态和资源约束的规划系 统，如d o h e r t y 和k v a r n s t r o m 的t a l p l a n n e r 等；分层任务网络规划系统，如w i l k i n s 的s i p e 2 ，d s n a u 等开发的s h o p 2 以及e r o l 和h e n d l e r 设计的第一个使用被 证明是可靠且完备的规划算法系统u m c p 等；基于m a r k o v 决策过程的规划系统， 如b o n e t 和g e f f n e r 开发的g p t 等。 1 4 本文的组织结构 本文内容宏观上分为三部分：智能规划研究历史和现状，领域知识提取策略 和规划系统s t e p b y s t e p 简介，基于c o n f o r m a n t 规划的规划策略研究与实现。具 体章节安排如下： 9 基于c o n f o r m a n t 领域的一种规划策略第1 章引言 第l 章简单叙述了智能规划研究的历史与现状，对智能规划的应用进行了简 要说明，并对一些主要的规划系统进行了分类，使得对智能规划领域有个清晰的 了解。 第2 章介绍了p d d l 描述语言的语法和语义，对智能规划问题的描述有一个 整体的了解，为问题求解提供必要的预备知识。 第3 章简要阐述了领域知识提取策略和规划系统s t e p b y s t e p 的研究与实现。 第4 章介绍c o n f o r m a n t 规划的现状和扩展p d d l 描述语言的语法语义，为 c o n f o r m a n t 规划提供一个宏观而清晰的视角，并为c o n f o r m a n t 规划策略的设计提 供必需的准备。 第5 章为本文的主要工作，详细阐述了基于c o n f o r m a n t 规划的规划策略，将 信念状态转换为若干确定性状态的组合，研究和分析了信念状态间的关系，并将 领域知识运用于不确定性领域当中。 第6 章利用实验对规划策略进行了验证，分析了规划系统c o n f o r m a n t s b s 的 表现。 1 0 基于c o n f o r m a n t 领域的一种规划策略第2 章智能规划领域描述语言 第2 章智能规划领域描述语言 智能规划经过半个世纪的起伏和发展，取得了很大的进步，其中规划领域描 述语言( p l a n n i n gd o m a i nd e s c r i p t i o nl a n g u a g e ，p d d l ) 是智能规划领域的一个重 要成果。1 9 9 8 年，d r e wm c d e r m o t t 在a i p s 一9 8 会议上提出了p d d l 描述语言。 虽然p d d l 有着不太令人满意的地方，但是凭借着其共享系统标准的容易程度 和共享规划资源的大量增加，p d d l 逐渐成为智能规划领域的描述语言。随着领 域研究的不断深入，智能规划逐步得以应用到一些实际应用中，而p d d l 也随 着得以扩充和完善，至今已经发展到第三个版本，即p d d l 3 1 1 4 】。我们在这里只 介绍p d d l 描述语言与论文研究有关的部分。 p d d l 旨在描述一个领域的物理特性：谓阋表示什么意思，什么动作是可能 的，复合动作的结构是什么，动作的效果是什么。通过b n f ( b a c k u sn a u rf o r m ) 范式，p d d l 能够简单地表达它的语法和语义。 2 - 1 规划领域的e b n f 符号 p d d l 的e b n f 是一种扩展后的b n f ，它必须符合以下规则【1 4 1 ： ( 1 ) 每个规则都具有这种形式 ：= e x p a n s i o n 。 ( 2 ) 尖括号“ 划定了一个句法元素( s y n t a c t i ce l e m e n t ) 的名字。 ( 3 ) 方括号“【】括住的是可选的内容。如 【( ：t y p e s ) 】：t y p l n g ) 当且仅当领域定义中声明t ( ：t y p i n g ) 元素，：t y p e s 才是可选的。 ( 4 ) 星号“枣 表示零个或者以上；加号“+ 表示一个或者以上。例如a 幸表 示零个或者零个以上a ，a + 表示一个或者一个以上a 。 ( 5 ) 一些语法元素已经参数化了。如 表示一个s y m b o l 元素的 列表，在e b n f 中， 和 都有定义，其中 ：= ( x 丰) 那么 ：= ( * ) ( 6 ) 括弧“( ) ”表示是必须元素。 2 2 规划领域定义 用e b n f 对规划领域的结构进行定义i l 4 1 ，其主要形式如图2 i 图2 4 ： ：= ( d e f i n e ( d o m a i n ) t y p e s _ d e t ：修p i 坞 】 * ) 图2 1 规划领域的e b n f 定义 ：2 ( ：r e q u i r e m e n t s + ) q p e s - d e 今：= ( ：t y p e s ) ：= x 簟 ：_ ：嘶“8x + 一 ：= ：2 ( e i t h e r + ) 龟s t a 嗖d e ：2 ( ：c o n s t a n t s ) p 删i c a t e 趾d e 今：2 ( ：p r e d i c a t e s + 1 ：- - - ( t y p e dl i s t ( v 撕a b l e h ：= ：= ? 图2 2 规划领域可选内容的e b n f 定义 ：2 ：2 ( a n d 幸) g d ：2 ：产：击巧”喇。伊。击6 。n ( o r 幸) ：2 碰s j ”甜”9 ”“d i d 。“( n o t g d 勺 图2 3 规划领域g o a ld e s c r i p t i o n 的e b n f 定义 l ， 基于c o n f o r m a n t 领域的一种规划策略第2 章智能规划领域描述语言 ：_ ：_ ( ：a c t i o n ：p a r a m e t e r s ( ) ) ：= ：； ：v a n s ( ) 【：p r e c o n d i t i o n 】 ：e f f e c t ：孑 l i t e r a l ( t ) ：? ( n o t ) a t o m i cf o r m u l a ( t ) p ：= ( t 拳) ：- - - ：= ：。( a n d ) ：2 ( n o t ) ：= ：= ：。击6 “d 。p r * e o n d i t i o n ( w h e n g d ) 图2 4 规划领域动作的e b n f 定义 上述领域定义中，除7 ( d o m a i n ) 之外，其他元素都可以按照任意顺序 来组织。 ( 1 ) 领域名称定义( d o m a i n ) 。该语句表示规划领域的名称，唯一标 示该领域，而n a m e 是一个字符串。例t h ( d o m a i nb l o c k s w o r l d ) 定义了一个名为 b l o c k w o r l d 的领域。 ( 2 ) 领域的描述能力定义 ：= ( ：r e q u i r e m e n t s + ) 。 该语句形式化地定义了规划规划当前能处理的问题。如果领域定义中没有该 r e q u i r e m e n t 语句，那么r e q u i r e k e y 将默认为：s t r i p s 。同时，一个领域能够从它的 祖先中继承祖先声明的r e q u i r e m e n t 。r e q u i r e _ k e y 的内容如表2 1 f 1 4 1 表2 1r e q u i r e _ k e y 属性 r e q u i r e _ k e y 描述 ：s t r i p s 基本的s t r i p s 形式 1 3 基于c o n f o r m a n t 领域的一。乖l 规划策略