| With the progress of the research in distributed artificial intelligence, cooperative agents have been applied to more dynamic, complex application domains. The key problem in those domains can commonly be modeled as Distributed Generalized Assignment Problem (D-GAP), such as task allocations in USAR and UAVs coordination. However, existing algorithms are not effective or efficient in large scale or highly dynamic domains due to the limited communication and computation resource. Therefore, how to improve the efficient and effective of solving D-GAP in large scale is the key problem in this paper.1. To reduce the communication in large scale or highly dynamic domains, we present a decentralized model for agents to jointly search for optimized solutions. In this framework, each agent works out a partial solution independently, and cooperatively achieves their common objectives. The decentralized control with the advantages, low communication cost, low computation, high flexibility, can well adapt to solving large-scale D-GAP.2. Considering the complexity of D-GAP in a massive multi-agent system, agents cannot perform the optimal search based on their local views, we propose a heuristic algorithm. By inferring knowledge from their previous communicated searches, agents are able to predict how to deploy their future similar searches more efficiently. If an agent can solve some parts of D-GAP well, similar searches will be sent to it. By taking the advantage of the accumulation effect to agents’ local knowledge, agents can independently make simple decisions with highly reliable performance and limited communication overheads.3. Finally, we present a simulation and the experiment results demonstrate the feasibility and efficiency of our algorithm. Moreover, we choose some typical application domains, such as UAVs coordination, urban search and rescue, large team coordination, to demonstrate our heuristic algorithm could handle the real problem with feasibility and efficiency. |
PDF Full Text Request