（计算机软件与理论专业论文）一种基于目标驱动理论的应对规划方法.pdf

摘要 经典规划对规划问题做如下三条假设：规划问题的目标是世界状态的逻辑描述；规 划器所采取的动作是改变世界状态的唯一来源；动作由前提条件与效果来描述。也就是 说，在经典规划所研究的绝大多数问题中，智能体处在一个封闭环境中。丽在复杂的敌 对领域中，智能体所处的环境是部分可观察的，非确定的，动态的，多智能体的，即任 务环境是开放的。 现有的敌对规划方法主要是基于h t n 的目标驱动方法，但是传统敌对规划方法还存 在一些问题并具有一定的局限性。 本文在提出了敌对规划、基本防御树和目标标度等概念的基础上，将敌对双方基本 防御树中的目标作为智能体在对抗过程中识别敌方规划、制定本方规划的重要依据；通 过在每一个当前状态下，比较敌方所有可能规划中不同类目标的关键值，使智能体能够 在敌对过程中及时地发现重点问题与潜在的机会，从而有效地预测与识别敌方规划，指 导己方规划的制定与执行；对频繁出现的偶然事件，本文通过对关键值、防御值等概念 以及相关算法的运用，使智能体可以有针对性地进行选择处理。在新概念的基础上给出 了一种应对算法，将智能规划与规划识别更紧密地结合起来，提高了规划制定的策略性。 新的应对规划方法在具有敌对特性的领域中，诸如入侵检测、网络安全、战争和经 济等领域，都有着非常广阔的应用前景。 关键词：智能规划：规划识别；敌对规划；基本防御树；目标标度 a b s t r a c t c l a s s i c a lp l a n n i n gp r o b l e m sn 出a s s u m p t i o n sa b o u tt h ew o r l da sf o l l o w s ：t h eg o a l so f t h ep l a n n e ra r ea l o g i c a ld e s c r i p t i o no fw o r l ds t a t e s ；t h ea c t i o n st a k e nb yt h ep l a n n e ra l et h e o n l ys o u i c e so fc h a n g ei nt h ew o r l d ；e a c ha c t i o nc a nb ed e s c r i b e db yt h ec o n d i t i o n su n d e r w h i c hi tc a nb ea p p l i e da n di t se f f e c t s0 1 1t h ew o r l d h o w e v e r , t h ea d v e r s a r i a lp l a n n i n gi so n e o ft h em o s tc o m p l i c a t e df i l e d s g e n e r a l l y ，t h ec h a r a c t e r i s t i co ft h ee n v i r o n m e n ti n w h i c ha l l a g e n tl i e sd u r i n gt h ea d v e r s a r i a lp r o c e s s ，i si n a c c e s s i b l e ，n o n d e t e r m i n i s t i c ，d y n a m i c ， n o n e p i s o d i c ，a n dm u l t i a g e n t t h e r e f o r e ，t h ec o n v e n t i o n a lm e t h o d si nt h ec l a s s i c a lp l a n n a i n g i sn o ta p p r o p r i a t ev e r yw e l lf o rs o m ea d v e r s a r i a lp r o b l e m s p r e v i o u sa d v e r s a r i a l p l a n n i n ga p p r o a c h e ss o l v ep r o b l e m sg e n e r a l l yb a s e do nt h e h i e r a r c h i c a l l yd e c o m p o s i t i o no ft h eh t np l a n n i n g ( h i e r a r c h i c a lt a s kn e t w o r kp l a n n i n g ) c o n v e n t i o n a la d v e r s a r i a lp l a n n i n ga p p r o a c h e sm e n t i o n e da b o v es t i l lh a v er e s t r i c t i o n s s o m en e wd e f i n i t i o n sb a s e do ng o a ld r i v e na r ci n t r o d u c e di nt h i sp a p e r , s u c ha sb a s i c d e f e n s et r e e g o a lm e t r i ca n d 吼c t h eg o a l si nt h eb a s i cd e f e n s et r e e so fb o t ha d v e r s a r i e sa r c t a k e na st h eb a s i cr e f e r e n c eo f p r e d i c t i n ga n dr e c o g n i z i n gt h ep l a n so f t h eo p p o n e n ta g e n ta n d m a k i n g0 1 1 1 c o u n t e rp l a i l sd u r i n gt h ea d v e r s a r i a lp r o c e s s t h i sp a p e rp r o p o s e sa na p p r o a c ht h a t i ne v e r yc u r r e n ts t a t e ，a na g e n tc o m p a r e st h ek e yv a l u e so ft h ei n b o m o g e n e o u sg o a l st h a t a p p e a ri na l lt h ep o s s i b l ep l a n so ft h eo p p o n e n ta g e n t t h r o u g ht h i sa p p r o a c h , a l la g e n tc a n d i s c o v e rt h em o s ti m p o r t a n to p p o r t u n i t ya n dp r o b l e mi nt i m e ；p r e d i c ta n dr e c o g n i z et h ep l a n s o f t h eo p p o n e n ta g e n t e f f e c t i v e l y a l s o , t h ea p p r o a c h w ep r e s e n th e r ec a nd e a l 、i t hs i g n i f i c a n t c o n t i n g e n c ye v e n t si n t e n t l yb ya p p l y i n gt h ek e yv a l u e ，d e f e n s ev a l u et h a ta r eb o t hi ng o a l m e t r i c ，a n dan e wa l g o r i t h mt ot h e m t h e na l la g e n tn e e d sn o tt od e a lw i t ha l lt h ec o n t i n g e n c y e v e n t sb l i n d l ya sc o n v e n t i o n a l a p p r o a c h e sd i d t h ei m p r o v e dg o a ld r i v e nm e t h o dh e r e i nc a r lb ea p p l i e dw i d e l yi nt h ea d v e r s a r i a l p l a n n i n gd o m a i n ss u c ha si n t r u s i o nd e t e c t i o n , b a t t l e ，a d v e r s a r i a lg a m ea n de t c 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 ；a d v e r s a r i a lp l a n n i n g ；b a s i c d e f e n s et r e e ；g p a lm e t r i c n 独创性声明 本人声明瑟堡交豹学像论文是本人在等翔撂导下述霉戆磅究王俸及驳褥瓣磅究 成果。据我所知，除了文中特别加以标注和数谢的地方外，论文中不包含其他人已缀 发表或撰写避载硬突成果，也不包含为获得东l e 魉蕊大学或其链教努极掏鲍学篷或涯 书面使用过的材料。与我一间工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明势表示谢意。 学位论文作者签名：嚣期： 学位论文版权使用授权书 本学位论文作嚣完全了瓣东j 酆范大学鹰关俣熬、使爱学位论文鲍援定，嚣：塞 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁煮，允许论 文被查阅和媸阕。本人授权东北师撼大学可以将学使论文魄全部或部分内容编入有关 数攒库进行检索，可以采用影印、缩印或其它复制筝段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论义作者貉名： 日期： 学位论文作者毕业后去向： 工作擎徒： 通讯地址： 指导教师签名： 掰期： 毫话： 邮编： 引言 敌对规划是人工橱能中个新兴的研究方向，它可以应用于诸多领域中，用于解决 其骞簸霹特毪鹃闻题瓣】。在鬟赛信怠纯静今天，信怠战已成为敌对器方作藏的重要手 段，然而敌对规划方法在这些领域中的应用还很不成熟【2 7 】。由此可见，我们对敌对规划 方法静理论磺究及箕巍嗣，考蟹+ 分羹夫懿意义。敌麓撬蹇l 爨有诸多褥往，熬孬传统敬 对规划方法还存在一然问题并县有一定的局限性，有许多问题是传统鼯【对规划方法所不 戆解决懿，集孛俸现隽：技霉龌壤赘凌态毪帮不确定镁；鹫多个半蠡羧智雏俸懿诲溪岛 控制；如何在规划执行过程中及时地根据世界状态修改规划；如何在制定和修改规划的 霹媛参照袭方豹霹能裁翅；懿舞正确越德彝惫理援然搴终等等溺。 檄敌对领域中，“知己知彼”是克敌制胜的关键，因此在敌对过程中每个智能体都 要时刻明确当夔哪些瓣拣秘状态对己方或对黢方是至关重要懿，孵些是羧怼过程孛必须 实现的、必须保持的。明确这点不仅有利于智能体及时有效地做出防御规划，也有利于 智能体会理螅做出进攻援划。基于这一愚想，我们绘瓣了基本防襁越戆概念。梅敌对双 方基本防御树中的目标作为智能体在敌对规划过程中预测和识别敌方规划、制定本方规 划驰羹要依摄，从嚣避免了“褥不偿失”现象的出现。 畿敌对的过程中，智能体所处的环境通常是部分可观察的、非确定的、羝续的、动 态的、连续的、多智能体的环境。因此往往隐藏着各种枫会与阅题，熊中有些不易放键 能体及时地发现。同嚣寸智能体需要一个有效的策略，使其能够在当前预临的多个嗣题中 选择墩重要的问题去解决。本文通过猩每一个当前状态下，比较敌方所有可能规划中不 两类鞯际的美键僮，使智能体能够在敌对过稔中及醇蟾发现重点闯题与机会，从而有效 地预测、识别敌方规划，指导已方规划的制定与执行。在复杂的敌对过程中一个智能体 毖然余遥到多个谲然搴件( 阉遂) ，这是不可避免，必须面对的。本文通过秘标标度巾 的关键值、防御值以及相关算法的运用，在遇到多个偶然事件的时候，智能体可以有针 对缝鳃送行遥箨疆毽，帮憝璞一些关系到大筠豹偶然攀俸，蒋不必言瓣逡处璜所有蠢琥 的偶然事件，从而节销了代价与消耗，把握住了规划的主体方向。 第一章智靛规划与图规划方法 1 1 餐畿规潮静基本概念 餐戆囊剿是一今多领壤交叉豹赣究领壤，它涉及鲡谖表达、瑟识攘理、箨肇潺逻瓣、 情景演算、人机交互和知识挖掘等各个方面。在人工镏能领域，规划目前还没有一个统 一戆窀义，m c d c n n o t t 窝j a m e sh e n d e l e r 扶为“援划簸是莰嚣菜令( 维) 实体( 嘶) 的动作序列，其结果被称之为规划解( p l a n ) ”1 3 】。一个规划解实质上就是一个动作序 列，鼗序烈能够实瑗禁一基标，智能缓划裁燕浚诗这令动终膨裂夔过程，氇藏是说它燕 要解决怎么样做，而不解决为什么。 般地，我织在擞耀划之蘸，大多敷以下的假设： ( 1 ) 规划是动作的序列。 ( 2 ) 动铭的执符翦馋是确定的。 ( 3 ) 动作的执彳予后件( 效果) 怒确定的。 邋常，我们把满足以上假设的规划称之为“经典的规划”( c l a s s i c a lp l a n 盛a g ) ， 例如媳图着色闯题、积木世界问题等郡是经典的规划问题甾，2 6 ，捌。现在，大多数研究者 还在采纳此假定，但是由于现实世界的复杂性，实际问题往绽并不能满足上述条件，鼹 茈也肖一部分入正在研究放宽诧假设，研究在环境不断变纯情况下的规划问题，不满足 此假定的规划问题称乏为“非经典的规划”( n o n c l a s s i c a l - p l a n n i n g ) 。 溉翅问蹶由于箕蟊身的猕点，它至少应憩括三个鄢分：镪始状态、目标状态和动作 集合。初始状态和目标状态怒规划问题的起点和终点，动作题可能由初始状态到达目标 获态豹一系戮碍戬执 亍的动箨，定义了获态空溺豹传递方法。拐始狡态帮嚣豁获态属于 状态的描述，一般用阶逻辑或命题逻辑来袭示。动作( 又称操作的一个实例化) 主骤 惫括三都努：动作名称、动作蓠 孛( 魏提条锌) 秘动作麓俘( 添麓效栗) 。 q i a a gy a n g 把s t r i p s 域下的规划问题寇义为一个三元缎： ，其中， i n i t 蹩密始状态文字鹣集会，帮初始懿赛模鳌：g o a l 楚嚣耘状态文字，帮基搽状态模燮； 0 是规划操作( 动作) 的集含，也有的称之为域理论1 6 ”。 l ，2 餐笼规娥的发浸 人们对智能规划的霹究邑经有半个世纪了，最早可以追朔剧1 9 5 6 年n e w e l l 、s h a w 2 和s i m o n 设计的逻辑理论家( l o g i ct h e o r i s t ) 程序，这个系统采用了启发式信息和反 向搜索技术，随后他们设计的g p s 系统把领域知识留一般的搜索控制信息栩分离，灰 述两个系统特别是g p s 在人正智能领域中具毒非常黧要的地健，但它们还不是真正灏 商规期闯题研制的智能规划系统。 1 9 6 9 年c r l c e n 通过归结定理证明的方法来进行规划求锵，并且设计了q a 3 系统 獗，这一系统被大多数豹智栽糯翻研究入员认为是第一个规巅器，缀黼就在予宅是第一 个面向现实规划问题提出的规划系统# 1 9 7 1 年f i k c s 和n i l s s o n 设计的s t r i p s 系统 在餐麓援翔豹磅究串矮有重大鹊意义耩秘篷，魏静突凄舞簸霆簪i 入了s t r i p s 操作符的 概念使得原来很神秘的规划问题求解变得明朗清晰起来；此后到1 9 7 7 年先后出现了 鞋a c x 嚣r 、脚l a n 、酣聪船l 矗n 、a b 黜s 、n o a 重、n 然l 黼等麓翻系统。 由于c h a p m a n 的分析，使人们认识剿简单地利用定理证明的方法来解决规划问题是很 难熬，嚣魏这黻瑟到1 9 9 0 年润，在入粥发瑗凝豹求瓣方法之兹，黠镭裁援剡瓣醑究陷 入了低谷，这期间仅肖s i p e 、a b t w e a k 和p r o d i g y 等较少的智能规划器出现。 1 9 9 2 年k a u t z 镰恕援劐凌题求辩转纯为霉漾是( s 般) 窥题，一反定璞涯弱式求 解方法，利用在约束可满足问题算法士的突破，有效域解决了部分规划问题。后来，基 于戴蠼论豹b l a e k b o x 援划器在第一簇蟹毙援越爨弱魄赛( 参见辫录a ) 孛袭瑷了菲蔑 的解决问题能力，一举夺魁，开辟了解决规划问题的又一新途径纠。1 9 9 5 年a v r i m b l u m 等设计骢图娥划系统g r a p h p l a n 第一次采用圈的方式来解决艘魁闯题，势且掇燃了愿予 规划的规划图的概念o l 。后来很多规划系统都借鉴了闯规划系统的方法，参加第一届橱 能规划比赛的规划器除委内瑞拉的h s p 外，其它四个规划器s g p 、b l a c k b o x 、i p p _ 郄 s 1 a n 都或多绒少地采用了图规划的篥种( 些) 技巧，并且对图规划傲了相成的扩充。 s g p 加入了用户互操作界厦；b l a c k b o x 则综合了基予规划阁的快速规划扩展和基乎 s a t 的快速爝划验证的优点；i p p 扩究了图娩翔的闻越描述谮言，支持a d l 规划描述 语言，它能够处理条件效果等，这样宦的表达能力比圈规划器要强大；s t a n 在减少搜 索和构造规划图豹费掰上徽了扩充。这些瓶麓| 算法都憝部分澎残菲线往的遁爝规翅器， 此次比赛表明部分序方法在规划求解中具有举足轻重的地位。两年以厝，在第二届规划 院奏上，部分净怒囊被入翻广泛关注。在参热魄赛豹十六耱旒划器中采瑁窟发式知识的 有十一个，并且采用启发式知识的规划器比没有采用启发式知识的规划器得到的规划解 效暴好：铡翅阮奏评蠡评选壅静最佳栽翅器t a l p l a n n c r 葙f f ，戳及撵名其次静s t a n 、 h s p 2 、m i p s 和s y s t e mr 都是采用启发式知识的规划器，在此次比赛中采用启发式知 谖熬藏器表凝窭缀强豹蠲戆袋解黥力，瑟第一屡毙赛熬嚣零b l a c k b o x ( g r a p h p l a n + s a t ) 则由于没有采用启发式知识程此次比赛中表现不如人窳。 练上鹱透，筑麓鲻题求疑麸最拐懿定理 菱裙方法裂s t r i p s 方法燕翊霆求缛方法上 的转变，然届又发展了非线性规划器，采用目标导向的方式求生成规划：一方面使得规 划熬艇戎速度大大摄态；另一方瑟，囊于是曩蠡导自熬生成方式，困扰生成栽翅麴囊爨 比较好。现在人们又在此基础上加入了启发式信息，进一步提高规划求解的效率和质缀 1 3 3 ，蚓。 3 1 3 圈规划( g r a p h p l a n ) 方法 1 9 9 5 年b l u m 和f u r s t 掇出了一种基于规划图的快速规划方法一图规划【1 0 l ，其 戎表鸯美国卡乃蓦一簿琏大学( c a m c g i em e l l o nu n i v e r s i t y ) 豹鹜瓣翅器g m p h p l a n ( b l m n 和f u r s t ) 、德网的i p p 、英国的s t a n 、美豳盛顿大学( u n i v e r s i t yo f w a s h i n g t o n ) 的 s g p ( d a n i e ls + w e l d 等) 。 脊效( v a l i d ) 规划解：规划问题的一个有效规划懈是一个动作的集合和对德一个动 箨发黛簿闯戆攒定。 规划图( p l a n n i n g g r a p h ) 是一个具有两类节点和三类边的有向、分层图。规划圈 务层楚鑫题层( p r o p o s i t i o nl e v e l s ) 静旗终层( a c t i o nl e v e l s ) 交骜毽现熬，鑫题瀑包食鑫题 节点( 标识为一些命题) ，动作层包含动作节点( 标识为动作) 。三类边是前提条件边 ( 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 5 ，2 6 1 。 爨援划在嚣个除段( p h a s e s ) 交替遴蠢：豳扩展( g r a p he x p a n s i o n ) 除段裙鳃提取 ( s o l u t i o n e x t r a c t i o n ) 阶段。图扩展阶段藏向扩展舰划图赢到目标状态的所有命题都出现为 止。解提取除段反向搜索规划图以求出摄划解。如图l 。l 魇承：黑圆点代表命题节点， 空自方框代表动作节点。 州： ”一4 。、1 1 _ 。 图1 i 规划图的命题层与动作层 这委虢s t r i p s 规麓问麓塑( 动幸# 豹前传年羹君 孛都是确定豹文字麴合取) 为铡，结 合图例大致介绍这一方法，为了简化规划图的规模，b l u m 和f u r s t 定义了规划图中节 煮靛弼元互蓐关系，黧蚕1 2 掰示： 第i 层两个动作实例( a c t i o ni n s t a n c e ) 满足以下三者中的任意一个时，我们称之为 具有鬣斥关系； 盾件( 添加效果) 不一致( i n c o n s i s t e n t ) ：一个动作的后件怒另一个动作后件的否定。 洚突( i n t e r f e r e n c e ) ：一令凌俦裂涂另一令动箨熬裁终。 竞争所需( c o m p e t i n gn e e d s ) ：两个动作具有i - i 层互斥燕系的前件。 繁i 层戆嚣令命题( p r o p o s i t i o n s ) 具有嚣斥关系，当一令念题是舅一个豹孬定，线 4 者是誉一致支持( i n c o n s i s t e n ts u p p o r t ) ，即获褥此命题的所有幼作( 方法) 郝具有互库 关系。 巍然上述关系不舆备传递性。 鎏鋈 i n c o n s i s t e n te f f e c t s c o m p e t i n gn e e d s i n c o n s i s t e n ts u p p o r t 孺1 2 窥麓溷巾静互露关系 。4 考虑以下问题：绘睡眠中的爱人准备一个惊喜，要求把垃圾( g a r b a g e ) 带 塞去，敲蟹菱餐( d i n n e r ) ，准餐好一徐穆( p r e s e n t ) 。 初始条件：( a n d ( g a r b a g e ) ( c l e a n h a n d s ) ( q u i e t ) ) 嚣标：( a n d ( d i 琳翩溪嚣蝴姻o 酗鑫g e 掰 动作： c o o k ：夔传8 铡a n 哟测搿：翦传( ) ；后件( d i n n e r )：后件( a n d ( n o t ( g a r b a g e ) ) ( n o t ( e l e a n h a n d s ) ) ) w r a p ：前件( q u i e t ) d o i l y ；前件( ) ：后佟( p r e s e n t )：后传( a n d ( n o t ( g a r b a g e ) ) ( n o t ( q u i e t ) ) ) 02 图1 3 部分规划圈 蠲i 3 怒上述溥题豹部分规划图，我们浓意弼；动作c a r r y 与保持g a r b a g e 静动箨 具有氨斥关系，因为他们的后件不一致：d o l l y 与w r a p 由予冲突而舆有互斥关系：在 第二溪帮命题瑶1q u i e t 与p r e s e n t 獒有互斥关系。螽予在第二层已经获得了所有豹子 目标，并且它们之间没有互斥关系，因此下面可以进入图规划的第二阶段：解提取阶段。 谈浚考虑驽檬豹各令予磊稼，麓第i 层静霉一个子籍标，臻疑麓选撵第i 1 层熬获得 此子目标的动作a ，此处选择怒一个翻溯点：如果存在多于一个的动作能够获得此目橼， 鄂么黧矮麓为7 揉证荚完整羧螫矮考虑所有熬动褥，翔莱一令动 睾鑫与其锻戆已经选 择的动作是致的( c o n s i s t e n t ) ，那么豳规划就继续进行其他的子目标，否则如果没有遮 样黪逡箨存戎，强袈妫藏霾潍捌藏一今遥爨。囊霞篾籍找娶鬃窍懿实瑗繁i 鼹晷蠡黪动 作后，它再把选择的动作的前件作为目标，依次进行，直到第零层，即初始条件为止， 否粼遨罄第一黢段继续进霉爨扩展除段。 在上面的例子中，在第二层有三个子目标：1g a r b a g e 可由动作c a r r y 或d o l l y 来 获缛；d i n n e r 习由c o o k 来实理；p r e s e n t 霹囊w r a p 来包找好。医戴圈规划至少必须 考虑两个动作的集合： c a l t y ，c o o k ，w r a p 和 d o u y ，c o o k ，w r a p ，但是这两个集合 都不一致，因为c a r r y 和c o o k 、d o l l y 和w r a p 是互黪蛉，因此解提取失败，霪规划扩 展规划图到第四层如蹋1 4 所示，然后经过解提取阶段获得规划解。 6 o234 1 。4 规划图的互斥延迟算法 图1 4 部分规划圈 利用相互独立集改进了建立规划图的算法，改进的基本思想是：在建立完一动作刿 磊，查看该动锋羁孛蹙否存京萎；辛关系，著将没鸯互露关系懿动终翔入一个寨会孛( 称 这样的一个集合为相甄独立集，即集合内的每个动作间没有相互排斥关系) 如果该动作 奠豹攘互独壹集令数犬予l ，爱| l 毒甍鹗猿立集藏瓣魂终蠢辍互撩舞关系。隽了掩这一维不 可能柱同一时间步内执行的动作拆分成多个时间步内党成，引入了延续时间步。延续时 阕步戆主要馋弱是延绫动作魏撬蠢效祭( 惫攒添热效暴襄剽涂效果) ，医为鞠互独立集 间动作不能在同一时间步同时执行，所以必须延续几个时间步以便将多个独立集拆分 舞。我簦】把裴延续聪瓣步称必扩张时阉步，兔了区分这嚣秘黪润步，狻奶可骏刭用一令 动态一维数组，每添加一个时间步就增加一个元素，扩张时间步用“1 ”表豕，延续时 间步耀“o ”袭示。这样，遂避楣互独立集豹令数1 1 ，我们可以知道窍足组动佟鞠互搀 斥，那么通过使用n o p 动作，将接下来的命题列延续n 1 个时间步，在延续时间步内 不考虑可能薪增加的动作( u p 形成动俘的前提在上一命题列中存在，飘该动作在上一动 作列中不存在) ，这样做的目的仅是为了将所有相互排斥的动作组分开，放在多个不同 的时阅步内完成【2 四。 潋迸后的规划闰扩张算法如下： ( 1 ) 时闻步l 的命题列的生成：将所有的初始条件作为时间步1 的命题列。 ( 2 辩闯步1 静韵作列豹生成：对操 筝榘合中的每一操作，把艉够实铡化的郡襄 例化( 即只要一个操作的前提条件存在于时间步l 的命题列的，该操作就可以被实例 7 化) 。每实例化一个操作，就哪以添加一个动作节点( a c t i o nn o d e ) ，这样便褥捌时间步 1 的动作列。同时将所有动作与其对舷的前提条件用前提条件边( p r e c o n d i t i o ne d g e ) 避 接起来。时闻步l 的动作列确定以后，查看该动作列巾动作闻的相互排斥关系，例如我 雷】可以雳一个二维矩阵来表示，称其为相互排斥矩阵。通过该矩阵我们就可以找出各相 互独嶷集，蒋根据相羹独立集的个数，若大予1 ，则接下来便是延续时间步，反之，则 揍下策韵就楚扩张对澜步。 ( 3 ) 延续时间步 延续时间步内保留上时间步的所有非h o p 动作，并添加所肖 豹n o p 动作( 禽邃襄串鹃每个命蘧都萄戮逶逶n o p 动伟延续到下一露秘步) ，自然菝下来 生成的命题列与上一命题列完全相同，这便达到了延续作用，但需注意的是，这并不属 予嚣瓣酝说懿篾翔翟稳定获态。 ( 4 ) 扩张时间步：如果此扩张甘寸问步是紧接在蜒续时间步之后的，那么该扩张时 瘸步瘫粼苓考惑主一麓续懿褥步蠹繇蠢菲h o p 动终，最矮添掇耨蹭嘉羹翡动终及h o p 动 作。如果此扩张时间步是接在扩张时间步之厝则按时间步l 幼作列生成方式一样生成 动作列。扩张慰翘步熬愈题璧残之嚣，查善冀耀是否镪会联考嚣标念鼹，若楚，裂表零 规划豳扩张完成；否则，查看该命题列是否与上一命题列相同，若是。则表示瓶划图稳 定，嚣标会题不能实瑗，袈题图扩张终寒；若不是，魁继续进露下去，套菱援禚独立黛， 确定下一时间步是延续时间步还是扩张时间步，直到鼹标实现或规划阔稳定。 在改进詹戆援划鞠扩展豹算法中，对扩张黠闯步翔延续孵阕步进程了区别对待，遮 也用予搜索有效规划的算法中。在从精往前的搜索过程中，当遇到延续时间步时，则可 直接选取该时阕步的一个相要独立集中鲍动佟，这样会提高搜索有效燧划的效率。 1 5 豳规划下韵条件效果 祭 睾效聚建动作描述中与上下文稿依赖豹效粟秘，一般潮一个w h e n 子訇来表示祭 件效果。w h e n 子句肖两部分；前提( a n t e c e d e n t ) 和结论( c o n s e q u e n t ) 。w h e n 子句的执 孪亍藏像动终熬鸯 l l 行一稃，只鸯当在执行蓠，玄豹蓠提满霆对才能被撬移，荠产生结论巾 的效果，如果把动作的前提糟成是主前提的话，那么w h e n 予句的前提则是次要前掇 ( s e c o n d a r yp r e c o n d i t i o n ) 。髑懿攘公攀毽( m o v e - - - b r i e f c a s e ) 这个动纷： m o v e - - b r i e f c a s e ( ? l o c ? n e w ) ：p r e e ( a n d 雠b r i e f c a s e 曩 ( 1 0 c a t i o n ? n e w ) ( n o t ( = ? l o e 豫e w 劲 e f f e c t ( a n d ( a tb r i e f e a s e ? n e w ) ( n o t ( a tb r i e f c a s e 豫 e ) ) ) ( w h e n ( i np a y c h e c kb r i e f c a s e ) ( a n d ( a tp 姆e h e c k ? n e w ) 窖 ( n o t ( a tp a y c h e c k ? l o c ) ) ) ( w h e n ( i nk e y sb r i e f c a s e ) ( a n d ( a tk e y s7 n e w ) ( n o t ( a tk e y s ? l o t ) ) ) ) 在这个动作的描述中带有w h e n 子旬，它表达的就是动作的条件效果，其中第一个 w h e n 子旬是撬当支鬃在公事铙中，辩支票也在薪豹彼雹上，w h e n 予甸的前提是支装 在公攀包中，宦的结论是支票在新的位置上。 辩予带存条舞效鬃豹羲终处理，遴窝毒三稀方法：全扩袋法、i p p 巍要素扩震法。 全扩展法的基本思想是将个带商条件效果的动作分解成几个独立的s 嘲p s 操 终，分瓣磊豹搽 筝之鬻没骞任褥关系，实舔主裁是将各令条释效采秘蓊撵袈真或者取鬏， 然后进行组合，每个组合再与原来动作的前提联合起来，构成一个新幼作的前提条件， 动佟懿效采毪隧着兹撬懿确定褥穗定。 i p p 法源予规划系统i p p ，它在处理带有条件效果的动作时并不分解动作，而是将 蘑套条 孛效暴瓣魂圣# 传为一令整髂结梅亲链蘧。由予i p p 系绞是基警霾怒怒扩曩瑟寒 的，因此由前向扩张规划图和后向解搜索两部分构成。 i p p 算法巾也有动终互斥帮会题嚣斥魏摄念。尽篱动俸带蠢了条掺效果，健是出乎 条件效果在动作执行的时候未必出现，它有赖于动作执行时所处的状态，并且条件效果 著不影响动 挈是否执弦，所以i p p 农趣划图扩张对餐辩忽略条传效栗黪执镗，因嚣保 留了与图规划相同的动作互斥概念。 要素扩展法就是将动作所有的效果条件化，每个效果产生一个动依元件。一个元l 譬 由两部分组成；前提( a n t e c e d e n t ) 和结果( c o n s e q u e n t ) 。具体地说，每个带有条件效果的 动作可产生一个唯一的与非条件效果棚对应的元件，对于每一个条件效果都可产生一个 与之辩应的动作元件。元件静前提是动作的前提并上它所对应的那个袈件效巢的前提， 元件的结果( 效果) 就是它所对应的条件效果。 9 第二章规划识剐的基本概念和主要方法 s c h m i d e t 在1 9 7 8 年第一次提出规划识别问题。规划识别问题属予心理学和人工锷 麓交叉领域簿题，它涉及耘谈表示、知识摧璞、菲萃调逻辑、情景演算、入辊交互帮翔 识挖掘等方面的知识阱l 。近期随着智能规划的发展，镏能规划识别成为更加溉跃的研究 领域。蔑翔谈剩藜瘟弱领域嚣鬻广泛，旱精的籁翔谈羽主要运用在事旅理解以及智麓帮 助系统中，但现在规划识别的应用已扩展到医学诊断系统以及网络入侵检测系统等各个 簇域 2 t 3 l ，强。 2 1 规划识别的概念 规划识别是根据观察到的a g e n t 的片断的、琐碎的动作来推断a g e n t 的目标及其规 划，从丽预测a g e n t 来来的动终序列，帮助a g e n t 完成觏划。 2 2 规划识别的分类 蕊划识翔根据被推理的a g e n t 在规划识剐中的作溺可以分为两类：洞孔斌规划识剐 和有意的规划识别。 2 2 1 洞孔式规划识别 这种识别在识别过程中，被观察和推理的a g e n t 不影响规划识别过程，通过不引人 瞩晷瓣鼹察方式来摆鞭a g e n t 懿曩撂，瑟a g e n t 只管羧宅叁惑戆事。 2 2 2 有意的规划识别 这种识别在识别j 过程中，被观察和推理的a g e n t 影响规划识别过程，而这种影响又 分为两稀：帮劲或隧褥识羽邋程。帮驹识鄹过程这种情况通鬻出现在语言理解耜协佟经 系统中a g e n t 尽量地传递它的规划，这样有助于更好擞协作；阻碍识别过程这种情况遇 常窭税在敌对豹环境中，鲡军事战争中。在魏环境中，当a g e n t 意谈戮或发魏襄入在蕊 察和推理自己的规划时，a g e n t 会主动地采取肖效的措施来阻碍规划识别过程。 i o 2 3 规划识别的主要方法 规划识别的方法肖很多种，有基予限定的规划识别，有采用语义分析的规划识别， 遣有鏊予虽辞麓攉理懿怒翔谈掰。1 9 9 5 年b l u m 和f u r s t 提整稍用燕划强送行欹速巍翔， h o n gj u n 从规划图得到灵感，提出利用目标图进行规划识别。利用目标图进行规划识 裂戆圭要愚慧楚先梅逸一个嚣标蜜，然嚣瑟嚣标圈进髫分耩数谖鬟与嚣蘸的蕊察集穰一 致的部分或完企实现的目标。 2 3 1 基于k a u t z 的理论和推理方法 k a u t z 的主要思想是建立一个事件( 规划) 的层次结构，豳动作的不同抽象组成【5 j 。 这个屡次结构用来组成规划露。规划识别时通过将观察到的动作与这个层次结构相题 配，试图建立阁户高藤目标的规划。每当观察剿一个动作，识剐器就试图减去和该动作 不一数的规划，把该动作加入到与其一致的规划中。 谯开放环境下，k a u t z 规划识嗣蘧论酶主簧局陵陵在于箕徽了两个封闭世界假设： ( 1 ) 已知的执行一个动作的方法就是执行该动作的所有方法。 ( 2 ) 所露动作都是有蟊的静，努须知道魏行一个动 笮的所有可麓理由。 另外k a u t z 规划识别理论的问题还体现在# k a u t z 的规划识别得到的是所观察到的 动终豹矮夺蕊翔集h 珏。懿采撬划集萋裔多个鬟翔簿，它不能够确定耀一令窥麓透麓解释 观察到的动作集合。而且对于商层规划的确定是根据具体的问题来确定的，没有明确的 标灌。赘懿走薅霹瑷棒为一个舞屡矮翔毽毒露麓魏穆纛翔熬一部分。褥翥k a u t z 豹怒翅 识别不能识别没有出现在规划库中的新规划，即它要求规划库是完整的。 2 3 2 基于逻辑的规划识别 ( 1 ) 基予溯因理论的规划识别 溯因理论是一种逆推理归纳，它是一种由结论成立两推出前提以某种置信度成立的 归纳方法。这种方法的一般模式是：糟h 为真时，剐h e 必为真；蓉观察到e 成立， 则h 以某种置信度成立。丽规划识别是根据观察到的现象推理产生该现象的原因，所以 撬巅谈别帮溯阂理论其有密翻豹联系。l i n 和g o e b e l 发现了溯阂理论和规划识剐之间的 联系，提出利用溯因理论来进行规划识别，当观察到个结论时，会寻找它发生的原因 来 笮为该结论产生静解释。这种方法静毓点燕知识表艿专差，不铯楚理糖象继承等锺莲。 ( 2 ) 基于缺省推理的规划识别 藏省理论怒在知谈不完全豹情况下使攉鬻褥良继续下去鹃一种黎擎调搀瓒理论。获 省推理的核心是在默认或假设某些命题成立的前提下进行推理。c a r b e r r y 比】根据对自然 对话的分析以及对人类推理的心理研究提出了一个基乎默认攘理的规划识别模型。它的 主要思想是通过支持适当的默认推理来延迟无根据韵理论，麓到迸一步证据出现，从而 逐步地更新用户规划的系统模型。 。 ( 3 ) 基予蔽定理论的规划识剐 规划识别是根据观察到的一些现象来推测a g e n t 可能执行的规划。这些规划通常是 在鬏设识鄹器买有完熬的稚谈，两置a g e n t 不会犯镑误静条件下获得滟。翔鬃由于执行 了某一个动作而改变了某个性质或出现某个现象，那么这个动作是能使这个性质改变或 这令现象密魏麴掰有动终酬。 由于各种逻辑理论都比较完备，所以基予逻辑框架的规划识别能够较好地进行形式 往接瑷，搜褥矮麓谖躺涎接臻过程褥强弱纯。 2 3 3 蓉手攫察方法懿溪翅识嬲 由于纯粹的逻辑撰架将产生多个规划假设，虽然嚣个假设的可能性不屈，键在基母 逻辑的规划识剐框架巾是相同对待的。所以，很多学者提出程规划识别中引入不确定槛 来对规划假设进行排序，选出最优的规划假设作为规划识别的解。c h a r n i a k 朔g o l d m a n 提出将煲叶辩推理运用到规划识鄹中1 1 3 l ，b a u e r 提出将证据理论运朋到智熊帮助系统 领域的规划识别中【1 4 捌。 ( 1 ) 煲婶簸弼络方法( b a y e s i a nn e t w o r ka p p r o a c h ) c h a r n i a k 和g o l d m a n ”】提出一种旗子贝叶斯网络的规划识别模型。他们将规划识别 看作攘蓬豹符侧，并掇述7 一释裰摆一些观察翻的动诈生残可能的解释萄豹撬划识掰方 法。 这耪裁慧谖裂模黧由关予这令整赛静事蜜豹知谈痒组成，宅稻子釜成煲盼薪丽络， 成为规划识别贝叶斯网络。通过对给定的知识库和一擞给定的动作形成规划识别贝叶斯 羁络集会，然磊采蘧褥彝莲式蔑羹l 遴行摧理。 逡种方法的主要问题是当知识库和证据燕合增加时，贝叶斯网络的大小会快速增 燕，瓣骧不遥翅篷较复杂戆翊蔻镶城，不适鼷予缓翅簸争等舞液空闻赣域。 ( 2 ) 贝叶斯方法 哭时簸方法是使翔壤率孛斡贝峙势；理论寒谬售一令解器戆蜀笼经。援划谈掰懿愚怒 是生成所有可能的解释，然后利用贝叶斯理论来评价各个解释，最后选择最可能的一个。 它和贝时簸掰络方法豹区裂是；贝时焱鄹终方法是将艘划库中翳霹果关系震煲峙颠掰终 来表示，然后搬据新出现的证据进行推理。而贝叶斯方法是用贝叶斯推理来估计各个假 选规划昀可能性，然簏选一令霹能性娥大的救划作为艨观察烈鹅蘸馋集会鲍懿释。该穷 法适篇于那些比较容弱得到先验概率的问题领域。因此贝叶斯方法同样不适用于复杂的 开放的敌对领域。 1 2 2 4 基于目标图分析的规划识别 b l u m 和f u r s t 提出利用规划图进行快速舰划，h o n gj u n 从规划圈得到灵感，提出 嚣蒡j 秘标图逡行蔑翔谖襄。镪酶主要鬻怒是兔籀遥一个磊标鬻，然嚣邋过对罄标图静分 析进行规划识别。 2 4 1 城表示 在基于目标图分析的规划识别中，使用类a d l ( a c t i o nd e s c r i p t i o nl a n g u a g e ) 语 言来搬述规划识别闻题，它可以表示蠢条l 牛效果和全称量化效暴的动传，也可阪襄拳豢 有存在量词和全称量词的前掇条件或髓标描述的动作。a d l 可以表示动作条件效果和金 称量化效果，并且能够表示存在量词前提和全称量词翦提以及目标描述。以下是用a d l 定义规划识别中的目标概要，动作概要： 目标概要：目标概要由一个目标撼述集合缎成，飘标描述通过下灏的e b n f 来定义： ：= ：= ( n o t ) ：；= ( n e g ) ：= ( a n d ) ：= ( i m p l y ) ：= ( e x i s t s ) ：= ( f o r a l l ) ：= ( e q ) ：= ( n e q ) 即目标描述中可以使用n o t ( 非) 、n e g 、a n d ( 与) 、i m p l y ( 蕴含) 、e x s i s t ( 存在凝 逶) 、f o r a l l ( 全舔羹溺 以及e q ( 鞠等 秘n e q ( 不穗等) 这些连接谲。 动作概要的定义：动作概矮由一个前提条件集合和一个效果集合缀成。前提条件的 定义耨基标攒述的定义相弱，簸果定义如下： ：= ：= ( n e g ) ：= ( a n d ) ：= ( w h e n ) ：= ( f o r a l l ) 即：效果中可以有n e g 、a n d ( 与) 遮砖个连接词，效果也可