Paper Info
Title
Improving Asynchronous Search for Distributed Generalized Assignment Problem
Abstract
Distributed Generalized Assignment Problem (D-GAP) is very popular in scalable multi-agent systems. However, existing algorithms are not effective or efficient in large scale or highly dynamic domains due to the limited communication and computation resource. In this paper, we present a novel approach to address this issue. To reduce communication, we propose a decentralized model for agents to jointly search for optimized solutions. 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. Finally, we present a simulation to demonstrate the feasibility and efficiency of our algorithm.
Year
DOI
Venue
2012
10.1109/WI-IAT.2012.142
IAT
Keywords
Field
DocType
future similar search,generalized assignment problem,limited communication,local knowledge,decentralized heuristic algorithm,local view,d-gap,heuristic algorithm,asynchronous search,highly dynamic domains,massive multi-agent system,heuristic programming,multi-agent systems,optimal search,massive multiagent system,inferring knowledge,coordination,large scale domains,heterogeneous multi-agent system,scalable multiagent systems,limited communication overhead,scalable multi-agent system,distributed processing,agent decentralized model,distributed generalized assignment problem
Asynchronous communication,Incremental heuristic search,Heuristic (computer science),Computer science,Generalized assignment problem,Theoretical computer science,Computation,Distributed computing,Scalability,Overhead (business)
Conference
Volume
ISBN
Citations 
2
978-1-4673-6057-9
2
PageRank 
References 
Authors
0.37
5
3
Name
Order
Citations
PageRank
Tingting Sun120.37
Yang Xu2165.33
Qingyi He380.93