（计算机软件与理论专业论文）基于规划图的用户规划识别研究.pdf

r 一 瑟 j 甲 0 ： 霹孑 i l 璃 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指 导下独立进行研究工作所取得的成果。据我所知，除了 特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明 的法律结果由本人承担。 学位论文作者签名：遍趟 日期： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：巡 日 期：翘芝：厶7 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： e t 期：型d - g - ， 。 ，。，i_ 一 ，o 藉 f蠡蠹qrl 7 - 。 1 j 摘要 智能规划与规划识别是目前人工智能研究的热点领域之一。以规划图为基础的研究 方法是这一领域最突出的研究方法之一，它的研究技术应用广泛。在许多实际的应用中， 如辅助教学、办公事务、电子商务等其面向的大多是普通用户；所以对用户规划识别问 题的研究具有深刻的理论价值和广泛的应用前景。 传统的用户规划识别的研究方法是根据观察动作建立规划库，根据一定的搜索和匹 配机制来获取规划解。但是传统的规划库是静态的，手工编制的，需要进行更新和维护。 本文改进传统的规划图算法的缺点，利用规划图算法动态生成规划解，即在识别的过程 中及时更新和维护用户规划库。如何组建用户规划库是以规划库为基础的用户规划识别 算法研究的另一个关键性问题；本文利用改进规划图算法得到的动态规划解来动态组建 用户规划库，即在原有用户规划库的基础上，边规划边生成新的规划解，新的规划解及 时更新到用户规划库中。通过这些改进方法，算法的应用效率大大提高。 本文的研究基础是智能规划和规划识别理论，研究工具是规划图算法，采用有库规 划模型实现用户规划识别算法。本文算法简单易懂，概念完整，过程清晰，为以后的继 续研究打下良好基础。 关键词：智能规划；规划识别；规划图；用户规划识别 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 ga n dp l a nr e c o g n i t i o ni so n eo fh o tr e s e a r c hf i e l do fa r t i f i c i a l i n t e l l i g e n c e t h ep i c t u r es h o w st h eb a s et op l a nt h er e s e a r c hm e t h o di st h em o s t p r o m i n e n tr e s e a r c hi nt h i sa r e ao n eo f t h em e t h o d s ，i ti sw i d e l yu s e dr e s e a r c ht e c h n i q u e s i nm a n yp r a c t i c a la p p l i c a t i o n s ，s u c ha sr e m e d i a lt e a c h i n g , o f f i c es e r v i c e s ，e - c o m m e r c ef o r m o s to fi t so r d i n a r yu s e r s ；s ot h eu s e ri d e n t i f i c a t i o no ft h ep r o b l e mo fp l a n n i n gh a sa p r o f o u n dt h e o r e t i c a lv a l u ea n daw i d er a n g eo fa p p l i c a t i o n s t h et r a d i t i o n a li d e n t i f i c a t i o no ft h eu s e rp l a ni se s t a b l i s h e db a s e do nt h eo b s e r v e d m o t i o np l a n n i n gl i b r a r y , s e a r c ha n dm a t c ha c c o r d i n gt os o m em e c h a n i s mt o g e tt h e p l a n n i n gs o l u t i o n b u tt h et r a d i t i o n a lp l a n n i n gl i b r a r yi ss t a t i c ，h a n d - p r e p a r e d ，n e e dt o u p d a t ea n dm a i n t a i n t h i si m p r o v e m e n to ft h et r a d i t i o n a ls h o r t c o m i n g so ft h ep l a n n i n g g r a p ha l g o r i t h m ，g r a p ha l g o r i t h md y n a m i c a l l yg e n e r a t e du s i n gp l a n n i n gp l a n n i n g s o l u t i o n , w h i c hi si nt h ep r o c e s so fi d e n t i f i c a t i o nt ou p d a t ea n dm a i n t a i nu s e rp l a n n i n g l i b r a r y h o wt o s e tu pp l a n n i n gl i b r a r yi sp l a n n i n gl i b r a r yu s e r sb a s e do nu s e rp l a n r e c o g n i t i o na l g o r i t h mb a s e do na n o t h e rk e yi s s u e ；t h i sp a p e ri m p r o v et h ep l a nb yt h e d y n a m i cp r o g r a m m i n gs o l u t i o na l g o r i t h mt od y n a m i c a l l ys e tu pu s e rp l a n n i n gl i b r a r y , t h e l i b r a r yi nt h eo r i g i n a lp l a n n i n gb a s i sf o rt h eu s e ro nt h es i d eo fp l a n n i n gw h i l eg e n e r a t i n g n e wp l a n n i n gs o l u t i o n , t h en e w p l a n n i n gs o l u t i o nt ot h eu s e rp l a n st ou p d a t et h el i b r a r y w i t ht h e s ei m p r o v e dm e t h o d s ，a p p l i c a t i o no ft h ea l g o r i t h me f f i c i e n c yg r e a t l yi n c r e a s e d t h i ss t u d yi sb a s e do ns m a r tp l a n n i n ga n dp l a nr e c o g n i t i o nt h e o r y , r e s e a r c ht o o l sa r e p l a n n i n gg r a p ha l g o r i t h m ，u s i n gad a t a b a s ep r o g r a m m i n gm o d e lt oa c h i e v et h en s e rp l a n r e c o g n i t i o na l g o r i t h m t h i si se a s yt ou n d e r s t a n dt h ec o n c e p to fi n t e g r i t y , ac l e a rp r o c e s s f o rt h ef u t u r ec o n t i n u et ol a ya g o o df o u n d a t i o n 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 ；p l a nr e c o g n i t i o n ；p l a n s ；u s e r sp l a nr e c o g n i t i o n f - y-?- f，r 目录 中文摘要i 英文摘要i i 目录 弓l言1 第一章智能规划2 1 1 智能规划的概念2 1 2 智能规划的研究方法2 1 3 智能规划的发展与应用3 第二章规划识别5 2 1 规划识别的概念5 2 2 规划识别的研究方法5 2 3 规划识别的分类6 2 4 规划识别的应用7 第三章规划图8 3 1 经典的规划图算法8 3 2k a u z e 的规划识别算法一1 1 第四章基于规划图的用户规划识别研究1 3 4 1 用户规划识别问题1 3 4 2 基于规划图的用户规划识别算法葺1 3 结论1 8 参考文献1 9 m i 东北师范大学硕士学位论文 己i言 丁l目 智能规划与规划识别是人工智能研究的较早的领域之一，它的研究内容涉及到多 门学科交叉的知识内容，如知识表达、知识推理、人机交互和知识挖掘等一系列的多 门学科内容。它的研究方法也很多，其中以规划图为基础的研究方法是最突出的方法 之一。它的研究技术应用广泛，航天技术、工业技术、军事领域等等。 在许多实际的应用中，如辅助教学、办公事务、电子商务等其面向的大多是普通 用户；所以对用户规划识别问题的研究具有深刻的理论价值和广泛的应用前景。 传统的用户规划识别的研究方法是根据观察动作建立规划库，根据一定的搜索和 匹配机制来获取规划解。但是由于所观察到的动作的往往是片面的，而同样的动作经 常出现在不同的规划中，确定一个无二义性的规划通常是困难的。其中，如何组建用 户规划库是以规划库为基础的用户规划识别算法研究的关键问题。 本文针对上述用户规划识别过程中存在的问题改进规划图算法，使规划解的可以 动态生成，并及时更新和维护用户规划库。本文的研究基础是智能规划和规划识别理 论，研究工具是规划图算法，采用有库规划模型实现用户规划识别算法。本算法简单 易懂，清晰明了。 本篇论文的结构如下：第一章对智能规划基本理论进行概述；第二章对规划识别 基本理论进行概述；第三章对规划图算法从智能规划和规划识别两个方向进行概述； 第四章详细阐述用户规划识别算法的相关概念，以及整个算法的设计过程。 东北师范大学硕士学位论文 1 1 智能规划的概念 第一章智能规划 智能规划是这样的一门人工智能学科，它的知识内容涵盖了人工智能的多领域知 识，这些知识之间还有很多的交叉，如知识表达、非单调逻辑、知识推理、人机交互 和知识挖掘等学科的内容都是它研究所涉及所交叉的学科内容。所以说智能规划是人 工智能研究的活跃、重要的子领域之一。 智能规划是这样的一个过程：智能系统依据实体的初始状态和最初的几个动作， 利用一定的规则推断出实体要到达的目标状态，然后构造可以达到目标状态的动作序 列，这个动作序列常被称为规划解。也就是说智能规划是得到规划解的一个过程。 智能规划系统是一个应用软件，其应用的目的就是找出规划解，帮助或协助智能 体完成其要完成的任务。 1 2 智能规划的研究方法 1 、以逻辑为基础的规划研究方法 该方法首先得到一个完整但比较粗略的规划解，然后逐步细化、逐步明确该规划 解，最后找到一个完整又细致的规划解。代表的规划系统有：s h o p 2 。 2 、以启发式搜索为基础的规划研究方法 该方法使用启发信息进行搜索。首先定义一个启发函数，然后计算每个搜索状态 的启发值，最后选择最好的状态进行扩展，直到找到规划解为止。该方法的效率与启 发函数有密切关系，因此选择合适的启发函数至关重要。 3 、以模型检测为基础的规划研究方法 基于转换的方法该方法是将规划问题转换为某种较容易求解问题进行求解。迄今 为止，大概有三种转换的方法：( 1 ) 将规划问题转化为模型检测问题求解：模型检测 ( m o d e lc h e c k i n g ) 是比较系统模型和逻辑需要，判断是否一致。代表规划系统有： m b p 、m i p s 、t a l p l a n n e r 、t l p l a n 和u m o p 等。( 2 ) 将规划问题转化为约束可满足问 题( s a t 问题) 求解：s a t 问题是命题可满足性问题的简称。该方法将规划问题编译 逻辑命题公式，然后使用s a t 求解器进行求解，最后将得到的可满足赋值转换为规划 解。该方法具有较好的性能，如b l a c k b o x 、s a t p l a n 0 4 、m a x l a n 分别获得了第一届、 第四届、第五届s t r i p s 规划域的冠军。( 3 ) 将规划问题转化为量化布尔范式( q b f 问题) 求解：q b f 问题是s a t 问题的扩展，应用更广泛。该方法首先将规划问题( 初 始状态、目标状态和动作集合) 转换成q b f 问题，然后使用q b f 求解器找到该问题的 可满足赋值，最后将赋值转换成一个规划解。 2 东北师范大学硕士学位论文 4 、以规划图为基础的规划研究方法 图规划算法主要内容是规划图扩展和有效规划搜索两个部分。 1 3 智能规划的发展与应用 1 智能规划的发展 智能规划发展历史智能规划的研究已逾半个世纪之久，最早的智能规划系统主要 用于模拟人类处理问题的能力。2 0 世纪6 0 年代，基于搜索和定理证明，n e w e l l 和 s i m o n 设计实现了第一个智能规划系统g p s 1 1 ( 通用问题求解器) 。g p s 在理论上可 以解决任何类型的搜索问题，但是它必须设计繁琐的操作符表示。同时期的g r e e n 系统已经将规划问题归约为定理证明问题，即引入状态演算对动作序列进行演绎。但 是其缺点是解决问题的效率很低。所以，这两种规划系统都由于各自的局限性而只能 解决简单的规划问题。1 9 7 1 年，由斯坦福研究所设计实现的机器人动作规划系统 s t r i p s 成为最早的具有重大影响的自动规划系统。它的出现对规划技术的研究发展 具有划时代的意义。此后的二十年间，人们设计研究了许多规划系统，普遍的规划问 题解决方法都是使用定理证明方法。但是在c h a m a n 设计的规划系统t w e a k 中，它使 人们意识到单纯地使用定理证明方法去解决规划问题是困难重重的，于是智能规划研 究陷入了低谷。上世纪九十年代，智能规划的众多成就重新点燃了这项科学研究的火 焰。此时出现了三种解决规划问题的方法。第一种方法是1 9 9 2 年k a u t z 和s e l m a n 提出的规划可满足性方法( s a t ，s a t i s f i a b i l i t y ) 。s a t 方法将原规划问题表示形式 翻译为命题可满足性问题加以处理解决。这种方法在现今的规划求解器中得到了广泛 的应用。第二种方法是1 9 9 5 年b l u m 和f u r s t 提出的图规划( g r a h l a n ) 方法。图规 划方法创新性地使用了规划图的结构来求解规划问题，为规划问题的求解开辟了新的 篇章，在智能规划历史上具有里程碑式的意义。图规划方法为规划问题求解构建一个 以命题和动作元素的层结构，并以可用动作作为层间传递要素。可用动作包括可由前 一层命题满足的动作和不产生命题改变的n o - o 动作组成的。在图规划中，解决了问 题处理时的框架问题，更为关键的是，它使用了互斥约束的概念为解搜索过程提高效 率。互斥约束包括命题和动作约束。正是由于互斥约束的使用，使得图规划方法拥有 优于其它规划方法的速度。正因为如此，后续的许多研究都以图规划方法作为基础， 研发了诸如t g p 、s g p 、i p p 、p g p 、l p g 等优秀的规划器。第三种方法是引入启发式搜 索的智能规划方法。1 9 9 8 年b o n e r 和g e f f e r 提出了此方法，它使用启发式函数作为 衡量标准对规划求解空间进行剪枝，以达到提高效率的目的。着名的启发式规划器有 h s p 和f f 。与经典图规划方法不同的是，这两种规划方法都采用了放松的规划求解方 法。放松的规划图中不包含任何的互斥约束关系，而是使用启发式函数值如距离估计 作为求解中的启发式估计值，以便估量动作路径的优劣。 2 智能规划的应用 目前智能规划在机器人、智能软件、军事、航空航天等领域都得到了关注和应用。 3 东北师范大学硕士学位论文 智能规划在航空航天领域最好的应用是美国宇航局的a s p e n ( a u t o m a t e ds c h e d u l i n g a n dp l a n n i n ge n v i r o n m e n t ) 规划系统。1 9 9 9 年，a s p e n 获得了美国宇航局的软件比 赛优秀奖并且被广泛应用在外太空宇航器上。 在现代工厂生产中，智能规划思想也得到了较多的应用。例如工厂的作业调度问 题，在考虑加工资源有限的情况下根据现实条件对整个工厂的工作做出安排，力图使 得工厂的整体加工速度提升，机床空闲时间减少，全面提高同等水平设备条件下的生 产效率，从而给工厂带来可观的经济效益。 智能规划也可以应用于现今的商业中，例如运输问题。在物流应用问题中，需要 根据物资和交通工具的不断动态变化进行实时的行程安排和规划。交通工具可以是虚 拟问题中的房子里移动的机器人，也可以是城市运输队中的卡车，或是经典的电梯问 题中的电梯。在这些问题中，会涉及许多经典的规划问题中没有的资源限制，例如时 间限制、运输能力、行程时间、路途状况、资源优化等，并且在实际应用中还会遇到 不可预知的如交通拥挤、天气恶劣等问题。另外，这些运输规划在一定程度上还可以 应用于国家的军事调度问题。 智能规划的研究已经实际应用到许多领域之中，这里不能一一列举，这些应用 很多都取得了很好的效果，不仅提高了相应的工作效率，还带来了一定的经济价值， 为理论研究向实际应用指明了方向，为我们提出了更新的研究领域。 4 东北师范大学硕士学位论文 第二章规划识别 2 1 规划识别的概念 规划识别是这样一个过程，根据观察到智能体的片断的琐碎现象，推出具有合理 的因果联系的完整全面的规划描述的过程。一个规划识别器推出的规划既能补充一些 我们未观察到但又实际发生的现象，同时还可以预测未来，合理地推出智能体未来可 能采取的动作。 2 2 规划识别的研究方法 1 、以k a u t z 的理论为基础的研究方法 这种方法的主要思想是建立一个由动作的不同抽象组成的事件规划的层次结构， 该层次结构可以用来组成规划库。每当观察到一个动作，识别器就试图剪去和该动作 不一致的规划，把该动作加入到与其一致的规划中。规划识别时通过将观察到的动作 与这个层次结构相匹配，试图建立用户高层目标的规划。并作了两个封闭世界的假设： 已知的执行一个动作的方法就是执行该动作的所有方法： 所有动作都是有目的的，必须知道执行一个动作的所有可能的理由。这些假设 用来评价从一个观察到的动作集合得到的结论是否合理，可以通过m c c a r t h y 的限定 理论体现。 2 、以逻辑原理为基础的研究方法 根据采用的逻辑原理不同，主要有以溯因理论为基础的规划识别研究方法、以缺 省推理为基础的规划识别研究方法和以限定理论为基础的规划识别研究方法。 溯因理论是一种逆推理归纳，它是一种由结论成立推出前提以某种置信度成立的 归纳方法。这种方法的一般模式是：若h 为真时，则h 一 e 必为真：观察到e 成立： 则h 以某种置信度成立。l i n 和g o e b e l 发现了溯因理论和规划识别之间的联系， 可以将溯因理论运用到规划识别中，当观察到一个结论时，会寻找它发生的原因来作 为该结论产生的解释。 缺省理论是在知识不完全的情况下使推理得以继续下去的一种非单调推理理论。 缺省推理的核心是在默认或假设某些命题成立的前提下进行推理。c a r b e r r y 根据对 自然对话的分析以及对人类推理的心理研究提出了一个基于默认推理的规划识别的 模型。它的主要思想是通过支持适当的默认推理来延迟无根据的结论( 或决策) 直到进 一步的证据出现，从而逐步( 逐渐) 地更新用户规划的系统模型。 限定逻辑的基本思想是“从某些事实a 出发能够推出具有某一性质p 的对象就是 5 东北师范大学硕士学位论文 满足性质p 的全部对象”。规划识别和限定理论很相似，所以用限定理论来求解规划 东北师范大学硕士学位论文 1 、根据被推理的智能体在规划识别中的作用可以分为两类：洞孔式规划识别 ( k e y h o l er e c o g n i t i o n ) 和有意的规划识别( i n t e n d e dr e c o g n i t i o n ) ：这两种规划识别 的主要区别在于，在识别过程中，被观察和推理的智能体影不影响规划识别过程，洞 孔式规划识别不影响规划识别的过程，而有意规划识别它要起到影响的作用，这种影 响分别起到帮助识别过程或阻碍识别过程的作用。 2 、根据有无规划库又可以分为：有规划库的规划识别和无规划库的规划识别，有 规划库的规划识别主要以k a u t z 的方法为代表。无规划库的规划识别，j u nh o n g 的 基于目标图分析的规划识别和m i n g - h a oy i n ) i ij 的基于回归图分析的规划识别方法 都属十无规划库的规划识别。 2 4 规划识别的应用 规划识别的应用广泛，随着规划识别研究的发展，它的应用领域仍然在扩展。如 故事理解、自然语言识别、谈话分析、心理学模型和智能计算机接口等领域， 在操作系统环境中识别用户的规划是规划识别研究的一个方面，它可以使系统做 许多有用的事情。例如：提出建议、自动地纠正用户的错误，并自动完成任务。! 自然语言理解是规划识别研究的早期的最主要的应用领域。人与人之间的沟通和 交流就是有意地识别，需要识别讲话的意图。早期的故事理解系统都采用了规划识别 来提取故事的结构。根据一段谈话，这段谈话所传达的意思，识别出谈话的内容后， 自动地生成回答，这在早期的人机对话系统很有意义。规划识别在谈话分析上应用也 很广泛。一个好的机器翻译系统需要理解讲话者的规划和目标及意图。在一个对话系 统中使用规划识别来建议大学生的选课、如何得到学位等。识别用户的规划可以使系 统提出更适合和更有用的回答给学生。 智能用户接口直接面向的就是广大普通用户，运用规划识别可以站在用户的肩膀 上观察用户的动作，在适当的时候给用户提供帮助或识别出用户的目标后直接帮助用 户完成任务，减轻用户的负担。许多的智能帮助系统都是规划识别的典型代表；在智 能教学上、多智能体交互协作上也能找到规划识别的身影，并具有重要的应用价值。 在军事防御方面战术规划识别在军事防御中尤为重要。它可以识别敌方的目标及 规划，也可以阻止敌方对自己的规划的识别，在发现自己的目标被对方识别时，立即 生应对规划来阻碍规划识别过程。 在自动控制方面尤其是自动驾驶中智能体必须将自己的规划与其它驾驶员的规 划相互协调。这种协调依赖十对其它驾驶员动作的观察，如车的移动及标志。根据观 察到的其它驾驶员的动作识别出其它驾驶员的规划，然后调整和修改自己的驾驶规 划。 以上这些应用都向我们展示了规划识别研究的理论指导意义和它重要的实践意 义，相信对它的研究还将继续扩展，继续前进，更好的为我们的生活提供方便高效的 服务。 7 东北师范大学硕士学位论文 3 1 经典规划图算法 第三章规划图 1 9 9 5 年b 1 u m 和f u r s t 提出的图规划( 6 r a h l a n ) 方法。该方法创新性地使用了 规划图的结构来求解规划问题，在智能规划历史上具有里程碑式的意义。以规划图为 基础的智能规划算法主要包括两个算法：扩张规划图算法和搜索有效规划算法，在详 细阐述这两给算法之前，先对以图规划为基础的智能规划中所遇到的相关基本概念作 以详细交代。 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 ) 的集合，其中每个元素都是一个命题，而 且要求规划结束时这些命题必须是真命题。 我们要回答的问题是：在初始条件下，对对象实施怎样一些操作，才能使问题目 标得以实现。 操作有前提，有添加效果( a d d - e f f e c t ) ，删除效果( d e l e t e - e f f e c t ) ，有参数 ( p a r a m e t e r ) 。 时间可以被离散地表示。 操作不能创造对象也不能消灭对象。 2 动作与n o - o p 动作 一个完全实例化的操作叫做一个动作( a c t i o n ) 。 l o a d 是操作 l o a dal 是动作 m o v e 是操作 m o v el p 是动作 一种什么事也不做的动作叫做n o - o p 动作。 通常，在几个命题均为真的情况下，一个操作可以被执行；当一个操作被执行后， 通常有些真命题变假了，有些新命题产生了。 3 有效规划( v a l i dp l a n ) 设有一个动作的集合，其中的每个动作都被指明其被执行的时间步；在同一个时 8 东北师范大学硕士学位论文 间步中被执行的任何两个动作都是不相冲突( i n t e r f e r e ) 的，所有的问题目标在最 后的时间步均为真，那么，我们就称这个动作的集合为一个有效规划( v a l i dp l a n ) 。 其中，两个动作相冲突是指，如果动作a 删除动作b 的前提，或者动作a 删除动 作b 的添加效果，我们就说这两个动作相冲突。 如果一个动作的所有前提都在初始条件中，那么，这个动作可以在时间步1 中被 执行。一般地，对于t l ，当一个动作的所有前提条件都在时间步t 为真，那么该动 作在时间步t 可以被执行。 如果动作a 删除动作b 的前提，动作b 就不能被执行，当然动作a 与b 就不能同 时被执行。所以此时动作a 与b 是冲突的。当动作a 删除动作b 的添加结果时，就改 变了动作b 对整个规划的影响，改变了动作b 在整个规划中的作用，所以此时动作a 与b 也是相冲突的。 在规划问题中一个核心工作就是尽快找到一个有效规划。 4 规划图( p l a n n i n gg r a p h ) 规划图是这样一种数据结构，它将规划问题编码为规划图，利用规划图分析来搜 索规划解。 ( 1 ) 规划图的概念 规划图是由两种结点、三种边组成的有向分层图。规划图各层依次由命题层和动 作层交替出现，其中命题层由命题节点组成，动作层由动作节点组成。规划图中的边 用来表示动作与命题之间的关系，连接动作结点与上一层的命题结点的边( 前提条件 边( 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 ) ) 表示这 些命题是该动作的效果( 包括增加效果和删除效果) 。 ( 2 ) 规划图节点间的互斥关系 图规划方法的最重要的特征就是发现和记录动作结点或者命题结点间的互斥关 系，通过互斥关系，可以显著减少搜索的开销。 两个动作结点a 与b 互斥 设a 与b 是在一个规划图中某一动作列上的两个动作，如果不存在一个有效规 划能同时包含两者，就说动作a 与b 是互斥的。 判别方法： 如果动作a 删除动作b 的前提，则动作a 与动作b 互斥； 如果动作a 删除动作b 的添加效果，则动作a 与b 互斥； 如果动作a 的前提条件与动作b 的前提条件互斥，则动作a 与b 互斥。 o 两个命题结点p 与q 互斥 设p 与q 是在一个规划图中某一命题列上的两个命题，如果不存在一个有效规 划能同时包含两者，就说命题p 与q 是互斥的。 判别方法： 如果产生命题p 的所有动作和产生命题q 的所有动作都是互斥的，则命题p o 东北师范大学硕士学位论文 东北师范大学硕士学位论文 把动作1 的所有前提，动作2 的所有前提，动作n 的所有前提都放到一起 构成一个新的命题集，这是由时间步t - 1 中的命题列中的命题构成的命题集，叫做次 目标集。如果这个次目标集能用t - 1 步实现，则原目标集就能用t 步实现。创建次目 标集的过程叫做目标集合创建步( g o a ls e tc r e a t i o ns t e p ) 。 对次目标集在时间步t - 1 继续这一过程。 如果到某一步次目标集恰好是初始条件中命题集的子集，则有效规划就被找到。 如果到某一步排在前面的一个目标支持它的任意一个动作都与已经选定的动作 相冲突，则我们需要立即倒退。注意，此时并不意味着没有有效规划，因为支持动作 还可以有不同选法。 2 、以知识图为基础的规划识别算法 以规划图为基础的规划识别算法不止一种，有以规划知识图为基础的算法、有以 目标图分析为基础的算法、有以回归图为基础的算法等等，这里不一一列举，本文主 要以规划知识图为研究基础，所以重点介绍规划知识图算法。 1 、规划知识图基本概念 规划知识图是一个非循环的与或图。 是由代表规划( 事件) 的节点的集合组成的。节点间均由连接符连接，每一个k 连接符是从一个父节点指向一组共k 个后继结点，k 连接符还可以表示事件之间的整 体与部分、具体与抽象的关系，分别用两个表达式来表示：抽象表达式和分解表达式。 节点有两类：与节点和或节点。对应那种节点要看其与父节点的关系而定。详细 的说：如果一个父节点的后继是此父节点的具体化，即父节点与其后继节点的关系是 抽象与具体的关系时，这些节点称为或节点；如果一个父节点的后继是一组组成部分 节点，即父节点与其后继结点之间是整体与部分的关系时，这些节点称为与节点。 抽象与具体的关系：具体类型规划的出现蕴涵着抽象类型规划肯定出现，所以具 体类型规划的出现对抽象类型规划出现的支持程度为1 。 整体与部分的关系如果一个规划是由n 个组成部分规划组成的，那么全部n 个组 成部分规划都出现，这个规划肯定出现；即组成一个规划的所有组成部分规划的出现 对此规划出现的支持程度的和为l 。 支持程度：指一个规划的出现使另一个规划出现的可能性。 3 2k a u z e 的规划识别算法 k a u t z 的表示由于其形式化和丰富的表达能力而成为规划识别领域最著名的一 种表示方法。这篇文章中规划和动作都被统一称为事件。识别器的知识被描述为一个 被称为事件层的一阶描述集，它定义了抽象、具体、以及各种类型事件间的基本关系。 基于四个假设：穷尽假设( e k a ) 、互斥假设( d j a ) 、使用部件假设( c u a ) 、最小基数假设 ( m c a ) 。 对于每一个发现，都应用c u a 和抽象公理直接推导出一个e n d 类型的实例。有约 1 1 东北师范大学硕士学位论文 束检查来减少可选择物的数目。为了从两个发现中合并信息，使每一个发现或传递实 体中推导出的e n d 实例等价，从而减少析取式如果所有可选择物替代物都被删除了， 那么所有的发现都属十一个明确地e n d 事件。可以通过n 组发现来识别多个同时发生 的e n d 事件。因此有系统返回地最好的解释也许是事实不一致，因为发现是n 组不能 合并的信息。 该算法只描述了对事件层的处理，其中抽象层是一个森林，也就是说，它不处理： “多继承性 ( ”m u l t i p l ei n h e r i t a n c e ”) 。进一步说，为了限制推理，实现不 能处理和分解定理相关的推理。这种约束某种程度上限制了系统的预言的权利。 解释图( e x p l a n a t i o n g r a p h ) ：我们的实现通过用无因果描述规划识别来解决问 题。这种描述采用代标签弧降的形式，成为“解释图 ( ”e x p l a n a t i o n g r a p h ”或 “e g r a p h ”) 。这些图通过共享结构对分离的结论加以编码。由一个发现产生的 e g r a p h 在最坏的情况下能产生事件层的指数级的宽度。在所有例子中我们考虑共享 结构允许用的e g r a p h 比事件层小。一个e - g r a p h 包含二种结点。事件结点由事件标 签和单独事件辅助类型组成。一个事件标签n 一旦出现在e g r a p h 中，我们可以简化 结点的定义，恢复事件的辅助类型。n 1 到n 7 是所有的事件结点。专有的名词对对象 i f u 言是唯一的名字而不是事件或事件。模糊的时序约束( f u z z y t e m p o r a lb o u n d s ) 是 一个实数的四兀组。有两种弧，都能连到事件结点。参数弧标识一个角色功能f ：并 指向其值v 。第二种弧是交替弧，也是指向事件结点的。这些弧意味着原始结点和通 过交替弧指向的一个结点等价。注意事件标识不是事件结点唯一的名字，一般来讲， e - g r a p h 中的几个结点标识一个相同的真实世界事件。交替弧从一个特殊类型的结点 指向一个更具体类型的结点。 具体包含三个算法 1 、x p l a i n o b s e r v a t i o n 算法 2 、m a t c h g r a p h s 算法，实现最小基数假设( m c a ) 。即对所生成的解释图进行匹 配合并发现。 3 、g r o u p o b s e r v a t i o n s 算法，实现最小基数假设( m c a ) ，对不能合并的发现进 行分组，找到最细小数目的e n d 类型事件。 1 2 东北师范大学硕士学位论文 第四章基于规划图的用户规划识别研究 4 1 用户规划识别问题的相关概念 目前用户规划识别研究的相关内容并没有比较完整权威的定义，本文对研究所涉 及到的相关的用户规划识别概念作如下定义。 1 、用户规划 顾名思义，用户所执行的规划。一个用户访问一个系统总是为了一定的目的，为 了实现他的目的，他要执行一系列的动作，他所执行的这些动作使他从系统的初始状 态到达了他的目标状态，实际上他在执行一个规划，我们称之为用户规划。 2 、用户规划识别 从观察到的系统的初始状态和用户的最初几个动作，预测出用户的目标状态及到 达目标状态的可能的规划，这一过程我们称之为用户规划识别，得到的用户规划我们 称之为用户规划解。 3 、用户规划识别系统 。 实现用户规划识别的应用系统，也就是说，它是个应用软件，是我们应用与开发 的目的，是我们实现的最终目标。 4 、用户动作集 。 用户规划识别系统采集到的用户使用应用系统的动作。 5 、用户规划库 用户规划的仓库，它是一个动态的规划库，每一个新的用户规划将自动入库。 6 、用户目标库 用户动作集的集合，是用户规划识别系统识别的用户使用应用系统的可能目标。 4 2 基于规划图的用户规划识别算法 智能规划力求找到从初始状态到目标状态的规划解，规划识别要通过初始状态和 最初的几个动作识别其目标状态。本文将二者合一来研究用户规划识别问题。 1 、初始状态当用户使用应用系统，用户规划识别系统及时采集用户的最初几个 动作，生成用户动作集1 ； 东北师范大学硕士学位论文 2 、将此动作集与已有用户规划库中的规划进行比对；如果存在等于或大于的规 划，将这些规划生成用户目标库1 ，并反馈给用户； 3 、用户根据用户规划识别系统的反馈信息，选择在目标库中他使用应用系统的 目标，如果存在，用户规划识别系统识别成功，它将分析用户的目标，找到 用户实现目标的最优规划解，帮助用户完成下面的工作； 4 、如果不存在，用户规划识别系统继续采集用户动作，扩大用户动作集，生成 新的用户目标库，以此反复上述过程，直到生成用户规划为止； 5 、如果知道用户完成目标，用户规划识别系统也没有帮助用户找到最优规划， 那么将这个用户规划作为新的规划纳入到用户规划库中，用户规划识别系统 识别失败。 1 4 东北师范大学硕士学位论文 用户从反馈信息中选择一个规划 1 l 系统利用基于规划图的用户规划识 别算法找到最优规划 i 规划识别成功 将此规划作为新规 划纳入规划库中 6 、基于规划图的用户规划识别算法分析得到最优规划示意图 i 问题原型图 观察； l 规戈悃集 根据f 1 i 规划图解集 去除了 r l 最优规划 7 、以煮意大利面为例 问题原型图： 集 户反馈信息 余 1 5 东北师范大学硕士学位论文 a n y e v e n t f i g u r el ：c o o 嗯e v e n th i e r a r c l n , ，t h ea b s t r a c t i o na r c ，f r o m m a k e s a u c et oa n y l i v e n ti so m i n e d b rc l a r i t y ) 转换为规划图集为： 廷j 做饭( 3 国傲面团3 1 哼i 烧水3 ，图傲面条】1 - 1 9 傲调昧汁1 2 1 ， 傲大蔫番茄酱意 大科面条0 4 、奎散太蔫番苗酱自我奶滔蔼t 3 论6 做意大鹊面积i d 5 ：擎傲自脱 奶油面l1 的5 蛳做大蒜番茄酱2 1 1 1 6 【 ， - d 东北师范大学硕士学位论文 得到的规划图解集： d 傲饭。国髓暖团零烧水，回授函杀：傲潮睬汁做大慧 番茄蕾白晚钓醯。o 饿白糙奶浊。固微丈蕊番稚酱。 最后得到的最优规划： 订髓s i t 士剥噘蠡j 两暂砸薹圆蔼嗦升闯讳窳勘鲞厩蠡固豫鲁 1 7 东北师范大学硕士学位论文 结，论 用户规划识别作为规划识别的重要分支越来越得到的重视，众多专家、学者和研 究人员致力于这一交叉学科的研究。 本文通过对国内外用户规划识别算法的分析和研究，从全新的角度，对用户规划 识别算法提供了新的研究思路，对相关问题给出明确定义，对用户规划识别过程给出 完整描述，并给出了基于规划图的用户规划识别算法。算法过程也以图例的形式清晰 展示。 但由于精力与时间有限，对基于规划图的用户规划识别方法的研究中一些没有解 决问题的研究还将继续，我将乐此不疲： 1 用户规划识别器的开发。在后续的工作中，我们务必要提供更多业务领域的识 别算法和模型定义语言，力求制定出一套行之有效、适用于多领域的通用识别算法和 模型描述语言。从而使规划识别技术能够更好的适应实时性的用户规划检测，更好的 发挥用户规划识别器的研究意义与应用意义； 2 由于用户规划识别问题在现实世界中广泛存在，是智能体应用的主要方面，应 用系统的使用主要是面向广大的普通用户，尽快设计出具有多领域实用性的用户规划 识别器，实现从科学技术研究到商业应用的转变，推动规划识别技术在适用领域的业 务推广。 用户规划识别研究的应用前景是光明的，这激励着我们继续前行。 w ， 一 酊 东北师范大学硕士学位论文 参考文献 1 丁德路，姜云飞智能规划及其应用研究 j 计算机科学，v 0 1 2 9 ，第2 期，2 0 0 2 年2 月：1 0 0 1 0 3 2 3 d r e wm c d e r m o t t ，j a m e sh e n d l e r p l a n n i n g ：w h a t i ti s ，w h a ti tc o u l db e ，a n i n t r o d u c t i o nt ot h e s p e c i a l i s s u e o n p l a n n i n g a n ds c h e d u li n g a i m a g z in e ，7 6 ：卜1 6 ，1 9 9 5 3 p e d n a u l te a d l ：e x p l o r i