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.

Task allocation plays an important role in multi-robot systems regarding team efficiency. Conventional heuristic or meta-heuristic methods face difficulties in generating satisfactory solutions in a reasonable computational time, particularly for large-scale multi-robot task allocation problems. This paper proposes a novel graph deep-reinforcement-learning-based approach, which solves the problem through learning. The framework leverages the graph sample and aggregate concept as the encoder to extract the node features in the context of the graph, followed by a cross-attention decoder to output the probability that each task is allocated to each robot. A graph normalization technique is also proposed prior to the input, enabling an easy adaption to real-world applications, and a deterministic solution can be guaranteed. The most important advantage of this architecture is the scalability and quick feed-forward character; regardless of whether cases have a varying number of robots or tasks, single depots, multiple depots, or even mixed single and multiple depots, solutions can be output with little computational effort. The high efficiency and robustness of the proposed method are confirmed by extensive experiments in this paper, and various multi-robot task allocation scenarios demonstrate its advantage.