Search

In this paper we present a technique for adding functionality to swarm programs leveraging both human observation and mechanical program transformation. The technique combines two homogeneous swarms - one that executes a baseline set of behaviors and another that independently implements the new functionality. The two are combined into a heterogeneous swarm with which humans interact to establish effective population ratios between the two, to produce the best outcome. The two behavioral rulesets are then mechanically fused to create a new homogeneous swarm that exhibits both behaviors. This swarm becomes the new baseline to which additional behaviors can be added by repeating the process. We demonstrate this technique in a simulated swarm environment.

Humans and swarms have different problem-solving skillsets. Hybrid systems blending those skillsets in an effective manner can produce a solution that outperforms either separately. To be effective, this blending must be done in a scalable way. This investigation demonstrates that by limiting the human's interaction with the swarm to broad, high-level commands, the human's contribution can be scaled to multiple, simultaneous scenarios. The improved performance of the hybrid system of one human and one swarm solving one digital jigsaw puzzle, does not degrade when the same human forms a hybrid systems with up to four separate swarms at the same time.

We propose a new card game to allow users to experience two levels of an emergent process in the same context. Our goal is to help swarm programmers to better understand the relationship between actions at the agent level and the resulting behavior at the swarm level.

Through visualization humans are able to perceive the efficiency of particle swarms with respect to several levels of applied inertia as well as the inclusion or exclusion of dampening. We also are able to find relationships between these levels, the diversity of a swarm, and the swarm�s efficiency in finding the minimum for five typical particle swarm optimization functions. This makes it possible to look at new areas of investigation to understand the connection between individual actions and emergent behavior. This paper demonstrates how to blend human intelligence, by using both their visual systems and their deductive reasoning with a swarm�s computational intelligence to produce results better than each could achieve independently.

We compare three approaches to solving digital jigsaw puzzles with wrap-around connections: human-only, swarm-only, and a hybrid approach that requires humans to interact with the swarm in a high-level, scalable manner. Using an iterative improvement strategy, some positive aspects of the human solvers migrate to the swarm-only approach. As the swarm-only approach gets better, humans continue to assist and the hybrid outperforms either of the independent approaches. This strategy for improving swarms is general, and continuously applicable. We show that even after many iterations and significant improvements to the swarm-only approach, support from a human improves the performance of the swarm.

Twelve radiologists independently diagnosed 74 medical images. We use two approaches to combine their diagnoses: a collective algorithmic strategy and a social consensus strategy using swarm techniques. The algorithmic strategy uses weighted averages and a geometric approach to automatically produce an aggregate diagnosis. The social consensus strategy used visual cues to quickly impart the essence of the diagnoses to the radiologists as they produced an emergent diagnosis. Both strategies provide access to additional useful information from the original diagnoses. The mean number of correct diagnoses from the radiologists was 50 and the best was 60. The algorithmic strategy produced 63 correct diagnoses and the social consensus produced 67. The algorithm’s accuracy in distinguishing normal vs. abnormal patients (0.919) was significantly higher than the radiologists’ mean accuracy (0.861; p = 0.047). The social consensus’ accuracy (0.951; p = 0.007) showed further improvement.

Architecting systems designed to elicit group-level behavior beyond the capability of any single agent, however, demands a labor and experimentation-intensive cycle on the part of the programmer. As part of a system to evolve swarm behaviors, we have developed a mixed radix fitness function to overcome the problems encountered with typical fitness functions when used in a multi-objective optimization problem. In this work, we show that mixed radix fitness functions can be used to encode sequential dependencies and prioritize metrics within the context of agent-based swarm behavior. To demonstrate the effectiveness of our approach, we construct a mixed radix fitness function and evolve swarm algorithms to solve a complex extension of the classic object collection problem. Further, we show the mixed radix fitness function is successful in driving evolution towards a feasible solution while avoiding local extrema.

When promoting emergent behavior as a viable problem-solving option to a community unfamiliar with the concept but nevertheless key stakeholders in the effort, swarm researchers can find themselves making rudimentary analogies to social insects that provide some familiarity, but offers nothing in the way of real understanding. Yet, if these stakeholders are to adopt such a seemingly radical approach, they need to be somewhat conversant with the concepts, the obstacles and the process of an emergent system. We have built an Emergent Behavior Simulation Tool (EBST) to make issues of emergent systems and bottom-up design quickly accessible to interested neophytes. The contextual scenarios are built by swarm researchers, but provide an interface accessible to all. The tool provides an environment in which the consequences of agent based actions can be observed at the global level, and then quickly changed based on observations. Yet the scenarios are specific, and goal-oriented, so that the swarm-layperson is not left to fend for themselves in a sea of syntax, and open-ended possibilities. The tool is the centerpiece of an online course being developed for military students at the US Naval Postgraduate School.

Swarm algorithms rely on randomness to produce solutions for complex problems. The random selection of actions and chance interactions of agents force a swarm to attempt many behavioral possibilities - reinforcing the productive ones and dampening the dead ends. Randomness however, is a dual-edged sword: it is necessary to insure a wide range of agent behavior, but also a source of inefficiency and wasted resources. Using behavioral feedback, we reinforce effective use of randomness - using it to select from a restricted list of useful actions. By observing an agent's behavior over the three domains of time, space, or category, we establish a context for the application of randomness. The set of possible agent actions can be reduced to only those that are potentially beneficial. With this constraint, our results show we can dramatically improve performance and induce faster emergence from swarm algorithms using behavioral feedback

In this paper we describe emergence-oriented programming (EOP), a novel, human-centric technique to engineer swarm algorithms at a higher level of complexity than those developed with simple reactive agents. The process is iterative, building modules of behavior that can be layered to produce solutions that converge faster than reactive swarms to the desired emergent goal. The layers are modular and can be independently applied, mirroring the arbitrarily nested cognitive model proposed by Baas and Emmeche. The layers are produced by external observers recognizing and reinforcing patterns within swarms that are not visible at lower levels. Each layer builds upon the previous one leading to emergence, but the entire hierarchy can be mechanically collapsed into executable if-then rules based on robot primitives. We demonstrate portions of this technique to improve on the reactive swarm approach for solving the 4-color mapping problem

To gain insight into swarm algorithms, researchers can study insect societies and other natural collectives, program multi-agent software simulations or build groups of cooperating robots. In our research, we consider another resource: swarms of humans. Human swarms provide three primary benefits: quick feedback and evaluation of swarm algorithms, experience with high-level swarm directives instead of low-level agent programs, and a source of swarm algorithms that can potentially be reverse-engineered for use in other applications. Planning is a human's preferred problem solving methodology because we are intelligent creatures with high-level communication skills. Due to the intelligence of the agents, human swarms can be quickly programmed, for subsequent observation and analysis. This paper describes human swarm experiments designed for gathering information on swarm algorithms. At these events 100 volunteers, wearing data-encoded T-shirts, work together to perform tasks of differing degrees of complexity. Researchers provide simple instructions for each task (programming the swarm), record the swarm's behavior (videotaped observation) and analyze the results (problem identification and algorithm-mining). We demonstrate the viability of this research by presenting the quick identification of a swarm algorithm "bug" and by producing a software implementation of a swarm algorithm gleaned from our observations.

Complex behaviors emerge from the interaction of swarms of independent agents. When an agent malfunctions, these interactions can magnify the failure, propagate incorrect information, and adversely alter the swarm’s behavior. In this research we categorize swarm control algorithms based on the type and amount of influence agents exert on others. We investigate the resilience of algorithms by varying both the amount of influence and the probability of anomalous behavior. Algorithms that can best take advantage of the success of individual agents can also be the most susceptible to their failure. We strike a balance by dynamically shifting influence among agents based on local information.

Traditional control approaches fall well short of the necessary flexibility and efficiency needed to meet the commercial and military demands placed upon UAV swarms. Effective coordination of these swarms requires development of control strategies based on emergent behavior. We have developed a rule-based, decentralized control algorithm that relies on constrained randomized behavior and respects UAV restrictions on sensors, computation, and flight envelope. To demonstrate and evaluate the effectiveness of our approach, we have created a simulation of an air vehicle swarm searching for and mapping a chemical cloud within a patrolled region. We then consider several different detection and mapping strategies based on emergent behavior. We then establish an inverse linear relation between the size of the swarm and the time to detect the cloud, regardless of the size of the cloud. Further, we also show the size of the swarm has a linear relation with the successful detection of the cloud.