摘要：目前大部分Agent联盟问题的研究在考虑任务分配时，通常认为任务之间是孤立的，任务与任务之间不存在任何联系。本文认为在Agent联盟问题中各个子任务之间具有复杂的逻辑依赖关系，这种逻辑依赖关系不仅使得子任务在完成次序上有先后之分，而且也使相邻任务之间在协作过程中产生了转移成本。基于这种背景，本文给出了一种基于图论思想的算法来解决在该环境中的Agent联盟问题，讨论了在规范化的逻辑依赖关系下如何将最优联盟成本转化为求解图的最短路径问题，并且分析了算法的时间复杂度，最后的实验结果表明，算法具有良好的运行性能。

关键词：agent联盟 逻辑依赖关系 转移成本 

单位：上海交通大学计算机系协同计算与智能技术研究室 上海200240 上海理工大学光电信息与计算机工程学院 上海200093