Applying Machine Learning in Designing Distributed Auction for Multi-agent Task Allocation with Budget Constraints

Chen Luo, Qinwei Huang, Fanxin Kong, Simon Khan, Qinru Qiu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The multi-agent task allocation can be solved in a distributed manner using Consensus-Based Bundle Algorithm (CBBA). Under this distributed auction process, each agent greedily maximizes the global score, which is the difference of the reward and the cost, through an iterative bundle construction and conflict resolution procedure. The distributed algorithm has provable convergence and guarantees 50% optimality if the score function satisfies the condition of diminishing marginal gain (DMG). While the previous work focuses on unconstrained optimization of rewards, this paper aims at applying CBBA to task allocation with budget constraints. Several heuristics were proposed to build the bundle and calculate the bidding scores as improvements to the original CBBA algorithm. We then prove that some of the new score functions are DMG, and therefore guarantees the convergence of the distributed process. We also show that these heuristic extended CBBAs are Pareto efficient; using different heuristic extensions under different scenarios is more efficient than consistently using the same one. To decide which heuristic extension should be used for a given task allocation problem, a graph convolutional neural network (GCN) model is trained to extract and analyze the features of the constrained optimization problem as a graph, and predict the potential performance (i.e., global reward) of different heuristic extensions. Based on the prediction, the best heuristic extension will be selected. Experimental results show that the predicted reward has more than 0.98 correlation with the actual reward and for 70% of time the prediction guided selection picks the best heuristic extension for the budget constrained task allocation problem.

Original languageEnglish (US)
Title of host publication2021 20th International Conference on Advanced Robotics, ICAR 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages356-363
Number of pages8
ISBN (Electronic)9781665436847
DOIs
StatePublished - 2021
Event20th International Conference on Advanced Robotics, ICAR 2021 - Ljubljana, Slovenia
Duration: Dec 6 2021Dec 10 2021

Publication series

Name2021 20th International Conference on Advanced Robotics, ICAR 2021

Conference

Conference20th International Conference on Advanced Robotics, ICAR 2021
Country/TerritorySlovenia
CityLjubljana
Period12/6/2112/10/21

Keywords

  • GCN
  • Graph embedding
  • Limited budget
  • Multi-agent
  • Task allocation

ASJC Scopus subject areas

  • Artificial Intelligence
  • Human-Computer Interaction
  • Software

Fingerprint

Dive into the research topics of 'Applying Machine Learning in Designing Distributed Auction for Multi-agent Task Allocation with Budget Constraints'. Together they form a unique fingerprint.

Cite this