A novel memetic algorithm for distributed shape formation of swarm robots with both acceleration and velocity constraints

This article investigates the problem of distributed shape formation (DSF) in swarm robot systems. DSF involves each robot autonomously selecting and moving toward a target point to achieve a desired shape. A comprehensive mathematical model for DSF of swarm robots is developed, capturing the relationships among states, behaviors, and kinematics constraints. A novel memetic algorithm (MA) is proposed to generate and evolve behavior strategies that enable real-time decision-making for each robot. The proposed MA includes specifically designed behaviors to address subproblems within DSF, such as target selection conflict, collision, and deadlock. These behaviors, along with propositions about the states of robots, are utilized to construct strategies by a tree-based encoding scheme. An evaluation mechanism based on multiagent simulation is devised to evaluate the performance of strategies. Additionally, a repair mechanism is introduced to eliminate redundant or unreachable subtrees in a strategy. To further improve the performance of generated strategies, tree-based local search operators are employed to exploit the neighborhood of the best strategy found yet during the iteration. Experimental results and the Wilcoxon rank-sum test show that the strategies generated by the proposed MA outperform state-of-the-art algorithms, significantly reducing the completion time of DSF.