面向复杂任务结构的Agent联盟算法  

Agent Coalition Algorithm for Complex Task Structure

作　　者：傅一峰[1] 曹健[1] 李明禄[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200240

出　　处：《小型微型计算机系统》2011年第3期402-406,共5页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2007AA01Z137)资助;国家自然科学基金项目(60873230)资助;上海市科委基础研究重点课题项目(08JC1411700)资助;教育部新世纪优秀人才计划项目(NCET-08-0347)资助

摘　　要：Agent联盟形成是多Agent系统的一个基本操作.多个Agent往往需要形成联盟来协作完成任务或者提高联盟体的能力.现有的Agent联盟算法并不考虑任务内部的结构.本文则考虑一类具有复杂内部结构的任务.任务由一组子任务构成,子任务之间存在着逻辑依赖关系,并且以BPMN的流程形式描述.本文还在此基础上加入了对相邻子任务之间的转移成本的考虑.并且本文提出了一种基于动态规划的多项式时间算法来解决此类加入了逻辑依赖关系和转移成本因素的Agent联盟问题.Agent Coalition Formation is a basic operation in a Multi-Agent System （ MAS ）. Agents usually need to join an agent coalition in order to complete tasks in a collaborative way or to improve the capability of the coalition. Currently, the existing coalition formation algorithms do not take the internal task structure into consideration. In this paper, we consider the complex internal structure of the tasks. A task consists of a set of sub-tasks. The logical dependency between the subtasks is also considered in this paper. The logic dependency is described by BPMN, which allows the task to be a process or workflow. We also consider the transfer cost between the adjacent sub-tasks in this paper. Finally, we propose an algorithm with polynomial time complexity on the basis of Dynamic Planning, to solve the agent coalition problem with logical dependency and transfer cost.

关 键 词：Agent联盟问题 逻辑依赖关系 转移成本 动态规划 BPMN 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]