Clustering Based Neural Combinatorial Optimization for Scanning Path Planning of Heterogeneous Multi-Agent System

An effective solution method is proposed for the scanning path planning problem of heterogeneous multi-agent systems. Target mission is divided into multiple task clusters by density clustering to balance the task difficulty. Afterwards, the method innovatively first performs path planning for each task cluster, then systematically allocates tasks by utilizing mixed-integer linear programming (MILP) based on the planning outcomes and the diverse capabilities within the heterogeneous system, ensuring that agents possess unique adaptability to tasks that align with their specific capabilities. In the optimization solving phase, a neural combinatorial optimization (NCO) algorithm based on graph neural network (GNN) is proposed. Through supervised learning and cross-instance parallel training, the automation of heuristic design and the enhancement of heuristic rules are achieved, avoiding the inefficiency and suboptimality of expert design and manual parameter tuning. Simulation results show that the algorithm has better performance in terms of task completion time, execution time and deviation rate, showing its application potential in the rapid task planning problem of heterogeneous multi-agent systems.