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

Efficient task allocation and path planningin heterogeneous multi-robot systems (MRS) remainsasignificant challengein industrial inspection contexts, particularly when robotsexhibit diversesensingcapabilitiesandmust operateacross spatially distributed sites. To address the limitations ofexact methodsand conventional heuristics, we proposea novel two-phaseenhanced geneticalgorithm(EGA) tailored for capability-constrained task assignment and route optimization. Thefirst phaseemploysa domain-specificchromosomeencodingto assign tasks whileenforcingrobot-measurement compatibility. Thesecond phaselocally refineseach robot’s path tominimizetravel distanceand improveload balancing. We benchmark theEGAagainst an exact mixed integer linear programming(MILP)model,astandard geneticalgorithm
(single-phase),a particleswarmoptimization (PSO)approach,and an adapted version of the bi-levelsurrogate-assisted evolutionary algorithm (BL-SAEA)across scenarios involvingup to 50 inspection sitesand 4 heterogeneous robots. Experimental results showthat our EGA consistently produces near-optimalsolutions,achievingaverage optimality gaps below1.5%, whilereducingcomputation times by up to 90% compared toMILP. Furthermore, thesecond phasesignificantly enhancesconvergencestability and solution robustness,especially in largescaleinstances. Theseresults demonstratethescalability and practicalsuitability of the proposedmethod for real-time, resource-constrained industrial inspectionmissions