DGS-EDA: A double-guided sampling estimation of distribution algorithm for multi-robot task assignment as a permutation optimization problem
Blanca López, Luis E. Moreno, Concepción A. Monje · Swarm and Evolutionary Computation · 2025
Task assignment refers to the challenge of efficiently allocating tasks, duties, or resources among members of a system. This work investigates the multi-robot task assignment (MRTA) problem, modeled as a variation of the multiple traveling salesman problem (mTSP), and proposes novel approaches based on permutation optimization. An initial study evaluates state-of-the-art evolutionary algorithms (EAs), particularly focusing on estimation of distribution algorithms (EDAs), for their suitability in handling both A-permutation problems, where absolute positioning of the elements within the permutations mostly impact the quality of the solutions, like in the quadratic assignment problem (QAP); and R-permutation problems, where relative positioning dominates, like in the traveling salesman problem (TSP). The adaptation of these algorithms to B-permutation challenges, where both absolute and relative positioning are relevant, such as those presented by the mTSP, has received comparatively limited attention. In this work, addressing this gap led to the creation of a novel double-guided sampling estimation of distribution algorithm (DGS-EDA). The proposed methodologies strategically utilize adjacency relations and consecutive position sampling, guiding the search toward both the least and most observed edges and gene absolute positions to optimize solution paths. Their effectiveness is validated across both problem types; DGS-EDA ew improves mTSP results by targeting least observed edges, while DGS-EDA eb enhances TSP outcomes by focusing on the most observed edges. Comprehensive testing using TSPLIB instances demonstrates that the proposed DGS-EDA surpasses existing methods, effectively enhancing the exploration and exploitation of the solution space.