chapter  10
32 Pages

Ant-Inspired Allocation: Top-Down Controller Design for Distributing a Robot Swarm among Multiple Tasks

WithSPRING BERMAN, ÁDÁM HALÁSZ, ANDM. ANI HSIEH

Contents 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 10.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

10.2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 10.2.2 Ant House-Hunting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

10.3 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 10.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 10.3.2 Linear Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 10.3.3 Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 10.3.4 Quorum Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

10.4 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 10.4.1 Linear Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 10.4.2 Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 10.4.3 Quorum Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

10.5 Design of Transition Rate Matrix K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 10.5.1 Linear Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 10.5.2 Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

10.6 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 10.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

10.7.1 Linear Model vs. Quorum Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 10.7.2 Linear Model vs. Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . 263

10.8 Discussion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 10.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

We present a decentralized, scalable, communication-less approach to the dynamic allocation of a swarm of homogeneous robots to multiple sites in specified fractions. This strategy has applications in surveillance, search-and-rescue, environmental monitoring, and other task allocation problems. Our work is inspired by an experimentally based model of ant house-hunting, a decentralized process in which a colony attempts to emigrate to the best nest site among several alternatives. In our approach, we design a continuous model of the swarm that satisfies the global objectives and use this model to define stochastic control policies for individual robots that produce the desired collective behavior. We define control policies that are derived from a linear continuous model, a model that includes navigation delays, and a model that incorporates switching behaviors based on quorum sensing. The stability and convergence properties of these models are analyzed. We present methods of optimizing a linear model for fast redistribution subject to a constraint on inter-site traffic at equilibrium, both with and without knowledge of the initial distribution. We use simulations of multi-site swarm deployments to compare the control policies and observe the performance gains obtained through model optimization, quorum-activated behaviors, and accounting for time delays.