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.

The Air Force Research Laboratory has identified multiple spacecraft formation flying as an enabling technology for several future space missions. A key benefit of formation flying is the ability to reconfigure the spacecraft formation to achieve different mission objectives. In this paper, generation of fuel optimal manoeuvres for spacecraft formation reconfiguration is modelled and analysed as a multi-agent optimal control problem. Multi-agent optimal control is quite different from the traditional optimal control for single agent. Specifically, in addition to fuel optimization for a single agent, multi-agent optimal control necessitates consideration of task assignment among agents for terminal targets in the optimization process. In this paper, we develop an efficient hybrid optimization algorithm to address such a problem. The proposed multi-agent optimal control methodology uses calculus of variation, task assignment, and parameter optimization at different stages of the optimization process. This optimization algorithm employs a distributed computational architecture. In addition, the task assignment algorithm, which guarantees the global optimal assignment of agents, is constructed using the celebrated principle of optimality from dynamic programming. A communication protocol is developed to facilitate decentralized decision making among agents. Simulation results are included to illustrate the efficacy of the proposed multi-agent optimal control algorithm for fuel optimal spacecraft formation reconfiguration. Copyright © 2002 John Wiley & Sons, Ltd.

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.

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

A collection of agents, faced with multiple tasks to perform, must effectively map agents to tasks in order to perform the tasks quickly with limited wasted resources. We propose a decentralized control algorithm based on synchronized random number generators to enact a cooperative task auction among the agents. The algorithm finds probabilistically reasonable solutions in few rounds of bidding. Additionally, as the length of the auction increases, the expectation of a better solution increases. This algorithm is not intended to find the optimal solution; it finds a good solution with less computation and communication.

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.

Generation of fuel optimal maneuvers for spacecraft formation reconfiguration is modeled and analyzed as a multi-agent optimal control problem. Multi-agent optimal control is quite different from the traditional optimal control for single agent. Specifically, in addition to fuel optimization for a single agent, multi-agent optimal control necessitates consideration of task assignment among agents for terminal targets in the optimization process. We develop an efficient hybrid optimization algorithm to address such a problem. Simulation results illustrate the efficacy of the proposed algorithm.

An apply-to-all construct is the key mechanism for expressing data-parallelism, but data-parallel programming languages like HPF and C* significantly restrict which operations can appear in the construct. Allowing arbitrary operations substantially simplifies the expression of irregular and nested data-parallel computations. The technique of flattening nested parallelism introduced by Blelloch, compiles data-parallel programs with unrestricted apply-to-all constructs into vector operations, and has achieved notable success, particularly with irregular data-parallel programs. However, these programs must be carefully constructed so that flattening them does not lead to suboptimal work complexity due to unnecessary replication in index operations. We present new flattening transformations that generate programs with correct work complexity. Because these transformations may introduce concurrent reads in parallel indexing, we developed a randomized indexing that reduces concurrent reads while maintaining work-efficiency. Experimental results show that the new rules and implementations significantly reduce memory usage and improve performance. >

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.

The technique of flattening nested data parallelism combines all the independent operations in nested apply-to-all constructs and generates large amounts of potential parallelism for both regular and irregular expressions. However, the resulting data-parallel programs can have enormous memory requirements, limiting their utility. In this paper, we present piecewise execution, an automatic method of partially serializing data-parallel programs so that they achieve maximum parallelism within storage limitations. By computing large intermediate sequences in pieces, our approach requires asymptotically less memory to perform the same amount of work. By using characteristics of the underlying parallel architecture to drive the computation size, we retain effective use of a parallel machine at each step. This dramatically expands the class of nested data-parallel programs that can be executed using the flattening technique. With the addition of piecewise I/O operations, these techniques can be applied to generate out-of-core execution on large datasets.

Efficient parallel execution of a high-level data-parallel language based on nested sequences, higher order functions and generalized iterators can be realized in the vector model using a suitable representation of nested sequences and a small set of transformational rules to distribute iterators through the constructs of the language.