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

Created by W.Langdon from gp-bibliography.bib Revision:1.7650

@Article{Qu:ASE,

• author = "Yun Qu and Bin Xin and Qing Wang and Miao Wang and Miao Guo",
• journal = "IEEE Transactions on Automation Science and Engineering",
• title = "Automated Discovery of Efficient Behavior Strategies for Distributed Shape Formation of Swarm Robots by Genetic Programming",
• note = "Early access",
• abstract = "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 behaviours to construct behaviour 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 behaviour strategies followed by each robot to achieve DSF efficiently. The framework is distinguished by a centralized optimisation of behaviour strategies followed by each robot, along with strategy-driven decentralized decision-making and execution processes. In centralized optimisation, to find behaviour strategies with better generalisation regarding shape types, a shape generator is designed to generate diverse training instances for comprehensively evaluating each behaviour strategy in multi-agent simulation. Then, GP is used to evolve behaviour strategies. In decentralized decision-making and execution, each robot can be guided by the same behaviour strategy to form the shape. In terms of DSF completion time, the behaviour 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 behaviours for realizing DSF. Note to Practitioners-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 behaviours 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 behaviours 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 behaviour 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.",
• keywords = "genetic algorithms, genetic programming, Robots, Behavioural sciences, Robot kinematics, Shape, Collision avoidance, Task analysis, Swarm robotics, Swarm robots, shape formation",
• DOI = "doi:10.1109/TASE.2023.3346277",
• ISSN = "1558-3783",
• notes = "Also known as \cite{10375949}",

}

Genetic Programming entries for Yun Qu Bin Xin Qing Wang Miao Wang Miao Guo

Citations