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

摘要

Contents 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 10.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24610.2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 10.2.2 Ant House-Hunting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24710.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25110.4 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 10.4.1 Linear Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 10.4.2 Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 10.4.3 Quorum Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25510.5 Design of Transition Rate Matrix K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 10.5.1 Linear Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 10.5.2 Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25810.6 Simulation Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 10.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26010.7.1 Linear Model vs. Quorum Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 10.7.2 Linear Model vs. Time-Delayed Model . . . . . . . . . . . . . . . . . . . . . . . . 26310.8 Discussion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 10.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272We 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.