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.8028
- @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