（计算机软件与理论专业论文）多agent系统模型概率框架的研究.pdf

多a g e n t 系统模型概率框架的研究 摘要 贝叶斯技术和贝叶斯网络是人工智能中不确定性问题处理的一种工 具。贝叶斯技术和a g e n t 技术的融合形成了一个具有广阔前景的新兴研究 领域。 多a g e n t 系统的模型表示是多a g e n t 系统中推理、学习、合作等一系 列操作实现的关键。本文在对贝叶斯技术理论和贝叶斯网络模型进行了介 绍和讨论的基础上，讨论了大知识域上多a g e n t 系统模型的表示框架：多 分片贝叶斯网络模型，探究了便于推理的连接联合森林的实现，并给出其 上的系统信念表示以及实现推理的具体操作。具体工作如下： ( 1 ) 在分析动态贝叶斯网络结构的同时提出了l ；片联合树算法。此算 法具有实现简单、不必限定消去顺序、只需作一次扩展等较好的特性：且 通过实验比较，证明了此算法在运行时间、空间上要优于普通的扩展联合 树算法和2 片联合树算法。 ( 2 ) 由于大知识域的局部性，在利用多分片贝叶斯网络对大知识域上 多a g e n t 系统进行模型表示的基础上结合联合树的思想，探究了便于推理 的连接联合森林的实现并对推理操作u p d a t e b e l i e f 进行了有效的改进。 关键词：多a g e n t 系统，贝叶斯网络，多分片贝叶斯网络，连接联合森林 系统信念 r e s e a r c ho ft h ep m b a b i l i s t i cf r a m e w o r kf o r m u l t i - a g 蛐t s y s t e mm o d e l a b s t r a c t b a y e s i a j lt e c h | 1 0 l o g ya n db a y e s i a nn e l w d r k sa r eu s e dt on r o c e s s u n c e r t a i n t yp r o b l e m so fa r t i f i c i a l i n t e l l i g e n c e d o m a i n b e c a u s eo ft h e i n c o r p o r a t i o nb e t w e e nb a y e s i a nt e c h n o l o g ya n da g e mt e c l l n o l o g y ，a v e r y p r o m i s i n gn e wd o m a i nw h i c hp o s s e s s e sad i s t a n ts p e c t a c l ei sf o r m e d t h er e p r e s e n t a t i o no fm u n i a g e ms y s t e mi s t h ek e yo fas e r i e so f o p e r a t i o n so nm u l t i - a g e n ts y s t e m ，s u c ha sr e a s o n i n g ，l e a r n i n ga n dc o o r p c r a t i o n b a s e do nt h ei m r o d u c t i o na n dd i s c u s s i o no f t h et h e o r yo f a g e n tt e c h n o l o g ya n d b a y e s i a nn e t w o r k s ，t h et h e s i s s t a t e st h er e p r e s e n t a t i o n矗a m w o r ko f i 肌l t i a g e m sm o d e lo nh g ek n o w l e d g ed o m a i n m u n i p l ys e c t i o n e db a y e s i a n n e t w o r k sm o d e l t h et h e s i ss t u d i e dt h er e a l i z 砒i o no fl i i l k e dj u n c t i o nf o r e s t w h i c hi e a d st o f a c i l i t yo fr e a s o n i n ga n di m r o d u c e st h er e p r e s e n t a t i o no f s y s t e i n a t i cb e l i e fa n dt h es p e c i f i co p e r a t i o nu s e dt or e a l i s er e a s o n i n g t h em a i n 、o r k sa r ea sf b l k l w s ： ( 1 ) t h et h e s i sp r o p o s e da n 1 ；- s l i c ej u n c t i o nt r e ea l g o r i t h ma sw e l la s a i l a l y z e dd y n a m i cb a y e s i a nn e t w o r k s t u c t u r e t h ea l g o r “h mh a sb e t t e r c h a r a c t e r i s t i cp r o p e r t y ，s u c ha st h es i m p i er e a l i z a t i o n ，w i t h o u tl i m “i n gt h e s e q u e n c eo fe x p u r g a t i o n ，o n l yo n ee x t e n s i o n ；a n db ye x p e r i m e n t ，t h et h e s i s h a sp r o v e dt h a tt h ea l g o r “h ma r es u p e r i o rt oo r d i n a r ye x t e n d e dj u n c t i o nt r e e a l g o r i t h ma n d2 - s l i c ej u n c t i o nt r e ea l g o r i t l l n l 址r e s p e c to fr u n - t i m ea n ds p a c e ( 2 ) o w i n gt ot h el o c a l i t yo fl a r g ek n o w l e d g ed o m a i n ，t h ed i s s e r t a t i o nh a s r e p r e s e n t e d h l l t i - a g e n ts y s t e mo nl a r g ek n o w l e d g ed o m a i nb ym e a n so f m u l t i p l ys e c t i o n e db a y e s i a nn e t w o r k ，a n dt h e nc o m b i n e dt h ei d e ao fj u n c t i o n t r e e ，t h ed i s s e r t a t i o nh a ss t u d i e dt h er e a l i z a t i o no fl i n k e dj u n c t i o nf o r e s ta n d t h ee f f e c t i v ei m p r o v e i i 坞mo fu p d a t e b e l i e f k e yw o r d s ：m u l t i a g e n ts y s t e m ，b a y e s i 趾n c t w o r k s ，m u n i p l ys e c t i o n e db a y e s i 蹰n e t w o r k s ，l i n k e dj u n c t i o nf o r e s t ， s y s t e mb e l i e 图型目录 图2 1 贝叶斯网络示意图， 图22 动态贝叶斯网络示意图 图2 3 接口示意图+ 图2 41 ：片联合树示意图 图25 隐马尔可夫模型中的1 ；片联合树示意图 闰2 6m i l d e w 网中三个算法推理时间比较 图2 7 w a t e ，网中三个算法推理时间比较，+ 。 图2 8 b a t 网中三个算法推理时间比较 图3l m s b n s 图组件所对应的超树 图3 2 。个未划分之前的贝叶斯网络 图3 3 划分后的各个贝叶斯子网示意图 图3 4 一个数字的电路图 图3 5 三个子网转化为联合树后的结果 图3 6 图3 5 ( c ) 所对应的联合森林 图3 7 算法3 2 对图3 3 施行后的结果。 图3 8 由图3 7 转化所得的连接联合森林 图4l 联合森林示意图 耵如虬挖 恐 弱卯盯船弛姐拍5均船 表格目录 表2 】= i 个算法对m l l d e w 网络施行推理所用时间比较( 单位：秒) 表3 1 未划分之前贝叶斯网络中各结点的概率表 表3 2 划分后的各个贝叶斯子网中结点的概率表 表3 3 图3 8 中联合森林中联合树r ，上的信念袁占( r ，) 表3 4 图3 8 中联合森林中联合树r ，e 的信念表占( r ，) 表3 5 图3 8 巾联合森林中联合树r ，上的信念表b ( r ，) 2 6 3 2 3 3 4 2 4 3 4 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得合肥工业 大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签嘶笆签字日期： 年6 月，- 9 日 学位论文版权使用授权书 本学位论文作者完全了解垒邀! 丝z ：蕴有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权龇。z ，业丛盔：可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：f 芗捧也 签字日期：可年6 月，。日 学位论文作者毕业后去向 工作单位： 通讯地址 导师签名 z 龟 签字日期：厉晖勿o 日 电话 邮编 致谢 在论文完成之际，首先向我的导师王浩教授表示衷心地感谢! 王老师为我的 论文倾注了大量的精力，从论文的选题、修改到定稿都给予了精心的指导。在三 年的研究生学习和生活期间，王老师严谨的治学精神、渊博的学识以及对学术前 沿的敏锐洞察力都对我产生了深远的影响。 在此真诚地感谢胡学钢副院长j 胡老师广博的学识、严谨的学术风格和严格 的要求对我产生了重大的影响。 感谢计算机学院的王新生老师、徐静老师等，正是他们在这三年的时间 里对我的无私帮助才使得我得以顺利完成学业；感谢研究生部、学科学位 建设处的各位老师在办理答辩手续时给予的帮助。 同时，要感谢姚宏亮、李俊照老师! 在我完成论文的过程中他们给予了许许 多多的帮助。 另外，还要感谢和我一起学习的曹义新、王一雄、林联明、虞靓靓，以及研 究室的所有同学。 最后，深深感谢我的父母家人对我学业的大力支持! 作者：周本达 2 0 0 5 年4 月 第一章绪论 人类在经历了漫长的农业时代咀及经济快速发展的工、i k 时代后，伴随 着计算机技术、通讯技术的飞速发展，又迎来了一场具有深远意义的革命 一信息革命。信息时代，机遇与挑战并存。信息也成为一个组织发展最重 要的资源，谁能迅速获取关键信息，谁就能掌握制胜的先机。信息时代改 变了人类的工作方式、思维方式、生活方式，许多令人难以置信的场景变 为现实。由于信息技术的迅猛发展、i n t e r n e t 技术的普及，电子商务和虚 拟企业成为信息领域的新的研究热点。这些应用都迫切需要研究异构主体 如何自主地实现台作的问题，这里的异构主体可能是由不同的人，在不同 时间，用不同软件工具、技术实现的从属于不同组织的主体，这些应用需 求导致新的台作技术的出现。 l i1 科学研究的一个趋势 工智能 哲学研究可以分为三个阶段。第一阶段集中在对客体的研究，即世界 的本原问题和发展问题：第二阶段集中研究客体与主体的关系问题：第三阶 段也就是现阶段转入对主体的集中研究，即对人类自身的研究，对人类思 维与智能的研究。作为信息时代科学研究主力军的信息科学和计算机科 学，已经把重点从如何对信息进行收集、存储、处理、加工与利用转移到 研究知识的收集、存储、处理、加工与利用。从人工智能的三大领域来讲， 也就是对知识获取、知识表示、知识推理的研究。 哲学以及具体科学中的研究趋势人工智能反映了人类的一个宏 伟日标。工业革命把人类从繁重的体力劳动中解放出来，人类希望在信息 时代，能够从更为繁重的脑力劳动中解脱出来，或者至少能为人类的脑力 劳动提供更为有效的方法和技术支持。 1 2 合作研究的重要性 当今产业、金融、投资、运输、通讯等都已逐渐打破了国家和地区的 界限，在全球范围内融为一个统一的整体，经济全球化已成为不可阻挡的 导向。经济全球化的主要特征是生产的全球化与消费倾向的全球化。经济 发展的全球化、企业经营战略的国际化都迫切需要能够支持行业间、企业 问、企业内部进行更好地合作的信息技术“1 。 信息在各个行业的爆炸性增长给科学研究带来了丰富资源的同时又带 来了巨大的困难。同一学科、同一领域的新文献、新术语层出不穷，使学 科内部的科学研究更需要加强合作，以保证同一学科的科研人员处在同一 科内部的科学研究更需要加强合作，以保证同一学科的科研人员处在同一 第一章绪论 人类在经历了漫长的农业时代以及经济快速发展的工业时代后，伴随 着计算机技术、通讯技术的飞速发展，又迎来了一场具有深远意义的革命 一信息革命。信息时代，机遇与挑战并存。信息也成为一个组织发展最重 要的资源，谁能迅速获取关键信息，谁就能掌握制胜的先机。信息时代改 变了人类的工作方式、思维方式、生活方式，许多令人难以置信的场景变 为现实。由于信息技术的迅猛发展、i n t e r n e t 技术的普及，电子商务和虚 拟企业成为信息领域的新的研究热点。这些应用都迫切需要研究异构主体 如何自主地实现合作的问题，这里的异构主体可能是由不同的人，在不同 时间，用不同软件工具、技术实现的从属于不同组织的主体，这些应用需 求导致新的合作技术的出现。 1 1 科学研究的一个趋势人工智能 哲学研究可以分为三个阶段。第一阶段集中在对客体的研究，即世界 的本原问题和发展问题：第二阶段集中研究客体与主体的关系问题：第三阶 段也就是现阶段转入对主体的集中研究，即对人类自身的研究，对人类思 维与智能的研究“3 。作为信息时代科学研究主力军的信息科学和计算机科 学，已经把重点从如何对信息进行收集、存储、处理、加工与利用转移到 研究知识的收集、存储、处理、加工与利用。从人工智能的三大领域来讲， 也就是对知识获取、知识表示、知识推理的研究。 哲学以及具体科学中的研究趋势一一人工智能，反映了人类的一个宏 伟目标。工业革命把人类从繁重的体力劳动中解放出来，人类希望在信息 时代，能够从更为繁重的脑力劳动中解脱出来，或者至少能为人类的脑力 劳动提供更为有效的方法和技术支持。 1 2 合作研究的重要性 当今产业、金融、投资、运输、通讯等都已逐渐打破了国家和地区的 界限，在全球范围内融为个统一的整体，经济全球化已成为不可阻挡的 导向。经济全球化的主要特征是生产的全球化与消费倾向的全球化。经济 发展的全球化、企业经营战略的国际化都迫切需要能够支持行业间、企业 间、企业内部进行更好地合作的信息技术。1 。 信息在各个行业的爆炸性增长给科学研究带来了丰富资源的同时又带 来了巨大的困难。同一学科、同一领域的新文献、新术语层出不穷，使学 科内部的科学研究更需要加强合作，以保证同一学科的科研人员处在同一 平台进行科学研究，以达到科学研究高效能高效率的目的。当今世界，跨 学科交流是当前科学研究的一大趋势，学科交叉、科学研究的跨学科合作 已成为解决科学难题的一个法宝：学科交叉产生了许多新的研究领域，同时 也对不同学科的科研人员如何合作提出了更高的要求。 科学研究的目的是认识大自然和发展生产力。当前存在着科学研究成 果转换与企业对科学技术需求的矛盾：一方面，大量的科学研究成果得不到 转换，另一方面，企业迫切需要面向市场的科学研究成果。因此，如何加 强科学界与企业界的合作，也是迫切需要研究的一个课题。 合作是智能系统中一个重要的特征，合作本身就属于一种智能行为：个 体的智能与群体合作的智能表现出巨大的差异，整个系统比单个a g e n t 具 有更强的功能。因此，合作行为是当前许多学科领域( 如人工智能、复杂系 统) 的研究热点。 综上所述，无论是从经济全球化、科学研究的宏观角度来看，还是从 具体学科的研究需求来看，都需要对合作进行深入地研究，相应的信息技 术如何对经济合作、科研合作进行支持：信息技术如何促迸经济合作、科研 合作等都是迫切需要研究的课题。 1 3a g e n t 技术与多a g e n t 系统 产生于分布式人工智能( d a i ) 领域的a g e n t 技术，经过上世纪七十年代、 八十年代的孕育，在九十年代达到了研究的高潮，将会成为二十一世纪人 工智能相关领域研究的一个重点。n i c h o l a sn e g r e p o n t e 博士认为d ta g e n t 技术的发展代表第三次计算机革命的到来，第三次浪潮所处的环境是计算 机、通讯以及基于知识的a g e n t 所组成的一个有机融合的环境。现在，a g e n t 领域已成为人工智能研究的前沿并在各个领域得到了广泛的应用，如个人 助手”“1 ，信息检索“1 ，电子商务1 “，工作流管理“”等。 无论是全球化的经济合作、企业间的合作，还是科学研究中的合作， 都是以人或者组织团体为主体的合作。a g e n t 技术既可以模拟人类的合作， 也可以支持人类进行合作。因此，a g e n t 如何模拟人类的合作，a g e n t 如何 为人类合作提供智能化的支持，如何最大限度的实现自治，a g e n t 相互间如 何合作就成为摆在我们面前的一系列重大课题。 a g e n t 真正有前途的领域是多a g e n t 技术领域，多a g e n t 技术的优势就 是通过a g e n t 之间的合作与分工，完成单个a g e n t 所不能完成的任务或以 更小的代价，更高的效率完成任务。多a g e n t 合作和推理是多a g e n t 系统 研究的一项重要内容，而多a g e n t 系统的模型表示是研究合作和推理的基 础。研究合作的目标主要有三个：通过多a g e n t 的合作去支持人类更好的合 作( 比如虚拟组织中的合作，科学研究中的合作) ：通过a g e n t 的合作去研 2 究、解释自然界和人类社会的一些合作行为( 如复杂系统的研究) ：通过 a g e n t 的合作去研究解决一些复杂的优化问题( 如分布式计算) 。 a g e n t 的历史可以追溯到对a i 的早期研究。1 9 7 7 年，h e w i t t 的 “c o n c u r r e n ta c t o rm o d e l ”是第一个a g e n t 系统“。在模型中，他提出“一 个自封装，交互型的，并行执行”的对象，并称之为“a c t o r ”。每个a c t o r 都有它的内部状态，并能够对来自其他a c t o r 的信息做出反应”。 1 4 g e n t 的定义及特征 1 4 1a g e n t 的定义 a g e n t 目前尚未有一致的定义。研究a g e n t 的不同领域对其有不同的定 义和别称。我们首先介绍不同领域中对a g e n t 的定义： 1 ，4 1 1 人工智能当中的a g e n t 一理想 g e n t 智能 g e n t “1 理想a g e n t ：人工智能的本质是研究如何制造出人工的智能机器或智能 系统，来模拟人类智能活动的能力，以延伸人类智能的科学。人类智能活 动的能力一般是指人类在认识世界和改造世界活动中，由脑力劳动表现出 来的能力。具体概括如下： ( 1 ) 通过视觉、听觉、触觉等感官活动，接受并理解文字、图像、声音、 语言等各种外界的自然信息，即接受环境信息的能力。 ( 2 ) 通过人脑的活动进行信息处理过程，将感性信息抽象为理性知识， 并进行分析、判断和推理，即认识和理解客观事物、提出概念、建立或调 用方法、进行演绎和归纳推理以及做出决策并对可能影响外部世界的问题 求解能力。 ( 3 ) 通过教育、训练和学习过程，日益丰富自身的知识和技能，即学习 能力。 ( 4 ) 对变化多端的外部环境条件，如干扰、刺激等作用能灵活地作出反 应，即自我适应能力。 ( 5 ) 能与其他人合作，解决单个人无法解决的大型复杂问题，即协作能 力。 目前，随着a g e n t 概念的发展，人工智能研究者认为理想a g e n t 应当 具有上述五种职能，正如著名的a i 学者h a y e sr o t h 在一篇报告中所指出： “智能的计算机a g e n t 既是人工智能的最初目标，也是人工智能的最终目 标”。我们所要研究的船e n t 应当是a i 各个领域的研究成果集成为一个具 有智能概念的计算实体。 大部分人类智能行为都涉及多个人构成的社会团体，大型复杂问题的 求解也需要多个专业人员或组织协作完成。计算机上的复杂信息处理可对 应为多a g e n t 系统来完成。 智能a g e n t ：目前的人工智能技术还难以实现理想a g e n t 的智能行为。 智能a g e n t 是指能在某一环境中运行，并能响应环境的变化，灵活、自主 地采取行动以满足其设计目标的计算实体。这类a g e n t 通常由当前的人工 智能技术来实现，一般具有某种程度的感知、推理、学习、自适应和协作 能力，如某些智能控制系统、实时专家系统等。 近年来，新的人工智能定义为：人工智能是计算机学科的一个分支，其 目标是构造具有一定智能行为的眶e n t ，a g e n t 的研究仍然是智能的核心 问题。 1 4 1 2 计算机领域的a g e n t 一软件a g e n t 2 软件a g e n t 是从软件设计的角度研究a g e n t ，s h o h a m 等人将其定义如 下： “a g e n t 是一种在特定环境下连续、自主地运行的软件实体，通常与其 他a g e n t 一起，联合求解问题”。 连续与自主的需求来自我们需要a g e n t 以一种灵活和智能的方式完成 其活动，无需人为的引导与干扰而响应环境的变化。最理想的情况是，一 个a g e n t 能够在种环境中连续的运作一段较长时间，并能从它自己的经 验中学习。而且我们希望一个a g e n t 能够与其他a g e n t 同处于一个环境， 并能相互通讯和协同，或从一个地方移动到另外一个地方求解问题。目前， 大部分软件a g e n t 都十分脆弱并针对特定目的，还没有个系统能以一般 形式完成这些功能。 倡导研究软件a g e n t 的另一种观点类似于早期对面向对象的研究，将 其作为设计和实现软件系统的新范例。正如一些算法用面向对象的表示形 式比用过程的形式更易于表达和理解，有时对开发者和用户来说，根据 a g e n t 来设计程序的行为比各种对象更容易。 我们希望a g e n t 能够像人一样完成分配给它的一些特定任务，能够从 我们告诉它的内容中推导出所需结果。a g e n t 只有在“知道”有关请求的背 景知识时才能做到这一点。因此，最好的a g e n t 不仅需要特定形式的专家 知识，而且需要考虑用户和当前状态的独特性质。 s i n g h 曾指出采用a g e n t 方法进行软件开发的实用和技术原因：它们对 设计者和分析者来说，比较自然：提供了简明描述复杂系统行为的工具，有 助于理解和解释复杂系统的行为：可获得一定的行为规则和模式，这些行为 是独立于系统中a g e n t 的精确的物理实现：能够被旭e n t 用于推导其他 a g e n t 的意图状态和行为。 4 其他人关于软件a g e n t 的定义有： ( i ) a g e n t 是设计完成某类任务的，能在一定环境中自主发挥作用，有 生命周期的计算实体”“。 ( 2 ) m i c h a e l 0 0 l d r i d g e 的定义 弱定义：具有下列属性的基于硬件的或者基于软件的计算机系统。 自治能力：可以不受人或外界因素的干扰而独立存在，对自己的行为 和状态有一定的控制权。 社交能力：可以通过某种a g e n t 通讯语言( a g e n tc o m m u n i c a t i o n 1 a n g u a g ea c l ) 和其他a g e n t ( 包括人) 进行信息交流。 反应能力：可以理解周围的环境，并对环境的变化做出实时的响应。 预动能力：可以主动地做出有目标的动作。 强定义：除了弱定义中应具有的属性外，还应具有类人的精神状态，如 信念、承诺、意图。 这两种定义同a i 中并存的两类智能观隐隐相应，其中都隐含着类比人 类的某些行为与心理特征的思想。 ( 3 ) y o a vs h o h a m 的定义“” 她e n t 是包含了信念、能力、决定和承诺等精神状态的智能体。 ( 4 ) f r e e m a n 的定义o ” f r e e m a n 在一类称为约束满足的问题领域中，用船e n t 表示相互作用的 自主知识库，并用一个8 元组来定义：a g e n t = ( m ，k ，a ，i ，e ，s ，r ，g ) 。 其中m 表示方法( m e t h o d ) ，k 表示知识( k n o w l e d g e ) ，a 代表属性 ( a t t r i b u t e ) ，i 代表推理机制( i n f e r e n c e ) ，e 表示语言( 1 a n g u a g e ) ，s 表示消息传送协议( p r o t o c o lo fm e s s a g es e n d i n g ) ，r 表示消息接受协议 ( p r o t o c 0 1o fm e s s a g er e c e i v i n g ) ，g 表示全局知识( 9 1 0 b a lk n o w l e d g e ) 。 1 4 1 3 复杂性领域的a g e n t ”6 在复杂系统研究中，把组成复杂系统的具有主动性的个体或单元称为 a g e n t ，研究这些a g e n t 的个体行为如何导致整个系统的整体行为。正如霍 兰所说，“复杂自适应系统毫无例外地皆由大量具有主动性的元素组成，为 了说明具有主动性的元素，同时，不求助于专门的内容，我借用了经济学中 的a g e n t 一词，这个术语是描述性的。如果我们准备搞明白大量a g e n t 的 相互作用，我们就必须首先能够描述单个a g e n t 的性能，将a g e n t 的行为 看成是由一组规则( 刺激一反应规则) 决定的，是很有用的”。 1 4 1 4 社会心理学领域的a g e n t 在社会心理学研究领域，把a g e n t 作为一个人或者拟人的个体，他们 具有人的思想和行为，通过a g e n t 对人的模拟来解释、预测一些人类社会 的行为和现象。 1 4 1 5 博弈论中的a g e n t 博弈论的研究中，或者有些使用博弈论进行分析的研究中，把参加博 弈的个体称为a g e n t ，研究这些a g e n t 如何交互与决策以达到各自利益或者 整体利益的最大化。 这几个领域中的a g e n t 研究又不是截然分开的，各领域的研究相互联 系，相互借鉴。 1 4 2a g e n t 的特征 a g e n t 的特征包括基本特征和可选特征。基本特征包括自主性 ( a u t o n o m y ) ，社会性( s o c i a la b i l i t y ) ，反应性( r e a c t i v i t y ) ，能动性 ( p r o a c ti v e n e s s ) 2 引。 自主性：在没有人直接干预下进行工作，可以以某种方式控制自身的动 作及其内部状态。 社会性：它也称为协作性，能够通过某种a g e n t 通讯语言与人或其他 a g e n t 相互作用。 反应性：它能够接受环境的信息并做出反应，这里环境包括其他的 a g e n t 、人以及i n t e r n e t 等。 能动性：它不仅能对环境做出反应，而且呈现目标驱动的特性。 每个a g e n t 首先应具备这4 条最基本的特性，然后再根据其应用情况 拥有其它可选特征，例如： 移动( m o b i l i t y ) ：能够在电子网络中漫游。 诚实( v e r a c i t y ) ：不会故意发送错误信息。 合作( c o o p e r a t i o n ) ：同其他a g e n t 一起为完成同样的目标而努力。 竞争( c o m p e t e n c e ) ：同其他a g e n t 竞争。 1 5a g e n t 的行为特征表示及其推理 a g e n t 行为特征表示的主流思想是赋予其精神状态，这种方法借用人类 心理学中的思想，一个人的行为可以通过它的态度属性，例如相信、想要， 希望，担心等来预测和解释。态度在人类心理学中用“动机”来描述。任 何实体都能被看作具有精神状态的实体，问题的关键不在于一个系统是否 真正具有精神状态，而在于我们怎样用这样的观点来看待它。 o h nm c c a r t h v 论述了赋予机器精神状态的正确性和有用性的区别o 。 当赋予一个机器或计算机程序某种信仰、意愿、动机、意识、能力和 愿望时，如果这样的赋予表达了机器所要正确表达的关于人类的信息，那 么这种赋予就是正确的。当这种赋予有助于我们理解机器的结构、机器的 过去和将来的行为，或者能够提高和改进它时，我们就说这样的赋予是有 用的。从逻辑上来说，甚至人类都可能不需要精神状态，但是能够简短的、 合理的表示机器在某种情况下的状态可能需要精神状态或与精神状态同构 的事物。把精神属性赋予已知结构的机器如温度计或计算机操作系统是最 简单的，但是当把他们应用于结构不太清楚或很不清楚的实体时将会是非 常有用的。 人们意识到，用经典逻辑表示意识概念并进行推理是很不够的，现在 普遍采用的是k r i p k e ”发展的模态逻辑。最简单的模态逻辑就是经典逻辑 附加两个操作符r ( 必然) 和( 可能) 。如果对从当前世界可达到的每个世 界都有工为真，则rz 为真。如果对至少一个从当前世界可达到的世界有x 为 真，则为x 真。m a n n a 与p n u e l i ”发现了时态逻辑在并发程序规范说明和 验证中的应用。他们引入了一种时态逻辑形式作为对并发程序引起的状态 序列进行推理的方法。 h a l p e r n ，m a n n a 与m a s z k o w s k i “”则利用一种变形的时态逻辑对硬件电 路进行了描述。c o h e n 和l e v e s q u e 的意图理论使用了两种观念：信念和目标。 该理论适于a g e n t 之间的推理，已应用于多a g e n t 交互中对合作与冲突的 分析。并可以作为协作问题求解的理论基础。r a o 和g e o r g e f f 建立的逻辑 框架则基于三种观念。”：信念、愿望和意图( b e l i f ，d e s i r e ，i n t e n t i o n ： b d i ) 。w 0 0 1 d r i d g e 。”发展了一系列逻辑用来表示多a g e n t 系统的特性，他 的目标不是a g e n t 理论的通用框架而是对实际的多a g e n t 系统的说明与 验证。 1 6 多a g e n t 系统的定义及特征 随着a g e n t 技术的发展和日益复杂的应用问题提出，对以对等方式进 行通讯的多a g e n t 系统的需求正变得日益突出。多a g e n t 系统( m a s ) 设计 和有效实施的关键技术正是分布式人工智能领域已研究多年的问题。单 a g e n t 的能力已不能解决大型、复杂的现实问题，一个智能a g e n t 的能力受 其知识、计算资源及其与其他a g e n t 相互关系的限制，因此m a s 的出现并 成为研究的主流是必然的。 1 6 1 多a g e n t 系统的定义 当前m a s 也没有统一的定义，从m a s 所具有的两大功能来看，可以定 义为： ( 1 ) 面向问题求解： m a s 定义为由分布在网络上的多个问题求解器松散欧藕合而成的大型 复杂系统，这些问题求解器相互作用以解决由单一a g e n t 的能力和知识所 不能处理的复杂问题。这些问题求解器通常称为a g e n t ，具有自主性，并可 以是不同的异质计算实体。 ( 2 ) 市场机制： 基于提供服务二使用服务( 或者，提供服务一一中介一一使用服务) 的市场机制，由多个a g e n t 组成的面向某一领域的多a g e n t 系统。例如基 于多a g e n t 技术的汽车交易系统等。 1 6 2 多a g e n t 系统的特征 m a s 具有以下特征o “： ( 1 ) 每一个a g e n t 具有有限信息资源和问题求解能力，缺乏实现协作的 全局观点。 ( 2 ) 系统不存在全局控制，即控制是分散的。 ( 3 ) 知识与数据都是分散的。 ( 4 ) 计算是异步执行的。 1 6 3 多a g e n t 系统需要解决的问题 m a s 存在着不少难题。1 9 9 1 年，g a s s e r 提出设计和实现任何协作问题 求解器内在的、网有的六大问题，1 9 9 8 年，s y c a r a 对此进行了补充，如下 所述“州： ( 1 ) 如何在一组智能旭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 在制定决策或采取行动方面能够一致行动，并使局 部决策具有非局部效果以及避免有害的相互作用? 怎样确保m a s 不受资源限 制? 怎样避免系统行为的不稳定? ( 4 ) 如何使每一蟾e n t 了解其他a g e n t 的行为、计划和知识，并能针对 这些内容进行推理，以便与其他a g e n t 协调? 如何对他们的协调过程进行推 理( 如初始化和完成) ? ( 5 ) 如何识别和消解合作a g e n t 之间不同的观点和冲突的意图，以便协 调它们的行为? ( 6 ) 如何工程化实现实际的分布式人工智能系统? 如何为m a s 设计技术 平台和开发方法学? l _ 7 本文的组织 本文对a g e n t 技术和贝叶斯网络的理论体系进行了一定的介绍，提出 了处理动态贝叶斯网络中精确推理的1 ；片联合树算法，在此基础上对扩展 联合树算法、2 片联合树算法以及此算法进行了实验比较。对基于贝叶斯方 法的m a s 模型进行了较为深入的讨论，给出了基于多分片贝叶斯网络结构 的m a s 模型表示框架，并对基于多分片贝叶斯网络结构的m a s 模型中的推 理操作进行了一定的探索。本文是围绕贝叶斯技术和多船e n t 系统这个中 心而展开的。具体章节的安排如下： 第一章绪言。论述了a g e n t 及多a g e n t 技术的基本理论，并概述了 a g e n t 和多a g e n t 技术的产生、发展、应用以及其需要解决的问题。 第二章贝叶斯技术与贝叶斯网络。比较系统地论述了贝叶斯网络的理 论基础，并讨论了贝叶斯网络、动态贝叶斯网络的模型结构及其有关的推 理算法，提出l ；片联合树算法并进行两人实验比较。 第三章多分片贝叶斯网络与连接联合森林。在探讨多分片贝叶斯网络 结构中分片划分合理性的基础上，提出便于多分片贝叶斯网络结构推理豹 第二结构一一连接联合森林，并给出整个系统的信念表示。 第四章多分片贝叶斯网络中的推理。基于第三章提出的连接联合森林 结构的基础上讨论了多分片贝叶斯网络中的推理操作，从而实现系统的一 致性，便于对系统中感兴趣结点的信念求解。讨论了几个合理的推理操作 并对推理的有效性进行的一定的探究。 第五章总结与展望。 第二章贝叶斯技术与贝叶斯网络 贝叶斯技术和贝叶斯网络”4 1 ( b a y e s i a nn e t w o r k s ，b n s ) 是从传统的统 计学中分离出来的、对不确定性问题进行处理的一种有力工具。在智能 他e n t s 和多a g e n t 系统中，不确定性问题的处理是研究的关键所在。因而 研究如何利用以坚实的数学理论为基础的贝叶斯技术和贝叶斯网络这个理 论框架来处理这些不确定性问题具有极其重要的意义。 由于贝叶斯网络给出了一个环境的模型，模拟了在环境中进行操作的 机制，因而贝叶斯网络可生成各种推理模型( 包括预测、分布式推断和控制 模型等) ，这和神经网络等许多知识表示方法不同，它们给出的只是一个模 型的推理过程。这使贝叶斯网络更适用于对与环境紧密关联的智能a g e n t 进行建模，因而贝叶斯技术可用于解决m s 的模型表示，m a s 的学习，a g e n t 的行为决策，以及a g e n t 之间的协作和协商等问题。对于由最简单的a g e n t 构成的m a s ，就是一个传统意义上的贝叶斯网络，而对于一般的、较大知识 域上多a g e n t 系统可以用多分片的贝叶斯网络来进行模型表示。 应用贝叶斯技术和贝叶斯网络为智能a g e n t 和m a s 所提供的这一形式 化的数学框架和处理工具，可有效地解决a g e n t 研究领域所遇到的知识表 示、学习和行为决策问题。然而贝叶斯网络也有自身的局限性，传统的贝 叶斯网络不太适合用于大规模和动态领域的知识表示，而自治的和现行的 a g e n t 可实现对大规模复杂的数据进行处理，另一方面由于多分片的和动态 的贝叶斯网络适合于表示大规模和动态的知识领域，所以这两者的结合将 克服传统贝叶斯网络的不足。 由上述可见，a g e n t 技术和贝叶斯技术的结合，相互弥补对方的不足之 处，且能相互利用到对方的优点。从而，贝叶斯技术和a g e n t 技术这两个 似乎不相关的研究领域相结合，形成了一个具有广阔前景的新的理论和应 用性研究领域。下面首先讨论贝叶斯技术和贝叶斯网络的数学基础和形式 化定义。 贝叶斯技术是以贝叶斯概率为基础，是贝叶斯概率的应用和发展，主 要用于处理在概率领域中所遇到的不确定性问题：由p e a r l 提出的贝叶颠 网络是贝叶斯技术和图论结合的产物，其理论基础是贝叶斯定理和图形理 论。 2 1 贝叶斯定理 定义2 1 样本空间 一个随机试验所有可能的“基本结果”构成的集合称为该随机试验的 1 0 基本空间，常用集合q = ) 表示，基本空间又称为样本空间，其元素称 为样本点。 例如：对于任意掷一枚硬币的随机实验，其样本空间q ：f 正，反) 。 定义2 2 随机事件 给定了基本空间q ，一个随机事件就是n 的一个子集，也就是由某些 基本结果组成的集合。随机事件表示随机试验的某种结果。随机事件一般 简称为事件。 例如：投掷两颗骰子，“其和为4 点”这一事件就是子集彳= ( 1 ，3 ) ，( 2 ，2 ) ， ( 3 ，1 ) ) 。 定义2 3 对立事件 若给定一个事件a ，则“a 不发生”这个事件称为a 的对立事件。用子 集a 在q 中的补集爿。= q 一4 表示。 定义2 4 不相容事件 给定样本空间q 中的两个事件彳与b ，显然有爿q ，b q ，如果 爿n 占= a ，则称爿与b 为互不相容事件。 定义2 5 事件类 在概率论中为了保证符合规定性质的概率存在，并不总是把基本空间 q 的一切子集都当作事件，尤其是当q 为不可数无穷集时，为了研究事件 间的各种关系，记全体事件构成的集类为贸，要求孵满足： ( 1 ) q 辨 ( 2 ) 若彳孵，则彳。婀 ( 3 ) 若4 ，鸣，4 ，婀，则u 4 贸 f _ l 下面给出概率的定义 定义2 6 概率空间 如果p 是孵上的一个实值函数，即对每一个彳e 孵，有一个实函数p ( 4 ) 与之对应，并且满足以下三点： ( 1 ) 非负性：对w 倪，) 0 ( 2 ) 规范性：p ( 识) = l ( 3 ) 可列可加性：若4 ，4 ，4 ，是孵中两两不相容的事件，定有 p ( u 4 ) = p ( 4 ) ( 2 1 ) 则称p 是( q ，孵) 上的一个概率( 测度) ，p ( 4 ) 称为事件彳的概率，三元组 ( q ，孵，p ) 称为概率空间。 定义2 7 条件概率 设( q ，m ，