An enhanced genetic algorithm for optimized task allocation and planning in heterogeneous multi-robot systems

Abstract

Efficient task allocation and path planning in heterogeneous multi-robot systems (MRS) remains a significant challenge in industrial inspection contexts, particularly when robots exhibit diverse sensing capabilities and must operate across spatially distributed sites. To address the limitations of exact methods and conventional heuristics, we propose a novel two-phase enhanced genetic algorithm (EGA) tailored for capability-constrained task assignment and route optimization. The first phase employs a domain-specific chromosome encoding to assign tasks while enforcing robot-measurement compatibility. The second phase locally refines each robot’s path to minimize travel distance and improve load balancing. We benchmark the EGA against an exact mixed integer linear programming (MILP) model, a standard genetic algorithm (single-phase), a particle swarm optimization (PSO) approach, and an adapted version of the bi-level surrogate-assisted evolutionary algorithm (BL-SAEA) across scenarios involving up to 50 inspection sites and 4 heterogeneous robots. Experimental results show that our EGA consistently produces near-optimal solutions, achieving average optimality gaps below 1.5%, while reducing computation times by up to 90% compared to MILP. Furthermore, the second phase significantly enhances convergence stability and solution robustness, especially in large-scale instances. These results demonstrate the scalability and practical suitability of the proposed method for real-time, resource-constrained industrial inspection missions.