sg 16(9): e4

Research Article

Exploring Algorithmic Options for the Efficient Design and Reconfiguration of Reactive Robot Swarms

Download245 downloads
  • @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
Todd Wareham,*
    *Contact email: harold@mun.ca

    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.