Problem Specific Genetic Differential Evolution Algorithm for Multi-skill Resource-constrained Project Scheduling of Collaborative Multi-Robot Systems for Search and Rescue

Abstract

Multi-Robot system can be applied to search and rescue (SAR) tasks in complex environment. This paper focuses on resource scheduling and task allocation of cooperative multi-robot system for SAR (RSTA-RSSAR). RSTA-RSSAR is an extention of MSRCPSP. In RSTA-RSSAR, skills of multi-robot system considered from both depth and breadth. And resouece transfer time between tasks are considered. Meanwhile, Processing time of activities in RSTA-RSSAR changes with skill ability resouces provided. In order to solve the problem effectively, a genetic differential evolution algorithm (PS-GDEA) is proposed. An encoding, decoding and population initialization methods is designed according to the characteristics of RSTA-RSSAR. In this algorithm, a multi-attribute choosing method based on Shannon entropy is proposed. Meanwhile, a genetic algorithm with new selection, crossover and mutation operators is used to generate offspring and a priority based differential evolution strategy is used to evolute parents. The effectiveness of the algorithm is obtained by experiments on test cases. Compared with the classical genetic algorithm for msrcpsp, the proposed algorithm has better performance.