Adaptive Coordination Ant Colony Optimization for Multipoint Dynamic Aggregation

Guanqiang Gao, Yi Mei, Ya Hui Jia, Will N. Browne, Bin Xin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)

Abstract

Multipoint dynamic aggregation is a meaningful optimization problem due to its important real-world applications, such as post-disaster relief, medical resource scheduling, and bushfire elimination. The problem aims to design the optimal plan for a set of robots to execute geographically distributed tasks. Unlike the majority of scheduling and routing problems, the tasks in this problem can be executed by multiple robots collaboratively. Meanwhile, the demand of each task changes over time at an incremental rate and is affected by the abilities of the robots executing it. This poses extra challenges to the problem, as it has to consider complex coupled relationships among robots and tasks. To effectively solve the problem, this article develops a new metaheuristic algorithm, called adaptive coordination ant colony optimization (ACO). We develop a novel coordinated solution construction process using multiple ants and pheromone matrices (each robot/ant forages a path according to its own pheromone matrix) to effectively handle the collaborations between robots. We also propose adaptive heuristic information based on domain knowledge to promote efficiency, a pheromone-based repair mechanism to tackle the tight constraints of the problem, and an elaborate local search to enhance the exploitation ability of the algorithm. The experimental results show that the proposed adaptive coordination ACO significantly outperforms the state-of-the-art methods in terms of both effectiveness and efficiency.

Original languageEnglish
Pages (from-to)7362-7376
Number of pages15
JournalIEEE Transactions on Cybernetics
Volume52
Issue number8
DOIs
Publication statusPublished - 1 Aug 2022

Keywords

  • Ant colony optimization (ACO)
  • multipoint dynamic aggregation (MPDA)
  • multirobot system
  • task allocation

Fingerprint

Dive into the research topics of 'Adaptive Coordination Ant Colony Optimization for Multipoint Dynamic Aggregation'. Together they form a unique fingerprint.

Cite this