一种任一时间联盟结构生成算法

联盟形成是多 Agent系统中的一个关键问题 .人们寻求能极大化联盟值的总和的联盟结构 ,但通常情况下可能的联盟结构的数目太大 ,以致不允许进行穷尽搜索而找出最优解 .给出了一个算法 ,可在最小搜索量内保证找到一个与最优解相距在一个限界内的联盟结构 .然后 ,这个任一时间算法进一步搜索 ,渐进地给出越来越低的限界 ,并急剧地降低这个限界 ,在这一阶段 ,此算法明显地优于由 Sandholm等人给出的算法 .

Agent的意图模型

意图是 Agent的一个不可缺少的意识属性 ,在决定理性 Agent的行为时起着重要的作用 .已经有了若干种基于正规模态逻辑的意图模型 ,但它们存在着严重的“逻辑全知”问题 .该文阐明意图不是正规模态算子 ,并提出了另一种意图模型 ,它不存在“逻辑全知”问题和其他相关问题 (例如 ,副作用问题等 ) .这种意图模型与Konolige和 Pollack的意图模型相比 ,比较简单、自然 ,且满足 K公理和联合一致性原理 ,实际上 。

Agent-BDI逻辑

阐述了 Agent的形式化描述应该采用含有正规和非正规模态算子的混合模态逻辑为逻辑工具的观点 .建立了 Agent- BDI逻辑的代表系统 A- BI,讨论了它的语法和语义 .特别是给出了非正规模态算子基于 Kripke标准可能世界的新的语义解释 ,证明了 A- BI逻辑系统不但是可靠的 ,而且是完备的 .A- BI逻辑系统恰当地刻画了信念与意图的本质与内在联系 ,可作为 Agent形式化研究的逻辑工具 .

给定限界的势结构分组与联盟结构生成

联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.

Agent形式化研究的逻辑工具

Agent在AI/DAI和其他计算机学科中正成为一个广泛使用、十分重要的概念,由此产生了一系列新的思想、方法和技术,甚至有人把“基于Agent计算”誉为“软件开发的又一重大突破”。有关Agent的理论、技术的研究和应用引起了人们的高度重视和极大兴趣。近年来,关于Agent的形式化研究已成为人工智能、哲学逻辑和计算语言学共同关心的重要课题,有着广泛的应用。

给定限界要求的联盟结构生成

联盟形成是多 Agent系统中的一个关键问题 ,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益 .但通常可能的联盟结构的数目太大 ,不允许穷尽搜索来找出最优解 .当实际问题提出最坏情况的具体限界要求时 ,如何以最小的搜索达到这个要求是需要解决的 .文中给出的算法对给定的限界要求 K* 2以最少的搜索层数解决了这个问题 . Sandholm等人已经证明 ,要建立最坏情况下的限界 K ( n) ,搜索联盟结构图的最底两层是必要且是充分的 ,此时限界是 n(系统的 Agent数 ) .以此为基础 ,文中给出了算法 ,在搜索最底两层之后 ,只要搜索一层就能保证 K( n) 3 ;而在搜索最底两层之后 ,最多搜索两层就能保证 K( n) 2 .与 Samdholm等人给出的算法相比 ,文中给出的算法达到指定限界的搜索量显著减少 .

Agent意图的双子集语义改进模型

意图是Agent的一个关键的意识属性,在决定理性Agent的行为中起着重要作用.为了克服现有意图逻辑中存在的缺陷,建立了适用于意图的语义表示.讨论了理性Agent性态的形式化中对意图语义的要求以及现有意图逻辑中存在的问题.介绍了在前期工作——真假子集语义基础上开发的双子集语义改进模型及其在Agent意图形式化中的应用,并且证明通过对模型的代数结构施加一定的约束,能获得许多希望得到的性质.在二值逻辑中,真和假是同等重要的.当然,对一个命题,描述了真值也就知道了假值;但对于一类命题却不是这样,对假值的刻画与对真值的刻画具有同等重要的意义.而对意图的描述是对一类命题(Agent意图实现的命题)的刻画.经典的正规模态算子的可能世界语义只重视真,用RI(w)来描述,可看成是单子集语义.而改进的双子集语义真假并重,用RIT(w)来描述真,并用RIF(w)来描述假,从而能更全面地描述二值逻辑中的模态算子.经典的正规模态算子的可能世界语义可以看成是改进的双子集语义当RIF(w)=?时的退化情形.改进的双子集语义不仅避免了基于正规模态逻辑表示的“逻辑全知”问题以及由此带来的副作用等问题,与Konolige和Pollack的意图模型相比,比较简单、自然,且满足K公理和联合一致性原理,而且克服了前期工作真假子集语义和双子集语义表示的缺陷.实际上,改进的双子集语义为非正规模态算子的语义表示提供了一种新的方法,可应用于建立新的合适的Agent逻辑系统.

最坏情况具有限界的联盟结构生成

联盟形成是多Agent系统中的一个关键问题.寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能解决的问题.Dang等人给出的算法,对于奇数限界k≥3,在搜索最底两层及顶层后,进一步搜索最大联盟的势不小于n(k-1)/(k+1)的所有联盟结构,是迄今所知的第1个不以层为搜索单位的算法,对于较小的限界明显地优于Sandholm等人给出的算法.文中深刻分析了联盟结构间的关系,提出的算法在搜索最底两层后,只需进一步搜索最大联盟的势等于n(k-1)/(k+1)的所有联盟结构,从而使需要搜索的联盟结构数大大减少,并进一步将搜索某些层最大联盟的势等于n(k-1)/(k+1)的联盟结构巧妙地改为搜索联盟结构数更少的相应层,使需要搜索的联盟结构数进一步减少,较大地改进了Sandholm等人和Dang等人的工作.

一个改进的理性Agent-BDI模型

利用一种新的可能世界语义 ,在 Rao和 Georgeff的基于分支时间可能世界模型的 BDI形式化的基础上 ,得到一个改进的 BDI模型 .与 Rao和 Georgeff的 BDI模型以及大多数基于可能世界的形式化相比 ,不存在逻辑全知问题和除等价情况外的副作用问题 .

适用于Agent非正规模态算子的一种语义解释

文中提出了适用于Ａｇｅｎｔ非正规模态算子的一种语义解释．这种解释是基于正规可能世界的，不存在“逻辑全知”问题和由此带来的副作用等问题．与基于非正规可能世界的传统方法相比，不必增加可能世界的种类，比较自然、合理．

理性Agent的意图维护模型

在理性 Agent的形式化中 ,通常认为 Agent的思维状态包含信念、愿望和意图这 3个属性 .它们之间的静态关系已被人们充分重视 ,但它们随时间的动态变化还未被很好研究 .考察了意图维护直观语义中的一些问题 ,给出了随信念、愿望改变的意图维护的动态模型 ,与 Rao和 Georgeff的意图维护模型相比 ,适用性更广、更简明 ,不必限制可能世界的时序结构 ,不必另外引入信念、愿望、意图算子的 only模态形式 .

Agent逻辑和真假子集语义

理性Agent规约的形式框架通常基于信念、愿望和意图逻辑.为了克服现有的信念、愿望和意图逻辑中存在的问题,为非正规模态算子提供一种合适的语义表示.讨论了理性Agent性态的抽象规约中对语义表示的要求以及现有的信念、愿望和意图逻辑中存在的问题.介绍了作者开发的真假子集语义及其在Agent形式化中的应用.他们的框架使意图的有问题的性质无效.并且证明通过对模型的代数结构施加一定的约束,能获得许多希望的性质.最后对真假子集语义进行了分析.这一切表明真假子集语义为非正规模态算子提供了一种合适的语义表示,是对经典的正规模态算子可能世界语义的一个重要发展,是理性Agent性态的逻辑规约的有力工具,可应用于建立新的合适的Agent逻辑系统.

意图形式化中的副作用问题

在多Agent系统中,如何抽象和模型化Agent,已成为当前人工智能、软件工程等领域的一项重要的研究课题。在AI领域,人们通常基于意向立场来研究Agent。从意向立场出发,一般把信念(belief)、愿望(desire)和意图(intention)

基于局部最优的联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题.针对多Agent联盟数量是Agent个数指数倍的问题,给出了基于局部最优Agent联盟结构生成算法——OCS算法.基于局部最优,将Agent联盟结构图化简,并利用划分所对应的一类联盟结构的上界对Agent联盟结构图进行剪枝,极大降低了搜索空间.接着证明了OCS算法的时间复杂性为O(3n),但在实验上已经接近O(23n/2).最后通过对比数据分析,表明了OCS算法的效率.OCS算法是对Rothkopf和刘惊雷等人相关工作的改进.

基于势结构的任一时间联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法.深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n,b)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快1035倍,当n=100,K=2)和Dang等人(快1018倍,当n=100,K=3)的工作.

基于情感组织Agent的联盟形成研究

情感Agent通过同动态环境(包括人)的交互,能够感知周围环境,自治运行以实现特定的目标,同时也能影响和改变环境。把EBDI中的情感Agent引入到组织和联盟中,提出情感因子,对形成联盟的Agent的能力贡献多少进行评估,能充分体现了动态环境中情感Agent的各个情感分量的变化及这种变化对Agent行为的影响。因此,提出基于情感组织Agent的联盟形成策略,引入组织Agent的情感因子对形成联盟过程中的能力贡献进行评估,体现额外效用分配方法有效性、简单性、动态性、时效性,也使整个系统更趋于人性化,显示出协商机制的公平合理性。

一种基于势结构分组思想的任一时间联盟结构生成

联盟形成是多agent系统中的一个关键问题,找到最优的联盟结构是NP-完全的.Sandholm和Larson等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能完全解决的问题.在任务分配等实际问题中,不同联盟存在同势同值的特征,或同势的2个联盟的值相差不大.研究了最优势结构生成问题,分析了基于势结构的分组思想,并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法.算法在最小搜索之后给出进一步降低限界至2的搜索,也讨论了限界从2降到1的过程中由底向上的补充搜索.从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法,是基于势结构的联盟生成问题的一个重要进展.

基于蚁群算法的组合拍卖胜者决定问题求解

胜者决定问题是组合拍卖中研究的一个重要问题.在组合拍卖的多Agent系统中,以第一价格密封拍卖方式为背景,针对胜者决定问题的一般模型,提出运用蚁群算法求最优解.该算法在搜索过程中随机放置蚂蚁,扩大了解的搜索空间,通过改变局部信息素浓度,加快了算法的收敛速度,有效缓解了算法容易出现的早熟停滞现象.与遗传算法相比,实验表明蚁群算法在早期就容易达到较好的最优解,收敛速度较快且求解质量较稳定.

多Agent模糊概率信念逻辑

在经典信念形式化研究中,信念在某一可能世界中的真值取值范围是{0,1}。基于新模糊集合论给出信念真值的模糊真值计算方法,将信念的真值取值范围推广到[0,1]。在这样模糊逻辑框架下,将广义概率Aumann语义推广到广义模糊概率Aumann语义,从而建立多Agent模糊概率信念逻辑。在该逻辑中,给出多Agent模糊概率信念逻辑的语法和语义,并且证明了该逻辑系统的可靠性。

基于神经网络的Agent电子商务协商模型

提出一个在电子商务中能辅助用户网上采购的智能Agent协商模型,并对模型进行仿真实验,以验证模型的有效性。模型的构造基于BP神经网络,通过对用户的购物偏好训练学习,使Agent获得一组包含用户偏好特征的规则信息并作为协商过程中推理的依据;每次协商的结果都作为学习样本,以提高Agent对市场变化的适应能力。