Automated Discovery of Efficient Behavior Strategies for Distributed Shape Formation of Swarm Robots by Genetic Programming

The distributed shape formation (DSF) of swarm robots is to form a specific shape, where each robot autonomously selects and moves to one target position in the desired shape. In this paper, we design some basic behaviors to construct behavior strategies, in which the swap selector and the obstacle avoidance planner are designed to guide robots in mitigating the negative effects of deadlock and collision during the DSF task. We propose a framework based on multi-agent simulation and genetic programming (GP) to automatically discover efficient behavior strategies followed by each robot to achieve DSF efficiently. The framework is distinguished by a centralized optimization of behavior strategies followed by each robot, along with strategy-driven decentralized decision-making and execution processes. In centralized optimization, to find behavior strategies with better generalization regarding shape types, a shape generator is designed to generate diverse training instances for comprehensively evaluating each behavior strategy in multi-agent simulation. Then, GP is used to evolve behavior strategies. In decentralized decision-making and execution, each robot can be guided by the same behavior strategy to form the shape. In terms of DSF completion time, the behavior strategies discovered by GP outperform the state-of-the-art distributed algorithm significantly across all test instances. These strategies can be well applied to different instances beyond the training instances. Through the statistical analysis, we also identify some crucial behaviors for realizing DSF. <italic>Note to Practitioners</italic>&#x2014;This paper was motivated by a problem of distributed shape formation (DSF) for swarm robots but it also applies to other complex systems such as distributed task allocation and motion planning of swarm. Existing distributed algorithms (manually designed heuristics) can solve the DSF problem quickly but rely too much on human experience and cannot sufficiently mine the associations between behaviors and states of robots. Evolutionary algorithms are inspired by natural processes such as reproduction, mutation, and natural selection, enabling them to automatically evolve heuristic rules. The evolved heuristic rules possess the ability to adapt to dynamic environments in real time. To the best of our knowledge, while evolutionary algorithms have not been extensively explored in DSF, notable advancements have been achieved in complex systems such as swarm robots and industrial production. Considering that robots need to respond to dynamic states of robots in real time and the tree-structure representation facilitates the construction of associations between the states and behaviors of robots, we employ GP to search the space of heuristic rules instead of directly searching the solution space about the position-robot assignment and motion planning. Computational experiment results show that the DSF completion time by the evolved behavior strategies is remarkably reduced as compared to that of the manually designed the state-of-the-art heuristics in most test instances. In the future, we plan to explore the possibility of enabling robots to dynamically generate shapes that can adapt to complex environments.