（计算机应用技术专业论文）基于学习和推测计算的多agent协商机制研究.pdf

北京交通大学博士学位论文 摘要 多a g e n t 协商是分布式人工智能的主要研究领域之一，在电子商务中有重要 的应用。随着i n t e r n c t 的不断发展和成熟，企业的电子化、虚拟化的趋势不断加 强，尤其是网上电子交易更加引人注意。为能充分利用i n t e m e t 的网络资源优势， 电子交易领域的问题也日渐突出，比如交易的精度低、效率低和交易者的智能性 不足等。分布式人工智能协商技术为这些问题的解决提供了条途径。协商是一 个动态复杂的过程，尤其是面对复杂的协商，解决上述问题不是一件易事。自从 z e n g 5 】提出基于b a y c s 学习的协商模型，并指出学习可以促进协商以来，协商 和机器学习结合起来成了新的研究热点，提高协商者在协商过程中的学习能力是 解决上述问题的有效途径。 本论文针对协商中目前存在的问题，在对当前机器学习方法和协商技术进行 深入细致的分析并对它们各自的特点及优缺点有了充分认识的基础上，本文对协 商过程中的一些关键问题进行了研究，主要研究内容有： ( 1 ) 对推测计算进行了扩充，并提出了基于信念修正的推测计算。在计算 过程中，如果应答和信念不一致，则主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 的选择问题。为了充分学习协商历史，实现 探索( e x p l o r a t i o n ) 和利用( e x p l o i t a t i o n ) 的折衷，把销售者的选择问题转 变成k 臂赌博机问题( k a r e d b a n d i tp r o b l e m ) 来求解。文中提出了信任和声 誉的度量模型，结合x 臂赌博机问题的求解技术，采用基于模拟协商( ( 置) ) 的学习机制，提出了几个确定奖励分布的改进算法日 ，珂) 、e ，y ) 、皿 ，) 和 珊，最后，以模拟协商过程为基础将改进算法和信任及声誉模型有机地结合起 来，提高了选择销售a g e n t 的准确性和实用性。几个实验都证实了本文工作的有 效性。 ( 3 ) 提出了一个以理性a g e n t 为基础的基于多阶段的多问题协商框架。该 框架在时间约束下适用于信息不完全的场景，它描述了多问题的价格协商。为了 北京交通大学博士学位论文 降低多问题协商的复杂性，它将多问题协商分解为多阶段协商，每个阶段的大小 ( 问题数) 相同。阶段数和顺序在协商前确定，每个阶段中的问题顺序在协商中 确定。在阶段大小相同的情况下，对给定协商问题的分解，框架能给出优化协商 议程( a g e n d a ) ，提出以仲裁a g e n t 为基础的多阶段协商协议，给出了确定多阶 段的过程。尤其是，框架能为参与协商的a g e n t 建立学习系统( l s ) ，以增强a g e n t 的学习能力。最后基于这个框架的原型系统证实这个框架是有效的。 ( 4 ) 提出个基于推测计算的一对多并行协商模型。在多a g e n t 环境中， 推测计算就是一个a g e n t 在还没有得到应答的情况下提前做出决策的过程。这部 分将推测计算用于多个有偿资源获取的一对多协商中。首先将推测计算模型扩充 为可容纳多协商线程的模型，并提出具有信念修正的多问题协商模型。基于这两 个模型又提出了多线程并行协商过程。为实现这个多线程并行协商过程，给出两 种并行方案，并对这两种方案和相应的并行策略进行了讨论。最后通过实验证实 了所给出的模型和并行协商过程是有效的。 ( 5 ) 协商双方用动态影响图( d y i l a m i ci n n u e n c ed i a g r 眦d i d ) 序列作为协 商双方a g e n t 的信念机构，提出固定时间区间的不同时刻的多d i d 综合推理机制。 改进v o t i n ge m 算法为n e v o t i n ge m ( s ，y r ) 算法。基于n e v j t i n ge m ( s ，y t ) 算法的协商过程适应于指定时间区间不同时刻网络参数的在线学习，还具有考虑 不同时刻多网络相关性、确保已有信念的一定延迟等特点。n e j v o t i n g e m ( s ，y t ) 算法不仅具有v 0 t i n ge m 的优点，而且在自适应学习率变化方面更精确。提出 d i d 序列更新过程r e v i s i o n _ i d ( v ) ，并将n e v o d n ge m ( s ，”) 算法嵌入到 r e v i s i o r l d ( v ) 过程中。实验证实基于该算法，通过对多d i d 的综合推理，可以 提高对对方私有信息的预测精度，缩短协商线程，提高协商效率。 关键词：学习，推测计算，协商，多阶段协商，议程，多臂赌博机，动态影 响图，多线程 i i 北京交通大学博士学位论文 p r e s e n t e d v i 8u s i n gm es e q u e n c eo f d i dw 酶蠡x e dt i m ep 舔o d a l g 撕t h m 、狱i n ge m i si m p r o v e da sn e v o t i n ge m ( s ，y t ) ，n c g o t i a t i o nb a s e do nn e - v o t i n ge m ( s ，y t ) i n c l u d e s o n l i n el o a m i n g 最坩b a y e s i a nn e 椭o f kp a e 诎so fd i 艄艟t i m e 证t 圭l e n x e dt i m ep e f i o d ，d e p e 姒l e n c e 踟o n gm u i t i n e t w o r ka tt 1 1 ed i 珏b r e mm o m e n ti s c o n s i d e i 冒da n dt h eb e l i e f o b t a i n e de a nk e p tf o r 矗x e dt i m e n 嚣一v o t i n ge m ( s ，y t ) n o t o n l yh a sa d v a n t a g eo fa l g o r m nv 。t i n ge m ，b u ta l s oi ti sm a c c u r a t ei nc h a i l g i n g t h el e a n l i n gr a t eo fs e l f - a d a p 诅蛀o n r g v 秘册一( 矿) f o ru p d a t i n gt i l es e q u e n c eo f d i d i s p r 0 8 e m e d ，a n d n e - 、，o t i n g e m ( s ，y t ) i se m b o d d e d i n t o 如v 鼢如雄一肋( ，) t h o e x p e r i m e n t sp r o v e dc o m p r e 圭l e n s i v er e a s o n i n go ft h cs e q u e n c eo fd i dc a ni m p r o v e a c e u r a e yo f p r e d i c 斑培o p p o n e n t s 辨i v a t ei n f o r m a t i o 鹞a n ds h o r t e nn e g o t i a t i o n 啦r e a d ， a n di m p r o v ee 翁c i e n c yo f n e g o t i a o n 圣y w o r d s ： l e a m i n g ，s p e e 娜a t i v ec o m p 妇垃驰，n e g o 虹a t i o n ，m 越疸s 掘g e n e g o t i a t i o n ，a g e n d a ，m u l 小a 衄e db a n d i t ，d y n a m i ci n n u e n c ed i a g r a m ，m i l l t i t h r e a d v 北京交通大学博士学位论文 第一章绪论 随着信息技术和通讯技术的不断发展，企业或市场的虚拟化和电子化进程在 不断加快，尤其是i n t e r n e t 技术的不断成熟，为企业的电子交易和商品信息发 布提供了主要渠道。通过i n t e r n e t 这个媒体，企业可以把产品信息快速地发送 到全球各地，缩短了企业和企业之间、企业和客户之间、客户和客户之间的空间 距离，实现2 4 小时新信息的全球共享，这样可以大大降低企业的管理成本和运 营成本。基于w e b 的网上商店和购物是第一代电子商务的特征，但这种形式的电 子商务远远没有挖掘出i n t e r n e t 的潜能【l j ，也远远没有满足企业发展的要求。 新一代电子商务的特征是在i n t e r n e t 上实现企业和企业之间、企业和客户之间 的大规模物流信息共享，实现企业和企业之间、企业和客户之间的大规模货物在 线交易，对应的就是l o 哪s c i o 等 1 所谈到的自动协商( a u t o a t i c n e g o t i a t i o n ) 。其中，在线交易是企业销售其产品，购买所需的主要方式，分布 式人工智能中a g e n t 之间的协商技术为在线交易提供了有效的途径。 分布式人工智能( 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 ) 是人工智 能领域的研究热点，它包括分布式问题求解( d i s t r i b u t e dp r o b l e ms 0 1 v i n g d p s ) 和多a g e n t 系统( m u l t i a g e n ts y s t e m - m a s ) 1 4 6 ，1 9 0 ，1 9 2 1 。分布式问题求解主要考 虑怎样将一个特殊问题求解任务分布在多个合作的、知识共享的多个a g e n t 或节 点之间进行；多a g e n t 系统主要研究一组自治的a g e n t 之间智能行为的协调。在 这两个领域的问题求解中，协商都是关键的技术环节。协商( n e g o t i a t i o n ) 是 问题求解中联盟( c o a l i t i o n ) 、协作( c o o p e r a t i o n ) 和协调( c o o r d i n a t i o n ) 的前提。它是建立在通讯语言基础之上的一种动态交互机制，对某些问题，通过 协商达成一种协议。协商a g e n t 在协商中要采取有效的策略，提高自己的提议被 对方接受的可能性，同时又使协商的结果对己有利或者对双方都有利1 7 5 ，1 8 2 】。协 商机制要保证：( 1 ) 单调性，协商双方在协商过程中要逐步做出让步，否则就难 以达成一个协议；( 2 ) 收敛性，协商要在一定的时间约束下进行，否则就没有意 义；( 3 ) 理性，协商的结果对协商者有利。 协商在电子商务中有重要的应用，交易能否成功完全取决于双方协商是否能 达成协议。协商是一个复杂的动态交互过程，本文的主要目的就是通过学习来提 高协商的效率，并使协商双方获得较高的收益。 第一章绪论 1 1 研究背景 a g e n t 是分布式人工智能求解问题的主体，也是协商机制的执行主体。a g e n t 是具有如下特性的执行实体1 7 5 ，1 9 0 ，1 9 2 ，1 9 8 】：( 1 ) 自治性，a g e n t 可以在没有人为的 干预下自行执行任务，并能对自己的行为和内部状态进行有效的控制；( 2 ) 社会 性，a g e n t 之间可以通过相互交往彼此产生影响；( 3 ) 反应性，a g e n t 时刻感觉 来自环境的反应，并能对这些反应进行回应；( 4 ) 主动性，a g e n t 不仅可以感知 环境，还可以以自己内部状态为基础体现目标驱动的行为；( 5 ) 移动性，a g e n t 为了达到自己的目的，在分布式环境中有目的的进行迁移。在基于w e b 的电子商 务环境中，一个a g e n t 可以是用户的代表，携带着用户的需求到i n t e r n e t 上去 寻找答案。一个购物a g e n t ( 购买者) 可以携带用户的购物需求到网上的交易市 场去寻找相应的销售a g e n t ( 销售者) ，一旦找到目标，购买者就和销售者进行 协商，如果协商成功，购买者就将协商结果返给购物用户，这就是购物代理【1 ，2 3 ，25 1 。 一个协商一旦建立，需要考虑三个方面的问题【l ，1 67 】( 1 ) 协商双方在协商过 程中应该遵循什么协议( p r o t o c 0 1 ) ；( 2 ) 双方协商的问题( i s s u e ) 是什么? ( 3 ) 协商双方在协商过程中分别采用什么推理模型( r e a s o n i n gm o d e l ) ? 在协商过 程中，协商双方所遵循的协议是一个规则集，或者是一个状态转换图，协商双方 只能在状念转换图所规定的状态之间进行迁移，这是协商双方的行为规范。所协 商的问题是双方所关注的焦点，这些问题可以是单个问题，也可以是多个问题， 多个问题之间可以是相关的，也可以是相互独立的。协商者( n e g o t i a t o r ) 所采 用的推理模型是反映协商者智能性的关键，由于协商是一个动态过程，而且协商 双方的私有信息( 内部状态) 彼此之间是隐蔽的，那么，一个高智能的协商者应 该能够在协商过程中很快掌握对方的私有信息，处于主导地位，从而能从协商过 程中获得较大的收益。协商者如何才能变为高智能的呢? 这是本文的主题，本文 基于学习研究协商机制，探讨学习对协商过程及结果的影响。f a r a t i n 等 2 ( 1 9 9 8 ) 以协商决策函数( n e g o t i a t i o nd e c i s i o nf u n c t i o n s - n d f ) 为基础建立 了一个形式协商模型，模型定义了协商双方产生初始提议、评价提议、产生反提 议的策略，并通过面向服务( s e r v i c e o r i e n t e d ) 的协商展示了协商过程，模型 包含几个隐合的假设：信息私有( p r i v a c yo fi n f o 珈a t i o n ) ，协商双方彼此保 持自己的私有信息；模型私有( p r i v a c yo fi n f o r a t i o n ) ，协商双方彼此保持 自己私有的推理模型；值约束( v a l u er e s t r i c t i o n s ) ，所协商问题和评价函数 都在一定范围内取值；时间约束( t i m er e s t r i c t i o n s ) ，在一定时间约束下的协 北京变通大学博士学钕论文 商才有意义；资源约束( r e s o u r c er e s t r i c t i o n s ，资滁对协商a g e n t 盼行为有 定的影响。这个模型为以后的协商奠定了基础。k u n g j e n gw a n g 等 3 ( 2 0 0 3 ) 遂一步研究了基于n d f s 的协商梳制，对协商策略的分孵和评价说明协商对闻约 獭( d e a d l i n e ) 严重影响协商的收敛特性。l o m u s c i o 等 1 ( 2 0 0 0 ) 对自动协商 酌分类及相关参数进行了讨论。风t i m a 簿 4 ( 2 2 ) 稳出了一个在信意不完全 的环境下具有时间约束的多问题协商模数，模型体现了协商a g e n t 的信息状态、 协商协议、均衡策略、实现方寨、均衡解的特往等内容。这个穰麓为多阏遂诱商 夔定了慕础。f a t i i i l a 等 6 ( 2 0 0 4 ) 提出了一个旗于议程( a g e n d a - b a s e d ) 的协 简模型，分析和探讨了肉定议程和舞定议程对协商过程及其结果的影响。议程决 定了协崩的结构，文献( 7 ，9 ，3 0 ，4 0 ，1 4 3 ( 2 0 0 0 ，2 0 0 l ，1 9 9 0 ，2 0 0 3 ，2 0 0 0 ) 也都从 不同角度对议程避行了探讨，议程影响协商的结栗和协商的风除。f a t i m a 等 9 ( 2 0 0 1 ) 研究了内外议程对协商效用的影响，探讨了优化议程和效用最大化问题， 褥出“来自k 阶段协商协议的效褥不沈荦阶段协商协议的效用藏”的结论。这蹙 文献都从不同角度探讨了协商及其影响您的因素，但是，都没有考虑学习因素对 协商的影响。 1 2a g e n t 之间的学习 在多a g e n t 环境中，a g e n t 要很好地体现其自治性和主动性，就要在工作过 程中觚环境中学习，觚交互的英它8 9 e n t 那墨学习，通过学习方髓更好燎充分体 现a g e n t 的各个特性。w a n 等 1 6 2 ( 1 9 9 6 ) 提出了a 3 结构理论( a 3 一a r c h i t e c t u r o t b e o r y ) ，岔藏怒宣遥疲啻治矗g e n t ( 矗d a p t i v ea u t o n o m o u sa g e n t ) ，通过调熬 ( r e g u l a t i o n ) 和学习( l e a r n i n g ) 双黧机制来增强a g e n t 的自适应能力，以此 遴论为基石蠡实糯了一个增强学习系统( r e i n f o r c e m e n tl e a r n i n gs y s t e m r l s ) ， 并且通过增强a g e n t 的自适应能力解决了到达动态目标的探索问题。 s l u h u 矗l l u 等 1 2 】( 2 0 0 2 ) 综述了多a g e n t 在不确定环境中的学习方法， 并从强和弱两个层次对多a g e n t 学习进行了分类，从更强的学习含义上说，多 a g e n t 学溜可以怒合作j 陡学习，从弱含义上说，多a g e n t 学习可黻是竞争性学习。 凝体的举习方* 安有：( 1 ) t p o t r l ( t e a m p a r t i t i o n e do d a a u e t r a n s i t i o n r e i n f o r c e m e n tl e a r n i n g ) ，多a g e n t 和用这种) 亨法合作进行学习以便达到一个 特定的目标；( 2 ) m i n i m a x ql e a r n i n g ，这是一个单8 9 e n t 的学习方法；( 3 ) o p p o n e n t 艟o d e l i n g ，这建多a g e n t 之间的竞争学习方法，一方学习另一方的掩 第一章绪论 理模型：( 4 ) 使用变量学习率的增强学习，该学习方法可以根据不同情况选择不 同的学习率，从而改变学习收敛速度：( 5 ) p r o f i t s h a r i n g 增强学习，该方法 没有中间奖励，到达目标才有奖励，这也是一个单a g e n t 学习方法；( 6 ) 无私的 增强学习，这是一种合作性的学习方法。i s b e l l 等 1 6 3 ( 2 0 0 0 ) 给出了一个a g e n t c o b o t 的学习过程，c o b o t 在一个在线聊天社区l a m b d a m 0 0 ( o n l i n ec h a t c o m u n i t yl a m b d a m o o ) 感受社区不同人的行为，然后做一个社会统计( s o c i a l s t a t i s t i c s ) ，并将这个统计主动地返回给用户，用户根据满意程度给c o b o t 奖 励，c o b o t 不断改变自己的行为，以便使自己所获得的奖励最大，这是a g e n t 从 环境中学习的例子。 s e o 等 1 6 4 ( 2 0 0 0 ) 提出了一个基于w e b 的个性化信息过滤系统w a i r ，在 这个系统中，有一个a g e n t 通过增强学习对用户的行为来学习用户的偏好 ( p r e f e r e n c e s ) 和兴趣( i n t e r e s t s ) ，根据用户的偏好不断收集用户喜好的信 息，过滤用户不喜好的信息。c a r m e l 等 1 2 3 ( 1 9 9 8 ) 提出了一个基于模型的学 习策略，a g e n t 是个商务代理，它可以代表它的主人( s t e r ) 到市场进行交 互( i n t e r a c t ) 和交易( t r a d e ) ，通过学习它有能力识别对手或者其它a g e n t 的 意图和目标，并能预测对手未来的行为。a g e n t 所在的环境是一个交互的m a r k o v 博弈( a l t e r n a t i n gm a r k o vg a m e s ) ，在学习中使用了正规策略( r e h u l a r s t r a t e g i e s ) 、基于向前看的探索策略( l o o k a h e a d b a s e de x p l o r a t i o n s t r a t e g y ) ，采用了基于模型的学习方法，先后提出了m 、口、m + 、筇和m ： 算法，最后在迭代囚徒困境博弈( i t e r a t e dp r i s o n e r sd i l e i i l i n ag a m e ) 中给 出了实验结果，这是一个a g e n t 从其它a g e n t 那里学习的实例。p e g o r a r o 等 1 6 5 ( 2 0 0 1 ) 提出了在多a g e n t 系统中改进控制策略的在线学习时间问题，并在 q l e a r n i n g 算法和m i n i m a x q 算法的基础上提出了q s 算法，该算法比前两个算 法收敛速度都快。在过去的若干年中，多a g e n t 使用在线学习实现协同 ( c o o r d i n a t i o n ) ，当其它a g e n t 学习环境并采取不同的动作对环境做出反应的 时候，不稳定的场景就出现了。单个a g e n t 的稳定场景可以通过m d p s ( m a r k o v d e c i s i o np r o c e s s e s - m d p s ) 来模拟，在狮p 场景中，增强学习算法可以在线学 习优化控制策略，矩阵博弈( m a t r i xg 枷e s ) 可以处理多a g e n t 的单状态场景， 极小极大化算法( m i n i m a xa l g o r i t h m ) 可以求解矩阵博弈，m a r k o v 博弈将 i d p s 和m a t r i x 博弈结合起来，并能模拟a g e n t 不稳定场景的问题。 s u r y a d i 等 9 4 ( 1 9 9 9 ) 提供了一个框架( f r a m e w o r k ) ，可以使一个a g e n t 通过观察其它a g e n t 的行为来学习其它a g e n t 的模型。文献利用影响图 ( i n f l u e n c ed i a g r a m s ) 来模拟其它a g e n t 的能力( c a p a b i l i t i e s ) 、偏好 北京交通大学博士学位论文 ( p r e f e r e n e e ) 和信念( b e l i e f ) 。其中，偏好邋过神经瞬络来学习，耩稻梯度 f 降技7 r 来调整相应的权重。 多a g e n t 系统大多都存在不稳定的因素，多8 9 e n t 谯这种不稳定的球境中为 了合作或者竞争迭到它们的目标，它们分别都要进行在线( o n l i n e ) 学习，执 行任务之前要对脊关闯憨进行离线( 。f f l i n e ) 学习，只有这样8 9 e n t 才可美充 分发挥它的特性，精确地做出决策。 ，3 学习对协商的影晌 诲鼹楚a g e 雌双方迸雩亍交互瓣一个动态的复杂过程1 # 一，程这个过程中，协 商双方可以是合作的实现双方受凝，也可以是竞争的实现自己的利益最大化。无 论是鄂一释方式，傍商双方静瓤帮信怠帮楚镀魏隐蔽静，所戮，协商者簧憨在协 商中占主导地位，它就要有足够的智能。协商是一个过稷，协商潜的智能可以在 协商蘸遗遗学习获得，穗可颤在协商遘稷中获褥，或者阏拜亏在两个过程中获得。 协商双方在协商过程中进行学习是提高协商效率和效朋的主要途径之一。在 8 9 e n t 之闼要建立关于货物或者黻务薛合霞( e o n t r a c t s ) ，主要方式是协商【姗， 协商的问题通常是多个问题，而熙这些问题之间也是相关的，从而增加了协商这 盛闯蘧静难度，协商者嚣先要通过学习才能够瓣对这些复杂闻麓做出猴确的提 议。 在协商过程中，首先能够糠到静学习对象就是对对方偏好的学习。文献 c o e h o o r l l 等 9 9 ( 2 0 0 4 ) 使用核密度估计( k e r n e ld e n 8 i t ye s t i m t i 。n k d e ) 学习对方滟偏好，从而蜜疆有效翡多闻鼷协商挢中( t r a d e o f f s ) 隧9 懿。一个协 商者在不了解对方对所协商问题的偏好的情况下是无法实现这种折中的。折中就 燕协商一方就莱个闯题诖步，值对另一个问题就骚提高要求，在保持自融效用不 变的情况下，来提高对方的效用，从而提高达成协议的可能性。文献c o e h 。o r n 等 9 9 ( 2 4 ) 将k 琵方法和文献 38 ，9 8 ( 2 0 0 2 ，2 0 0 。) 中基于糟似标准 ( s i m i l a r i t yc r i t e r i a ) 的折中算法结台起来，在知道对方对器个问题偏好的 情况下，可以实璇眈文献 3 8 ，9 8 中的方法更有效的折中，文中实验说嘲利用这 种方法进行协商折中的成功率比文献 3 8 ，9 8 的方法高，烂然这是学习带来的效 菜。具有学习能力的a g e n t 可以猩信息不完全的情况下做出正确的决策躐预测， 协商是个信息不完全的过程，学习可以改善协藏的效率。b u i 答 1 4 6 ( 1 9 9 9 ) 鼹出了将个学习部件集成到协商a g e n t 结构中的方法，学习部件使用b a y e s 分 5 第一章绪论 类技术作为基本的学习机制，从协商历史中学习协商对方的偏好，掌握对方偏好 的协商者可以在协商中做出较准确的决策。 z e n g 5 ，1 0 5 ( 1 9 9 7 ，1 9 9 8 ) 提出一个顺序决策模型( s e q u e n t i a ld e c i s i o n m a k i n g ) b a z a a r ，在这个模型中，利用了朴素b a y e s 信念更新过程描述了协商过 程中协商者的学习问题，并分三种情况做了实验：( 1 ) 不学习的购买者和不学习 的供应者进行协商；( 2 ) 学习的购买者和学习的供应者进行协商；( 3 ) 学习的购 买者和不学习的供应者进行协商。通过实验可以说明情况( 2 ) 的协商结果( 联 合效用) 比情况( 1 ) 和( 3 ) 的结果要好；情况( 3 ) 的结果甚至不如情况( 1 ) 的协商结果。文献z e n g 1 0 5 ( 1 9 9 8 ) 认为一个用于协商的计算框架应该满足 如下特性：( 1 ) 能够进行复杂问题( m u l t i i s s u e ) 和多标准( m u l t i c r i t e r i a ) 的协商；( 2 ) 模型所提供的算法要能够产生提议，而不是仅仅描述协商的最终结 果；( 3 ) 学习机制很容易结合到协商模型中。文献z e n g 5 ( 1 9 9 7 ) 认为协商 中学习的熏要性在于它是理解人类行为和开发新的求解概念( d e v e l o p i n gn e w s o l u t i o nc o n c e p t s ) 的基础。 协商是多a g e n t 环境的特殊过程，这个过程具备如下特点：( 1 ) 信息不完全， 协商双方彼此掌握对方的信息是不完全的；( 2 ) 动态性，协商过程和结构可能在 外界的影响下发生改变；( 3 ) 交互性，协商是以交互特性为主的一个过程；( 4 ) 协商者可以感知环境，也可以感知对方，它通过决策来响应环境，响应对方。从 以上文献的工作和结论，结合协商过程的特点，可以看出，协商一方具有学习能 力可以提高自己的协商效用，协商双方都具有学习能力可以提高双方的联合效 用。 1 4 协商方法论综述 协商是一个复杂过程，人们对协商采用了不同的方法并从不同的角度进行了 研究，在各个方面都取得了丰硕的成果。下面从博弈论、争辩、学习和兴趣四个 方面来讨论。 1 4 1 基于博弈论的协商方法 博弈论( g a m et h e o r y ) 既是一门古老的学科，又是一门极具生命力的新兴 的发展中学科。对博弈论的研究可以追溯到1 8 世纪初，例如瓦德格拉夫 ( 稃a l d e g r 8 v e ) 1 7 1 3 年就提出了两入博弈的极小亿极大纯混合策略解、吉诺 ( c 叫r n o t ) 和伯特兰德( b e r t r a n d ) 则分别在1 8 3 8 年和1 8 8 3 年提出了博弈论 鬣经典的模蝥。灞诺伊照帮摩税斯毽1 9 唾唾年岛舨鲍 簿奔论和经济行为应该 被看作是博弈论历史的真正起点【1 9 9 1 。研究协商问题有两种基本方法【1 8 7 ，1 8 8 】：公理 化方法和策略仡方法。每个公理系统都觚不丽侧褥反映协商者的邂性行为，并作 为一种规则对每个协商问题给出确定的结局。有两种不同的公理化方法：关于结 稀空阊和关于冲突点的公理佬方法。簿稀公理亿方法谗有两种不同倾向：醵 n a s h 1 9 9 1 为代表的公理化方法是对协商问题的解概念和解的属性公理化；以 l a r s a n y i 为代表的公理化方法燕对理往行为的锫个侧面公理讫，从而给出解概 念。策略方法是研究协商问题讨价还价( b a r g a i n i n g ) 过程的方法，它摁协商闷 磁描述成多对策过程。z e u t h e n 嘏早使用策略方法研究协商闯鼹，提出了研究协 商过程的踅要模型和原理，被称为z e u t h e n 原理。文献 2 ，3 ，8 ，9 ，2 2 ，2 3 ( 1 9 9 8 ， 2 0 0 3 ，2 i ，2 0 0 l ，2 0 0 2 ，1 9 9 8 ) 都注重使用策略方法研究协商问题。 j e n n i n g s 等 4 5 ( 2 0 0 1 ) 认为计算机科学为博弈论在协商釉讨价还价方面 的研究带来了两个新的内容：( 1 ) 博弈论研究理。陡选择，并假设协商a g e n t 可戳 谯所有可能的策略空间中选择最优策略，丽计算机科学要现实地去考虑诗箕复杂 襁问题；( 2 ) i n t e r n e t 技术的啦现为协商和讨价还价技术的迸一步开放提供了 广阔的平台和丰富的商业机遇。 1 4 2 基于争辫( a r g u m e n t a t i o n ) 的协商方法 关于协商的大部分研究都假设协商过程中的协商内霎i 霞l g 自! i 薹i ： l | = l ；2 ；l 羹霎奘剐j 噬站咀疆椎征廷醛蕊撑鲢塑鋈 ￥n v 8 】。一盆h q j e 。ij ；繇群 阜州掣甄罂荃烹缝焉硎黑巅瑗潆鹭瘴磷荔| 霏蛳撼苘；篷婴i 薹燮磊釜吐蔓强秀。 所牡到殴耄矬熠攫嗣臻掣盔罐蠼淄强爿趔峰萎舔辅“耋姜i 圄j 。3 5 ：i 5 母；受解的证明过程 一些假设证明过程在文献【1 8 ，1 9 ，1 6 9 ，1 7 0 】( 2 0 0 0 ，1 9 9 7 ，1 9 9 7 ，1 9 9 8 ) 中可以看 到，其中以潞证明过程最为普遍。s a d r i 等【1 8 】( 2 0 0 0 ) 对文献f u n g 等 1 9 ( 1 9 9 7 ) 所介绍的衙证明过程进行了修正。这部分介绍一下i f f 证明过程。 给定一个目标q ，一个假设原子集d 和目标q 中的一个变量代换口，一个对 偶( d ，目) 是关于假设逻辑程序( p ，4 ，佗) 的q 的假设解，当且仅当，尸u d 蕴涵q 口且尸u d 满足圯 x 第一章绪论 提出一些额外的属性来影响对方接受提议；劝说争辩是劝说对方接受提议；证明 争辩就是证明以前的提议( 或者争辩) 是正确的。j e n n i n g s 等 5 2 ( 1 9 9 8 ) 认 为参与争辩协商的协商者应该具有如下技术：( 1 ) 传递对方容易理解的提议和相 关的争辩；( 2 ) 产生提议和相关的争辩；( 3 ) 评价提议和相关的争辩；( 4 ) 响应 提议和相关的争辩。文献 1 3 2 ，1 3 3 ( 2 0 0 4 ，2 0 0 3 ) 都给出了争辩a g e n t 的决策结 构。所以具有争辩机制的协商是一种复杂协商，但它更贴近现实，协商效率更高。 1 4 3 基于机器学习的协商方法 机器学习是提高机器智能行为的主要方法。在多a g e n t 系统中，a g e n t 的智 能行为也要通过机器学习的方式获得。机器学习的常规方法主要包括 8 0 ，1 8 5 ，1 8 6 ，2 0 0 】： ( 1 ) 基于神经网络的学习方法；( 2 ) 基于b a y e s 的学习方法；( 3 ) 基于支持向 量机( s v m ) 的学习方法；( 4 ) 增强学习方法；( 5 ) 基于模型的学习方法；( 6 ) 基于数据分析的学习方法等等，这些方法在现实中都不同程度地提高了机器的决 策精度。协商是一个特殊的多a g e n t 的交互过程，由于协商双方的私有信息相互 隐蔽，协商双方为了提高自己的效用，需要提高自己的决策精度，优化自己的智 能行为，所以，协商双方只有通过机器学习的方法来提高自己的适应性和智能性， 从而提高协商的效用。 协商有两个环节可以介入学习机制，一个环节是在协商前，协商a g e n t 可以 在协商前通过阅读对方的协商历史学习对对方的协商信念，这是个离线学习过 程；另一个环节就是在协商过程中，协商a g e n t 在协商过程中可以根据对方的提 议来调整对对方的信念，从而提高决策精度，这是一个在线学习过程。 0 p r e a 1 0 ( 2 0 0 2 ) 基于人工神经网络开发了一个自适应的协商模型，模型 中主要是在线学习过程，实验中涉及到基于人工神经网络的a g e n t ( a n n a g e n t ) 和基于q 学习的a g e n t ( q a g e n t ) 。b a n e r j e e 等 8 5 ( 1 9 9 9 ) 使用b a y e s 网络来 辅助a g e n t 之间的协商，z e n g 等 1 0 5 ( 1 9 9 8 ) 将朴素b a y e s 学习用在了协商过 程中，s a h a 等 1 3 2 ( 2 0 0 4 ) 将b a y e s 网络学习用到了基于争辩的协商过程中， b u i 等 1 4 6 ( 1 9 9 9 ) 使用b a y e s 分类器来学习协商对方的模型。c a 姗e l 等 1 2 4 ( 1 9 9 6 ) 使用博弈树来学习对方的模型。这些文献和工作都充分说明机器学习是 在协商过程中不可缺少的技术。本文主要采用的就是这种协商方法。 i 蓬! ! l 毒 ? ! | | j 譬圭丢张华冬蛋褒髓列荔划鲥彰冀剽黟薹雾霞聪j 鼍漤 i ；! ；m 邕静蓼蒂i ；i ! j i _ ；i 霜猹弼器i l l 辐骄i l ；t 照趑型巍鳃鞭g 酷矿彦邑壅州。密；剿烈豁鹳墨藿孺瀵l 臻浮釜协i i 囊茗碍釜斗番型虿| 托d 施誊蠢霪鏊鏊喾具供妻坚鼻璧奏i i i ! 。州蟊p 鹫疆匝再堕藿呵掳獭溲；2 8 5 ：i ；。j ；密鹜 奏翼酩坠磐尊霄釜菱，螳廷遵驱囊蜚醐 弧惦冀嘴酯醛够一验卜鼬搠强u 二鳆壁 p 叠藓瞢垡斛誊餮器酗韩曩臻鐾誊砸饕i 幕菇蘑是名字公弹集随巍：翥萄咖 孥是基罾囊嚣藿螽疆篱衙下翥臀。羹蛩俸罂显萧届搭箱榻嚣囊翥蜒基；苇 0 n f i ；i ；诣籍繇蓦 酲褡悄警击嚷瑶瑶翼g 罾要点辈盛喂珞竭型罨型礴；墓 i i ；g l 酹辩雏蓟再酶鳊捌嚣嚣攀美霪鬻噩驵翮髦蠢涛澄萼j 尚艄弱雨羁酞 鼠i 基鹱藿蠢摧巍鬟黧毯肇誊崮蹦晰爱! 雪s k g 圈i 号i = 7 i 器霎辇霾霹! 毯墼m 籽塞 甄皤甜稳芝蕊甏坩；g 镕，二s s 羹巽3 蔫蓊骛目烯翁嚣搿琵魁辑j 罐彳雅谨孺 隧候碧现珂嘲陟鼋啦陲；剥朝囊；i ；? 二烈塑。彗霪i ；i ；：l il 。i i j iii l i ； l ；& ? ：旦i ! ! ! i i ；| i ji l l 嚯姆f 誊塑譬“磊剧制懋委蠡錾琵 囊女女l # z 心l ；| ； i i ； 班酐刳替矧将韩馨霪骢篓蟊塞划墒藩哺璎础熠撑 瑁臻濮灌攫围塞曩嶙场追渗ii ； 塑蕊霉甫如错：撂爨憾j 馥照堕篱靼# # 氯挺 争f 霆誊f 蠹葳百玲冒犀全霉强塞；誊k 囊冀霉爨呼萋笱瞄坤岈墨婆是j 谴谨垡ji 0 ! ! ：i ；i ! i 翻氢襄鑫稻强再蓥鎏箜冒刊霉奎丢z 坦罂篓丽蕊择箅 蓉崔蕊嚣羹蚕登蛙裹蘩甍越型i i 莹；萼雾囊瑟薹| 鸥蠢翼暮妊謇萋i 妻目l 薹妻| 薷篓羹蠢蓬 磊慨滔瑚理瀑蠹强k 要嚣霉掺狙篁肴霎霪鋈蠢霉雾霎i 霞l g 自! i 薹i ： l | = l ；2 ；l 羹霎奘剐j 噬站咀疆椎征廷醛蕊撑鲢塑鋈 ￥n v 8 】。一盆h q j e 。ij ；繇群 阜州掣甄罂荃烹缝焉硎黑巅瑗潆鹭瘴磷薹! 霏蛳撼苘；篷婴i 薹燮磊釜吐蔓强秀。 所牡到殴耄矬熠攫嗣臻掣盔罐蠼淄强爿趔峰萎舔辅“1 1 i 圄j 。3 5 ：i 5 母；受解的证明 过程一些假设证明过程在文献 【18，19，169，17ll(2aao，1997，1997，1998)中可以看到，其中以潞证明过程最 为普遍。saiii等【18】(2aa0)对文献fu毒等19(1997)所介绍的衙证明过程进行 了修正。这部分介绍一下i|l证明过程。给定一个目标q，一个假 设原子集d和目标q中的一个变量代换口，一个对偶(d，目)是关于假设 逻辑程序(p，4，佗)的q的假设解，当且仅当，尸ud蕴涵q口且尸ud满足圯 x 北京交通大学博士学位论文 应用到上，且力船。给定这样一个成功推导，从中提取的假设解就是 一个对偶( d ，盯) ，其中，盯是q 中所有存在量化变量的代换，d 是口中的所有 可假设原子集。 2 1 3 基于假设推理的推测计算 推测计算就是在执行计算的完全信息还没有完全获得之前所进行的临时计 算过程，这个计算是以假设推理为基础的，详细内容参阅文献 1 5 ，1 6 ，1 7 ，1 5 0 ， 1 5 l ，1 5 2 ，1 5 3 ( 2 0 0 1 ，2 0 0 2 ，2 0 0 0 ，2 0 0 2 ，2 0 0 2 ，2 0 0 2 ，2 0 0 4 ) ，下面给出推测计算的 基本框架。 用于主仆a g e n t 系统的基本推测框架是【1 6 ，1 7 1 ： 5 t = 表示一个多a g e n t 系统，系统中只有一个主a g e n t ，其它为仆a g e n t 。 s 表示一个外部谓词集，当q 是一个具有外部谓词的文字，s 是一个仆a g e n t 标识时，我们称q s 为一个可问文字( a s k a b l el i t e r a l ) 。 表示一个基可问文字( g r o u n da s k | ；i 易 ! i 嚣i 蚕釉蚓吲漫测骚i 毒 淄繁强蔼滔塞i i 。i ? 蠢l 噬茎甄一参8 一，；冀i m 薹；型鳓雕臻害摄嘤咝崾憾 e 墨饕雾譬睦g 副墓霉笔! 事囊善 纛i ； s 羹始蘑囊鞲匹娃艏赘；u i 截；i1 j l | 主要考虑的是单问题的协商过程，现 实中所协商的问题一般是多问 题的。 f a t i m a 等 4 ( 2 0 0 2 ) 首先提出了在时间约束下的单问题协商模型，模型在 6 种时间约束下，在4 种场景中考虑了协商过程中的优化策略问题，然后又提出 了多问题协商模型，模型在协商多问题时采用两种方式：顺序实现( s e q u e n t i a l i m p l e m e n t a t i o n ) 方式和同时实现( s i m u l t a n e o u si m p l e m e n t a t i o n ) 方式，并 且得出结论：由顺序实现方式所得的协商结果不比同时实现方式所得的结果差。 f a t i m a 等 6 5 ( 2 0 0 4 ) 进一步讨论了在不完全信息情况下多问题的优化协商， 提出决定结果的两个因素：协商议程( a g en d a ) 和