TY - GEN
T1 - An Improved Multi-Population Genetic Algorithm for Multi-Robot Task Assignment With Complex Precedence Constraints
AU - Bai, Xiaoshan
AU - Jiang, Haoyu
AU - Zhang, Bo
AU - Wu, Zongze
N1 - Publisher Copyright:
© Beijing HIWING Scientific and Technological Information Institute 2025.
PY - 2025
Y1 - 2025
N2 - This article investigates the multi-robot task assignment problem with complex precedence constraints, where multiple robots need to visit a set of target locations respecting the prescribed order/sequence precedence constraints. These precedence constraints include strong precedence constraints and weak precedence constraints: 1) a strong precedence constraint between two target locations implies that the same robot should uninterruptedly visit these two locations, and 2) a weak precedence constraint between two target locations implies that the time for visiting one target location should be earlier/later than the other one. The objective is to minimize the time for the last target location to be visited while satisfying all precedence constraints. First, it is analyzed that the studied multi-robot task assignment problem is NP-hard. A lower bound on the optimal solution is constructed based on graph theory to measure the proximity of a suboptimal solution to the optimal one. Then, an improved multi-population genetic algorithm is proposed, in which two crossover operators tailored for precedence constraints and an adaptive termination strategy are designed. Simulation results show that the designed algorithm exhibits advantages in solving the multi-robot task assignment problem with complex precedence constraints compared with the existing iterative auction algorithm, adaptive large neighborhood search algorithm, and the co-evolutionary multi-population genetic algorithm.
AB - This article investigates the multi-robot task assignment problem with complex precedence constraints, where multiple robots need to visit a set of target locations respecting the prescribed order/sequence precedence constraints. These precedence constraints include strong precedence constraints and weak precedence constraints: 1) a strong precedence constraint between two target locations implies that the same robot should uninterruptedly visit these two locations, and 2) a weak precedence constraint between two target locations implies that the time for visiting one target location should be earlier/later than the other one. The objective is to minimize the time for the last target location to be visited while satisfying all precedence constraints. First, it is analyzed that the studied multi-robot task assignment problem is NP-hard. A lower bound on the optimal solution is constructed based on graph theory to measure the proximity of a suboptimal solution to the optimal one. Then, an improved multi-population genetic algorithm is proposed, in which two crossover operators tailored for precedence constraints and an adaptive termination strategy are designed. Simulation results show that the designed algorithm exhibits advantages in solving the multi-robot task assignment problem with complex precedence constraints compared with the existing iterative auction algorithm, adaptive large neighborhood search algorithm, and the co-evolutionary multi-population genetic algorithm.
KW - Complex precedence constraints
KW - Improved multi-population genetic algorithm
KW - Lower bound
KW - Multi-robot task assignment
UR - https://www.scopus.com/pages/publications/105003148182
U2 - 10.1007/978-981-96-3560-3_52
DO - 10.1007/978-981-96-3560-3_52
M3 - 会议稿件
AN - SCOPUS:105003148182
SN - 9789819635597
T3 - Lecture Notes in Electrical Engineering
SP - 589
EP - 601
BT - Proceedings of 4th 2024 International Conference on Autonomous Unmanned Systems (4th ICAUS 2024)
A2 - Liu, Lianqing
A2 - Niu, Yifeng
A2 - Fu, Wenxing
A2 - Qu, Yi
PB - Springer Science and Business Media Deutschland GmbH
T2 - 4th International Conference on Autonomous Unmanned Systems, ICAUS 2024
Y2 - 19 September 2024 through 21 September 2024
ER -