Research on Multi-Objective Multi-Robot Task Allocation by Lin–Kernighan–Helsgaun Guided Evolutionary Algorithms

Abstract

Multi-robot task allocation (MRTA) and route planning are crucial for a large-scale multi-robot system. In this paper, the problem is formulated to minimize the total energy consumption and overall task completion time simultaneously, with some constraints taken into consideration. To represent a solution, a novel one-chromosome representation technique is proposed, which eases the consequent genetic operations and the construction of the cost matrix. Lin–Kernighan–Helsgaun (LKH), a highly efficient sub-tour planner, is employed to generate prophet generation beforehand as well as guide the evolutionary direction during the proceeding of multi-objective evolutionary algorithms, aiming to promote convergence of the Pareto front. Numerical experiments on the benchmark show the LKH guidance mechanism is effective for two famous multi-objective evolutionary algorithms, namely multi-objective evolutionary algorithm based on decomposition (MOEA/D) and non-dominated sorting genetic algorithm (NSGA), of which LKH-guided NSGA exhibits the best performance on three predefined indicators, namely C-metric, HV, and Spacing, respectively. The generalization experiment on a multiple depots MRTA problem with constraints further demonstrates the effectiveness of the proposed approach for practical decision making.