Paper Info
Title
Heuristic routing algorithm toward scalable distributed generalized assignment problem.
Abstract
Distributed generalized assignment problem (D-GAP) is very popular in scalable multi-agent systems. However, existing algorithms are either not effective or efficient in large-scale or highly dynamic domains owing to limited communications and computational resources. In this paper, we present a novel approach named intelligent routing algorithm (IRA) to address this issue. In IRA, in order to reduce communication load, a decentralized model for agents is proposed to jointly search for optimized solutions. Moreover, due to the complexity of distributed generalized assignment problem (D-GAP) in a massive multi-agent system where agents cannot perform optimal search based on their local views, we propose a heuristic algorithm that can find an approximate optimized solution. By inferring knowledge from their previous communicated searches, agents are able to predict how to deploy 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 advantage of the accumulation effect to agents’ local knowledge, agents can independently make simple decisions with highly reliable performance and limited communication overheads. The simulation and the experimental results demonstrate the feasibility and efficiency of our algorithm.
Year
DOI
Venue
2018
10.1007/s00500-016-2388-3
Soft Comput.
Keywords
Field
DocType
Multi-agent system, D-GAP, Heuristic routing algorithm
Computer science,Generalized assignment problem,Theoretical computer science,Multi-agent system,Artificial intelligence,Heuristic routing,Distributed computing,Overhead (business),Mathematical optimization,Heuristic (computer science),Algorithm,Scalable distributed,Machine learning,Scalability,Routing algorithm
Journal
Volume
Issue
ISSN
22
3
1433-7479
Citations 
PageRank 
References 
0
0.34
13
Authors
3
Name
Order
Citations
PageRank
Yang Xu1165.33
Xiaofeng Wang2410.54
Tingting Sun365.56