Swarming Agents on Mobile Ad Hoc Networks

The Secure Wireless Agent Testbed (SWAT) and the Philadelphia Area Urban Wireless Network Testbed (PA-UWNT) projects at Drexel University utilized swarms of mobile agents for a variety of tasks. These projects developed distributed and decentralized communications for first-responders on a Mobile Ad Hoc Network (MANET) of light-weight, resource constrained devices (e.g., tablets, portable digital assistants, etc). One of the assumptions in the design is that existing networking infrastructure at a site may be damaged and inoperable. Additionally, the project considered a variety of challenges that an urban environment creates for MANETs (e.g., subterranean tunnels for subway systems, passing trains, crowds, etc). Swarms of mobile agents (i.e., agents that can traverse the network hopping among nodes) were used the data management and network monitoring. A good overview of the project can be found in an article, Designing Dependable Agent Systems for Mobile Wireless Networks, published in IEEE Intelligent Systems.

The agent swarms in this system self-adapt their population size to balance the need for agents to complete monitoring tasks with the resource limitations of the mobile devices operating on the MANET. This is explained in the paper Ecology Based Decentralized Agent Management System from the Third International Workshop on Formal Approaches to Agent-Based Systems. We also defined design patterns for mobile swarming agents, such as in our paper Designing Decentralized Software for a Wireless Network Environment: Evaluating Patterns of Mobility for a Mobile Agent Swarm, which was presented at the Second IEEE Symposium on Multi-Agent Security and Survivability.

Industrial Scheduling and Factory Automation

Among the applications of my swarm intelligence research are various problems related to factory automation and other industrial problems. These include dynamic and autonomous routing of jobs through the factory floor to relevant machine queues capable of processing the next step of the manufacturing plan of the job in question, as well as sequencing jobs awaiting processing in the queue of a machine.

Ant Colony Control: Much of the early work on ACO focused on solving statically defined optimization problems, such as scheduling problems where all jobs or tasks are known in advance, including all task characteristics (deadlines, process times, setup times, etc). Essentially the early work on ACO focused primarily on combinatorial optimization problems, providing an alternative to other metaheuristics such as genetic algorithms, simulated annealing, and related techniques. My first exploration into swarm intelligence took some of the ACO concepts further into a dynamic problem. We developed Ant Colony Control (Cicirello and Smith, 2001), introduced in a paper titled Ant Colony Control for Autonomous Decentralized Shop Floor Routing and presented at the Fifth International Symposium on Autonomous Decentralized Systems. Ant Colony Control is a multiagent system where agents communicate indirectly using a pheromone trail following approach to dynamically route jobs through a shop floor.

Wasp Behavior Models: My next exploration into swarm-inspired problem solving utilized computational models of wasp task allocation behavior and wasp dominance hierarchies. The biological models that my work was based on was that of Theraulaz, Goss, Gervet, and Deneubourg (1991) who studied the behavior of wasps of the genus Polistes, more commonly known as the paper wasps. In the task allocation model, tasks give off stimuli, and each wasp has a threshold for each type of task that the colony may need to complete, such as foraging for food, caring for the brood, and defending the nest. In a paper wasp colony any individual is capable of working on any task, but they tend to specialize (e.g., some are more likely to forage for food than others). The computational model of this allocation behavior is probabilistic. As the strength of the stimulus for a task increases, the probability that a wasp begins that task also increases. This probability is also dependent upon the individual wasp's threshold for that task, with lower thresholds leading to higher probability of responding to a given task stimulus. The response thresholds of the wasps adapt as well with a simple form of reinforcement learning, enabling wasps to specialize in tasks, with the colony adapting the specializations based on demand for tasks. In the dominance hierarchy model, pairs of wasps engage in dominance contests, where the winner is determined probabilistically based on the so-called force variables of the competitors. The force variable of the winner increases, while the force variable of the loser decreases, essentially some of the force of the loser is transferred to the winner.

Wasp-Like Agents: In my research, I developed a multiagent system based on the wasp task allocation behavioral model for dynamic coordination within a factory environment. The earliest version was introduced in the paper Wasp Nests for Self-Configurable Factories, published in the proceedings of the Fifth International Conference on Autonomous Agents. In this multiagent swarming system, there are two agent types, routing wasps and scheduling wasps, the former in charge of routing jobs to relevant machines, and the latter then dynamically sequencing the jobs within a machine's queue. This wasp-inspired multiagent system was improved to incorporate elements of the wasp dominance hierarchy model in a paper titled Improved Routing Wasps for Distributed Factory Control, presented at the IJCAI-01 Workshop on Artificial Intelligence and Manufacturing. We then explored the performance of this adaptive wasp-inspired multiagent system compared to commonly employed dispatch scheduling heuristics in a paper titled Distributed Coordination of Resources via Wasp-like Agents at the First International Workshop on Radical Agent Concepts. This work culminated into a multiagent system for an industrial factory problem involving vehicle paint booths. The system involved one of the final stages of the manufacture of trucks, namely painting each one of several colors. Each paint booth is capable of painting any of the colors, but in order to paint the next truck a different color than the previous, it must first flush paint from the system incurring a cost associated with some wasted paint. There is also a time cost associated with this, however the time to paint the truck is longer than the time to switch the system over from one color to another. The jobs (i.e., trucks) in the queue of a paint booth cannot be rearranged (e.g., there is a physical queue of trucks, so rearranging jobs means physically rearranging the trucks). In a paper titled Wasp-like Agents for Distributed Factory Coordination, published in the journal Autonomous Agents and Multi-Agent Systems, we applied the wasp-behavior inspired multiagent system to this problem, demonstrating that the wasp agents can learn to specialize the paint booths to colors to balance the current demand, as well as later adapt the system if demand changes.

Game Theoretic Analysis: As part of my swarm intelligence research, I also formally studied why these systems are effective. In particular, I used game theory to analyze the Ant Colony Control (Cicirello, 2001) and wasp-like multiagent systems (Cicirello, 2008) models of agent coordination.

WHISTLING

I expanded upon the wasp-inspired multiagent systems work (see above section) into a stochastic sampling algorithm for solving scheduling problems and other combinatorial optimization problems. This consisted in developing an algorithm called WHISTLING, which is an acronym for Wasp beHavior Inspired STochastic SampLING. This work began with a preliminary exploration of how to utilize the wasp behavior model for a statically defined problem, including an experimental comparison of several tournament style approaches involving wasps competing in dominance tournaments to generate an ordering over jobs in a machine scheduling problem. That preliminary study of different tournament structures for wasp agent dominance contests is detailed in a paper titled Randomizing Dispatch Scheduling Policies, presented at the 2001 AAAI Fall Symposium on Using Uncertainty Within Computation. That preliminary work formed the foundation for the WHISTLING algorithm itself, which was introduced in the paper Amplification of Search Performance through Randomization of Heuristics at the 8th International Conference on the Principles and Practice of Constraint Programming.

The WHISTLING algorithm was also one of the components of a multirobot space exploration project, Federation of Intelligent Robotic Explorers (FIRE). The FIRE project focused on a team of autonomous robots exploring a planetary environment, such as Mars. The team of robots of FIRE utilized a market-based approach with robots bidding on tasks based on their capabilities (Goldberg et al, 2003; Goldberg et al, 2002). Once allocated to a robot, the WHISTLING algorithm would compute a schedule for completing the tasks. One of the benefits of this approach to scheduling for this environment is that WHISTLING provides an anytime approach, where some solution is available immediately, but the system can continue to improve upon the schedule for the robot's exploration tasks. It is also easy for this approach to adapt as the robot is assigned additional tasks.