基于合同网的多agent任务分配分布式优化算法

针对合同网下的多agent系统，基于集合覆盖理论提出了一种解决子任务分配的严格启发式搜索算法；并分析了该算法的收敛性及渐进时间复杂度；证明了其搜索结果的上确界．该算法具有分布性，搜索空间缩减快，适合于中小型的多agent系统的子任务分配．

Distributed algorithm for task allocation in multi-agent system based on contract net

Coordination and cooperation are two major concerns in multi-agent system (MAS). How can a set of tasks be allocated properly to a group of agents is the key problem for coordination and cooperation. This was dons as. First, the concept of task coalition was defined and the task allocation was transformed into a set-covering problem, Second, the MAS was assumedts conformed to the contract net protocol, a heuristic algorithm for task allocation was proposed based on set-covering theory. Third, the convergence and supremum of the algorithm were proved, and the asymptotic time complexity was analyzed; At last, a simple example was given. With the property of the distributed calculation and quick reduction of the search space, the algorithm is suitable for task distributed problem solving for small and middle scale multi-agent system.