Algorithms for Timing and Sequencing Behaviors in Robotic Swarms
Robotic swarms are multi-robot systems whose global behavior emerges from local interactions between individual robots and spatially proximal neighboring robots. Each robot can be programmed with several local control laws that can be activated depending on an operator’s choice of global swarm behavior (e.g. flocking, aggregation, formation control, area coverage). In contrast to other multi-robot systems, robotic swarms are inherently scalable since they are robust to addition and removal of members with minimal system reconfiguration. This makes them ideal for applications such as search and rescue, environmental exploration and surveillance. Practical missions often require a combination of swarm behaviors and may have dynamically changing mission goals. However, a robotic swarm is a complex distributed dynamical system, so its state evolution depends on the timing as well as sequence of the supervisory inputs. Thus, it is difficult to predict the effects of an input on the state evolution of the swarm. More specifically, after becoming aware of a change in mission goals, it is unclear at what time a supervisory operator must convey this information to the swarm or which combination of behaviors to use to accomplish the new goals. The main challenges we address in this thesis are characterizing the effects of input timing on swarm performance and using this theory to inform automated composition of swarm behaviors to accomplish updated mission goals. We begin by formalizing the notion of Neglect Benevolence — the idea that delaying the application of an input can sometimes be beneficial to overall swarm performance — and using the developed theory to demonstrate experimentally that humans can learn to approximate optimal input timing. In an adversarial setting, we also demonstrate that by altering only the timing of consensus updates for a subset of the swarm, we can influence the agreement point of the entire swarm. Given a library of swarm behaviors, automated behavior composition consists of identifying a behavior schedule that must specify (1) the appropriate sequence of behaviors and (2) the corresponding duration of execution for each behavior. Applying our notion of Neglect Benevolence, it is clear these two parts are intricately interdependent. By first assuming the durations are known, we present an algorithm to identify the optimal behavior sequence to achieve a desired swarm mission goal when our library contains general swarm behaviors. By restricting our library to consensus-based swarm behaviors, we then relax the assumption on known durations and present an algorithm to simultaneously find the sequence and durations of swarm behaviors to time-optimally accomplish multiple unordered goals.