（计算机应用技术专业论文）可满足性问题的约束规划算法研究.pdf

学位论文数据集 i i i ii i1 1i iil l l lii iiiil y 1810 319 中图分类号 一p 弓l |学科分类号w 0 论文编号 l 们lo 硼畎吨 密级 ，弓敲 学位授予单位代码 1 0 0 1 0 学位授予单位名称北京化工大学 作者姓名 徐坟脚 学号 ) 吵“噼 获学位专业名称 计嚷柏翩枯芸 获学位专业代码 d 亨 口 课题来源 主锄力嘞弘如日 研究方向 权仇计屏 论文题目 豸i 钨墓以j 高超南妈结枷1 1 缘法厕侥 关键词 5 舀t 两趋豹乏之瑚1 兹? 0 ，苫睨妇誊燃，泐 论文答辩日期洲7 占，弓论支类型 意回砷磊l ， ， 学位论文评阅及答辩委员会情况 姓名 职称 工作单位学科专长 指导教师 易绎凯刍1 劾硬砧寺批张2 西 - 缘，闵绝啦 评阅人i 珊口冲 评阅人2 舞蛑引极谴牝量、化久誓 评阅人3 评阅人4 评阅人5 答辫委员纵 弛5 茹参1 粕施牝弓、阮赙 答辩委员1 李髫矗、玉l 热撬沈j 札堪 答辩委员2 表哕参、刍忾5 掘此3 、见勰 1 答辩委员3 答辩委员4 答辩委员5 注：一论文类型：1 基础研究2 应用研究3 开发研究4 其它 二中图分类号在中国图书资料分类法查询 三学科分类号在中华人民共和国国家标准( g b t1 3 7 4 5 - 9 ) 学科分类与代码中 查询 四论文编号由单位代码和年份及学号的后四位组成 4 f j 尸 童 4 尸 摘要 可满足性问题的约束规划算法研究 摘要 可满足性问题( 简称s a t 问题) 是n p h a r d 问题，它是当前运筹 学、人工智能和计算机科学的热点领域，解决s a t 问题具有突出的 理论价值和应用价值。解决s a t 问题的传统算法往往要占用很长时 间和大量的内存，而最后往往还不能得到满意的结果。为了提高s a t 问题解决算法的性能，本文对于s a t 问题做了对已有算法的分析研 究、约束规划算法分析、约束规划算法的u m l 建模和约束规划算法 来求解s a t 问题的实验分析等方面的探讨，主要的内容有： 对s a t 问题已有的主要算法及存在的问题进行了研究，总结了提 高算法性能和跳出局部陷井所用的策略或机制。对局部搜索算法的实 验分析，针对局部搜索算法的灵活性、随机性和参数化等特点，深入 探讨了相应的算法实验分析所涉及的算法性能度量、性能比较和参数 调优等基本问题。提出了综合人工智能中一致性算法和启发式搜索算 法，采用约束推理的方法的约束规划算法。本文通过对约束规划算法 事件触发机制的分析和u m l 的建模，从而提高了搜索效率，提出了 解决s a t 问题。 结合s a t 问题特殊知识，提出了在启发式算法和一致性算法 的基础上，采用整数有限域的优化和搜索策略，对非线性约束问 题在其内部制作二叉树进行搜索的约束规划算法，描述了 北京化工大学硕士学位论文 f i r s t f a il 的分支策略设计和算法描述，提供了性能比较、参数 优化等等多种目的的实验结果。实验结果表明约束规划算法能有 效解决s a t 问题和显著提高性能。 关键词：s a t 问题，约束规划算法，搜索引擎，数学建模，实验分析 l l 摘要 c o n s t r a i n tp l a n n i n ga l g o r i t h m b a s e d s a tp r o b l e m s a b s t r a c t s a t i s f i a b i l i t yp r o b l e m s ( s a tp r o b l e m sf o rs h o r t ) i sn p - h a r dp r o b l e m s ， w h i c ha r ew e l l k n o w n e di na r e a so fo p e r a t i o n sr e s e a r c h , a r t i f i c i a l i n t e l l i g e n c ea n dc o m p u t e rs c i e n c en o w a d a y s s o l v i n gs a tp r o b l e mi so f g r e a tv a l u ei nt h e o r ya n da p p l i c a t i o n a l g o r i t h m s f o rs o l v i n gs a t p r o b l e m st a k eu pl o n gm r t i m e sa n dl o t so fs y s t e mr e s o u r c e sa n dc a n t g e ts a t i s f i e dr e s u l t si nt h ee n db e f o r e t oi m p r o v et h ep e r f o r m a n c eo fs a t s o l v e r s ，i nt h i st h e s i s ，t h es t u d yo fk n o w na l g o r i t h m s ，t h ea n a l y s i so f c o n s t r a i n tp l a n n i n ga l g o r i t h m ，u m lm o d e l i n go fc o n s t r a i n tp l a n n i n g a l g o r i t h ma n dt h ee x p e r i m e n t a la n a l y s i so fs o l v i n gs a tp r o b l e mb yt h e c o n s t r a i n t p l a n n i n ga l g o r i t h m s a r ed i s c u s s e d t h i st h e s i sc o n t a i n s f o l l o w i n g s ： s a tp r o b l e mi sr e s e a r c h e di nk n o w nm a i na l g o r i t h m sa n dt h ea l r e a d y e x i s t i n gp r o b l e m s ，s u m m e du pt h ea l g o r i t h mt oi m p r o v ep e r f o r m a n c ea n d j u m p i n go u to ft h el o c a ls t r a t e g yo rm e c h a n i s mu s e db yt h et r a p w i t h t h ee x p e r i m e n t a la n a l y s i so ft h el o c a ls e a r c ha l g o r i t h m ，l o c a ls e a r c h a l g o r i t h m s a r e f l e x i b l e ，r a n d o m i z e d a n d p a r a m e t e r i z e d ，a n d t h e c o r r e s p o n d i n ge x p e r i m e n t a la n a l y s i sm u s ts h o wh o wt om e a s u r ea n d l 北京化工大学硕士学位论文 c o m p a r ea l g o r i t h mp e r f o r m a n c e ，a n d h o wt o o p t i m i z ea l g o r i t h m p a r a m e t e r s c o n s t r a i n tp l a n n i n ga l g o r i t h mi sp r o p o s e dt os o l v es a t p r o b l e m sb yi n t e g r a t i n gc o n s i s t e n c ya n dh e u r i s t i cs e a r c ha l g o r i t h ma n d a d o p t sc o n s t r a i n tr e a s o n i n g i nt h i st h e s i s ，i m p r o v i n gt h es e a r c h i n g e f f i c i e n c yw i t he v e n ta n a l y s i so fv a r i a b l e sn a r r o w i n ga n du m lm o d e l i n g ， w e p r o p o s e t os o l v es a t p r o b l e m c o m b i n i n gt h es p e c i a lk n o w l e d g eo fs a tp r o b l e m , w ep r o p o s e t h ec o n s t r a i n tp l a n n i n ga l g o r i t h m , w h i c hi sb a s e do nh e u r i s t i cs e a r c h a l g o r i t h ma n dc o n s i s t e n c ya l g o r i t h ma n da d o p t s f i n i t ef i e l d s i n t e g e r o p t i m i z m i o na n ds e a r c hs t r a t e g yt os e a r c hb ym a k i n gb i n a r yt r e es e a r c h n o n l i n e a rc o n s t r a i n tp r o b l e m si ni t si n t e r n a l e x p e r i m e n t a lr e s u l t ss h o w t h a tc o n s t r a i n tp l a n n i n ga l g o r i t h mc a ne f f e c t i v e l ys o l v es a t p r o b l e ma n d i m p r o v ep e r f o r m a n c es i g n i f i c a n t l y k e yw o r d s ：s a tp r o b l e m s ，c o n s t r a i n tp l a n n i n ga l g o r i t h m ，s e a r c h e n g i n e ，m o d e l i n g ，e x p e r i m e n t a la n a l y s i s w 一 广 矗 ， 目录 目录 第一章绪论”1 1 1 研究背景l 1 2s a t 问题的有关定义3 1 3s a t 问题规划方法研究及存在的问题3 1 4s a t 问题研究方法特点5 1 5 研究课题介绍6 第二章s a t 问题的已有算法研究7 2 1 研究简介7 2 2d p l l 算法”8 2 3 局部搜索算法1 1 2 4 其他算法1 5 2 5 局部搜索算法的实验分析o o o oo b 1 7 2 6 算法的分析与比较2 3 第三章约束规划算法分析2 6 3 1 基本原理2 6 3 2 组件构成2 7 3 3 变量压缩事件分析3 2 3 4 总结 一3 5 第四章约束规划算法的u m l 建模3 7 4 1l q v i l 建模语言介绍3 7 4 2 约束规划算法的建模过程3 9 4 3 约束过滤器的可扩展性分析4 2 4 4 总结“4 3 第五章约束规划算法的f l y in g - t t 平台4 4 5 1 约束过滤器4 4 5 2 分支策略4 8 北京化工大学硕士学位论文 5 3 搜索策略5 0 5 4 内存分配策略5 2 第六章约束规划算法的实际应用分析5 3 6 1 约束规划模型的建立5 3 6 2 约束规划算法求解s a t 问题5 7 6 3 实验及分析5 9 6 4 总结“一”一”“一“一6 l 第七章结论6 3 参考文献6 4 p 付录6 7 致谢6 8 研究成果及发表的学术论文6 9 作者简介7 0 2 ， ： 目录 c o n t e n t s c h a p t e r 1i n t r o d u c t i o n 。1 1 1b a c k g r o u n d 1 1 2d e f i n i t i o no f s a tp r o b l e m s 3 1 3p l a n n i n g m e t h o d sr e s e a r c ho f s a tp r o b l e m s ，3 1 4f e a t u r e sr e s e a r c hm e t h o d so f s a = rp r o b l e m s 5 1 5r e s e a r c ht o p i c si n t r o d u c e d 6 c h a p t e r2k n o w na l g o r i t h mr e s e a r c ho fs a t p r o b l e m s 7 2 1r e s e a r c hb r i e f 7 2 2d p l la l g o r i t h m 8 2 3l o c a ls e a r c ha l g o r i t h m 1 1 2 4o t h e r sa l g o r i t h m 1 5 2 5e x p e r i m e n t a la n a l y s i so f l o c a ls e a r c ha l g o r i t h m 1 7 2 6 a n a l y s i sa n dc o m p a r i s o no f a l g o r i t h m s 2 3 c h a p t e r3a l g o r i t h ma n a l y s i so fc o n s t r a i n tp l a n n i n ga l g o r i t h m 2 6 3 1b a s i ct h e o r y ：1 6 3 2c o m p o n e n t s ：z 7 3 3e v e n t a n a l y s i so f v a r i a b l e sn a r r o w i n g 3 2 3 4s u m - u p 3 5 c h a p t e r 4u m l m o d e l i n go f c o n s t r a i n tp l a n n i n ga l g o r i t h m 3 7 4 1u m l m o d e l i n g l a n g u a g e 3 7 4 2m o d e l i n gp r o c e s so f c o n s t r a i n tp l a n n i n ga l g o r i t h m 3 9 4 3e x p a n s i b i l i t ya n a l y s i so f c o n s t r a i n t s 4 2 4 4s u m - u p 4 3 c h a p t e r 5f l y i n g - t tp l a t f o r mo fc o n s t r a i n t p l a n n i n g a l g o r i t h m 4 4 5 1c o n s t r a i n t s 4 4 5 2b r a n c h i n g a l g o r i t h m s 4 8 北京化工大学硕士学位论文 5 3e x p l o r a t i o n a l g o r i t h m s 5 0 5 4n o d er e s t o r a t i o np o l i c i e s ! ；：! c h a p t e r 6p r a c t i c a l a p p l i c a t i o n o fc o n s t r a i n t p l a n n i n g a l g o r i t h m 5 3 6 1m o d e l i n go f c o n s t r a i n tp l a n n i n g a l g o r i t h m 5 3 6 2s o l v i n gs a tp r o b l e m si nc o n s t r a i n tp l a n n i n g a l g o r i t h m 5 7 6 3e x p e r i m e n ta n d a n a l y s i s 5 9 6 4s u m - u p 6 1 c h a p t e r 7c o n c l u s i o n 6 3 b i b l i o g r a p h y 。6 4 a p p e n d i x 。6 7 a c k n o w l e d g e m e n t s 6 8 a c a d e m i cr e s e a r c hr e s u l t sa n dp u b l i s h e d p a p e r s 6 9 a b o u ta u t h o r 刁 o 4 第一章绪论 1 1 研究背景 第一章绪论 从二十世纪九十年代开始，人工智能界的经典问题约束满足问题( 包括可满足性问题) 的算法研究掀起了一个新的热潮。其根源是多方面的：首先，在知识表示方面，约束满足问 题是一类非常重要的问题，几乎所有的n t 问题和人工智能界绝大多数应用问题均可以用约 束满足问题模型表示。约束满足问题的一般形式是，给定一些变元，每个变元分别有多个可 能的取值，变元的取值之间存在一些约束，询问满足所有约束的变元取值是否存在；其次， 推理技术和算法设计等理论和计算机硬件技术等方面有了很大的发展，智能规划取得了一系 列成功的应用，智能规划已应用于太空飞行器控制( n a s a 太空一号控制器中的r a x p s 自治 智能体问题【l 司) 、生产调度( 哈勃太空望远镜调度器h s t s ) 、供应链管理、工作流管理，软件 模块集成管理( v _ i c a r 和c e l w a r e ) 3 1 、软件测试例生成、交互决策支持的优化和基于规划 的接口技术等等之中；第三，一些重要的研究工作如g r a p h p l a n 规划器 4 1 ，s a t p l a n 规划器【5 l 与b l a c k b o x 规划器【6 l ， f f 规划器【| 7 】等等先后完成，新一代的智能规划的性能取得了突破性 的进展，第四，出现了越来越多的研究组织和机构，在国外。近年来成立了许多专门从事智能 规划方面研究的协会和联盟例如欧洲智能规划网p l a n n e t , 英国诺丁汉大学a s a p 研究组 以及美国亚利桑那州立大学y o c h a n 研究组，长期聚集了一批优秀的学者进行智能规划专题研 究和讨论，促进了智能规划学术的繁荣。多种智能规则的专著先后出版，在a i 等著名杂志和 期刊近年来发表智能规划方面的文章日益增多，所有这些引起了广大研究人员对智能规划研 究的高度重视。下面以智能规划研究的简要回顾开始，介绍本文的研究背景。 智能规划研究早在二十世纪六十年代末就已兴起。g p s 程序是模拟模拟人类问题求解的 手段目标分析策略的一个通用问题求解程序，对已知状态s 和目标g ，以及一组关键性的f 规则，它根据s 与g 之间的差异，确定f 规则与差异之间的联系，在f 规则的先决条件都满 足时，这条f 规则应可以应用于当前状态描述上。g r e e n 提出的情景演算方法通过定理证明进 行问题求解哺j 。在他的方法中，把问题表示为一个待证明的公式，用谓词公式表示问题的状 态，用动作公理表示动作对问题的状态的影响，用框架公理描述不受动作影响的状态谓词， 并在每个状态谓词中增加了状态的参数，由一个状态转移函数确定问题的状态执行动作时发 生的转移。证明采用归结反演方法，并嵌入一个特殊谓词，保存证明过程中所用置换并最终 产生问题解。这种方法只能求解简单的问题，最大的不足是描述较复杂的问题时，需要大量 的框架公理，即所谓的框架问题，并因此造成归结中子句数量的组合爆炸。f i k e s 研制s t r i p s 通用问题求解程序时，正式地使用了规划( p l a n n i n g ) 术语，提出了一种称为s t r i p s 语言的动 作描述方法【9 】。s t r i p s 的动作模式用三个集合表示，即前提文字集、增加文字集和删除文字 集，可以省略框架公理。s t r i p s 描述方法发展成了经典规划中最主要的描述语言。著名的 s t r i p s 搜索过程使用目标分解回溯进行问题求解，可以使用启发知识提高搜索效率，在他们 的研究在基础上，发展了一系统列的智能规划方法和系统。最先发展起来的是基于规划问题 北京化工大学硕士学位论文 的状态空间搜索【i 叭。图搜索中应用目标手段分析，产生了前向搜索、反向搜索、双向搜索， s t r i p s 搜索等等经典方法，这些方法最大困难在于状态空间的组合爆炸。为了克服状态空闾 组合爆炸，使用了各种启发式搜索技术。但是，启发知识的获取和表示因问题而不同，没有 统一有效的启发知识，规划系统难于自动获得启发知识。 2 0 世纪7 0 年代中后期开始，算法理论方面的很大的发展。h o l l a n d 全面介绍了模拟生物 进化的遗传算法( g e n e t i ca l g o r i t h m ，g a ) t u 】。遗传算法模拟了达尔文的“优胜劣汰、适者生存一 的原理，在选择算子中激励有希望的候选解，再模拟盂德尔遗传变异理论在迭代过程中保持 已有的较好的候选解，同时寻找更好的解。它具有良好的并行性，对目标函数具有很强的通 用性，还具有良好的全局寻优能力和稳健性，可操作性和简单性。g o l d b c r 用有限马可夫链 数学理论分析遗传算法的数学基础，并在中全面介绍了遗传算法的应用。遗传算法的发展高 潮是二十世纪八十年代末开始，一直延续到今【1 2 】。 w a l t z 在三维线框图的理解中应用一种“过滤”算法取得了较大成功，这种成功刺激了 研究，最终发展形成了约束满足问题的局部一致性概念和算法，w a l t z 算法成为其中一个特例 【l 引。这项成果形式漂亮，在与回溯算法和后来的局部搜索算法相结合时有实用价值。 模拟退火算法( s i m u l a t e da n n e a l i n g , s a ) 是迭代求解的一种随机寻优算法，其出发点是基 于物体中固体物质的退火过程与一般优化问题之间相似性。模拟退火算法在某一初始温度下， 伴随温度参的下降，结合概率突跳特征在解空间中随机寻找目标函数的全局最优解，即局部 优解能以随温度下降而减小的概率跳出，并最终趋于全局最优解【l 引。 g l o v e r 在19 8 7 提出了禁忌搜索算法( t a b us e a r c h , t s ) 思想，是对局部邻域搜索的一种扩 展，也是一个全局逐步寻优算法。算法通过引入一个灵活在存储结构和相应的禁忌准则来避 免搜索中产生迂回，并通过藐视准则来赦免一些被禁忌的优良状态，保证多样化的有效探索 以最终找到全局最优解。 进入9 0 年代用局部搜索算法去求解约束满足这个古老的问题，带着这个问题回头看9 0 年代以前的局部搜索算法研究，可以发现所求解的问题均是优化形式，这种形式下，近似解 是有意义的，可以接受的；而约束满足问题一般为判定形式，要求回答有解或无解，这时局 部搜索找到的近似解没有意义，或者说，原则上局部搜索算法不能肯定地回答这种问题。因 此人们比较自然地认为只有回溯算法才能求解约束满足问题。 s e l m a n 在1 9 9 2 年提出的g s a t 算法用1 9 6 秒求解由1 0 0 皇后问题产生的s a t 问题l l 瓢。 后来引进了随机翻转等几个策略改进g s a t ，不久又提出新的算法w s a t ，其求解能力进一步 得到提高，用1 6 小时求解随机产生的5 0 0 个变元2 1 5 0 个子句的3 - s a t 问题。国内在这方面 的研究也非常突出，李末研究了s a t 问题的相变理论和算法复杂性分析【l 7 1 ，黄文奇提出的 拟物拟人算法【l 0 9 1 ，其s o l a r 系统在9 6 北京国际s a t 比赛中获得冠军。 在此基础上，k a u t z 提出了将规划问题编码为s a t 问题的方法，后来又实现了利用g s a t 和w s a t 算法的s a t p l a n 规划器，并参加1 9 9 8 年智能规划器国际比赛( a i p s 9 8 ) ，在领域无 关规划器大组内获取得总分第一名，基于s a t 的规划方法开始引人注目。在2 0 0 4 年的i c a p s 国际比赛中，s a t p l a n 2 0 0 4 在又获最优确定性规划组冠军。 2 ， 第一章绪论 在a i 规划领域最近发展中，b l u m 的g r a p h p l a n 算法是最令人振奋的。g r a p h p l a n 是一种 简单、优美的算法，产生了极快的规划器，比以前的s n l p , p r o d i g y 或u c p o p 快几个数量级。 以前的智能规划系统只能产生出有5 - 6 操作步的计划，并且需要几分钟的时间，而现在在同 样的时间内却可以产生出有1 0 5 操作步的计划，其问题世界的可能状态是1 0 1 6 个不同状态。 g r a p h p l a n 所用的规划图也是s a t 方法和其它最新方法的基础。 2s a t 问题的有关定义 定义l ，用符号v 表示一个命题变元的集合，若v 有n 个命题变元五，屯，毛。，那么 v _ “，屯，毛。 ，用i v f 表示v 的元素个数。 定义2 ，v 的一个真值指派a 是一个映射：v 一 o ，l ，它可用一个n 维向量( y l ，1 2 ，) 表 示，其中 0 , 1 ，0 和1 分别代表命题常元f a l s e 和t r u e 。对任意一个命题变元而，如果 其在真值指派a 下取真，则彳( 而) = l ，否则么( 而) = o 。在v 上存在2 一个不同的真值指派，所 有真值指派构成n 维向量空间。 定义3 ，对任意一个命题变元x ，称符号x 和一x 是其文字，其中x 是其正文字，- 1 x 是 其负文字。 定义4 ，子旬是v 上若干文字的析取，用集合c 表示，子旬c 中的文字数称为子句长度， 记为lci 。 定义5 ，子旬集c 是由v 上的子句组成的集合，它在真值指派a 下是可满足的，当且仅当 c 中所有子句在真值指派a 下都是真的。 定义6 ，s a t 问题定义为：给定命题变元的集合v 和其子句集c ，闯是否存在一个关于v 的真值指派a ，使得c 是可满足的。 1 3s a t 问题规划方法研究及存在的问题 s a t 问题最先发展起来的是状态空间搜索方法，描述为在隐式图中的搜索问题，提高效 率的途径是启发式搜索技术，这种方法同样存在巨大的困难，因为规划问题的状态空间是指 数级的，启发式知识通常与具体类型的问题相关，其构造往往因问题而异。另一类方法是基 于规划空间搜索的层次规划方法，这种方法可以通过对规划问题进行分层，模拟人类求解复 杂问题时常用的“自项向下，逐步求精的策略，可以简化问题和提高效率。这种方法从一 个最粗糙的计划开始，根据动作之问的因果关系和威协，不断地增加一些带参数的动作和给 出动作的时序约束和变元的取值约束，直到消除所有的威协和确定动作中的变元，再从中构 造出一个可行的计划，这种方法同样存在效率是上的问题，因为动作时序分析和变元约束处 理是n p 困难的。在二十世纪九十年代前，规划系统的能力非常有限，产生4 - 5 步的计划需要 数分钟时间1 2 0 1 。 因为s a t 问题早在二十世纪七十年代初已定性为n p - h a r d 问题，在s a t 问题算法没有突 3 北京化工大学硕：t 学位论文 破性进展之前，没有人会认将规划问题转化为s a t 问题进行求解是可行的。在1 9 9 5 年， g r a p h p l a n 规划器以前所未有的效率带来了规划器发展的高潮。b l u m 全面介绍了g r a p h p l a n 规划器，其中所用的规划图是一种高效的表示方法k a u t z 发现规划图与他的s a t 编码方法 非常相似，而且规划图可以等价地编码为s a t 问题。 实际上，一个c s p 问题也可以机械地编码为s a t 问题【2 1 2 2 1 。层次规划方法产生的偏序计 划，实质上一个c s p 问题，可以用因果理论进行描述，并机械地编码为s a t 问题，所产生的 编码具有最好的综合复杂性。 s a t 规划方法是关于动作的推理，为了达到预先确定的目标，通过预期动作的效果，选 择和组织一组动作，是一种抽象且清晰的推理过程。作为人工智能的一个领域，s a t 规划领 域专门从计算上研究动作推理过程。 s a t 的规划方法主要有基于基于情景演算的规划方法、基于规划图的规划方法和基于因 果关系的规划方法【2 3 】。 在人工智能的早期，有多种形式将规划形式化为演绎推理。演绎性规划系统中，最著名 的是情景演算。情景演算是基于谓词演算的形式系统。在这个系统中，状态、动作和动作结 果都表示为一阶谓词公式。规划问题表示为向一个演绎系统提问：存在满足目标属性的状态 吗? 如果存在，当前状态如何通过一系列的动作才能转换为目标状态? 这个提问被形式化为 一个定理证明问题。再通过扩展归结反演的定理证明方法构造规划问题的解。 情景演算方法存在一些严重的问题。首先是框架公理问题。因为在一个状态中执行一个 动作只会产生局部影响，还有很多状态谓词没有改变，也就是说，它们在当前状态的真( 或假) 会在新状态中保留，所以每一个状态谓词与动作的组合，就有正框架和负框架公理各一个， 在现实问题中，使用情景演算方法将产生大量的框架公理，导致证明无法有效地进行。 第二个问题是等式公理问题。在描述带参数的动作模式时，效应公理和框架公理的前提 条件中需要相等关系对变元进行约束，如( x 劫，( y z ) 等等。如果领域中存在数量较多的对 象时，将产生无穷多个象( a 寻a ) ，、( a - b ) ，一( a 产c ) 等等这样的公理，相等关系的表示和处理 将变得极为困难。 第三个问题是归结方法的效率问题。不论采用哪种策略，归结是困难的，因此只能求解 简单的规划问题。 后来许多研究探索了减少框架公理的途径 2 4 - 2 r l ，即使能够大量减少框架公理，用它们在 几个动作系列中推理哪些状态谓词保持不变的过程仍是低效的。 基于规划图的规划方法是b l u m 提出的g r a p h p l a n 算法，它是a i 规划的最近发展中令人 最振奋的。g r a p h p l a n 是一种简单、优美的算法，产生了极快的规划器，比以前的s n l p 、p r o d i g y 或u c p o p 快多个数量级。g r a p h p l a n 的表示构成了最成功的s a t 规划方法的基础，s a t 规划 方法将规划问题编码为命题逻辑s a t 问题。因此，认识g r a p h p l a n 有利于理解s a t 规划方法。 g r a p h p l a n 中，两个阶段交替进行：规划图扩展和解抽取。图扩展阶段中，按时间方向向前 扩展一个规划图，直到满足计划存在的必要( 但非充分) 条件。解抽取阶段在规划图中执行一个 反向链搜索，寻找解决问题的一个计划。如果不能找到解，再进一步扩展规划图，如此重复。 4 第一章绪论 规划图表示了每一动作层中平行的动作。这表明，七层动作层的规划图可以表示多于七个动 作的规划问题。但是，两个动作包含在规划图的同一层中并不意味着执行计划时两者可以同 时。 基于因果关系的规划方式是k a u t z 给出基于s n l p 因果链规划器的编码方法。这种编码 产生综合指标最好的s a t 编码。编码规模从指数级变为多项式的，变元数为o ( 刀2 ) 而文字出现 为o ( n 3 ) 。 我们可以将非线性多项式的因果关系直接转换为s a t 闯题。用j 和，表示初始动作和终 止动作。用彳表示除初始动作和终止动作之外的动作集合。用d 表示除初始动作和终止动作 之外操作步名字集。用于表示所有非线性多项式的操作符。对任意有限操作定义集，用l a l 表 示d ( 1o p sl id o mi ) 和i f i 表示d ( 1p r e di id o mr “+ l & l + l & 1 ) 。交元数目中下面两个 部分占绝大多数：表示因果链的变元，即o ( n 2 l f i ) ，和形式如a c t i o n ( o ，a ) 的变元数目即l a l ) 。 出现的文字数目中占大多数的是模式l o ，产生的子旬数量为o ( n 3 l f l ) 。对有3 目m o v e 操作 模式的b w 问题来说，且设l d 啪i = l s o l = l s g 产，l ( 行为计划限长 ，共有变元为o ( 矿1 ) 且文字出现数 目为o ( n 5 ) 。 1 4s a t 问题研究方法特点 在人工智能的传统上，规划被形式化为演绎推理【2 s - 3 1 。虽然各种形式化方法的细节上存 在差异，但它们都用使用公理。公理陈述的是，如果在动作的前提成立，则动作的发生蕴含 动作的效果。这种方法将规划问题形式化为寻找一个命题的演绎证明过程，这个命题是关于 初始条件和一个动作序列蕴含目标条件的一个断言。 因为演绎问题是非常困难的，人们开始寻找其它方法。最先发展起来的是基于规划问题 的状态空间搜索。图搜索中应用目标手段分析，产生了前向搜索、反向搜索、双向搜索，s t r i p s 搜索等等经典方法，这些方法最大困难在于状态空间的组合爆炸。在状态空间上定义启发式 知识，使用启发式搜索是解决困难的主要策略并一直应用于主流的方法中，但领域无关的规 划中，规划器很难使用具体问题特有的启发知识。 后来发展的基于规划空间搜索方法具有更高的效率，将规划空间划分为不同的抽象层次， 在每一层内的规划相对要容易，而且高层的计划能为简化下层的规划搜索，可以总体上提高 效率。可以实现部