（计算机应用技术专业论文）智能体行动推理中的信念改变的研究.pdf

江苏大学硕士学位论文 摘要 对于智能体而言，搜集世界信息的能力和搜集到新信息后修正原有 信念的能力是非常重要的。信念改变包括信念更新和信念修正，是指 改变智能体原有信念来接受更新，更准确，更可靠，并且有可能与原 来信念不一致的信息的过程。行动推理的核心思想是任何引起系统状 态变化的因素都可以看作是行动。信念改变和行动推理已成为人工智 能领域研究的两个重要分支。 在行动推理中允许智能体修正信念对行动推理系统而言是一种重 要扩展，然而之前的相关工作却存在一些问题或不足。因此，本文从 修正算法和行动推理系统两方面进行改进，然后将信念修正运用到行 动推理中。主要工作和创新包括以下几点： ( 1 ) 对现有的主要信念修正假设作了充分研究和分析，选择出适合 指导信念改变算法的假设组合作为研究改变算法的基础。对目前主要 的修正算法进行了研究，并指出了其存在的不足。 ( 2 ) 提出和实现了依赖信念改变算法。依赖信念改变算法是在依赖 信念集的基础上，以恢复遗弃信念集的方式完成迭代信念修正和更新。 更新算法满足i n d ，c 1 ，c 2 ，k m 假设，弥补了加强修正算法的不足。 用实例验证了依赖信念改变算法满足假设的情况以及对加强修正算法 的改进。 ( 3 ) 提出基于依赖信念改变的行动推理模型a r b c 。该模型使用公 式表示信念，用公式的集合表示信念集，用依赖信念修正算法进行信 念修正，用依赖信念更新算法进行行动推理。在层次结构上，分为决 策层、公理层和推理层，分别表示进行规划和设计时所采取的策略， 运行所遵循的公理和进行基本推理的推理机制，通过实例验证了a r b c 的可行性。 江苏大学硕士学位论文 关键词：信念修正，行动推理，流演算，状态演算，依赖信念修正， a r b c 模型 江苏大学硕士学位论文 a b s t r a c t t h ea b i l i t yo fg a t h e r i n gi n f o r m a t i o no ft h ew o r l da n dr e v i s i n gi t so r i g i n a lb e l i e f s b a s e do nt h en e wi n f o r m a t i o ni si m p o r t a n tf o ri n t e l l i g e n ta g e n t b e l i e fr e v i s i o ni st h e p r o c e s st h a tc h a n g i n go r i g i n a lb e l i e f so fa na g e n tt oa c c e p tn e w , m o r ep r e c i s ea n dm o r e r e l i a b l ei n f o r m a t i o nw h i c hm a yi n c o n s i s t e n tw i t he x i s t i n gb e l i e f s t h em a i ni d e ao f a c t i o nr e a s o n i n gi st h a te a c he l e m e n tc a u s e dt h ec h a n g eo ft h es y s t e ms t a t e sc a nb e r e g a r d e da sa c t i o n b e l i e fr e v i s i o na n da c t i o nr e a s o n i n gh a v eb e e nt w oi m p o r t a n t b r a n c h e so f a r t i f i c i a li n t e l l i g e n c e t h i sp a p e rf o c u s e so nb e l i e fr e v i s i o na n da c t i o nr e a s o n i n g f o rb e l i e fr e v i s i o n ，a d e p e n d e n tb e l i e fr e v i s i o na l g o r i t h mi sp u tf o r w a r d ，w h i c hs a t i s f i e si n da s s u m p t i o na n d c o v e r st h es h o r t a g eo fr e i n f o r c e m e n tr e v i s i o nm e t h o d s f o ra c t i o nr e a s o n i n g ，a n i m p r o v e da r b cm o d e li sp r o p o s e d ，w h i c hi n t r o d u c e s t h er e i n f o r c e m e n tr e v i s i o n a l g o r i t h mi nt h ep r o c e s so fm o d e lc o n s t r u c t i o n s e v e r a li n s t a n c e sa r ee m p l o y e dt o v a l i d a t et h ef e a s i b i l i t yo ft h er a i s e dm e t h o d t h em a i nw o r ko ft h i sp a p e ri ss t a t e da s f o l l o w s ： ( 1 ) f u l l yi n v e s t i g a t ea n da n a l y z et h ee x i s t i n gb e l i e fr e v i s i o na s s u m p t i o n ，a n dt h e n s e l e c tt h ep r o p e rh y p o t h e s i sc o m b i n a t i o ns u i t e dt og u i d eb e l i e fr e v i s i o na l g o r i t h ma st h e r e s e a r c hf o u n d a t i o no fb e l i e fr e v i s i o n i na d d i t i o n , m a i ne x i s t i n gb e l i e fr e v i s i o n a l g o r i t h m sa r es t u d i e dw h i l e t h e i rs h o r t a g e sa r ep o i n t e do u t ( 2 ) b a s i ca s s u m p t i o na n df r a m e w o r ka r er e s e a r c h e d i nd e t a i l s o nt h i sb a s i s ， d e p e n d e n tb e l i e fc h a n g ea l g o r i t h mi sp r o p o s e d ，w h i c hr e v i s e sb e l i e f sb a s e do nt h e d e p e n d e n tb e l i e fs e t si no r d e rt oi t e r a t i v e l yr e v i s e sb e l i e f sa c c o r d i n gt or e c o v e rt h e d i s c a r d e db e l i e f s b e l i e fu p d a t ea n db e l i e f sr e v i s i o na r et a l k e da b o u tf r o ma c t i o na n d a c k n o w l e d g eo fa g e n t f i n a l l y , t h ep r o g r a mc o d ei sp r o v i d e dw h i l es o m ei n s t a n c e sa r e u s e dt ov e r i f yt h ep r e s e n t e da l g o r i t h m sa n dt h ei m p r o v eo fr e i n f o r c e m e n tr e v i s i o n ( 3 ) a r b cm o d e li sp r e s e n t e da c c o r d i n gt oi n h e r i t i n ga n di m p r o v i n gt h ea x i o m a t i c s ， s u c ha sf l u e n tc a l c u l u sa n ds t a t ec a l c u l u s i nt h i sm o d e l ，f o r m u l a sd e n o t eb e l i e f sa n d f o r m u l as e t sd e n o t eb e l i e f ss e t s d e p e n d e n tb e l i e fr e v i s i o na l g o r i t h mi sa d o p t e di nb e l i e f r e v i s i o na n da c t i o nr e a s o n i n g i na r c h i t e c t u r e ，t h ea r b cm o d e li sd i v i d e di n t od e c i s i o n l e v e l 、a x i o ml e v e la n dr e a s o n i n gl e v e lt h a td e n o t es t r a t e g yo fp l a n n i n ga n dd e s i g n i n g ， w o r k i n ga x i o ma n dr e a s o n i n gi n f e r e n c ee n g i n e ，r e s p e c t i v e l y d e p e n d e n tb e l i e fr e v i s i o n a l g o r i t h mi si n j e c t e di n t oa r b c m o d e l w h i c hi se s t i m a t e db ys o m ei n s t a n c e s f i n a l l yt h e 1 1 1 江苏大学硕士学位论文 r e l a t e dw o r k sa r ec o m p a r e d k e yw o r d s ：b e l i e fr e v i s i o n ，a c t i o n r e a s o n i n g ，f l u e n tc a l c u l u s ，s t a t ec a l c u l u s ， d e p e n d e n tb e l i e fr e v i s i o n ，a r b cm o d e l i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密蚴。 学位论吝储躲本址 签字日期：矶加年石月珀 别币签名：勺幸 签字日期：f o 年6 月愿目 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： ：霖l 1 日期：沁fd 年舌月if 日 江苏大学硕士学位论文 第一章绪论 本章首先介绍了智能a g e n t 的定义、特征及应用领域，然后介绍了a g e n t 行 动推理理论的定义及其在国内外的研究现状和发展趋势，接着概述了信念修正的 研究背景以及发展现状，最后阐述了本文的主要工作及论文结构安排。 1 1 智能a g e n t a g e n t 的原意是“代理”指具有智能的任何实体，包括人类、智能硬件和智能 软件。到目前为止，a g e n t 在研究领域中尚没有一个统一的定义，但人们普遍认为， a g e n t 是驻留在某一环境下能够自主( a u t o n o m o u s ) 、灵活( f l e x i b l e ) 地执行动作以满 足设计目标的行为实体。a g e n t 通常具备下列特性【1 】： ( 1 ) 自主性 a g e n t 是一个行为主体，它具有一组动作并能执行这组动作，是动作执行的决 策者和实施者，同时它具有属于其自身的计算资源( 数据、信息等) 和局部于自身的 控制机制，能根据内部状态和从环境中获得的感知输入，自主地决定应该执行什 么样的动作以实现其设计目标。 ( 2 ) 反应性 反应性是指a g e n t 能够感知所处的环境( 可能是物理世界、或操纵图形界面的 用户或与它进行相互通信的其它a g e n t 等) ，并能对环境中发生的相关事件( 如a g e n t 之间交互和通信、系统中时钟事件的发生和用户的界面操作等) 作出适时地反应， 以满足系统设计目标。 ( 3 ) 自发性 a g e n t 并不只是简单地对环境中发生的事件做出适时的反应，它还能够表现出 某种目标制导机制。 ( 4 ) 社会性 a g e n t 行为的社会性是指它所驻留的环境可能存在其他主体，它拥有这些主体 的有关信息和知识( 如这些主体的名字、物理位置、所拥有的资源和能力和对外提 供的服务) ，并能与它们进行交互和通信，实现灵活多样的复杂的合作、协商和竞 争，以满足系统的设计的目标。 江苏大学硕士学位论文 1 2 行动推理 行动推理由j o h nm c c a r t h y 首次提出，并认为行动推理在常识推理研究中占有 根本性的作用。其核心思想为任何引起系统状态变化的因素都可以看作是动作。 行动推理有时也被称为行动逻辑。 行动推理在人工智能( a i ) 、计算机科学等研究领域占有重要地位，例如，常 识与非单调推理、知识表示、规划、自然语言理解、面向a g e n t 的程序设计( a o p ) 、 机器人1 2 、数据库理论【3 m 和语义w e b 5 1 等都和行动推理的研究相关联。行动推理 在认知机器人、w e b 服纠6 7 】、工作涮8 1 等多个领域都得到了不同程度的应用。 行动推理认为任何引起系统状态变化的因素都可以看作是动作，它主要解决 动态系统中两方面问题：8 ( 1 ) t e m p o r a lp r o j e c t 问题：即在给出系统的初始状态和变化规则以后，预测某 个行动或者行动序列的效果。 ( 2 ) p o s t d i c t i o n t e m p o r a le x p l a n a t i o n 问题：即给出系统的初始状态和目标状态， 解释系统经历了哪些动作，使得系统从初始状态到达了目标状态。 行动推理的研究始终伴随着三个基本问题，即框架问题( f r a m ep r o b l e m ) 、结 果问题( r a m i f i c a t i o np r o b l e m ) 以及资格问题( q u a l i f i c a t i o np r o b l e m ) ，其中框架 问题的研究取得了较大的进展，并激发了非单调逻辑的研究，如m c c a r t h y 的限定 论( c i r c u m s c r i p t i v e ) ，r e i t e r 的缺省逻辑( d e f a u l tl o g i c ) 。 行动推理的研究内容己涉及以下几方面： ( 1 ) 行动推理元理论； ( 2 ) 并发动作、不确定动作推理，不完全可知和连续变化环境下的行动推理， 模糊时间概念下的行动推理，感知与规划等； ( 3 ) 面向主体的行动推理，包括主体的心智成分与行动推理的相互影响； ( 4 ) 各种行动推理形式化系统之间的转换与融合，统一的行动推理； 目前影响较大的行动推理形式化系统主要有情景演算、流演算和事件演算、 状态演算等。 1 2 1s t r i p s s t r i p s ( s t a n f o r dr e s e a r c hi n s t i t u t ep r o b l e ms o l v e r ) 系统是一个实用的机器人 2 江苏大学硕士学位论文 规划系统。它所采用的办法十分简单：用一个逻辑公式的集合来描述系统某一时 刻的状态。一个动作由前提条件、加入表和删除表三部分构成。前提条件满足时 动作就可以执行。动作执行以后，在系统状态中添加加入表的事实，删去删除表 中的事实【8 l 。显然利用该系统进行动作推理是简单可行的，但是必须保证加入和删 除表的一致性，当系统要添加或删去一些状态描述变量时这种加入和删除表的操 作甚至可能导致全部重写。但是s t r i p s 系统的应用开创了机器人发展的先驱，在 s h a l 【e y 中得到实现，成为第一个通用性移动机器人。 1 2 2 情景演算 情景演算( s i t u a t i o nc a l c u l u s ) 是m c c a r t h y 在1 9 6 9 年首次提出的用于刻画动 态系统的变化规律。他最初只是给出了对情景演算的一个描述，是一种具有指导 意义的哲学观点，而没有给出具体的形式化系统。其后的几十年间，针对不同的 应用背景，研究者们对情景演算做了进一步的研究，并提出了各种不同的情景演 算系统【9 j ，其中以r e i t e r 等人对它的改进更为合理有效，采用所谓的后继状态公理 解决了框架问题的表示问题1 1 0 1 。 情景演算中的几个重要概念：情景( s i t u m i o n ) 是指某时刻宇宙万物所有状态 的集合。完全地描述一个情景几乎是不可能的，通常只是给出关于某情景的一些 事实，然后由这些事实推出这一情景以及将来情景乃至所有可以由此情景达到的 情景下的更多事实。情景不仅可以描述现实发生的世界，还可以描述可能达到的 世界。流( f l u e n t ) 是一个用来刻画与情景有关的函数，比如c o l o r ( x , s ) 表示在情景 s 下，物体x 的颜色。动作( a c t i o n ) 可以看作与外部世界的交互。 情景演算的直观思想是，当一个动态系统中所包含的每个原子动作的执行条 件及对各种流的影响条件均预先给定时，系统在任何情景下的状态也随之确定， 并可以通过推理方式获知系统在任何情景下的状态。 在情景演算的基础上，加拿大多伦多大学的认知机器人小组结合逻辑程序设 计语言p r o l o g 实现了一种面向a g e n t 的高级程序设计语言g o l o g 【】。g o l o g 是一种 逻辑程序语言，该语言融合了过程式程序设计语言与逻辑程序设计语言的思想， 以情景演算为理论基础，将过程性控制语句解释为情景演算中的复杂动作，利用 情景演算的回归( r e g r e s s i o n ) 1 1 3 1 推理机制将其分解为一组可执行的原子动作序列， 然后通过外部执行器逐条执行该动作序列中的各原子动作。目前，g o l o g 在机器人 江苏大学硕士学位论文 的高层编程、软件a g e n t s 、过程控制、离散事件模拟、复杂数据库的转换等动态 领域方面有较多的应用【1 2 】。 然而，g o l o g 只针对单个a g e n t ，不能处理并发等操作。为了支持m a s 的开 发，d eg i a c o m o 和y v e sl e s p e r a n c e 等人在g o l o g 基础上提出c o n g o l o g 程序设计 语言。c o n g o l o g 对传统的情景演算进行了扩充，体现在：c o n g o l o g 引入了并发动 作执行机制，允许a g e n t 的动作可交替( i n t e r l e a v e d ) 地并发执行，可表示多个动 作并发执行的不同优先级，引入了高级的中断机制来描述某些条件的成立如何触 发a g e n t 并发动作的执行。 然而，g o l o g 和c o n g o l o g 都采用回归的推理计算机制来推理a g e n t 的知识状 态。对于较长的动作序列而言，需要从整个序列回归到初始情景，因此只要增加 一个新的动作，回归的次数就会相应的增加，显然这种方法是低效的。 1 2 3 事件演算 事件演算( e v e n tc a l c u l u s ) 是基于一阶谓词演算的动作推理理论【l4 1 。最初由 k o w a l s k i 和s e r g o t 提出，是一种在逻辑编程框架内表示和推理事件和事件效应的 方法。事件演算的基本本体包含动作或事件( 动作或事件类型更合适) 、流和时间点。 把真值随着时间变化而变化这样的称为流。流用项表示，可以是个量，如“房间 的温度 ，其数值是个变量；也可以是个命题，如“天在下雨”。原子动作的定义 和情景演算下的类似。另外，为了刻画事件引起的效应，引入了时间点( t i m ep o i n t ) 。 这样，它就可以表示在某个时间点发生的事件，且该事件将开始或结束流的成立。 特别地，事件演算体现了一种默认保持性，即，流一直保持成立或不成立直到一 个中断该流的事件出现。 事件演算是基于事件的，事件的发生将改变世界状态，即使得流成立或不成 立，且流值还会持续一段时间。为了表示事件、时间点和流的关系，事件演算中 定义一组谓词，具体有：i n i t i a t e s ( a f t , r ) 表示在时间f ，执行动作a 后流开始成立； t e r m i n a t e s ( a f t ，力表示在时间f ，执行动作a 后流将终止成立；i n i t i a l l y p ( 所表示流 在时间0 就开始成立；i n i t i a l l y n ( f 1 ) 表示流在时间0 不成立；r l r 2 表示时间f 1 在时间记之前；h a p p e n s ( a ，r 1 ，记) 表示动作6 c 发生在时间r 1 ，且在时间记结束，即 动作的持续时间为r 1 到r 2 ；h o l d s a t ( f l ，力表示在时间f ，流成立；c l i p p e d ( d f t ，记) 指流终止成立在时间f 1 和记之间；d e c l i p p e d ( r i f t ，r 2 ) 表示流在时间f l 和记 4 江苏大学硕士学位论文 之间开始成立。这些谓词方便地刻画了在某时间点，事件是如何影响流的。 当环境中出现一个事件时，不仅需要刻画成立的新流，还要推理那些不成立 的流。因此，事件演算中定义了一组基本公理，把各种谓词联系起来。 ( 1 ) h o l d s a t ( f , , t ) - - l n i t i a l l y e ( d 八1c l i p p e d ( 0 z f ) 即，如果流厂在时间0 就开始成立，且在o 和f 之间没有终止，那么流厂在时 间t 成立。 ( 2 ) h o l d s a t ( f , , t 2 ) 卜 h a p p e n s ( a ，t 1 ) 八i n i t i a t e s ( a f , t 1 ) 八t 1 t 2 八1c l i p p e d ( t l f , t 2 ) 若在纪之前的某个时间点t l 发生的事件a 使得流厂开始成立，且中间没有被 终止，那么流在时间龙成立。 ( 3 ) c l i p p e d ( tlz t 2 ) 付 了a , t h a p p e n s ( a ，t ) at l k e y l ：l 表示一个信念集。 定义3 3 信念的可信度表示这个信念被相信的程度，可信度越高则这个信念越 有可能被相信，反之则越不被相信。 信念仅，的可信度表示为：a ：e l ，f l ：e , 2 反节f - p 如果e 2 e z ； a 节h 否则。 例如 a t r l ：2 ，a t r l - - - k e y l ：l 中的a t r l 的可信度为2 和a t r l 专k e y l 的可信度 为1 。 由d p 假设的c 1 ，c 2 可知，当原信念集k 被迭代修正后，在能够推出或 者1 时，原信念集实际上要进行还原，即k 木要还原成k 。因为在对k 进行 更新后，k 中的某些信念被更新去除了，只要还原这些被更新的信念，即可还原k 。 定义3 4 将每次信念更新后被去除的信念组成的集合称为遗弃信念集，用局 表示。 如果墨，萑k j ，且声萑则, a s k t 其中畅表示当前信念集，墨表示过去信念集，f 表示对于过去某个状态k 的 新信息。 当h 或者声卜叫时，称信念依赖于信念，由i n d 半可以推出，当某个信 念不依赖于当前被更新信念时，更新后的信念集应保留信念。可见，在信念 更新过程中，被更新信念应与新信息存在依赖关系，由此引入依赖信念集的概念。 定义3 5 将当前信念集中依赖于新信息的信念所组成的集合称为依赖信念集。 令当前信念集为k ，依赖信念集为物，新信息为夕，则u i k a 必须满足以下两个 条件之一： 1 h ，或声卜叫， 2 存在杨的子集k ，使声卜叱，a t ) ，7 为k 中所有信念的合取式 例如信念集为 a t r l ：2 ，a t r lj k e y l ：1 ) ，新信息为- - a t r l ：2 。则依赖信念集为 a t r l ：2 ) 。 通过研究依赖信念集杨可知，其分为两种类型，一是其中每个信念都与新信 息存在依赖关系，我们将其叫做完全依赖信念集，用玩表示，例如信念集为 a t r l ：2 ，a t r l - - - k e y l ：1 ) 则完全依赖信念集为 a t r l ：2 ) ；另一种是单个信念与新信息 江苏大学硕士学位论文 并不存在依赖关系，而整个依赖信念集中信念的合取式则与新信息存在依赖关系， 我们将这样的信念集叫做合取依赖信念集，用缸表示，例如信念集为 a t r l ：2 ，a t r l k e y l ：1 ) ，新信息为一k e y l ：1 ，则合取依赖信念集为 a t r l ：2 ，a t r l 专k e y l ：1 ) 。由定义3 4 可以得到，所有满足条件1 的信念组成的信念 集即是完全依赖信念集。而对于合取依赖信念集，则由能推出邓的多个最小单元 集组成。在下面的算法中，我们规定所有对合取依赖信念集的操作都是分别对每 个最小单元集合的操作。 3 3 依赖信念更新算法 在a g m 框架下，信念更新指的是满足新信息优先原则的信念修正方法，即信 念更新后的信念集必定能推出新的信息。在依赖信念更新算法中，虽然新信息是 具有可信