（计算机科学与技术专业论文）基于agent的多移动用户资源冲突协调技术研究.pdf

b a s e do nt h ea g e n to fm o b i l eu s e r sm o r er e s o u r c ec o n f l i c t - - 一一 c o o r d i n a t i o nt e c h n o l o g yr e s e a r c h at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o rt h e d e g r e eo f m a s t e ro f e n g i n e e r i n g z h a n ga n n a ( c o m p u t e r s c i e n c ea n d t e c h n o l o g y ) t h e s i ss u p e r v i s o r ：a s s o c i a t ep r o f e s s o r l i nz h e n g k u i j u n e2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 基王g 型的垒整麴题应童逦、冲塞迹迥这莶受宜：。除 论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已 经公开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：三幽f 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密口( 请在以上方框内打“) 敝储繇獭p 导师躲栉硷 日期：凶7 7 年7 月日 中文摘要 摘要 随着改革开放的日益深入和交通、电信等相关产业的快速发展，在全球化迅 猛发展的今天，商务和休闲旅游等跨区域移动外出活动日益频繁，仅以旅游为例， 2 0 1 0 年我国境内旅游人数就高达2 l 亿人次。移动用户在开展跨区域活动中，通常 首先基于自身的行动目标独立制定行动方案( 计划) ，然后基于行动方案( 计划) 开展相应活动，如按行程计划参观多个旅游景点，按走访计划拜访多个不同客户， 按面试计划参加多个面试活动等等，受到特定服务提供商( 旅游景点、客户、面 试单位等) 服务能力( 时间安排，接待人数等) 的有限性、移动用户自身活动目 标的多样性( 时间、费用等) 、移动用户及服务提供商之间服务信息的不对称性 和行动计划执行过程中环境因素变化( 天气、交通等) 的影响，随着移动外出活 动及规模的日益扩大，由于移动用户之间存在资源需求冲突( 竞争) 问题而导致 行动计划无法正常执行或更好执行的现象日益普遍，并已引起了社会各界的广泛 关注。 本文重点围绕移动用户资源冲突协调问题开展了相关研究。首先论文将移动 用户资源冲突问题转化为移动用户行动计划协调问题( m o b i l eu s e ra c t i v i t y s c h e d u l e sc o o r d i n a t i o np r o b l e m ，m u s p ) ，同时基于对m u s p 问题域特征的实证分 析，进一步将其定义为多准则语境相关的分布式约束优化问题；在对多准则语境 相关的分布式约束优化问题国内外研究情况进行汇总、分析的基础之上，针对该 问题域内移动用户、服务提供商的特点和目标约束提出了m u s p 问题的通用形式 化描述模型，同时结合对该问题的形式化描述模型求解问题提出了移动通讯环境 下基于a g e n t 的多移动用户资源冲突协调技术；最后以移动用户面试预约问题为 例对论文的研究成果进行了实验验证。实验表明，论文所提出的基于a g e n t 的多 移动用户资源冲突协调技术能有效改善移动用户的行动效能，提高其计划执行满 意度，同时有助于各类服务资源的有效利用。 实践证明，在移动用户开展各类跨区域活动过程中，资源冲突问题是普遍存 在的现实问题，同时也是一类复杂问题和极具挑战性的研究工作，具有重要的理 中文摘要 论研究价值和现实意义。由于研究时间和自身水平有限，论文的研究工作尚缺乏 深度，且存在很多不足之处，作者将在后续的研究过程中加以持续改进。 关键词：移动用户：资源冲突与协调；智能体a g e n t ；分布式约束优化 英文摘要 a b s t r a c t w i t ht h ep o p u l a r i z a t i o no fr e f o r ma n do p e n i n gu pa n dt h er a p i dd e v e l o p m e n to f t r a n s p o r t ，t e l e c o m m u n i c a t i o n sa n do t h e rr e l a t e di n d u s t r i e s ，i nt o d a yw i t ht h er a p i d d e v e l o p m e n to fg l o b a l i z a t i o n ，t h ea c t i v i t yo fm o v i n go u ta c r o s st h er e g i o n , f o r e x a m p l eb u s i n e s s ，l e i s u r et o u r i s ma n ds oo n ，h a v eb e c o m ei n c r e a s i n g l yf r e q u e n t ，o n l y t o u r i s ma sa ne x a m p l e ，i n2 010c h i n a sd o m e s t i ct o u r i s mn u m b e ro fp e o p l eu pt o21 m i l l i o np a s s e n g e r s m o b i l eu s e r si nc a r r y i n go u tc r o s s r e g i o n a la c t i v i t i e s ，u s u a l l yt h e f i r s tt a r g e to fa c t i o nb a s e do ni t so w n i n d e p e n d e n td e v e l o p m e n to fa c t i o np l a n s ( p l a n s ) ， a n da c t i o n - b a s e dp r o g r a m ( p l a n ) t oc a r r yo u tc o r r e s p o n d i n ga c t i v i t i e s ，s u c ha sb yt r a v e l p l a n st ov i s i ts e v e r a lt o u r i s ta t t r a c t i o n s ，v i s i t e db ym o r ev i s i t sp l a n n e dd i f f e r e n t c u s t o m e r s ，p l a n st oa t t e n dm o r et h a no n e i n t e r v i e wb yt h ei n t e r v i e wa c t i v i t i e s ，e t c ，a r e s u b j e c tt os p e c i f i cs e r v i c ep r o v i d e r s ( t o u r i s ta t t r a c t i o n s ，t h ec u s t o m e r , t h ei n t e r v i e w u n i t ，e t c ) s e r v i c ec a p a b i l i t i e s ( s c h e d u l e ，n u m b e ro fr e c e p t i o n ，e t c ) t h el i m i t e dn a t u r e o ft h em o b i l eu s e r so w n a c t i v i t yt a r g e t sd i v e r s i t y ( t i m e , c o s t ，e t c ) ，m o b i l eu s e r sa n d s e r v i c ep r o v i d e r so fi n f o r m a t i o na s y m m e t r yb e t w e e nt h es e r v i c ea n da c t i o np l a n i m p l e m e n t a t i o np r o c e s sc h a n g e si ne n v i r o n m e n t a lf a c t o r s ( w e a t h e r , t r a f f i c ，e t c ) ，w i l l m o v eo u tw i t ht h ei n c r e a s i n gs c a l eo fa c t i v i t i e sa n de x p a n s i o n ，d u et or e s o u r c e r e q u i r e m e n t sb e t w e e nm o b i l eu s e rc o n f l i c t ( c o m p e t i t i o n ) p r o b l e mw h i c hl e dt o t h e i m p l e m e n t a t i o no fa c t i o np l a no rb e t t e rc a nn o tb ep r o p e r l yp e r f o r m e di n c r e a s i n g l y c o m m o np h e n o m e n o na n dh a sa r o u s e dw i d e s p r e a dc o n c e r n t h i sa r t i c l ef o c u s e so nr e s o u r c ec o n f l i c t sa r o u n dt h em o b i l eu s e rc o o r d i n a t i o nw a s c a r d e do u tb yr e s e a r c h t h ef i r s tp a p e rw i l lb em o b i l eu s e r s ，t h er e s o u r c ec o n f l i c ti n t o a c t i o np l a n sf o r t h em o b i l eu s e rc o o r d i n a t i o n ( m o b i l eu s e ra c t i v i t ys c h e d u l e s c o o r d i n a t i o np r o b l e m ，m u s p ) ，a l s ob a s e do nt h em u s pp r o b l e md o m a i n c h a r a c t e r i s t i c so fe m p i r i c a la n a l y s i s ，f u r t h e rd e f i n e da st h ed i s t r i b u t i o no fm u l t i - c r i t e r i a c o n t e x tr e l a t e dc o n s t r a i n t o p t i m i z a t i o np r o b l e m ；i nt h e c o n t e x to fm u l t i c r i t e r i a o p t i m i z a t i o np r o b l e m sr e l a t e dt od i s t r i b u t e dc o n s t r a i n ta th o m ea n da b r o a dt oc o n d u c t r e s e a r c hs u m m a r y , a n a l y s i so ft h eb a s i so ft h ep r o b l e md o m a i nf o rm o b i l eu s e r s ，s e r v i c e p r o v i d e r st a r g e tb i n d i n gc h a r a c t e r i s t i c sa n di s s u e sr a i s e dm u s pf o r m a ld e s c r i p t i o no f t h eg e n e r a lm o d e l ，c o m b i n e d 、) i r i t l lt h ef o r m a ld e s c r i p t i o no ft h ep r o b l e ms o l v i n gm o d e l ， p u tf o r w a r dam o b i l ec o m m u n i c a t i o ne n v i r o n m e n t ，m o b i l ea g e n t - b a s e dm u l t i - u s e r 英文摘要 c o o r d i n a t i o no ft e c h n i c a lr e s o u r c ec o n f l i c t s ；f i n a li n t e r v i e wa p p o i n t m e n tt om o b i l eu s e r s 嬲a ne x a m p l eo fr e s e a r c hp a p e rf o re x p e r i m e n t a lv e r i f i c a t i o n e x p e r i m e n t ss h o wt h a t ， t h ep a p e rp r o p o s e da g e n t - b a s e dm u l t i - u s e rr e s o u r c ec o n f l i c t sm o b i l et e c h n o l o g yc a l l e f f e c t i v e l yi m p r o v et h ec o o r d i n a t i o no ft h eo p e r a t i o n a le f f e c t i v e n e s so fm o b i l eu s e r s ，t o i m p r o v et h e i ri m p l e m e n t a t i o no ft h ep l a ns a t i s f a c t i o n ，w h i l eh e l p i n g a l lk i n d so f s e r v i c e se f f e c t i v eu s eo fr e s o u r c e s p r a c t i c eh a sp r o v e dt h a tt h em o b i l eu s e rt oc a r r yo u tv a r i o u st y p e so fc r o s s - r e g i o n a l a c t i v i t i e s ，t h er e s o u r c ec o n f l i c t i sac o m m o nr e a l i t y , b u ta l s oac l a s so fc o m p l e x p r o b l e m sa n dc h a l l e n g i n gr e s e a r c hw o r k ， r e s e a r c hh a si m p o r t a n tt h e o r e t i c a la n d p r a c t i c a ls i g n i f i c a n c e a st h es t u d yo ft i m ea n ds e l f - l i m i t e d ，r e s e a r c hw o r k i n gp a p e r i s s t i l lal a c ko fd e p t h ，a n dt h e r e a r em a n ys h o r t c o m i n g s ，t h ea u t h o rw i l lf o l l o w u p 1 2 论文工作1 1 2 1 研究内容1 1 2 2 技术路线2 1 3 论文的组织结构3 1 4 本章小结3 第2 章相关问题研究综述4 2 1 无线移动通讯技术4 2 2 情境感知技术5 2 3 多智能体( m u l t i a g e n t ) 技术6 2 3 1 多智能体系统一6 2 3 2 基于a g e n t 的冲突协调机制研究7 2 4 多准则优化问题研究9 2 5 分布式约束优化问题研究12 2 5 1 约束满足问题1 2 2 5 2 分布式约束满足问题1 4 2 5 3 分布式约束优化问题16 2 6 代表性组合优化问题研究18 2 6 1 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m - t s p ) 19 2 6 2 加工调度问题( s c h e d u l i n gp r o b l e m ) 2 0 2 7 本章小结21 第3 章实证分析与问题建模2 2 3 1 移动用户资源冲突与协调问题实证分析2 2 3 1 1 情境描述2 2 3 1 2 移动用户独立制定行动计划2 2 3 1 3 合作制定面试计划2 6 3 1 4 问题的提出2 8 3 2 问题建模2 9 3 2 1d c o p 问题通用模型概述3 0 目录 。 3 2 2m u s p 问题建模3 l 3 3 本章小结3 4 第4 章分布式多a g e n t 动态协作网络与协商机制设计3 5 4 1m u s p 问题域特征3 5 4 2 分布式多a g e n t 动态协作网络与协商机制设计3 5 4 2 1 技术方案概述3 5 4 2 1 分布式移动a g e n t 动态协作网络3 6 4 2 2 动态协商机制设计4 1 4 3 本章小结4 4 第5 章仿真实验4 5 5 1 实验参数设计4 5 5 2 实验方案设计4 7 5 2 1 实验方案1 4 8 5 2 2 实验方案2 ：4 8 5 3 实验结果分析4 8 5 4 本章小结5 2 第6 章结论与展望5 3 参考文献一5 5 致谢5 8 基于a g e n t 的多移动用户资源冲突协调技术研究 第1 章绪论 1 1 研究背景及意义 一方面，随着改革开放的日益深入和交通、电信等相关产业的快速发展，在全球化 迅猛发展的今天，商务和休闲旅游等跨区域移动外出活动日益频繁，仅以旅游为例，2 0 1 0 年我国境内旅游人数就高达2 1 亿人次。移动用户在开展跨区域活动中，通常首先基于 自身的行动目标独立制定行动方案( 计划) ，然后基于行动方案( 计划) 开展相应活动， 如按行程计划参观多个旅游景点，按走访计划拜访多个不同客户，按面试计划参加多个 面试活动等等，受到特定服务提供商( 旅游景点、客户、面试单位等) 服务能力( 时间 安排，接待人数等) 的有限性、移动用户自身活动目标的多样性( 时间、费用等) 、移 动用户及服务提供商之间服务信息的不对称性和多重偶然性，以及行动计划执行过程中 环境因素变化( 天气、交通等) 的影响，随着移动外出活动规模的日益扩大和频繁，由 于移动用户之间存在资源需求冲突( 竞争) 问题而导致预设行动计划无法正常执行或更 好执行的现象日益普遍，并已引起了社会各界的广泛关注。 另一方面，近年来随着无线通讯技术n 卅的快速发展，尤其是无线网络和以智能手机、 笔记本电脑、平板电脑等为代表的支持无线通讯功能的各类便携式移动终端设备的快速 普及，使得在新一代移动环境睁力中，移动用户可以更加方便的借助智能移动终端设备感 知环境及相关信息资源变化，并据此制定、管理和分享个人行动计划，进而为解决移动 用户资源冲突问题提供了更有力的技术支撑条件。 基于上述背景，该类问题具有普遍性和计算复杂性特征，因此结合新一代无线通讯 技术和泛在网络计算环境，探索研究具有普遍性的多移动用户资源冲突协调问题，对于 提高移动用户的行动效能和服务资源的最大化利用具有重要现实意义和理论研究价值。 1 2 论文工作 1 2 1 研究内容 本文将移动用户资源冲突问题定义为“多准则语境相关的分布式约束优化问题 ， 重点研究其形式化问题建模和泛在网络环境下基于a g e n t 的问题求解机制，主要研究内 第1 章绪论 容包括： ( 1 ) 移动用户行动计划冲突协调问题实证分析； ( 2 ) 多准则语境相关的分布式多目标约束优化问题统一建模； ( 3 ) 分布式多a g e n t 动态协作网络与协商机制设计； ( 4 ) 原型系统构建与仿真实验验证。 1 2 2 技术路线 ( 1 ) 文献收集与整理 紧密跟踪国内外关于无线通讯技术、情境感知技术、多智能体技术，以及多准则优 化问题、分布式约束优化问题和代表性组合优化等相关技术领域的研究进展，开展文献 资料的收集与整理工作，为后续的研究提供理论基础。 ( 2 ) 关键技术研究 基于对多移动用户资源冲突与协调问题的实证分析，研究其形式化描述模型和求解 机制。 ( 3 ) 研究成果验证 以面试预约活动为背景对研究成果进行仿真实验验证。 技术路线如图1 1 所示。 l 查阅相关文献 彤 l 存在魏盆题与 相关技术及 相关问题研究 i 弋夕 移动用户行动 计划冲突协调 问题实证分析 l1 弋夕 相关建模统一j 图1 1 技术路线图 f i g 1 1t h n i cr o u t ec h a r t i 墚燃 商 基于a g e n t 的多移动用户资源冲突协调技术研究 1 3 论文的组织结构 本论文主要分为5 章，各章节安排如下： 第1 章绪论。本章主要介绍论文的研究背景及意义、研究内容以及技术路线，最 后对本文的组织结构进行说明。 第2 章相关问题研究综述。本章主要对本文用到的无线移动通讯技术、情境感知 技术和多智能体等相关技术以及多准则优化、分布式约束优化和代表性组合优化等相关 问题的研究进行了阐述。 第3 章问题描述与建模。本章主要对移动用户行动计划冲突协调问题进行实证分 析，之后对多准则语境相关的分布式约束优化问题统一建模。 第4 章分布式多a g e n t 动态协作网络与协商机制设计。本章主要介绍了泛在网络 环境下分布式多a g e n t 动态协作网络与协商机制的设计。 第5 章仿真实验。本章主要以面试预约活动为背景对研究成果进行仿真实验验证。 第6 章结论与展望对论文期间所做的工作进行总结，提出有待于进一步研究的相 关问题。 1 4 本章小结 本章主要介绍了论文的研究背景及意义、论文的研究内容、技术路线以及论文的组 织结构。 第2 章相关问题研究综述 第2 章相关问题研究综述 2 1 无线移动通讯技术 无线通信( w i r e l e s sc o m m u n i c a t i o n ) i s 9 】是利用电磁波信号可以在自由空间中传播的 特性进行信息交换的一种通信方式，是近些年信息通信领域中，发展最快、应用最广的 通信技术。在移动中实现的无线通信又通称为移动通信，人们把二者合称为无线移动通 信b o , l q 。从应用的角度出发，移动应用在物理上主要由无线通讯网络和移动计算终端构 成。其中，移动通讯网络利用无线通信技术可将各类移动计算终端设备连接起来，进而 构成可以互相通信、实现资源共享的信息网络，主要包括w i f i ( w l a n ) 1 1 2 1 、w i m a x 1 3 】 和3 g h 】；移动计算终端设备则可在移动环境下，利用移动通讯网络为移动用户提供无 线数据通讯、数据存储、数据访问和简单的数据计算功能，主要包括n o t e b o o k 、s m a r t p h o n e 、p e r s o n a ld i g i t a la s s i s t a n t ( p d a ) 和p o r t a b l em e d i ap l a y e r s ( p m p ) 、u l n a - m o b i l e p c ( u m p c ) 等便携式移动设备。 较之于有线网络通讯技术，无线网络通讯技术研究起步较晚，开始于上世纪7 0 年 代。在整个八十年代，伴随着以太局域网的迅猛发展，以具有不用架线、灵活性强等优 点的无线网络作为有线网络的补充逐渐得到了特定市场的认可，并于1 9 9 7 年6 月通过 了第一个国际无线局域网标准i e e e8 0 2 1 1 【1 2 】。 8 0 2 11 主要用于解决办公室局域网和校园网中用户与用户终端的无线接入，业务主 要限于数据存取，速率最高只能达到2 m b p s 。由于它在速率和传输距离上都不能满足人 们的需要，此后i e e e 小组又不断对这一标准进行补充和完善，形成了8 0 2 1 l x 标准系 列1 1 5 1 。8 0 2 1 1 x 标准是是w i f i ( w l a n ) 的技术基础，在无线局域网得到了广泛应用。 w i m a x ( w o r l d w i d ei n t e r o p e r a b i l i t yf o rm i c r o w a v ea c c e s s ) ，即全球微波互联接入，是 另一项新兴的宽带无线接入技术，也叫8 0 2 1 6 无线城域网或8 0 2 1 6 ，能提供面向互联网 的高速连接，数据传输距离最远可达5 0 k m ，同时具有q o s 保障、传输速率高、业务丰 富多样等优点。w i m a x 作为一项新兴技术，由于能够在比w i f i 更广阔的地域范围内 提供“最后一公里”宽带连接性，因此而得到了业界的广泛关注【1 3 】。 基于a g e n t 的多移动用户资源冲突协调技术研究 3 g ( 3 r d g e n e r a t i o n ) 是第三代移动通信技术( 网络) 的简称，它是指支持高速数据 1 1 传输的蜂窝移动通讯技术。3 g 服务能够同时传送声音( 通话) 及数据信息( 电子邮件、即 时通信等) ，代表特征是能提供高速的数据业斧1 4 】。目前国际电联确定的无线接口标准 主要包括美国的c d m a 2 0 0 0 、欧洲的w c d m a 和中国的t d s c d m a 。 近年来随着移动无线网络，尤其是3 g 网络的大范围部署，以各种支持移动通讯功 能的智能化便携式移动终端为载体的移动应用日益普及，据不完全统计，如今每天大约 有数万人成为新的无线用户，全球范围内的无线用户数量目前已经超过2 亿。不可否认， 无线技术正给人们带来深远影响。 2 2 情境感知技术 无线情境感知是普适计算中最重要的特征，也是关键研究领域。情境也被称为上下 文，情境定义了所有能够判断一个对象状态的一切信息。如果一个系统能够通过收集、 解释并利用情境信息来提供服务，则称它是情境感知的【临1 9 1 。近年来，随着无线移动通 讯技术的发展，无线情境感知技术和服务需求快速增长，国内外大量学者围绕情境信息 获取、情境信息建模、情境系统内的数据管理、情境推理等方面共性科学问题开展了大 量的研究工作。 情境获取。情境可分为静态情境和动态情境。静态情境基本不会随时间或者地点而 改变，或改变很慢；动态情境会随时间或者地点不断变化。对静态情境，可以通过初始 化的交互获取以及后续的维护来进行管理；对于动态情境，要求系统能够实时监测，包 括数据采集、数据预处理和数据融三个细化部分。其中，传感器技术作为信号采集和测 量控制的手段，是情境感知系统对于动态情境的主要采集途径。传感器具有分布性、异 构性、多态性等特性，这使得情境的获取遇到了很大挑战。传感器的输入量是某种被测 量，可能是物理量，也可能是化学量、生物量等；它的输出量是某种物理量( 主要是电 量) ，在在数据预处理方面，部分学者围绕传感器输入与输出之间如何建立对应关系， 且能达到一定的精度开展了部分研究工作，包括样本过滤技术、规格化技术、数据平滑 技术等。在多传感器环境中，同一情境信息可能从多个渠道获取，从多个侧面以互相独 立或者互相协作的方式共同反映目标信息。多传感器增加了数据的可靠性和精确度，但 第2 章相关问题研究综述 也带来了信息冗余甚至矛盾，在实践应用中需要把所采集的信息依据某种优化准则组 合，产生对观测环境致性的解释和描述，即数据融合技术，目前所采用的传感器融合 技术主要包括竞争型融合、互补型融合、协作型融合三种。 情境建模。情境包含的信息多样并且范围极广，导致它们的表达方式与相互联系各 有所不同。如何用一种统一的抽象逻辑模型来描述情境，表达、推理和共享这些数量庞 大且形式异构的信息，是情境感知中一个非常关键的问题。目前情境建模技术主要包括 键值对模型、标记配置模型、面向对象模型、逻辑模型、图模型等【1 9 1 。 情境推理。尽管每一时刻情境感知系统都能从传感器网络中获得大量信息，但是这 些信息只是原始未加工的信息，是对环境某一属性在一个时间点上的描述。这些信息只 有加以重新组织和聚类，依据一定的规则进行推理，才可以得到高层情境，并据此做出 相应的系统响应。当前情境感知系统采用的推理技术主要包括逻辑推理、机器学习、统 计和证据理论、本体推理、基于事例的推理等【2 0 1 。 2 3 多智能体( m u i t i - a g e n t ) 技术 2 3 1 多智能体系统 多智能体系统是当今人工智能中的热门学科之一，是分布式人工智能的一个重要研 究分支，其目标是把大的复杂系统如软硬件系统建造成小的、彼此之间相互通讯及协调 并且易于管理的系统。多智能体的研究涉及多个方面，比如智能体的知识、目标、技能、 规划以及如何使智能体协调行动解决问题等。多智能体系统的应用研究开始于2 0 世纪 8 0 年代中期，近几年呈明显增长的趋势。 多智能体系统是指由多个可计算的智能体组成的集合，其中每个智能体都可以作为 一个物理的或抽象的实体，能作用于自身和周围环境，并且与其它智能体进行通讯【2 1 捌。 这些智能体之间通过相互协调、相互服务，共同完成一个任务，其自身的目标和行为不 受其它智能体的限制和影响，每个智能体都是独立自主的，可以通过竞争或者协调协作 的方式去解决成员之间的矛盾和冲突【2 2 1 。 多智能体技术在人工智能技术领域是一次质的飞跃：首先，通过智能体之间的通讯， 开发出了新的规划或求解方法处理不完全和不确定的知识：其次，通过智能体之间的协 基于a g e n t 的多移动用户资源冲突协调技术研究 作，在改善了每个智能体基本能力的同时可从智能体的交互中进一步理解社会行为；最 后，可以用模块化风格来组织系统【2 。 多智能技术具有以下特性： ( 1 ) 自治性( a u t o n o m o u s ) ：即它可以在不受外部直接干涉的条件下独立的完成操作。 每个a g e n t 根据自己的经验在某种程度上控制内部的状态和操作，a g e n t 的这种操作不 是简单的方法调用，而是通过感知外部的环境变化来自主地进行操作。 ( 2 ) 社会性( s o c i a la b i l i t y ) ：即通过具体的通信协议，每个a g e n t 都能与其它a g e n t 进 行交流和协作。 ( 3 ) 反应性( r e a c t i v i t y ) ：即当外部环境或其他a g e n t 发生变化时，能及时做出响应。 在更高程度上，a g e n t 可以根据自己的经验及时做出调整。 ( 4 ) 主动性( p r o a c t i v e n e s s ) ：即根据当前的环境和自身经验，a g e n t 能对所处的环境 及时响应，主动地执行某种操作或者任务【2 1 ，2 3 甜】。 采用多智能体系统求解实际应用问题，具有较高的求解效率。多智能体技术打破了 传统知识工程领域的限制，仅通过使用一个专家就可以完成比较大的复杂系统的作业任 务。例如在表达实际系统时，通过各智能体间的通讯、合作、互解、协调、调度、管理 及控制，可以很好的表达系统的结构、功能及行为特性等其他多个方面。由于在同一个 多智能体系统中各智能体可以异构，因此多智能体技术对于复杂系统具有无可比拟的表 达力，它为各种实际系统提供了一种统一的模型，从而为各种实际系统的研究提供了一 种统一的框架，其应用领域十分广阔【2 l 】。 2 3 2 基于a g e n t 的冲突协调机制研究 多a g e n t 系统( m a s ) 和分布式问题求解( d i s t r b u t e dp r o b l e ms o l v i n g ，d p s ) 两者之间既 有联系又有区别，它们是分布式人工智能( 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 ，d a i ) q b 的两 个不同研究领域。d p s 是指在一个全局问题下，各子系统分布在逻辑、物理上，给各个 系统划分特定的任务，最终通过协作完成全局任务。所以，在d p s 问题中，已经隐含地 假定了参与协作的各子系统之间存在着“共同的利益1 2 s - 2 7 】。而在m a s 问题中，a g e n t 是分散、独立和自主的，并且分别有自己的模型和标准。各a g e n t 之间通过相互通信、 第2 章相关问题研究综述 协作、协商以及协调，不但可以解决实际环境中各自遇到的问题，而且通过协同可以解 决独自不能解决的问题。可见，m a s 中的各a g e n t 既有自己的设计目标和特色，又是自 治的，同时又能相互协作共处【2 5 2 7 ，2 羽。 由于m a s l , d p s 更适合开放、动态的环境，更能体现人类社会智能，因而受到人们 的重视。目前，m a s 的研究主要分为a g e n t 认知模型、多a g e n t 规划、冲突消解、多a g e n t 协调与协作等几个方面，而多a g e n t 协调与协作是m a s 研究的核心问题【2 5 捌。 多a g e n t 协调( m u l t i a g e n tc o o r d i n a t i o n ) 是指具有不同目标的多个智能体对其目标、 资源等进行合理安排，调整各自的行为，最大程度地实现各自的目标，它是一种动态行 为，是a g e n t 对环境及其他a g e n t 的适应【2 5 矧。多a g e l l t 协作( m u l t i a g e n tc o o p e r a t i o n ) 是指 多个智能体通过协调各自的行为，合作完成共同目标。一般地，协作是在非对抗的a g e n t 之间进行的，协调是在相互对抗或冲突i 拘a g e n t 之间进行的，我们认为协作是一种特殊 类型的协调【2 5 】。 在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 l 拘动作间存在不一致时，可以调用它来解决。然而，这 种协调方法需要有足够的时间支持，在某些动态、实时环境下以及对时间有限制的条件 下不适合。隐式协调是指a g e n t 需遵循某局部的行为规则，以明显的协调方式行动【2 5 2 6 2 9 1 。 目前a g e n t 间的协调方法主要有四种，分别是基于集中规划的协调、基于协商的协 调、基于对策论的协调和基于社会规则的协调【2 5 2 6 ，2 9 1 。 ( 1 ) 基于集中规划的协调：此协调方法中，有一个主控a g e n t 具备全局知识，对全 局系统的目标和任务分别进行分解和规划，其他a g e n 按照相关指示或建议执行相关的任 务。此协调方法比较常用且易于实现，主要适合于环境和任务相对固定、动态行为集可 设计和集中监控的情况。 ( 2 ) 基于协商的协调：此协调方法属于对等协商式协调，当协商时，系统中没有 主控a g e n t y 时任务进行规划，各a g e n t j l n 过协商交换信息、讨论和达成一致。合同网协商、 基于a g e n t 的多移动用户资源冲突协调技术研究 基于对策论的协商和功能精确的协作都属于基于协商的协调。 ( 3 ) 基于对策论的协调：此协调方法包括无通信协调和有通信协调两类。无通信 协调是在没有通信的情况下，a g e n t 根据对方及自身的效益模型，按照对策论选择适当 的行为。在这种协调方式中，a g e n t 至多只能达到协调的平衡解。在基于对策论的有通 信协调中则可以得到协作解【3 0 1 。 ( 4 ) 基于社会规则的协调：在这种协调方法中，每个a g e n t 都必须遵循相应的社会 规则、过滤策略、标准和管理，并且这些规则对各个a g e n t 的行为都加以限制，过滤某 些有冲突的意图和行为，保证其他a g e n t 必须具有的行为方式能够顺利执行，从而实现 整个a g e n t 系统社会行为的协调。 2 4 多准则优化问题研究 多准则优化问题( m u l t i c r i t e r i ao p t i m i z a t i o np r o b l e m ，m c o p ) 也称作多目标优化问 题( m u l t i p l eo b j e c t i v e so p t i m i z a t i o np r o b l e m ，m o o p ) ，与单目标优化问题求解不同，多目 标优化问题旨在寻求一组满足多目标约束的帕累托最优( p a r e t o o p t i m a l ) 方案，而不是 寻求单一的全局最优解【3 1 。3 1 。帕累托最优( p a r e t oo p t i m a l