论文研究-一种基于执行代价和传输代价的多Agent系统任务分配的优化方法 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.26M 资料格式：pdf 举报版权申诉

weixin_39840588-11576936-4744300845404322260.pdf-第1页.png

第1页 / 共6页

weixin_39840588-11576936-4744300845404322260.pdf-第2页.png

第2页 / 共6页

weixin_39840588-11576936-4744300845404322260.pdf-第3页.png

第3页 / 共6页

weixin_39840588-11576936-4744300845404322260.pdf-第4页.png

第4页 / 共6页

weixin_39840588-11576936-4744300845404322260.pdf-第5页.png

第5页 / 共6页

weixin_39840588-11576936-4744300845404322260.pdf-第6页.png

第6页 / 共6页

文本预览

中国科技论文在线 http://www.paper.edu.cn 一种基于执行代价和传输代价的多 Agent 系统任务分配的优化方法1 孟海战，周伟，徐媛，蒋嶷川东南大学学习科学研究中心，南京 (210096) E-mail: mhaizhanseu@163.com 摘要：多 Agent 系统处理问题时，通常将问题分解成多个子任务，然后多个 Agent 协调合作进行处理，这就使任务分配成为多 Agent 系统处理问题的前提和基础。本文提出了一种基于执行代价和传输代价的任务分配的优化方法。文中首先建立了任务分配的模型，推导出评价任务分配优化效果的目标函数，最后通过实例说明了该分配机制对多 Agent 系统处理问题性能的影响。结果表明，该种优化方法能有效的分析多 Agent 系统处理问题时的性能。关键词：多 Agent 系统；任务分配；代价矩阵；目标函数 1. 概述任务分配问题是多 Agent 系统研究中的一个关键问题。随着科技的发展，问题的复杂度越来越高，一个 Agent 去独立处理一个问题已经变得越来越不现实，在这种情况下，多个 Agent 协商合作共同去完成某个问题的求解是必然的趋势。这就需要将一个问题去分解为多个子任务，然后分配给不同的 Agent 协作处理，这使任务分配成为解决问题的前提和基础。任务分配问题作为多 Agent 系统中的一个关键问题，一直受到广泛的关注。文献[1]构想出一种模型，以第二价格逆向拍卖策略作为分配策略进行分配，解决了自利性 Agents 在不确定变化的开放环境下的任务分配问题；文献[2]描述了一种基于单个 Agent 和它周围环境相交互的 Agents 的总体资源作为任务分配资源的一种分配策略，在该策略中，进行任务分配时，将一个交互群体的资源作为分配资源，有效的适应了复杂软件系统的特征，很大程度上降低了通信代价；文献[3]提出了一种新的契约方式，用于描述多个任务同时在多个 Agent 之间进行交换的规则，提出了一种新的算法，通过已分配任务在多个 Agent 之间的交换来降低整个团体的代价；文献[4]提出了任务分配问题的一个变种，将 Agent 衔接在社会网络中，通过网络将任务分配给 Agents 执行，在此基础上提出了一种分配算法，并在小世界网络、随机网络和无尺度网络中对算法的性能和扩展性进行了评估。上述文献虽从不同的角度去研究任务分配问题，但均未具体研究任务分配策略对多 Agent 系统处理问题的性能的影响，本文在上述研究的基础上，重点考虑任务执行代价和传输代价（协商代价和移动代价），建立了一种任务分配模型，通过研究对该分配模型下多 Agent 系统处理问题的性能分析来说明该方法在任务分配问题中具有很大的优化效果。 2. 多 Agent 系统中任务分配的描述 swaps K − 在传统的 Agent 技术研究中，任务分配问题一般是在以下情景中出现：当一个问题产生时，根据 Agent 系统中 Agent 的资源和能力进行分配。侧重于一个 Agent 独立去处理一个问题，这使得问题的执行效率不高，降低了系统处理问题的性能。在 MAS 技术的研究中，当一个问题产生时，往往将一个问题分解为多个任务，多个 Agent 通过协调合作共同处理问题。这种问题的处理方式，一方面利用多个 Agent 处理问题的能力，明显的提高了问题处理的效率，另一方面由于多个 Agent 之间需要协调、合作去处理问题，系统耗费大大提高。以往的 1 课题得到高等学校博士学科点专项科研基金（项目编号：200802861077）的资助。 -1-

中国科技论文在线 http://www.paper.edu.cn 研究重在如何进行任务分配，很少具体的从系统处理问题的性能方面去研究任务分配方式的优化效果。本文提出一种多 Agent 系统中任务分配的优化方法：综合考虑单个 Agent 处理问题时的执行代价和协调合作造成的系统耗费代价两个方面的因素，构建总体最小代价函数，推导出了用于评价任务分配优化程度的目标函数，利用目标函数对多 Agent 系统处理问题的性能进行了分析证明该方法的优化之处。 3. 数学模型和目标函数的构建依据对任务分配的描述，我们构建了整体代价矩阵、任务分配矩阵和传输代价矩阵，并推导出任务执行代价矩阵和总体最小代价函数，最后我们构建了用于评价多 Agent 系统处理问题的性能的目标函数。 3.1 任务分配模型当一个问题产生时，问题被分成 n 个任务，各个任务根据多 Agent 系统中的 Agent 能力进行分配。用矩阵的形式来表示执行代价，矩阵的行代表执行任务的 Agent，矩阵的列表示问题被分解的一些子任务，矩阵的元素表示该 Agent 执行该子任务的代价，我们称之为整体代价矩阵；基于整体代价矩阵，我们构建了任务分配矩阵和任务执行代价矩阵；接着，我们考虑 MAS 中多个 Agent 在执行任务时的传输代价，本文从协商代价矩阵和移动代价矩阵作为执行任务的传输代价。（1）整体代价矩阵设一个问题被分成 m 个子任务，MAS 系统中有 n 个 Agent 去处理该问题， Agent 执行 Agent 执行子任务i 的总子任务i 的代价为 ijc ，整体代价矩阵代价，包括时间耗费代价、资源耗费代价等。在 MAS 中任务执行时，时间耗费代价和资源耗费代价是最主要的代价，所以， ijc 可表述为： t βα + ， nmC × ＝（ ijc ），其中 ijc 为 j j r ij ijc ＝ ij 其中 ijt 、 ijr 分别表示执行该任务的时间代价和资源耗费代价； βα, 为相对系数，表示时间耗费代价和资源耗费代价在总执行代价中所占的权重，可根据具体的情况进行合理的调整；本文在研究分配机制时不考虑具体的耗费，只考虑整体耗费，故不考虑 βα, 的设定；同时，若 Agent 不能完成某子任务，我们设置它的代价为 F ( Fail )；（2）任务分配矩阵任务分配矩阵用于表述子任务i 是否被分配给 Agent 处理。基于该目的，我们对整体 j 代价矩阵进行变换，得到任务分配矩阵 nmA × ＝（ ija ），其中 when Agent j Executes i And c ij ≠ a ij = 1 ⎧ ， ⎪ ⎨ ⎪ ⎩ F ⎫ ； ⎪ ⎬ ⎪ ⎭ ； i = ,2,1 , ⋅⋅⋅ jm ; = ,2,1 , ⋅⋅⋅ n ; ； otherwise F ，（3）任务执行代价矩阵整体代价矩阵表明了 Agents 具有的处理问题的能力的总代价，任务分配矩阵表示 Agent 实际是否分配到某个子任务，由整体代价矩阵和任务分配矩阵，我们得到任务执行代价矩阵，用来表示 Agents 实际处理问题时所耗费的执行代价，其中 ijc = ijc × ija ；并 C =× nm c ( ij ) -2-

中国科技论文在线 http://www.paper.edu.cn 规定：当 ijc =F 或 ija =F 时， ijc =F，表示 Agent 未处理任务i ； j （4）传输代价矩阵一个问题产生后分成 m 个子任务，被分配给 n 个 Agent 处理，在 n 个 Agent 共同协作处理任务时，会耗费整个系统的资源，比如多个 Agent 协商时必须进行通信协商，会耗费系统的能量；同时，相对于单个 Agent 执行时增加了通信协商的时间，我们把这些耗费统一定义为协商代价，对应的耗费矩阵称为协商代价矩阵。在多 Agent 协商合作处理问题时，承担各子任务的 Agent 往往需要移动到一定的主机去处理自己承担的子任务，在具有紧前紧后关系(即某个子任务的执行以另外已完成的子任务为前提)的子任务中尤其突出，这时 Agent 的移动耗费也成为耗费中的关键一部分，我们定义其为移动代价，对应的耗费矩阵为移动代价矩阵，本文的研究中以 Agent 之间的欧氏距离定义为它们的移动代价。本文的研究是在无向 Agent 也可以与拓扑结构图下研究的，即：若 Agent 进行协商通信，明显，在无向拓扑结构图中，协商代价矩阵和移动代价矩阵均为对 Agent 通信协商，我们认为 Agent 能够与 i j j i 称矩阵，这样我们就可以将两个代价矩阵变换到一个代价矩阵，我们称该矩阵为传输代价矩阵，记为 P =× nn ( p ij ) ，矩阵的行和列均表示 n 个 Agent： pij = ⎧ 协商代价， ⎪ when ⎨ ⎪ 移动代价， ⎩ ,0 when = when i j i < i > j j ⎫ ⎪ ⎬ ⎪ ⎭ ； i , j = ,2,1 , ⋅⋅⋅ n ; 设 P（k）为 k 个 Agent 协商合作处理任务时的代价函数，则 P（k）= p +∑ ( ij p ) ji ；当一个 Agent 单独处理一个问题时，P（1）= p +∑ ( ii p ii ) =0；（5）总体最小代价函数在上面构建的任务执行矩阵和传输代价矩阵的基础上，每个子任务的将其分配给参与问题处理的的 Agents 执行该子任务时所需代价最小的 Agent；本文没有考虑各个 Agent 在协商时的方向性，所以，在处理问题的 Agents 确定时，系统的传输代价也已经确定；由此，我们得到多 Agent 系统处理某个问题的总体最小代价函数的表达式： } ∑ ; + } ; + xD )( kP )( min min ∑ ∑ , , ⋅⋅⋅ , , ⋅⋅⋅ { c { c )1( + = = p p c c c c ) ( i 2 i 2 in , i 1 , i 1 in ij ji m i 1 = m i 1 = 3.2 多 Agent 系统的性能分析在多 Agent 系统中，系统处理问题的性能相对于参与问题处理的 Agent 个数是一个非递减函数[5]。根据我们构建的任务分配矩阵，我们引入评价 MAS 系统性能的影响因子η，定义为： )( λη = m k − ∑= ( i 1 = n ∩ j = k a − ) ij ，其中λ为系统的参与度，表示参与处理问题的 Agent 个数；k 为大于 1 的系数，用来λ值对 MAS 系统性能的影响程度；∩n j 1= ija 表示 aa , i 1 i 2 , , ⋅⋅⋅ a in = iF , = ,2,1 , ⋅⋅⋅ m 时才表示 Agent 未参与问题所有子任务的 j 逻辑与的结果，因为只有当处理，所以 F n ∩ j 1 = FFF = , aij n ∩ j 1 = 11 = 。 -3-

中国科技论文在线 3.3 目标函数的构建 http://www.paper.edu.cn 为了实现在基于单个 Agent 处理问题时的执行效率和多个 Agent 协调合作处理问题造成的系统耗费之间的平衡的前提下提高多 Agent 系统的性能，需要有一个目标函数对系统的整体性能的影响进行评价，根据本文提出的总体最小代价函数和 MAS 性能影响因子，我们构建了评价多 Agent 系统性能的目标函数 )(xG ： xG )( η ×= xD )( = ( m ∑ i 1 = n ∩ j 1 = − k a ij ) × min ⎡ ⎢ ⎣ m ∑ i 1 = { c , c i 2 i 1 , , ⋅⋅⋅ c in } ; + ∑ ( p ij + p ) ji ⎤ ⎥ ⎦ )2( 构建了目标函数后，在考虑单个 Agent 的处理问题的效率和多个 Agent 协调合作处理问题平衡的条件下，评价多 Agent 系统处理问题的性能， )(xG 越小，表明多 Agent 系统处理问题的性能越高。 4. 实例分析为了探讨该模型下多 Agent 系统的性能，我们设计一个实例对此进行分析。设已经存在一个整体代价矩阵 66×C ，表示有多 Agent 系统中有６个 Agent 去处理一个被 Agent 分成６个子任务的问题，矩阵元素为各个 Agent 处理子任务的执行代价；同时， j ）的拓扑结构图如图 1 所示，在本文中我们用欧氏距离表示其移动代价，用 ,2,1 =j ⋅⋅⋅ 6, （权重表示其协商代价。 C =× 66 3 6 5 4 2 5 ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 4 3 F 6 3 4 2 5 6 5 4 3 5 F 4 3 2 6 2 4 3 3 4 3 4 3 3 6 F 4 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ 1 A 2 =× 66 A 1 =× 66 A 3 =× 66 1 1 1 1 1 1 1 F F F F F F F FFFF F 1 FF FFFFF F （1) 根据整体代价矩阵，我们构建相应的分配矩阵： FFFF ⎡ ⎢ FFFF ⎢ FFFF ⎢ ⎢ FFFF ⎢ ⎢ FFFF ⎢ FFFF ⎢ ⎣ FFFF ⎡ ⎢ F ⎢ FFFF ⎢ ⎢ FFF 1 ⎢ ⎢ 1 ⎢ FFFF ⎢ ⎣ FFFFF 1 1 FFFFF FFFFF 1 FFF 1 FFFF 1 FF FFFFF FFF 1 FFFFF FFFFF 1 1 FFFFF FF F 1 FFFFF FFF 1 FF ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ 其中，矩阵 iA 66× 分别表示问题产生时由i 个 Agent 对问题进行处理所对应的分配矩阵；在对子任务进行分配时，当多个参与处理问题的 Agent 执行某个子任务的执行代价相同时， FF ⎡ ⎢ FFFFF ⎢ FFFFF ⎢ ⎢ 1 ⎢ ⎢ 1 ⎢ FF ⎢ ⎣ FF ⎡ ⎢ F 1 ⎢ FFFFF ⎢ ⎢ FFF ⎢ ⎢ 1 ⎢ FFFF ⎢ ⎣ FFF 1 1 FFFFF FFFFF FFF 1 FFF 1 FFFF 1 FF FFFFF F ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 1 1 1 1 A 4 =× 66 A 5 =× 66 A 6 =× 66 1 -4-

中国科技论文在线 http://www.paper.edu.cn 选取该 Agent 与其它 Agent 之间的传输代价较小的作为执行该子任务的 Agent。（2）根据拓扑结构图得到相对于产生问题的传输代价矩阵 66×P ，矩阵的上三角部分表示其协商代价，下三角部分表示其移动代价； 66P =× 321320 313402 232042 250424 404445 022546 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 有 Agent 之间的拓扑结构图可以看出，Agent1 与 Agent6、Agent2 与 Agent3、Agent4 与表 Agent5 不能直接协商时，将它们之间的间接协商总代价作为其协商代价，即示其间接协商总代价。 p 16 p p 45 23 , , （3）根据整体代价矩阵和分配矩阵得到问题处理的执行代价矩阵，有推导出的目标函数对多 Agent 系统处理问题的性能进行评价；系数 k 的值根据实际的多 Agent 系统进行设置，在本文的实例中，我们设 k=2，将相应数据带入公式（1）、（2），得到 MAS 性能结果，如表 1 所示：表 1 MAS 性能分析 66×A 1 19 19.00 66×A 3 36 4.00 66×A 4 53 3.31 66×A 5 76 3.04 66×A 6 106 2.94 Tab.1 Analysis of MAS’s Performance 66×A 2 28 D(x) G(x) 7.00 在基于基于执行代价和传输代价的条件下，我们根据提出的任务分配机制对多 Agent 系统处理问题的性能进行了评价，结果显示，随着参与处理问题的 Agent 的数目增多，系统处理问题的性能逐渐越来越高，这是由于多个 Agent 处理问题时需要交互合作，其消耗的系统总代价会随着升高；但当参与问题处理的 Agent 数目增到一定程度时，多 Agent 系统处理问题的性能提高的变得较慢，这是由于过多的 Agent 参与问题处理时，对系统资源会造成一定的浪费，从而使系统处理问题的能力增长变慢。 5. 总结本文提出了一种在考虑单个 Agent 执行效率和多个 Agent 传输代价条件下的任务分配方式，并建立了相应的目标函数，通过一个实例说明了在该模型下增加参与问题处理的 Agent 数目对多 Agent 系统处理问题的性能的影响；通过我们提出的任务分配方式，可以对具体系统处理问题的性能进行评测，从而确定最优的参与问题处理的 Agent 个数，减少了资源的而浪费，在多对多的问题处理中大大提高系统处理问题的能力，这对实际多 Agent 系统处理问题能力的提高有很大的意义。我们下一步的工作是将多 Agent 系统衔接在真实的的随机网络、小世界网络、无尺度网络等具有不同交互结构特性网络拓扑结构中进行实验模拟，研究在该任务分配机制下不同特性的多 Agent 系统处理问题时的性能变化；同时，我们将考虑有向拓扑结构下的任务分配模型对系统处理问题的性能的影响。 -5-

中国科技论文在线 http://www.paper.edu.cn 参考文献 [1] David Sarne, Sarit Kraus. Solving the Auction-Based Task Allocation Problem in an Open Environment. In Proc. of AAAI-2005: 164-169. [2] Yichuan Jiang, Jiuchuan Jiang. Contextual Resource Negotiation-Based Task Allocation and Load Balancing in Complex Software Systems. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 20, NO. 5, MAY 2009: 641-653. [3] Xiaoming Zheng, Sven Koenig. K-Swaps: Cooperative Negotiation for Solving Task-Allocation Problems. In Proc. Of IJCAI-2009: 373-378. [4] Mathijs de Weerdt, Yingqian Zhang, Tomas Klos. Distributed Task Allocation in Social Networks. In Proc. ofAAMAS-2007: 500-507. [5] Michael W. An introduction to Multi-Agent Systems[M].石纯一,译.北京:电子工业出版社,2003. An optimized task allocation method based-on implementation and transmission costs in MAS Meng Haizhan, Zhou Wei, Xu Yuan, Jiang Yichuan Research Center for Learning Science, Southeast University, Nanjing, PRC (210096) Abstract In Multi-Agent System(MAS), divided-and-conquer method is a main way to solve problems. In this paper, we propose an optimized task allocation method based on the implementation and transmission costs in MAS. First, we build a model for task allocation problem, using this model, and then we deduce the objective function for evaluating the effect of task allocation in MAS. Finally, we use a case to prove our optimized model to solve the task allocation problem is more effective. Keywords: Multi-Agent Systems; task allocation; cost matrix; objective function -6-

分享到：

赞收藏

资料库

论文研究-一种基于执行代价和传输代价的多Agent系统任务分配的优化方法 .pdf

相关推荐

开发技术

热门标签

最新资料