（计算机应用技术专业论文）敌意规划的识别和应对.pdf

摘要 人工智能的研究已经有半个世纪多的历史了，其影响几乎遍及整个计算机科学领 域。作为人工智能的分支智能规划和规划识别也取得了很好的研究成果，并且在航 空航天、工业制造等行业的应用中取得良好的表现。 许多关于智能规划的研究多关注于智能体之间的协作关系或不干涉关系，而对规划 中智能体之间敌意关系的研究则比较少。目前智能规划的应用已经深入到许多具有敌意 行为的环境中，例如网络安全领域、军事对抗领域等。因此对敌意规划的识别和应对进 行研究势在必行，而且这项研究具有深刻的理论价值和广泛的应用前景。 本文以智能规划和规划识别知识为基础，对敌意规划的识别和应对进行了研究，提 出一种应对规划器，给出了敌意环境、敌意规划、应对规划、敌意智能体及应对规划器 等概念，以及敌意规划的分类情况。 本文研究的应对规划器能够对敌意规划进行检测、识别和应对，其主要逻辑功能为 敌意规划识别和应对规划产生。该系统的主要组成模块为敌意动作捕捉器、敌意规划库、 敌意攻击检测器、模糊控制分析器和应对规划产生器，这些模块相互协作完成对敌意动 作的检测、观察，识别敌意规划，并根据识别出的敌意规划执行不同的应对规划以维护 系统的正常运行。 本文首次将相似度方法和模糊控制理论结合应用于应对规划器中。相似度可以用来 刻画两个变量的相似程度，在本文中使用相似度来描述两个动作向量的相似程度，用以 判断检测到的动作是否属于敌意规划；模糊控制是以模糊数学为理论基础，应用语言规 则表达方式和计算机技术，用模糊推理进行判断的一种控制策略，能够实现对非线性、 复杂系统的控制，敌意规划本身就具有模糊性，因此在应对规划器中加入模型控制原理 能够更好的解决敌意规划的识别问题。 本文提出的应对规划器是一种通用的概念模型，能够适用于多种应用环境，并且具 有良好的灵活性和可扩展性，可以方便的加入新的功能模块来扩展系统功能。 l 关键浏：智能脱划；规划识别；敌意规划；应对舰划；应对舰划器 a b s t r a c t a sar e s e a r c hf i e l do fs c i e n c ea r t i f i c i a li n t e l l i g e n c eh a sah i s t o r yo fm o r et h a nh a l fa c e n t u r y , a n di th a sa f f e c t e dt h ec o m p u t e rs c i e n c ei ne v e r ya s p e c t s a ip l a n n i n ga n dp l a n r e c o g n i t i o n a sb r a n c h e s o fa r t i f i c i a l i n t e l l i g e n c eh a v ea c h i e v e dg r e a tr e s e a r c hr e s u l t s ， m e a n w h i l ew i t hg o o dp e r f o r m a n c ei nm a n ya p p l i c a t i o nf i e l d ss u c ha sa v i a t i o na n di n d u s t r y m a n u f a c t u r e m o s tp l a n n i n gr e s e a r c hi sf o c u so nt h er e l a t i o n s h i po fc o o p e r a t i o na n di n d e p e n d e n t b e t w e e na g e n t s ，b u tf e w e ra t t e n t i o n so nh o s t i l er e l a t i o n s h i p h o w e v e rw i t ht h eu s i n go fa i p l a n n i n gi nm a n yr e a lf i e l d st h a tw i t hh o s t i l ea c t i o n s ，s u c ha sn e t w o r ks e c u r i t y , m i l i t a r y a n t a g o n i z i n g s ot h er e s e a r c ho nh o s t i l ep l a n si si m p e r a t i v eu n d e rt h es i t u a t i o n ，w h i c hw o u l d h a sg r e a tr e s e a r c hv a l u ea n dw i d e l ya p p l i c a t i o n 。 s o m er e s e a r c hw o r k sh a v eb e e nd o n ei nt h i sp a p e ro nt h er e c o g n i z i n ga n dc o u n t e r i n go f h o s t i l ep l a n sb a s e do nt h ea ip l a n n i n ga n dp l a n n i n gr e c o g n i t i o n ，b r i n g sf o r w a r dac o u n t e r p l a n n e r , a n dm a k e ss o m en e wd e f i n i t i o n so nh o s t i l ee n v i r o n m e n t ，h o s t i l ep l a n ，c o u n t e rp l a n ， h o s t i l ea g e n t ，a n dc o u n t e rp l a n n e ra n ds oo n t h ec l a s s i f y i n go fh o s t i l ep l a n si sa l s od i s c u s s e d i nt h i sp a p e r t h ec o u n t e rp l a n n e ri nt h i sp a p e ri su s e dt od e t e c t ，r e c o g n i z ea n dm a k ec o u n t e rp l a n st o t h eh o s t i l ep l a n s ，a n di t sl o g i c a lf u n c t i o n sa r er e c o g n i z i n gh o s t i l ep l a n sa n dm a k i n gc o u n t e r p l a n s t h em a i nm o d u l e sa r eh o s t i l ea n i o n sc a t c h e r , h o s t i l ep l a nl i b r a r y , h o s t i l ea t t a c k d e t e c t o r , f u z z yc o n t r o l l e ra n dc o u n t e rp l a np r o d u c e r a l lo ft h e s em o d u l e sw o r kt o g e t h e rt o d e t e c ta n dr e c o g n i z et h eh o s t i l ep l a n s ，a n dc a r r yo u tr e l e v a n tc o u n t e rp l a n st om a i n t a i nt h e s y s t e m sn o r m a lp e r f o r m a n c e t h i sp a p e rf i r s t l yb r i n g st h es i m i l a r i t ya n df u z z yc o n t r o lt h e o r yi n t ot h ec o u n t e rp l a n n e r t h es i m i l a r i t yi su s e dt od e s c r i b et h es i m i l i t u d eo ft w or a n d o mv a r i a b l e s ，a n di nt h i sp a p e rt h e l s i m i l a r i t yi su s e dt oe x p l a i nt h es i m i l i t u d eo ft w oa c t i o ns e q u e n c e si no r d e rt oj u d g ew h e t h e r t h ed e t e c t e da c t i o n sa r eh o s t i l ep l a n s ；t h e f u z z yc o n t r o lm e t h o di s b a s e do nt h ef u z z y m a t h e m a t i c s ，i sak i n do fc o n t r o l ss t r a t e g yu s e dt h ef u z z yr e a s o n i n g ，a n dc o u l dc a r r yo u tt h e c o n t r o lo ft h en o n l i n e a r , c o m p l e xs y s t e m t h eh o s t i l ep l a n sa l ef u z z y , s ot h eu s i n go ff u z z y c o n t r o lm e t h o dc o u l dm a k et h ec o u n t e rp i a n n e rw i t hg o o dp e r f o r m a n c e t h ec o u n t e rp l a n n e ri nt h i sp a p e ri sau n i v e r s a lm o d e l ；i tc o u l db ea p p l i e di nm a n y e n v i r o n m e n t sa sw e l la sw i t hw e l la c t i v i t ya n de x p a n s i b i l i t y k e y w o r d s ：a ip l a n n i n g ；p l a nr e c o g n i t i o n ；h o s t i l ep l a n ；c o u n t e r p l a n ；c o u n t e rp l a n n e r 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：翟咝日期：= 鲨 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定， 即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：甏邑丝星 指导教师签名： 日期：i = 丛日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 纽魁盟垡监 电话： 邮编： 引言 在人工智能领域中智能规划是较早的研究分支之一，对于它的研究涉及到知识表 达、知识推理、非单调逻辑、情景演算、人机交互和知识挖掘等多学科的内容。近年来 智能规划逐渐成为人工智能中的研究重点，先进入工智能学会( a a a i ，原名美国人工智能 学会) 每年的各种会议和期刊中都有大量有关智能规划研究的内容。随着研究的深入， 智能规划技术广泛应用于宇宙航行、车辆调度、工厂的作业调度等领域，并取得了很好 的效果。 传统的智能规划研究通常关注于执行规划的智能体之间的协作关系、互不干涉关 系，而对敌意关系、恶意行为研究的较少。但是在许多应用环境中，例如网络安全、军 事对抗、商业竞争等领域，都存在智能体或系统之间的对抗和敌意行为，因此对敌意规 划的识别和应对研究具有深刻的理论价值和广泛的应用前景。 本文以智能规划和规划识别的知识为基础，采用应对规划器对敌意规划进行识别 和应对。文中给出了敌意环境、敌意规划、应对规划、敌意智能体及应对规划器等概念， 并对敌意规划的分类进行了介绍。文中的应对规划器采用模块化设计思想，整个应对规 划器在逻辑功能上分为敌意规划识别和应对规划产生，其由敌意动作捕捉器、敌意规划 库、敌意攻击检测器、模糊控制分析器和应对规划产生器等五个模块组成。 本文的应对规划器中采用相似度和模糊控制思想实现对已知敌意规划的识别，以 及对不存在于敌意规划库中但已经威胁到系统安全性的潜在敌意规划的识别，并能及时 激活应对规划，从而阻止敌意规划的执行、维护系统的安全和正常运行。 本篇论文的结构如下：第一章对智能规划进行概述；第二章对规划识别进行概述： 第三章详细阐述了有关敌意规划的相关概念、应对规划器的模块组成及运行过程等内 容。 1 1 智能规划问题 第一章智能规划 智能规划是人工智能学科中的一个多领域交叉研究领域，是极富挑战性的一个研究 方向，它的研究方法和内容涉及到了知识表达、知识推理、非单调逻辑、情景演算、人 机交互和知识挖掘等多学科的各个方面。智能规划研究的是已知智能体的初始状态和目 标状态，求得一个动作序列，通过执行这个动作序列，智能体能够由初始状态到达目标 状态。 一个规划问题通常由以下集合组成： 操作的集合； 对象的集合； 初始条件的集合； 目标的集合。 1 2 智能规划的方法 ( 1 ) 基于逻辑的规划方法 逻辑规划系统是基于r o b i n s o n 的消解原理( r e f u t a t i o nr e s o l u t i o n ) 的，它采用 定理证明的方法，把求解规划的过程形式化为证明由初始状态和动作序列可以证明目标 状态的过程，其证明过程的解释就是一个规划解，也有人称这种方法为基于变化 ( c h a n g e b a s e d ) 的规划。逻辑规划系统以命题逻辑、一阶谓词逻辑等规范逻辑和各种 非规范逻辑如默认推理( d e f a u l ti n f e r e n c e ) 、或然推理( p l a u s i b l ei n f e r e n c e ) 、时 序( 时态) 逻辑( t e m p o r a ll o g i c ) 、内涵逻辑( i n t e n s i o n a ll o g i c ) 、非单调逻辑和 模糊逻辑等为其理论基础。较为典型的逻辑规划系统是n e w e l l 、s h a w 和s i m o n 等在1 9 5 6 年设计的逻辑理论家( l o g i ct h e o r i s t ) 程序“1 和g r e e n 的o a 3 脚系统。但是基于演绎的 定理证明方法直接应用于规划问题求解有其固有先天性不足，它会产生一些异常模型 ( a n o m a l o u sm o d e l s ) ：存在一些模型，它们满足定理，但是没有相应的有效规划解存 在。c h a p m a n 深入地研究了模型和规划解的对应关系，提出了模型对应规划解的充分条 件，并且给出了证明过程。因此在智能规划领域人们普遍认为：规划问题必须用具有特 定目的的定理证明器来解决，即一般性的定理证明器不能求解普遍的规划问题，或者增 加领域( 启发式) 知识，或者在推理的方式上进行有效的扩充。 2 ( 2 ) 基于启发式搜索的规划方法 目前规划系统为了提高效率，几乎都采用了启发信息。启发式搜索的基本思想是： 人为给定一个评估函数，对每个搜索状态进行计算，得到每个状态的值，从而决定哪个 状态较好。但是，这个启发函数用在与领域无关的规划系统上比较困难。 在当前智能规划研究中，领域无关的启发信息的抽取技术是基于实现目标的动作数 量，对要解决的问题p 放宽到一个比较简单的问题p ，抽取技术就是基于p 来评估。 b o n e t 汹3 提出的向前搜索的一个放宽方法就是将操作的删除边忽略，对于每个状态s ，得 到在放宽了的问题p 的启发函数h ( s ) 就可以作为原有问题p 的启发函数h ( s ) 的下 限，这样h ( s ) 就可以作为合适的启发函数作用在原有问题p 上。 实质上，初始状态和操作可以理解为一个定义了的节点有向图，对于每个操作o p 都 有一条由其前提条件节点指向正效果节点的边，这样从初始状态到达节点p 的开销就可 以计算。 使用了启法式思想的规划系统主要有：h s p 。2 1 规划系统，m e t r i c - f f 1 规划系统以及 l g p o ”规划系统等。 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 来评估。b o n e t 提出的向前搜索的一 个放宽方法就是将操作的删除边忽略。对于每个状态s 得到在放宽了的问题p 的启发 函数h ( s ) 就可以作为原有问题p 的启发函数h 车( s ) 的下限，这样h ( s ) 就可以作为合 适的启发函数作用在原有问题p 上。 m e t r i c f f 能处理用数字表示的约束和对用数字表示的状态数值变量的影响，它可以 根据用户两个要求来分别对规划系统进行两种设置，这两个要求是： 在最短时间内生成合法规划 生成最优的规划 前一种设置搜索技术采用跟f f v 2 2 类似的加强爬山法。这种方法是：采用放宽 规划长度作为从初始状态到目标状态距离的估计和利用动作互斥来剪枝向前搜索；后一 种设置搜索技术采用类似标准的斛算法，利用采用放宽规划长度作为从初始状态到目标 状态距离的估计也就是启发函数。在两种设置中放宽规划很自然的从s t r l p s a d l 中扩 展得到。只需要在预处理阶段把数值型约束和影响转化，使得它们都是严格单调的。 在这些严格单调的限定下通过忽略所有删除边和数值影响变元来放宽一个规划， 如果这个放宽规划得到解决，那么m e t r i c f f 综合考虑它的逻辑和数值因素跟f f - v 2 2 计算启发函数；假如在没有一个放宽规划能到达这个状态，那就证明这个状态是不可达 的。 l p g ( l o c a ls e a r c hi np l a n n i n gg r a p h s ) 规划系统是一种基于局部搜索和规划图的 规划系统，并且能够处理用数值来表示的度量和持续时间，并且能解决生成规划和优化 规划方面问题。l g p 基本的搜索策略基于w a l k s a t 个高效的s a t 问题求解程序。 3 l g p 的搜索空j 1 日j 是一个“动作图”( ”a c t i o ng r a p h s ”) ，部分规划子图就表示了部分规划 搜索步骤就是一个图的修改，使得一个“动作图”转换成为另一个“动作图”。l g p 使用 了一种紧凑的规划图表示形式来定义搜索邻近点，使用参数启发函数来评价它的值。这 些参数表示在这个部分规划中不同种类冲突的权值在搜索过程中动态计算。评价函数采 用了些通常的启发技术，例如对一个前提条件计算启发搜索开销和启发执行开销。持 续的动作和数字化的量值都表示在“动作图”，且通过评价函数模型化。l g p 在测试例子 中能产生高质量的规划，因为每一次生成一个规划的序列，下一次质量会在这基础上得 到提高。l g p 采用了跟f f 相似的“最好优先”( b e s t f i r s t ) 算法，系统能在进行了若干 步搜索后会自动转换到“最好优先”搜索。 ( 3 ) 基于模型检测的规划方法 模型检测( m o d e lc h e c k i n g ) 是当前计算机研究领域上的一个热点，它将一个系统模 型跟逻辑需要进行比较，从而发现不一致性。近期将这个思想应用在智能规划研究中， 取得了令人瞩目的成就，产生了一系列功能较强的规划系统如：m b p 、m i p s ”1 、 t a l p l a n n e r ”和u m o p 。 在2 0 0 0 年规划大赛上，规划系统m i p s ( t h em o d e lc h e c k i n gi n t e g r a t e dp l a n n i n g s y s t e m ) 使用两元判定图表b d d ( b i n a r yd e c i s i o nd i a g r a m s ) 来表示在规划问题中的状 态，有效地扩展了搜索空间。它是一个基于模型检测的规划系统，可以处理p d d l 语言 的s t r i p s 部分和a d l 一部分语言特性，例如：否定前提条件和全称的条件影响。在近 期，象征和显式的模式数据库已经作为与领域无关的、可容许的和非实时计算来对全局 的象征和显式的搜索过程进行估计。 在2 0 0 2 年a i p s 大赛上，规划系统m i p s ( t h em o d e lc h e c k i n gi n t e g r a t e dp l a n n i n g s y s t e m ) 夺得了表现优秀奖，并且基于模型检测( m o d e lc h e c k i n g ) 的规划方法被认为 是当前智能规划研究领域的一个热点。规划系统m i p s 向p d d l 2 1 扩展能够处理数值度 量和持续时间。在完全自动组，m i p s 解决问题的数量最多，唯一能在所有测试例子产生 规划，夺得了表现优秀奖。m i p s 主要结合了模型检测技术和放宽式规划技术：采用了静 态分析技术对状态编码进行优化，简化了命题和实例化动作的编码空间；在象征或显式 的模式数据库( p d b ) 内，采用放宽式规划技术来对搜索过程进行估值；根据动作集和利 用因果结构，采用路径分析来对生成有序的规划解进行调度优化。 图1 1m i p s 的体系结构 4 ( 4 ) 基于规划图的规划方法 图规划9 3 方法在智能规划领域中引入了规划图的方法，其主要思想是：由初始条件 对应的命题节点构成初始命题列。从初始命题列开始扩展规划图，在扩展的过程中，考 察同层命题节点的“互斥”关系以及同层动作节点问的“互斥”关系，通过对互斥的考 察有效的控制了规划图的增长速度，当所有目标命题都出现时，进行有效规划的提取。 如果有效规划提取成功，则输出有效规划，算法结束；否则继续扩展规划图，直到找到 有效规划( 成功) 或规划图进入稳定状态( 该规划问题无解) 。图规划算法主要包括规 划图扩展和有效规划搜索两个部分。 规划图扩展算法： a 时间步1 的命题列的生成，把初始条件中的所有命题作为时间步1 的命题列，一 个命题一个节点。 b 时间步1 的动作列的生成，对操作集合中的每一个操作进行考察，把能够实例化 的都进行实例化( 只要一个操作的前提都在当前命题列中，并且两两不互斥，该操作就 可以被实例化) ，每实例化一个操作，就得到一个动作节点。这样就可以生成时间步1 的动作列。将动作节点与作为其前提条件的命题节点用前提条件边连接。 c 假定时间步i 的命题列与动作列均已生成，时间步i + l 的命题列的生成，时间步 i 的所有动作( 包括n o - o p 动作) 的添加效果构成时间步i + l 的命题列。将时间步i 的 动作列的每个动作节点与作为其添加效果的命题节点用添加效果边相连接，与作为其删 除效果的命题节点用删除效果边相连接。如果命题p 是动作a 的一个添加效果，就说动 作a 支持命题p 。如果支持命题p 的任意一个动作都与支持命题q 的所有动作相冲突， 则说命题p 与q 互斥。考察动作间的冲突关系，对于每个动作标出与之互斥的动作列表。 考察命题间的互斥关系，标出相应的互斥的命题。 d 在当前的命题列中搜索问题目标，如果目标集中的所有命题均在此命题列中出现， 并且任意两个命题都不互斥，则规划图扩张结束，转为搜索有效规划；如果规划图进入 “稳定”状态则该问题无解，结束；如果目标集中还存在未在此命题列中出现的命题， 则生成时间步i + l 的动作列。 e 时间步i + l 的动作列的生成，对操作集合中的每个操作，只要它的所有前提都出 现在时间步i + l 的命题列中，并且任意两个命题都不互斥，便可以实例化该操作，并得 到一个动作节点，把所有可能实例化的操作都进行实例化，这样便得到时间步i + l 的动 作列。将时间步i + l 的每个动作节点与作为其前提条件的命题节点用前提条件边相连接， 转步骤c 。 有效规划搜索算法； 从时问步2 开始，每当一个时间步的命题列生成完毕后，就在此命题列中搜索目标 集。如果在时间步t 问题目标集合中还有未出现在命题列中的命题，则继续扩张规划图。 如果在时间步t 问题目标中的所有命题均出现在命题列中，并且任意两个都不相冲突， 则进行有效规划搜索，算法如下： 5 在规划图的最后一列( 必是第t 个时f 日j 步的命题列) ，任意取定一个目标集中的命 题( 可以是命题列中上数第一个属于目标集的命题) 考察在时间步t - l 中以这个命题 为添加效果的所有的动作( 叫做支持该命题的动作) ，从中取定一个动作，如动作1 。再 从余下的问题目标集中取定一个命题，考察时间步t 一1 中支持它的动作，从中取定动作 2 ，要求动作2 与动作1 不相冲突。如果动作2 与动作l 相冲突，就换一个与动作1 不 相冲突的动作来取代动作2 。依此类推，继续这一工作。最后，假定从时间步t - i 中取 定动作n ，它支持目标集中最后一个命题，并且它与已经取定的动作1 ，动作2 ， 动作n 一1 不相冲突。 把动作1 的所有前提，动作2 的所有前提，动作n 的所有前提都放到一起构 成一个新的命题集，叫做次目标集。如果这个次目标集能用t - i 步实现，则原目标集就 能用t 步实现。创建次目标集的过程叫做目标集合创建步，对次目标集在时问步t - i 继 续这一过程。如果到某一步次目标集恰好是初始条件中命题集的子集，则有效规划就被 找到。如果到某一步排在前面的一个目标支持它的任意一个动作都与已经选定的动作相 冲突，则需要立即回溯。注意，此时并不意味着没有有效规划，因为支持动作还可以有 不同的选法。 a t a l mbl a t 竞l 塞= = ： a t b l a f 托l “r 氍嚣：1 箸：麓。 麓篡。1 一嚣嚣鼍。：嚣“：瑟警 a “。 图1 1 火箭实验域中规划图的扩展 智能规划的研究在国际上已经进行的比较深入，在国内目前从事智能规划研究工作 的主要组织有：中山大学的姜云飞教授及其团队、吉林大学的孙吉贵教授及其团队和东 北师范大学的谷文祥教授带领的研究团队等，并且各研究组织都在相应的研究领域中取 得了不错的成果。 以上种种迹象表明智能规划已经再次成为人工智能研究领域的一个热点，有关智能 规划的火热研究已经展开。 6 a i # m z m n ga l m ! ，：h c d u l i u gi i 枷川s 。，+ j 。，一。一 ll h 簖删e1m 撼c o n t i n u o u st i m c 厂l d i r e t e s t a t e m l x c d s t a l c删s 龇 广一t 一1 厂 f _ 卜 s ”哪州c h e u f f d clo c a l t r a n ( o n n a l h m s y t e r m t l c h e u r i s t i c 亿衅“肼协l 蛔 s y q e 眦眦h e u r i s t i c l ，c ：i i s c a 呐s r c h s e a r c h m e t h o d s e a r c hs e a r c hm e i b o d s融a w hs e a r c hs e a r c h g 。ki l l | l 卵a x i t m pa s p f ns a t p l a ns p i e - 2m e t d e - f fl p s a ts f l o p 2m i p s l p g p m p p l a nf fi l p - p i ，a no - - p l a n 2( j r 。r ry a i 。p l a n n c r s a p a u c p o pa “a hb l a c k l x ) xg r t m o z e n o e u r o p a s v s t e m r g r t 1 2 智能规划的应用 图1 2 主要规划和调度方法分类 作为任何一种理论的研究其最终的推动力都来自实际应用的潜在价值，因此理论研 究想要进行的更加长远必须以广泛的应用前景和应用价值作为动力。目前智能规划主要 应用在自动系统中，智能规划理论的引入使得自动化系统的灵活性、健壮性和适应性都 得到提高。其主要的应用研究领域有：机器人、智能企业和商业软件。在i j c a i o l 的 智能规划讨论会上，讨论了会议主题“资源约束规划”，目标就是为实际应用上的规划 研究学者提供一个交流的平台，使理论研究与实际应用更好的接轨。会议上的规划系统 都是在计算机实际应用系统中得到广泛使用的规划系统，例如：美国宇航局的a s p e n 规 划系统、马里兰大学的c i r c a 、美国宇航局的e u r o p a 、华盛顿大学的l p s a t 规划系统和 爱丁堡大学的o - p l a n 规划系统等等，下面对智能规划的主要应用领域进行简要介绍。 ( 1 ) 在航空航天中的应用 智能规划的一个重要应用领域是航天航空，在航天航空应用中取得最好效果的是美 国宇航局的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 ge n v i r o n m e n t ) “3 1 规划系统。 a s p e n 获得了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 结合了宇航器操作约束、飞行规范、宇航器硬 件模型、科学实验目标和操作过程来自动生成较低层次的宇航器操作序列，同时通过自 动生成宇航器操作序列，然后结合了相关的领域知识a p s e n 使得宇航任务可以由一个小 分队来控制，这样降低了宇航任务的开销。 a s p e n 是一个基于面向对象的规划系统，提供了一组可重用的软件部件，这些部件 7 可以比较简单地应用在目前复杂的规划系统上，包括： 约束模型语言，可以令用户方便的定义应用领域； 约束管理系统，用来表示和维护宇航器的可操作性、资源约束和操作需要的条件； 一组搜索策略，用来规划生成和修改，并满足“硬约束”； 一种语言来表示规划选择和优化这些选择； “软”的、实时的修正规划能力； 时序推理系统，用来表示和维护时序约束； 图形化规划和调度的界面。 智能规划在航空航天领域应用的一个具体例子是哈勃空间望远镜( h s t ，f l u b b l e s p a c et e l e s c o p e ) 的修复，在修复过程中，地面人员不断得到关于h s t 能作什么、不能 作什么的最新信息，然后对修复工作做出规划，从而使h s t 恢复了正常观测能力。 智能规划在该领域中应用的实例还有：由国际计算机资源组织( c o m p u t e rr e s o u r c e i n t e r n a t i o n a l ) 、m a t r am a r c o n is p a c e 公司和爱丁堡大学( u n i v e r s i t yo fe d i n b u r g h ) 人工智能应用研究所( a z a z ) 的研究人员组成的协会，为欧洲航天局( e u r o p e a ns p a c e a g e n c y ，e s a ) 开发了一个名为o p t i m u m a i v 的系统，用于宇宙飞船装配和测试过程中动 作的规划和安排。这个系统主要负责飞船整个生命周期中的装配和检测工作，其中不仅 要对动作进行安排，还要对规划的执行情况进行监督。在该系统的自主规划和调度过程 中应用了基于知识的规则，用能够表示飞船装配动作先决条件和效果的算子来实现动作 的协调和规划的校验，并且利用修复规划机制对失败的测试加以修正。 和其他的应用软件一样，e s a 的o p t i m u m a i v 规划系统也需要将它的运行与其他的系 统或人类专家相结合。专业领域的工程师们可以参与到规划过程中，并可以在规划执行 过程中对遇到的问题进行再次规划。 ( 2 ) 在机器人中的应用 智能规划还可以应用在机器人领域中，其具体的应用主要有：环境的模型化描述、 机器人能力的模型化描述、目标的模型化描述和实时的输入响应。机器人规划研究跟其 它规划研究领域有些不同之处，主要在于机器人经常需要处于有噪音干扰的各种类型的 环境模型中，它通过感应器和交流信道收集和获得到的信息都可能存在着噪音，在这种 情况下机器人就需要将感应环境和执行直接规划进行整合。 目前在该领域的主要研究方向包括： 路径规划：指在机器人从一个开始的位置如何走到目标位置的控制机制并且要 满足动态的约束。 感知规划：主要是有关如何采集外部和内部信息的规划，例如：辨别物体确定机 器人位置对环境的观察。 任务规划：跟传统的规划问题相似，不过更加注重时间和资源的分配在动态的环 境、不确定的或部分已知的状态知识的条件下进行规划。 规划交流：多个机器人之间和人与机器人之间如何进行信息交换，包括询问信 8 息和反馈信息两大部分。 智能规划在机器入学中具体的应用方向有：环境模型的描述，控制知识的表示，路 径规划，任务规划，非结构环境下的规划，含有不确定性时的规划，协调操作( 运动) 规 划，装配规划，基于传感信息的规划，任务协商与调度和制造( 加工) 系统中机器人的调 度等。 ( 3 ) 在智能工厂中的应用 智能规划是人工智能研究中应用性很强的又一个研究领域例如，在工厂作业调度 规划问题中( j o bs h o ps c h e d u l i n g ) ，就是要考虑在有限的加工资源( 如车床，刨床，钻 床等) 的情况下，根据已知的工件加工顺序要求来对整个车间的生产做出合理有效安排 和规划，使得加工完所有工件所需的时间尽可能的少，每台机床的等待时间尽可能的 短。通过在生产中引入智能规划理论能够使工厂在具有同样设备条件下，由于作业调度 规划合理而增加了生产能力，从而给工厂带来了可观的经济效益。 智能规划在智能化工厂中的应用“”是指从生产设计到生成产品、监测生产等一系列 过程，它不只包括在单个企业中的应用，还可以同时处理多个企业之间的关系，例如：供 应链和虚拟企业。智能规划在智能化工厂中的应用主要采用资源约束的方法进行有效规 划求解。 目前主要研究领域包括： 生产流程规划：在一个功能化的工厂中将一个生产要求转变为一组详细的操作 指令。许多基于知识工程的软件在这方面取得了较好的效果，先将现实生产流程转化为 知识库中信息，然后再根据相应的生产要求来转化。 生产安排规划和调度：将生产安排用来迎合客户的需求按时交货，即我们通常 说的e r p ( e n t e r p r i s er e s o u r c ep l a n n i n g ，企业资源计划系统) 作业调度。 智能规划在工业行业中也有很大的应用价值：在酿造业中，发酵池属于紧缺资源， 在设计啤酒厂时，规划系统可用于分配当前可用的发酵池，用以生产小批量的啤酒和浅 色啤酒：在海运业，港口中要使用庞大的起重机往船上装卸集装箱货物，规划系统用于 确定船只行进和起重机分配的顺序，以保证工作的完成。 ( 4 ) 在商业中的应用 智能规划在商业中的应用更加广泛，目前主要的研究领域有：网络信息集成和运输 规划。 网络信息集成“”的过程是根据领域本体的内容，从互联网上采集信息并将信息集成 到领域本体中，网络信息集成的实质意义是为网络信息提供一种重新组织和理解的机 制，目前对这方面的研究主要集中在查询规划中。查询规划可以定义为：把对信息对象 框架的查询转化成只对信息源作访问的操作序列。在规划的执行过程中有时需要将信息 源返回的结果合并起来分析以做出下一步的规划，所以信息的合并是查询规划中的一个 重要环节。可以把信息的合并定义为：合并两个残缺信息对象的框架，即将两个属性值 q 对集结合成一个属性值对集，对其进行合并的依据是信息源之间的相关链接。目前查询 规划已经扩展到生物信息奄询上，较好的有在i b m 公司的d i s c o v e r yl i n k “”系统上的应 用。 在目前物流应用问题中根据动态的不断改变的运输要求可以对一队交通工具进行 实时规划( 行程调整和计划安排) “”。这些交通工具可以是：在一个房子里边的移动机 器人、在一个城市道路上的的士甚至是人工智能中经典的电梯问题。然而在这样的问题 中存在着很多的制约条件来使得运输规划变得复杂，例如时间限制( t i m ew i n d o w ) 、最 终期限、运输能力、行程时间、资源优化，更多的是如交通状况、天气状况、车辆中途 损坏等不可预测的事件，所有的这些因素使得事先制订的执行顺序无法正常运行，在这 些变得复杂的运输问题中引入智能规划方法，对问题域中的交通运输工具进行实时规 划，能够提高物流系统合理高效运行的效率。其优点就是在获取信息后自动安排出较优 方案，并能根据环境变化和需要随时修改方案。另外运输规划在处理突发事件的大规模 运输调度中也有所应用“”，例如可应用在交通控制和短时间内的军事调度、部署中。 另一种典型的工厂作业调度规划问题是考虑在货运汽车辆数有限的前提下，在不同 的地点之间运送货物。规划的输出是一张车辆运转计划表，使得汽车尽可能地满载运输， 空车运行情况尽可能地少，车辆闲置的情况尽可能地少，从而节省资源提高货车的使用 率，当然同时也会给运输公司带来可观的效益。美国联帮太平洋铁路( u n i o np a c i f i c r a i l r o a d ，u p r r ) 有3 1 0 0 0 多英里的铁路，覆盖美国西部的2 4 个州。如果采用手工编制 部分调度计划的话，完成全部的工作需要几天时间，而且会由于规划的资源利用率低造 成很大浪费。m u r p h y 等人1 9 9 6 年1 月为美国联帮太平洋铁路建立了铁路自动调度系统 r t s ( r a i lt r a i ns c h e d u l e r ) ，r t s 能够产生好的、低费用的调度规划。美国联帮太平 洋铁路由于使用了这个调度系统，每年在调度工作方面可以节约资金达5 0 万美元。 伴随着人们对智能规划研究的逐步加深，智能规划已经进入许多领域的实际应用之 中，并且取得了很好的效果。智能规划应用的推广不仅提高了相应的工作效率，带来了 一定的经济价值，更加为理论研究指明了方向、提出了不断更新的研究领域。 1 0 2 1 规划识别问题 第二章规划识别 规划识别是根据观察到的智能体片段的、琐碎的动作来推断智能体的目标和它所执 行的规划，从而能够解释智能体已执行的动作，并且预测智能体将要执行的动作序列。 作为人工智能研究的一个分支，规划识别涉及到知识表达、知识推理、非单调逻辑、情 景演算、人机交互、知识挖掘以及心理学等多个学科。 规划识别问题通常由如下集合组成： 动作描述集合； 有限的、动态世界的对象集合； 初始条件的命题集合； 已观察到的动作集合； 目标描述集合。 规划识别问题的解包括：与已观察的动作相一致的目标，以及与已识别的目标或部 分识别的目标相对应的动作组成的有效规划。 2 2 规划识别的方法 规划识别作为一个研究问题而出现开始于1 9 7 8 年，s ch i i l i d t ，s r i d h a r a n 和 g o o d s o n 把心理学实验与c o h e n 等人的提供人类行动证据的实验啪1 相结合，用于推理 其它智能体的规划及目标。在此后陆续出现了一些其他的规划识别理论方法。 ( 1 ) 基于事件层次的规划识别 1 9 8 6 年k a u t z 和a l l e n 在。中提出了一种通用的规划识别模型，这个规划识别模型 几乎包括了规划识别的所有子任务，是规划识别研究中的第一个形式化理论，这在规划 识别研究历史中具有重要的意义。该理论的主要思想是建立一个事件( 规划) 的层次结 构，由动作的不同抽象组成，如此建立一个规划库，在规划识别时通过将观察到的动作 与这个层次结构相匹配，试图建立用户高层目标的规划。每观察到一个动作规划识别器 就剪去和该动作不一致的规划，并把该动作加入到与其一致的规划中。 在这个规划识别方法中，k a u t z 作了两个有关封闭世界的假设： 已知的执行一个动作的方法就是执行该动作的所有方法： 所有动作都是有目的的，必须知道执行一个动作的所有可能原因。 这种规划识别方法具有丰富的表达能力，可以处理动作间的时序关系及不完全