Heuristic routing algorithm toward scalable distributed generalized assignment problem

Yang Xu

doi:10.1007/s00500-016-2388-3

Return

Heuristic routing algorithm toward scalable distributed generalized assignment problem

2016-10-06

PRE

Yang Xu *

Xiaofeng Wang

Tingting Sun

DOI：10.1007/s00500-016-2388-3

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Multi-agent system

D-GAP

Heuristic routing algorithm

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.