Research Article
Exploring Algorithmic Options for the Efficient Design and Reconfiguration of Reactive Robot Swarms
@ARTICLE{10.4108/eai.3-12-2015.2262395, author={Todd Wareham}, title={Exploring Algorithmic Options for the Efficient Design and Reconfiguration of Reactive Robot Swarms}, journal={EAI Endorsed Transactions on Serious Games}, volume={3}, number={9}, publisher={ACM}, journal_a={SG}, year={2016}, month={5}, keywords={swarm robotics, subsumption architecture, parameterized computational complexity}, doi={10.4108/eai.3-12-2015.2262395} }- Todd Wareham
Year: 2016
Exploring Algorithmic Options for the Efficient Design and Reconfiguration of Reactive Robot Swarms
SG
EAI
DOI: 10.4108/eai.3-12-2015.2262395
Abstract
A key challenge in robot swarm engineering is the design of individual robot controllers such that the robots as a group can perform a specified task. In this paper, we explore algorithmic options for designing and reconfiguring swarms of synchronous reactive robots to perform a joint navigation / morphogenesis task in a known world. Our results show that neither of these problems can be solved both efficiently and correctly either in general or relative to a surprisingly large number of restrictions on robot and swarm architecture. We also give restrictions under which these problems can be solved both efficiently and correctly.A key challenge in robot swarm engineering is the design of individual robot controllers such that the robots as a group can perform a specified task. In this paper, we explore algorithmic options for designing and reconfiguring swarms of synchronous reactive robots to perform a joint navigation / morphogenesis task in a known world. Our results show that neither of these problems can be solved both efficiently and correctly either in general or relative to a surprisingly large number of restrictions on robot and swarm architecture. We also give restrictions under which these problems can be solved both efficiently and correctly.
Copyright © 2015 T. Wareham, licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/3.0/), which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.
