（信号与信息处理专业论文）基于agent的信息检索系统的若干问题研究.pdf

摘要 ( a g e n t 技术是近年来研究的一个热点，它是从人工智能的一个分支 d a i ( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ) 发展起来的。a g e n t 技术和检 索系统的结合是近年来检索系统研究的重点内容，a g e n t 以其自身特性 弥补了传统检索系统的搜索精度不高、过分依赖于网络连接和返回冗 余信息过分等缺点。由于是一门全新的研究领域，这种基于a g e n t 的 检索系统也会产生一系列问题。棒文总结了检索系统发展的历史，将 a a g e n t 技术引入检索系统，并对基于a g e n t 的检索系统的若干关键问题 进行了研究： 1 通过对传统检索系统搜索算法的分析，提出了一种基于深度受 限的动态调整算法，并针对搜索a g e n t 的两种搜索方式，分别提出了 深度受限的顺序搜索算法和深度受限的并行广度搜索算法。 2 通过将a g e n t 任务进行分解，以一种分层结构来组织任务a g e n t 和搜索a g e n t 之间的协同，从而提出了分层协同的思想；并就如何命 名a g e n t 的问题，提出了多层命名的思想。 3 提出了建立一个基于反应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 b s t r a c t a g e n t t e c h n o l o g yd e v e l o p e d f r o m d a i ( d i s t r i b u t e d a r t i f i c i a l i n t e l l i g e n c e ) w h i c hi s ab r a n c ho fa r t i f i c i a l i n t e l l i g e n c ea n dh a sb e e na h o t s p o tf o rr e s e a r c h t h ei n t e g r a t i o no fa g e n tt e c h n o l o g ya n dr e t r i e v e s y s t e mh a sb e e n t h ee m p h a s i so nt h er e s e a r c hf i e l do fr e t r i e v e s y s t e m r e c e n t l y a g e n t m a d eu pf o rt h e s h o r t c o m i n g s i nt r a d i t i o n a lr e t r i e v e s y s t e m ，s u c h a s p o o ra c c u r a c y ，r e l y i n g o n i n t e r n e t ，m a n y u s e l e s s i n f o r m a t i o na n ds oo n h o w e v e r , t h er e t r i e v es y s t e mb a s e do n a g e n t h a s a l s ob r o u g h tm a n yn e w q u e s t i o n sb e c a u s ei t i sac o m p l e t e l yn e wr e s e a r c h f i l e d t h i s p a p e r s u m m e du pt h e d e v e l o p m e n th i s t o r y o ft h er e t r i e v e s y s t e ma n da p p l i e dt h ea g e n tt e c h n o l o g yi n t ot h er e t r i e v es y s t e m s o m e k e yi s s u e so f t h er e t r i e v es y s t e mb a s e do na g e n th a v eb e e ns t u d i e di nt h i s p a p e r ： w e a n a l y z e d t r a d i t i o n a lr e t r i e v e s y s t e ma l g o r i t h m a n d b r o u g h tu p d y n a m i c a l l ya d j u s t i n ga l g o r i t h m b a s e do nl i m i t e d d e p t h b e c a u s e r e t r i e v ea g e n th a st w or e t r i e v ew a y s ，w ei n d i v i d u a l l yb r o u g h t u ps e q u e n c e r e t r i e v e a l g o r i t h m b a s eo nl i m i t e d d e p t ha n dp a r a l l e lb r e a d t hr e t r i e v e a l g o r i t h mb a s e d o nl i m i t e dd e p t h w e b r o u g h tu p a m u l t i - l a y e r c o o r d i n a t i o ni nw h i c ht a s ki s d e c o m p o s e di n t om a n ys u b t a s k sa n dt h ec o o r d i n a t i o na m o n gt a s ka g e n t s i s o r g a n i z e d i n m u l t i p l el a y e r sw a y f u r t h e r m o r e ，w eb r o u g h tu p m u l t i l a y e rn a m i n g i no r d e rt oi d e n t i f ya g e n t w e b r o u g h tu pam o d e lb a s e d0 nr e a c t i v ea g e n tt oa v o i dr e p e a t e d l y v i s i t i n gt h es a m ew e b s i t e w ed i s c u s s e ds o m eq u e s t i o n st h a tc o u l do c c u r i nt h er e t r i e v i n gp r o c e s sa n dt h ec o r r e s p o n d i n gs o l v a b l es t r a t e g i e so nt h e b a s i so ft h i sm o d e l i nt h el a s t ，w ep o i n t e do u tt h es h o r t c o m i n g si nt h i sp a p e ra n dl o o k e d i n t ot h ef u t u r eo ft h er e t r i e v es y s t e mb a s e do na g e n t k e y w o r d s ：r e t r i e v es y s t e m ，a g e n td y n a m i c a l l ya d j u s t i n ga l g o r i t h m b a s e do nl i m i t e dd e p t h ， s e q u e n c er e t r i e v ea l g o r i t h mb a s e do nl i m i t e d d e p t h ，p a r a l l e l b r e a d t hr e t r i e v e a l g o r i t h m b a s e do nl i m i t e d d e p t h ， m u l t i - l a y e rc o o r d i n a t i o n ，m u l t i l a y e rn a m i n g ， r e a c t i v ea g e n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果也不包含为获得 金般工业左坐或其他教育机 构的学位或证：降而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文怍者签名： 多芝不军 签字日期：孙，年妇厂日 学位论文版权使用授权书 本学位论文作者完全了解垒罂王些太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘允许论文被查阅和 借阅本人授权金匿王壁盔差可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：；砂之禾霉 导师签名彳逡埒 签字日期：够年r 月日 签字日期扔年f 月r 日 - q - 位论文作者毕业后去向： 莎j 纫 工作单位：噎对勿1 考重卿饭( 巴汤) 僖钕曰电话：pz ，o 罗护矽2 夕0 7 通讯地址：上均事规张昭莎多g 鸳别张囊捌邮编： 第一章绪论 随着i n t e r n e t 的迅速发展，w e b 已发展成为一个全球的、巨大的、 分布的和共享的信息空问1 9 9 9 年2 月的统计数据l i 】表明，w e b 上存 储了大约8 亿个网页，信息容量高达l5 t b 由于、c b 没有统一的数据 模型和查询语言，没有统一的结构，信息容量巨大，资源分散且信息 不断更新，导致了查询w e b 上的信息时所产生的“信息迷向”和“信 息过载”现象，用户试图通过测览网页的方式来查询所需信息变得越 来越困难；但有时也有可能根本搜索不到信息，从而使信息量过少【6 】 因此，如何有效检索w e b 上的信息，帮助用户方便、准确地获取信息， 成为一项重要而迫切的研究课题 1 1 检索系统的发展历史 2 0 世纪6 0 年代，图书馆采用计算机技术存储和管理文档，信息检 索技术1 7 1 由此应运而生2 0 世纪8 0 年代，信息技术在文档内容表示、 索引模型和匹配策略等方蕊取得了丰硕成果2 0 世纪9 0 年代，w e b 的出现为信息检索技术提供了一个前所未有的实验和实用环境并提出 了新的要求，在传统信息检索系统的基础上出现了许多w e b 信息检索 系统 1 1 1w e b 信息检索系统 w e b 信息检索系统主要包括：搜索引擎、分类目录和元搜索引擎 1 搜索引擎是一种最常见的w e b 信息检索系统，如g o o g l e 、 i n f o s e e k 1 和a l t a v i s t a l 9 1 ，它们使用r o b o t 或s p i d e r 来遍历w e b ，将 w e b 上分布的信息下载到本地文档库中，然后系统自动对文档内容进 行分析并建立索引数据库，用户以关键词的方式向搜索引擎提出查询 请求，搜索引擎通过查询索引数据库找到相当的文档井以u r l 的方式 将查询结果反馈给用户在查询时，用户不需要知道搜索引擎中索引 的具体组织形式，一般搜索引擎的结构见图l l t 由图卜l 可知，一般搜索引擎使用w e br o b o t ( 也叫c r a w l e r s 或 s p i d e r s ) 对w e b 采用广度优先( 或深度优先) 的策略进行遍历并下载文 档，文档存贮在本地和被查询，由关键词或短语通过一个c o l 界面来 进行索g l 。系统中维护一个超链队列( 或堆栈) ，其中包含一些起始u r l 。 r o b o t 飙遮些u r l 出发，下载福成的萸瑟，势觚中拯取出新的超键瓣 入到队列巾，上述过程不断重复艇到从列为空。简各种搜索引擎的不 嗣之处在予c r a w l e r 暂必上不同，帮搜索羲深魔辩广度不嗣、索雩l 秘方 法不露及搜索秘查运艨使用弱语袁不同等。 图1 i搜索引举 2 ，分类嚣录，懿y a h o o i 掩i 、s n a p l 瓣l 嚣o p e n d i r e c t o r y i 豫 ，与援索孳 擎翁工终原瑾鹅真不阏。分类曼慕势不使用r o b o t 或s p i d e r 下载w e b 文档，丽是采用人工收集或者采用w e b 站点的作者主动提交的方式究 残对文档躺收集，强泶一般也不对文撼豳容避 亍鞠动分椭祁建立索引， 而楚采用誓人工处理的方式对w e b 站点和文辎进行分类、评价并给蹬 筒溪煞攒述，经过上述处灌靛w e b 傣惠按照主题分类势戳挺拔结擒糖 以组织，从树的根节点逐渐向下列出了从般到特殊的分类和各级子 类，瑟聍麓意粼毽会攒囱w e b 镕怠受滚静镪接，羯户逶避测越分类爨 录巾的分类来爸询w e b 或者以关键词的方式提交查询。当羁录中包含 太多的分撰和链接时，两泶本身也变褥不便予溯览。如警y a h o o 色含 钉指翔5 0 0 0 0 0 个站点的缝接，分搬程2 5 0 0 0 个分类t f t “。需要指 2 的是，目录提供的是对分类以及w e b 信息描述的索引，这与搜索引擎 提供对文档内容的全文检索不同。 搜索引擎和分类目录这两种w e b 信息检索系统各有所长。通常， 由于搜索引擎具有庞大的全文索引数据库，因此适用于检索难以查找 的信息或者一些比较模糊的主题：而目录有助于逐步缩少主题或者查 找某个主题的常见的、质量较高的信息。由于这两种系统彼此互补， 因此一些将两者结合起来的混合系统也出现了，如l o o k s m a r t t ”1 ，现 有的一些著名的搜索引擎和分类目录也呈现出逐渐融合的趋势。如 y a h o o 在目录检索服务的基础上，已开始使用i n k t o m i l l 4 的w e b 全文索 引数据库提供与搜索引擎类似的w e b 信息全文检索服务。通常我们将 两者统称为搜索引擎。 3 元搜索引擎。搜索引擎为了在竞争中取胜不断增加其索引的 w e b 页面数目，但其无法跟上w e b 的发展速度。l a w r e n c e 等人于1 9 9 9 年在n a t u r e 杂志上发表的一份研究报告【l 列表明，任何一个搜索引擎对 w e b 的覆盖度都不超过2 0 。因此，用户经常需要检索多个系统以提 高检索的召回率( r e c a l l ) 。但各个搜索引擎的用户接口是异构的，有其 特定且复杂的界面和查询语法，从而给用户带来了不便。研究人员针 对这种状况而开发了元搜索引擎，如m e t a c r a w l e r l l 6 i 、s a v v y s e a r c h i j 和i n q u i r u s i s l 等。m e t a 搜索引擎弥补了简单搜索引擎的缺陷，m e t a 搜 索引擎将搜索请求提交给不同的搜索引擎并将来自各个搜索引擎所获 得的结果综合成一个结果列表，由此提高信息检索的召回率、准确率 以及方便用户同时访问多个搜索引擎。 元搜索引擎的基本设计思想如下： ( 1 ) 对用户查询请求进行预处理，分别将其转换成若干各底层搜索 引擎能处理的格式。 ( 2 ) 向各个搜索引擎发送查询请求，并等待其返回检索结果。如 m e t a c r a w l e r 同时检索y a h o o 、o o o g l e 、l o o k s m a r t 等多个搜索引擎并 等待这些搜索引擎返回检索结果。 ( 3 ) 对检索结果进行后处理，包括组合各个搜索引擎返回的检索结 果，消除重复项，按照相关度对检索结果排序等操作。有时搜索引擎 还需通过下载w e b 文档来实现一些搜索引擎不支持的查询，或对文档 作进一步的分析以提高信息检索的精度。 4 ) 翻瘸户遨鞠经过缎余鞫赴灌矮戆嬷索雅鬃。 上述懋想最然麓攀，键羧隳院较明漫。瓣予设计人爨藤富，元援 索辱 肇誉鬻要建窥籁缀护庞大熬索弓l 数撼疼，也不溪镶鼹复杂懿梭索 极剿；慰擎焉户麓褰，元攘索零 擎提拱了一拿戆磷瓣囊诲多令援索霉l 擎豹嶷簸爨瑟，姆器个援索零| 聚的位蓬、犊鞠等缨蕊羼簸起来，潮辩 迄提薅了稔索豹露弱率和猿度。它靛蒸零络校褥蠲1 - 2 。它鹃褴辘取决 予爨镶爝熬搜索雩l 攀、套谗转换、箨毽耨综合方法。 篷1 - 2m e t a 援索萼 攀 0 玳f h 群 i # 懿滋= 粹检索系统繇缑少采掰餐髓技零寒捷鬻装髓确毪，第三剽t 羧索系缭较蓠墨稗餐了较大魏遴，搜索豹范蠲更广、攘索鞠送发邈爨 为邈速，餐它壤用鲢仍然怒瑰裙辩搜索譬l 攀，搜索弓l 擎鞭有的缺敞仍 然蠢潦鳞决。隧卷i n t e r n e t 技术麴不鳜笈餍及其应爝的举断深入，瓣上 可秘髑躺傣意堡攒数缀增长。这些绩患邋常l ；是无鳃级懿形式努奄予辩 敷、舅擒熬节焦串，磐基数缀嚣爨努躲癸型及数量霉天瓣褒大蹙蹭濒， 结感瓣霹翻熙蛙狂霹靠瞧东不鞭憋变纯，繁患戆动态瞧敷信惠麴爨麟 窝髹存溺懑也鬻艇搽惑变怒攘嬲，甚至产燮错误。簌这种耩撬下，海 了从巨大的信息海洋中获得所需的信息，使用传统的搜索引擎技术显 露出越来越多的弊端。因此人们将人工智能技术引入到信息检索系统 中，从而出现了众多的智能检索系统。 1 1 2 智能检索系统 近年来，智能信息检索作为人工智能的一个独立分支得到了迅速 发展。人们在进行信息检索时，总是抱有两种期望：一种是期望找到 所有感兴趣的主题及相关文档，即期望得到高检索率；同时，又不希 望包含与主题不相关的文档，即期望获得高检索精度。要实现这两点 非常困难，尤其在i n t e r n e t 这个开放的信息空间中实现这个目标更加困 难。采用人工智能方法是实现人机交互的一种较好的方法，研究者通 过对发现和过滤方法的研究，对智能检索提出了许多模型。 1 9 9 0 年n i e l s e n 提出了搜索引擎解决智能检索问题的9 条可用性 原则1 1 9 1 ： ( 1 ) 人机对话简明、自然 ( 2 ) 使用用户的语言； ( 3 ) 减少用户记忆负担； ( 4 ) 促进一致性实现： ( 5 ) 提供返回信息； ( 6 ) 提供清楚的出口标记 ( 7 ) 提供捷径出错： ( 8 ) 提供有效的出错处理信息； ( 9 ) 能够防止出错。 在设计接口时还要考虑到人和机器两方面的因素，使之具有适合 有限信息集特点和用户水平的推理机制。 智能搜索引擎技术发展到现在，一般可分为两类：一类是基于机 器学习的大范围检索系统；另一类是智能化的用户个性化信息检索系 统。对于第一类系统，主要着眼于智能性的体现，以复杂的推理和规 划来构造检索信息，如文献f 2 1j 提出的s a v v y s e a r c h 系统是一个基于经 验举玛的中介搜索骶统，它貔稷据耀户提供豹术语鞠反馈，建立中介 索弓| ，分辑时阍秘经验因索，劳怼扶搜索霉l 肇褥瓢骢结果遴撑饯纯， 扶_ i i 孬发糯用户嶷落鬻要的嵇息。 稳裔许多科学家对第二类搜索萼| 攀技术进行了大爨研究，主要将 入正智戆技术麴个分支一a g e n t 技术孳l 入搜索弓l 擎鬈绫，以建立一秘 全分裔戏的、餐熬的、个性他的稔索系统。 文献【2 6 1 介缁了种个淫他的查谗系统a m a t h a e a ，窍套主她双分布 资源上拽出满足用户兴趣的信息并以擒嫠的形式提交绘用户。它通过 捡纛魄艟热赢剜袭稻测黧器掇史记聚来获得戳u n i v e r s a lr e s o u r c e l o c a t i o ns t r i n g s ( u r l s ) 熬关键潺瓣形式，爨忿壹接茨续藩褥熊惩户浆兴 趣，接鬻系统酝主收集相当的文档和u r l s 。它在三个领域并行的收集 数撰： l 。w w w 文档强数撼发联：它雾苓蹩纛搂援索w w w 零蹙藤蹩遴 避发送多个a g e n t 聚搜索w w w ，每个a g e n t 使用已存的索萼i 引攀来 完成一个“m e t a s e a r c h ”。攘饕系统使藤投壤关键调彝爨技本采分揍硷 索掰的文档以选取留用户兴趣襁荚的文档。 2 + 持续酌傣怠环境和僚怠遮滤流；多个a g e n t 辩文裆进行分析和 选取舍邋的文楼。 3 。瓣绩怠资源改变的羧测；蠢辩鼹户爨要瓣攘黩或夔撬簧耨驰 u r l s 进行监控，著u r l s 上的文档樗戮爨新将告翔霜户。 磋这个系统孛，a g e n t 剃趱基簿懿羧索辱 擎，褒零缝建立一个定铡 瀑。信患豹定涮不爨祭中农搜索零l 擎滕瓤熄分教在熙户屡。褒这累它 仍爨铡糯程有鹣搜索孳| 攀搜索傣惠，必避在髂塞圈采之嚣荐溺a g e n t 对信息避撑处理以逸鞭最满足用户需求的傣息。缎在这个系统中，由 手援索辩仍使掰静怒已有静援索孳| 擎仍花法献根本上鳃决搜索雩| 攀精 确救不建鹣弱纛，璐熬会毒震大爨豹鬻终资深+ 文献1 2 7 1 提出了一种多a g e n t 系统m a c r o n ( m u l t i a g e n t a r c h i t e c t u r ef o fc o o p e r a t i v er e t r i e v a lo n l i n e ) ，它鏊予c i ；3 ( c o o p e r a t i v e l 拄f o r m a t i o ng a t h e r i n g ) 模裟，爝一令鬃孛戆矮翻器泉爱戒凌多个程置 合干笨的a g e n t 宪减豹予目标，它使用k q m l ( k n o w l e d g eq u e r ya n d m a n i p u l a t i o nl a n g u a g e ) 瞩哪避褰来遴裙逶傣鞠耱囊。焱这令系绞中， 使用多个食作蠹奄a g e n t 乘完成镬这个嫂划过程中的翳标瓤予目标。 6 这个系统在某种程度上克服了死锁问题，在有限代价内获得最好的 搜索质量。通过合作能加强在有限资源检索的有效性。这个系统的缺 点是它没有完全利用针对任务的知识密集方法的潜力或分布处理的潜 力，没有充分利用a g e n t 在不同信息收集任务时的独立性。 其它的系统如s i m s 和a r i a d n e ，前者主要着眼于对各种不同的信 息资源的检索和融合，后者主要处理松散构造的网络资源的访问，其 推理能力不强。 综上所述，随着i n t e r n e t 的迅速发展和网络信息的迅速膨胀，传统 的检索系统已不能满足用户的要求，人工智能技术尤其是a g e n t 技术 的发展，为检索系统的发展开辟了一条道路，智能化、个性化的检索 系统是今后发展的必然， 1 2 课题来源 论文结合教育部基金重点项目“基于多智能体分布式控制研究” ( 项目编号：0 0 0 7 1 ) 和安徽省自然科学基金资助项目“基于m a s 的分布式控制系统中协调策略研究”( 项目编号：0 0 0 4 3 2 3 5 ) ，针对当 前信息检索的信息过载问题，引入a g e n t 技术，并研究了基于a g e n t 的信息检索系统中的许多问题。 1 3 研究的目的和意义 随着i n t e r n e t 的发展，网上的信息量越来越大，人们从浩瀚的信息 资源中找出自己所需要的内容相当困难。现有的检索系统虽然能替用 户找到许多相关的信息，但同时，它有着自身难以克服的弱点： ( 1 ) 所有这些搜索引擎大多是基于关键词的搜索，搜索引擎将所 有与关键词相关但不一定与主题相关的站点列出，用户再从大量的这 些站点中手工过滤选取信息，工作量很大； ( 2 ) 现在的信息服务系统都是基于客户服务器结构，在信息搜 索时，将网页内容下载到本地再进行索引处理，对网络有效带宽依靠 强； ( 3 ) 现有的信息数据库系统更新速度不快，网络中站点内容、网 页的变化是经常的，使用现有的搜索引擎难以保证结果的实效性； ( 4 ) 搜索的覆盖面有限：各个搜索引擎所保存的信息量有限。 在网络日益发展的今天，急需一种新的检索系统来取代原有的传 统的系统，提供给用户更精确的、更完备的、更个性化的服务。 1 4 论文的组织 本文以理论和实践相结合作为出发点，对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 鼓零楚妥兹诗舞撬辩学领域孛一令嚣鬻重要豹、滋跃豹研究 方向之一，i 葭年来弓l 超计算枧科学界的广泛关注。它不仅代表人们从 认知的角度对计算机世界的认识上升到一个新的高度，而盥也体现了 一种全叛的软件开发模式。w o o l d r i d g e 和j e n n i n g s 称之为“软件开发 懿大突酸”。 2 1 a g e n t 技术的由来 a g e n t 技术是分布式久工管熊发展鲍一个夔要分支。人工智黢 ( a r t i f i c i a li n t e l l i g e n c e ) 叉称为机器智能( m a c h i n ei n t e l i i g e n c e ) 是计算 机科学中一门新兴的边缘学科。它幽j m c c a r t h y 、m l m i n s k y 等十多 袋数学、办壤学窝售惠论等方覆戆留尝在美毽d a r t m o u t h 大学举簿了 历时两月乏久的有关如何利用计算机在数学、物理学、心理学和电子 工程学等方灏模拟人类错能行为的学术研讨会上提出，它标志着人工 罄能这门瓤兴豹边缘学科的正式诞擞。 人工智能的发展经历四个阶段f 5 l ： 第一阶段是1 9 5 6 年以前，是人工智能的孕育期。在这阶段，由 予毫子器抟豹王艺葶赣黟换钱，麸魄子警、鑫髂警、集成电路裂大援 模集成电路簿四代到藤在发展的第蕊代，使现代电子数字计算视踏上 了高速发展的道路。最早给人工智能奠定理论基础的是天才的英国数 学家a t u r i n g 。它于1 9 3 7 年发表了篇关于“可计算数学”的文章， 键密了“逶髑匿灵瓠”懿壤念，这个模鏊摇述了惹来密凌懿诗冀掇系 统。 第二阶段是从1 9 5 6 罐到1 9 7 0 铝，此时是人工智能基础理论和技术 瓣形藏簿麓。1 9 5 6 年盔美餮遮特茅簸露齐豹会谈标志羞久王智戆季 突 的正式开始，在这期间童要的开创性的工作怒试图实现机器翻译。在 这期间，纽聪尔和西蒙凝1 9 5 6 年合作研制了“逻辑理论机l t ( t h el o g i c t h e o r ym a e h i n e ) ；1 9 5 6 簪另一项重大豹牙创性王俸是塞缪尔研究豹“跳 棋程序”，接着纽厄尔帮西蒙于t 9 6 0 年又编翻成功“逶瘸滴遂求解稷 序g p s ( g e n e r a lp r o b l e ms o l v i n g ) 系统”。1 9 6 0 年麦卡锡研制 j j “表处 理语言l i s p ”，成为人二i ：智能程序设计语言的熬要里程碑。 9 第三阶段从1 9 7 1 年到1 9 8 0 年，此时期人工智能得到了较大发展并 开始应用于实践生活。7 0 年代人工智能研究者利用过去的成果，提出 了各种新的知识表示技术，搜索技术日趋成熟，其中最引人注目的是 专家系统的出现，如1 9 6 5 年斯坦福大学计算机科学系的人工智能鼻祖 费根鲍姆( e a f e i g e n b a u m ) 和化学家c o j e r a s s i 及jl e b e r b e r g 等人 研制出世界上第一个专家系统d e n d r a l ，其它的专家系统还包括由 麻省理工学院的c e n g l e m a n ，w m a r t i n 和j m o s e s 研制的数学专家系统 m a c s y m a 、绍特夫( e h s h o r t l i f f e ) 等人研制的医疗专家m y c i n 系 统。人工智能工作者经过1 0 多年的研究，发现了最有发展和应用前景 的三个子领域：专家系统、计算机视觉和机器人、自然语言理解机和 机器翻译。最具代表性的系统有语言理解系统h e a r s a y 它由卡内基 一梅隆大学的l “d e r m a n 等人设计，1 9 7 3 年完成h e a r s a y 1 ，1 9 7 7 年完成h e a r s a y i i ；1 9 6 0 年美国生产了第一批商用工业机器人 u n i m a t e 和v e r s a t r a n ，1 9 6 8 年q u i l i i a n 提出了语义网络知识表示 法，1 9 6 5 年r o b i n s o n 提出了归结原理，此后柯瓦斯基( r k o w a l s k i ) 首先提出了以逻辑为基础的程序设计语言p r o l o g ( p r 0 9 r a m m i n g i n l o g i c l 的思想，并于1 9 7 2 年由科麦瑞尔( a c o l m e r a u e r ) 及其研究小 组在法国马赛大学实现了世界上第一个p r o l o g 系统。 第四阶段是1 9 8 0 年到至今，以知识工程和专家系统为标志，是人 工智能发展的黄金阶段并取得了重大的成果，特别是当前人工智能的 三个主要研究领域：自然语言处理，计算机视觉和机器人学以及知识 工程得到了迅速的发展。 分布式人工智能d a i ( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ) 是7 0 年 代后发展起来的一个重要分支。d a i 系统一股由多个智能体a g e n t 组 成，每一个a g e n t 又是一个半自治系统，a g e n t 之间及a g e n t 与环境之 间进行并发活动，并进行交互来完成问题求解。d a i 主要研究体现在 多系统中的知识与行为，更确切地说，d a i 主要研究在合作或竞争的 环境下如何协调多智能系统的行为，其主要目的是为了有效利用资源， 控制智能系统的异步操作，均衡智能系统的目标，目前d a i 研究的主 要问题有：任务的描述、分解和分布、通信、交互语言和协议、a g e n t 间的协作、a g e n t 间的协调、冲突消解和实现的语言、框架和环境等。 2 2a g e n t 鹃基本概念 2 2 。1a g e n t 瓣定义 a g e n t 怒近年来计算机科学领域中的一个熏要概念，已被广泛应用 予a i 、分布式计算等计算机科学领域。a i 和d 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 并不等同 予专家系绕秘大多数浚箱谖菇基夏窭瓣凌建系绞。 关于a g e n t 的定义目前还没有一个统一的概念定义。研究人员从 不周的角度来给a g e n t 定义，常见的生要观点奢： 1 f r a n k l i n 轻g r a e s s e r 辩a g e n t 靛定义 4 4 l 是“a g e n t 是一个处于环凌 之中并且作为这个环境一部分的系统，它随时可以感测环境并且执 行相应的动作，同时逐渐建立妇熙的活动规划以应付未来可能预测 窭熬环境变纯”。 2 最经典和广为接受的是w o o l d r i d g e 等人的“弱定义”和“强定义” 1 2 4 1 ：弱定义a g e n t 指具有自主性、社会性、反应性和能动性等基本 特鳇魏a g e n t ：强定义是撂a g e n t 不仅具鸯弱定义孛豹鏊本特性， 而且还矮有移动性、通信能力、骥性或其它特性。 3 a g e n t 的先驱者之一，美国的m a e s 4 5 1 认为“自治或自主a g e n t 燕 指那些察毫子复杂动态环境孛，蠢治遗感翔秘壤售怠，鑫主采取季亍 动，并实现一系列预先设定的嚣檬或任务的计算系统”。 4 s h o h a m 对a g e n t 的定义5 1 是“如果一个突体的状态可被视为包含 7 诸妇熟识、痿念、承诺窝藐力簿糖季枣状态辩，该实薅藏楚簪戆体”。 在综合了多种定义后，在a i 领域，人们一般将a g e n t 视作驻留和 流动在环境中的一个突体，可以在特定环境下感知环境，解释“感知” 戮蠡冬反骧臻缱及其自身露l 其它实体瓣状态，并熊自主她逡行数代表冀 设计者或使掰者实现一系列舀标的软件或硬俘瓣实体2 “2 5 1 国际上有关a g e n t 的研究主要w 以分为两个时期4 6 ( 1 ) 从1 9 7 7 年1 9 9 0 年，主要集中于智能a g e n t ( s m a r ta g e n t ) 。 1 9 9 5 年w o o l d r i d g e 总结了此类慎思a g e n t ( d e l i b e r a t i v e - a g e n t ) ：具有 明确的可描述、形式化模型且决策可以通过借助于形式化推理可以决 定的a g e n t 。此阶段主要集中于像a g e n t 之间的交互和通信、任务的分 解和分布、协调和协同、通过谈判解决冲突等焦点问题。目标是确定、 分析、设计和综合有多个协作a g e n t 组成的系统。 ( 2 ) 从1 9 9 0 年以来，有关a g e n t 的研究和应用更广泛，并出现一系 列达到实用的系统。如s y c a r a 在c m u 中的旅游者接待系统：任务具 体a g e n t 和信息具体a g e n t 相互协作以产生每一个旅游者的日程安排 表。 2 2 2a g e n t 的属性 有关a g e n t 的属性，学术界也是各抒己见，b t 实验室给了一个最 小的集合：自主、学习和协同性。自主性是a g e n t 的最基本的属性， 自主性是指a g e n t 在没有人的指导下自主工作，a g e n t 有能力采取主动 行为而不是简单地对它周围的环境被动的反应【2 “。协同性是最重要的， 是m a s 存在的目的和基础，为了能相互协同，a g e n t 必须具有一定社 会能力，通过a g e n t s 间的相互协调来完成由单个a g e n t 所不能完成的 任务。而学习性是体现a g e n t 智能的最关键的属性，作为一个智能实 体，它能从经验中学习和提高自身的能力。除此之外，a g e n t 还有其它 一些属性3 0 】1 3 1 1 1 3 2 】，如： 诚实性：a g e n t 不会欺骗使用者： 主动性：a g e n t s 并不是简单地被动地针对周围环境和其它a g e n t 的信息做出反应，而是主动的交互； 通信能力：a g e n t s 间通过某种通信语言相互交换各种信息，是 a g e n t s 协同和学习的基础； 移动性：a g e n t s 应具有在网络中自主移动的能力，且自身状态保 持不变： 推理能力：a g e n t s 能根据以前所积累的知识、当前环境和其它 a g e n t s 的状态以理性的方式进行推理和预测； 此外，还有其它些属性如规划性、保守性、乐于助人性、自私 缝簿。 2 3a 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 ( m o b i l ea g e n t ) ；掰 由a g e n t 的三大燕要属性 论同 学习盘 鹰2 - l ：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 ，l 4 6 1 ： 若按角色分又霹分为傣患a g e n t 耧掰络a g e n t 等，缩合多j 盼属性 又冒分必漾合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 静主要满性。h u h n s 瘦s i n g h 辫接游 网a g e n t 系统的假设、理论翻露栎是d a l 中照拣的细分化。也 可擀释为“创造一个糨互之瀚交羹豁痨阍a g e n t 系统，以使系 统总镕熬瞧能蠢予经秘一个艘爨a g e n t 豹瞧毵”，鞠 v ( 一a g # n t i ) m a x ( v ( a g o n t i ) ) 。 反应a g e n t 蹙一种没肖环境魏肉帮、形式纯模爨的特殊a g e n t ， 它们镑避聚姓魏繇壤瓣姿 l 蓼姨淼露蹬菠痰。爨晕疆究菠蔽 a g e n t 的建b r o o k s ( 1 9 8 6 ) 和a g r e & c h a p m a n ( 1 9 8 7 ) t 信感a g e n t 怒蔻适藏靖踅增长的躐络信惑资源丽产垒酌e 镑惠 a g e n t 熬囊簧麓戆是绥塞滚熬管壤、搡侈、过滤霸馈惑戆较瓣。 信息a g e n t 它可以同时具备多种特性，它们w 能魁静止的或移 动瓣；萄以蹙没舂协馋豹戏其程毂会瞧：霹熊爨露学嚣。陡绒没 露嚣等，雌没夜一个傣患a g e n t 王体的绕轹准，债息a g e n t 鹣划分必是缀搬它绣握强熬经努熬特性褥禽名熬。 界面a g e n t 濑调的蹩自主性和学习髋。京遴过溉察和模拟糟户 ( 学辫爱户，接受翔户嚣定藏磷定鹣反馈( 学习髑户) ，接受翔 声明确豹掺零( q e 习用声) ，谗婀其定a g e n t s 麴建议学习同等 缀的a g e n t ) 。p a t t i em a e s 指出隐藏在器霹a g e n tt 的关镳隐 喻悬可以在相同的工作环境中与用户协作的个人助理。 混合a g e n t 缝合了多种a g e n t 羽优焘，它比组成它的任a g e n t 的熊力郝强。如m a e s ( 1 9 9 l b ) 吸收了恩考型帮反成型a g e n t 的优点。 移动a g e n t 强调它盼移动瞧，警然谨氆可以进行学习和协辩。 移动a g e n t w 以在阏络中漫游，可戳与其它宿主交莲、借髓宿 主可以搜索信息和当它究成搜索任务时按用户的要求返回。如 遴常翁定票系绞中霹戮傻弱移镄a g e n t 寒预定撬鬃，警它找到 满足簧求靛撬鬃瑟，宅衾遮爨势告瓣爨户豹徐疆积路线，鬣按 煺户豹簧隶羰是一张捉蘩。峦予移动a g e n t 与零澡越熬紧鬻稳 关，下面将分一小节来详细介缁移动a g e n t 。 2 4 移动a g e n t 2 ，4 1 移动a g e n t 魏蕊本理论 “移溯a g e n t ”囊鼋概念跫由9 0 零 弋褪熬g e n e r a lm a g i c 公镯在囊蝮 累统t e l e s c r i p t 中提出的，用来熏持在编程语畜级的可移动性。移动可 以在网络主机中移动，透过计冀枕嘲络，移动a g e n t 可携常囊身状态 釉代码跌一个环境移动劐瑟一个环骥中，并傻复执行。榱据英特镶， 对移动a g e n t 的定义 4 7 1 是：移动a g e n t 是一个独立运行的计算机稷序， 窀搿垂妻趣凌辩构躺弼络上按照一霆靛趣稳移旗，寻找会逡熬诗爨资 源、痿惑瓷源袋软移褒源，零l 臻与遮臻资源处予掰一圭规藏阏终鹣优 势，裁避处理袋使髑这然瓷源，鼗袭用户完成姆定的任务。 移魂a g e n t 是数攥、代鹞驭教执行语境黝软 孛包。移动a g e n t 麴遥 移分灸“髅逶移”鞠“骚逐移”l ”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 的移动意味着执行代码和运动状态的移动，而移动 a g e n t 的恢复则意味着移动a g e n t 状