iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S00500-016-2388-3
Heuristic routing algorithm toward scalable distributed generalized assignment problem | Soft Computing Skip to main content
Springer Nature Link
Log in

Heuristic routing algorithm toward scalable distributed generalized assignment problem

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Amato C, Bernstein DS, Zilberstein S (2012) Optimizing memory-bounded controllers for decentralized POMDPs. In: arXiv preprint arXiv:1206.5258

  • Bloembergen D, Tuyls K, Hennes D et al (2015) Evolutionary dynamics of multi-agent learning: a survey. J Artif Intell Res 659–697

  • Brown KN (2015) A general framework for reordering agents asynchronously in distributed CSP. In: Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming 2015, vol 9255. Springer

  • Dunin-Keplicz B, Verbrugge R (2011) Teamwork in multi-agent systems: a formal approach. Wiley

  • Ferreira P, Boffo F, Bazzan A (2008) Using swarm-gap for distributed task allocation in complex scenarios. In: Massively multi-agent technology. Springer, Heidelberg, pp 107–121

  • Gaston M, desJardins M (2005) Social network structures and their impact on multi-agent system dynamics. In: Proceedings of the 18th International Florida Artificial Intelligence Research Society Conference

  • Kim Y, Lesser V (2014) A communication-constrained DCOP algorithm that combines features of ADOPT and action-GDL. In: Twenty-Eighth AAAI Conference on Artificial Intelligence

  • Korsah GA, Stentz A, Dias MB (2013) A comprehensive taxonomy for multi-robot task allocation. Int J Robot Res 32(12):1495–1512

  • Lesser V, Corkill D (2014) Challenges for multi-agent coordination theory based on empirical observations. In: Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems 1157–1160

  • Modi PJ, Shen W et al. (2002) Distributed constraint optimization and its application. Technical report ISI-TR-509, University of Southern California/Information Sciences Institute

  • Modi PJ, Shen WM, Tambe M et al (2003) An asynchronous complete method for distributed constraint optimization. AAMAS 3:161–168

    Google Scholar 

  • Nourjou R, Szekely P, Hatayama M et al (2014) Data model of the strategic action planning and scheduling problem in a disaster response team. J Disaster Res 9(3):381–399

    Article  Google Scholar 

  • Oh KK, Park MC, Ahn HS (2015) A survey of multi-agent formation control. Automatica 53:424–440

    Article  MathSciNet  MATH  Google Scholar 

  • Patriksson M (2015) The traffic assignment problem: models and methods. Dover Publication, Inc., Mineola

    Google Scholar 

  • Phillips AE, Waterer H et al (2015) Integer programming methods for large-scale practical classroom assignment problems. Comput Oper Res 53:42–53

    Article  MathSciNet  MATH  Google Scholar 

  • Riccio F, Patota F, Bella F, Borzi E, De Simone D, Suriani V. Iocchi L, Nardi D (2015) In: SPQR RoboCup 2015 Standard Platform League Team Description Paper

  • Sander PV, Peleshchuk D et al. (2002) A scalable, distributed algorithm for efficient task allocation. AAMAS 1191–1198

  • Sarratt T, Jhala A (2015) Rapid: a belief convergence strategy for collaborating with inconsistent agents. In: Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence. pp 1–6

  • Scerri P, Farinelli A, Okamoto S et al (2005) Allocating tasks in extreme teams. In: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems. ACM. pp 727–734

  • Sheikhalishahi M, Wallace RM, Grandinetti L et al (2016) A multi-dimensional job scheduling. Future Gener Comput Syst 54:123–131

    Article  Google Scholar 

  • Skobelev P, Simonova E, Zhilyaev A (2016) Using multi-agent technology for the distributed management of a cluster of remote sensing satellites. Complex Syst: Fundament Appl 90:287

    Article  MATH  Google Scholar 

  • Sun T, Xu Y, Improving He Q (2012) Search asynchronous, for distributed generalized assignment problem. In: International Conferences on IEEE/WIC/ACM, vol 2. pp 38–42

  • Vera S, Cobano JA et al (2015) Collision avoidance for multiple UAVs using rolling-horizon policy. J Intelligent Robot Sys 1–10

  • Xu Y, Scerri P, Sycara K et al (2005) An integrated token-based algorithm for scalable coordination. In: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, pp 407–414

  • Xu Y, Scerri P, Sycara K, Lewis M (2006) Comparing market and token-based coordination. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems. ACM. pp 1113–1115

  • Yeoh W, Yokoo M (2012) Distributed problem solving. AI Mag 33(3):53

    Article  Google Scholar 

Download references

Acknowledgments

This study was funded by NSFC 61370151 and 61202211, National Science and Technology Major Project of China 2015ZX03003012, Central University Basic Research Funds Foundation of China ZYGX2014J055 and the Science and Technology on Electronic Information Control Laboratory Project.

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, No. 2006, Xiyuan Ave, West Hi-Tech Zone, 611731, Chengdu, Sichuan, China

    Yang Xu, Xiaofeng Wang & Tingting Sun

Authors
  1. Yang Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaofeng Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tingting Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yang Xu.

Ethics declarations

Conflicts of interest

The authors declare that they have no conflict of interest

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Communicated by V. Loia.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, Y., Wang, X. & Sun, T. Heuristic routing algorithm toward scalable distributed generalized assignment problem. Soft Comput 22, 845–859 (2018). https://doi.org/10.1007/s00500-016-2388-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-016-2388-3

Keywords

Search

Navigation