论文部分内容阅读
任务/资源分配是计算机科学领域一个重要的研究问题,多Agent系统的特点决定了其任务分配与传统的任务分配有很大的不同。本文利用机制设计的方法研究集中式和分布式多Agent系统任务分配问题,更具体地,本文考虑一类特殊的多Agent系统:系统中提供资源的理性Agent供给能力是有限的,且具有较复杂的成本结构。
本文介绍了机制设计的基本理论,重点研究了两类基于市场的任务分配机制--VCG机制和CDA机制。VCG机制可以求出最优解,但只能用于求解集中式多Agent系统任务分配问题;CDA机制是分布式的,但无法保证最优解。
本文首先剖析了一个改进的VCG机制,其支付由效用转移和惩罚两部分构成,惩罚方案不仅保证了该VCG机制的激励相容特性,也对无法确定自身容量的Agent具有鲁棒性,该VCG机制的最优解可由中心在伪多项式时间内求得,本文用其求解了集中式多Agent系统的最优分配。
对于分布式多Agent系统任务分配问题的求解,本文考虑多单元CDA机制,买者和卖者分别连续地向系统提交报价及其需求量和供给容量,当买卖方的价格匹配时,即买者的出价高于卖者的要价,且卖方的需求能一次性满足时,匹配的买卖方即成功进行一次交易,随后市场出清一次。CDA机制通过买卖方的交互实现系统任务/资源的分配,并且是激励相容的。为让系统中Agent更加理性地参与市场交互,本文提出了ZIP2策略,借助一个简单的机器学习算法,让Agent根据市场历史信息预测将来市场环境,并不断调整自己的利润率,以保证其市场竞争力。实验表明,对“无政府”的分布式多Agent系统资源分配问题的求解,该ZIP2-CDA机制是有效的,且其求解效率高于采用零智能策略实现的CDA机制。
在此基础上,本文探讨了市场机制在传感器网络环境的应用,分析了传感器网络任务分配问题,其优化目标就是在满足网络中探测任务需求和各传感器节点电量约束的前提下,最小化整个网络消耗的电量。并用扩展的VCG机制和ZIP2-CDA机制求解了该网络环境下的任务分配问题。在用ZIP2-CDA机制求解该问题时,每个传感器节点的报价取决于其电量消耗的情况。实验表明,当网络中的数据需求量越来越接近于网络中所供给的总数据量时,ZIP2-CDA所求得的解越接近于集中式机制求得的最优解。