A Theoretical Framework for Estimating Swarm Success Probability Using Scouts

Introduction

This paper presents a novel theoretical framework for swarm risk assessment. The framework is applied to a scenario consisting of a swarm of agents that needs to travel from an initial location to a goal location, while avoiding obstacles. Before deploying the entire swarm, we would like to have a certain level of confidence that a desired portion of the swarm will successfully reach the goal. If not, then perhaps the swarm should not be deployed. For example, for a swarm of moving robots, the environment itself can pose a significant risk (rough terrain, sudden changes in elevation that agents are not equipped to handle, water, etc.) and, as with any hardware, circuit and mechanical failures can prevent agents from successfully reaching their destination. It is alternatively plausible that the swarm consists of software agents trying to achieve a more abstract goal, such as a successful transaction, while avoiding obstacles, such as provisions or constraints. For simplicity, in our simulation agents are modeled as robots and obstacles are modeled as physical objects.

The environment in which the agents are deployed is assumed to be static, though it may be completely or partially unknown. This environment can be highly unstructured as well, as in Mondada et al. (2005). Additionally, deployment of the entire swarm is potentially hazardous, e.g., due to the possible loss or corruption of agents – for example, some of the obstacles might contain explosives, agents could fall into inescapable holes as in Dorigo et al. (2006), or there could be environmental hazards as in Tatomir and Rothkrantz (2006). In these and many similar situations it is advantageous to do a preliminary phase of risk assessment before deploying the full swarm. The information gained from this phase will help the practitioner decide what deployment strategy to use, e.g. what starting location works best, how many agents to deploy in order to ensure a desired success rate, and whether the task at hand is worth the risk of losing a possibly large portion of the swarm.

The solution proposed here is the use of a group of expendable agent “scouts” to predict the success probability for the swarm, during the risk assessment phase. For practical reasons, only a few (less than 20) scouts are sent from the swarm, which may consist of hundreds of agents. A human or artificial agent, called the “sender,” deploys the scouts. Then, an agent (e.g., a person, an artificial scout, or a sensing device), called the “receiver,” counts the fraction of scouts that arrive at the goal successfully. The sender and receiver must be able to communicate with each other – to report the scout success rate, but no other agents require the capability of communicating messages. Using the fraction of scouts that successfully reach the goal, we apply a formula that predicts the probability that a desired percentage of the entire swarm will reach the goal. Based on this probability, the sender can decide whether or not to deploy the full swarm. Alternatively, based on this probability the sender can decide how many agents to deploy in order to yield a high probability that a desired number of agents will reach the goal.

Our theoretical framework is based on two formulas that use agent scouts as “samples” for making predictions regarding the success probability of a swarm. The first approach is the standard Bernoulli trials formula, and the second is a novel Bayesian formula. We report conclusions regarding the predictive accuracy of these formulas, based on an extensive set of experiments during which parameters were varied methodically. Our measure of predictive accuracy is the mean squared error (MSE) of each formula’s predictions versus “ground truth.” Experimental conclusions include the value of a uniform prior for the Bayesian formula in knowledge-lean situations, and the accuracy and robustness to changes in the environment of the Bayesian approach. This paper also reports an intriguing result, namely, that both formulas usually predict better in the presence of inter-agent forces (when a Lennard-Jones inter-agent force law is used) than when their independence assumptions hold. Inter-agent forces are useful for initiating and sustaining multi-agent formations while traveling to a target location. We conclude that these formulas, and especially our Bayesian formula, provide extremely practical solutions for solving “the swarm success rate prediction problem” in a variety of real-world situations. Additionally, this paper provides conclusions which lead to advice on selecting the values of controllable parameters in order to help the practitioner apply our framework.