一种基于P学习的分布式并行多任务分配算法

并行多任务分配是多agent系统中极具挑战性的课题, 主要面向资源分配、灾害应急管理等应用需求, 研究如何把一组待求解任务分配给相应的agent联盟去执行. 本文提出了一种基于自组织、自学习agent的分布式并行多任务分配算法, 该算法引入P学习设计了单agent寻找任务的学习模型, 并给出了agent之间通信和协商策略. 对比实验说明该算法不仅能快速寻找到每个任务的求解联盟, 而且能明确给出联盟中各agent成员的实际资源承担量, 从而可以为实际的控制和决策任务提供有价值的参考依据.

A Distributed Algorithm for Parallel Multi-task Allocation Based on Profit Sharing Learning

Task allocation via coalition formation is a fundamental research challenge in several application domains of multi-agent systems (MAS), such as resource allocation, disaster response management, and so on. It mainly deals with how to allocate many unresolved tasks to groups of agents in a distributed manner. In this paper, we propose a distributed parallel multi-task allocation algorithm among self-organizing and self-learning agents. To tackle the situation, we disperse agents and tasks geographically in two-dimensional cells, and then introduce profit sharing learning (PSL) for a single agent to search its tasks by continual self-learning. We also present strategies for communication and negotiation among agents to allocate real workload to every tasked agent. Finally, to evaluate the effectiveness of the proposed algorithm, we compare it with Shehory and Kraus' distributed task allocation algorithm which were discussed by many researchers in recent years. Experimental results show that the proposed algorithm can quickly form a solving coalition for every task. Moreover, the proposed algorithm can specifically tell us the real workload of every tasked agent, and thus can provide a specific and significant reference for practical control tasks.