Upon a white tiled floor with random black tiles and Lego Mindstorms, the Auctioning project hoped to find a swarm algorithm were Mindstorm robots would autonomously position one robot per black tile. The project finished with this ability intact.
TopSweep provides a simulation environment which in many ways performs the same job as Swarm or Repast. The major difference between Sweep and the other available swarm simulation software lies in the fact that Sweep runs upon a finite state automata (FSA) based framework. This FSA based framework, consists of an environment, agents, actions, sensors, probes, and the FSA itself.
The environment provides the software entity that allows a swarm of agents to interact with other agents and with the environment itself. In Sweep, the environment can be either a grid or a graph. The ability to implement a graph based environment provides an advancement over many other current swarm simulation programs.
Agents provide the instantiation of the FSA, actions, and sensors. Each agent maintains a state, from which can be computed a next state. These states find their basis in the sensors and actions that make up the agent. For example, imagine an agent with a food sensor, a random move action, and a move to food action. The agent would move randomly until its food sensor indicated that food was near. Then the agent would switch to the move to food action state. In the software, the agent also provides the entity which can store higher level variables such as how much food an agent has picked up.
Actions and sensors provide the software entities that allow the agents to interact with their environment. Through the use of actions, agents are able to manipulate their environment. An example action would be to pick up food. Combined with a food sensor this action would allow an agent to replenish its energy supply which could be a variable stored in the agent software entity.
Sensors, while they do not allow an agent to directly manipulate the environment like actions do, they allow an agent to learn about their environment. Through the use of a sensor an agent can detect objects in the environment and the presence and location of other agents. Locating other agents brings up another important aspect of Sweep, the ability of agents to directly or indirectly communicate with each other.
Agents can indirectly communicate through the use of sensors and actions. Such an example using sensors and actions would be the use of pheromone trails. A sensor could be used to detect pheromone trails in the environment and actions could be used to lay the trails. For more advanced simulations, one can have agents be able to directly communicate with each other. It should be noted that this ability, of direct communication, provides an advancement over many of the popular swarm simulators. Such direct communication becomes useful when swarms of robots are being simulated.
Probes provide the ability to have software entities which can observe a simulation. These probes have access to all information found in the environment and found in the agents. They can, through this information, be used to better understand a running simulation by allowing the user to obtain metrics.
To help understand how emergent behavior evolves in the world, the concept of the Virtual Human Swarm
involves the use of human beings performing some function and extracting the methodologies used during the experiment. These methodologies are then written into an algorithm and implemented into software. The latest development to this project involved humans interaction through a virtual world. In this world, each individual represents an agent with a color. From a bird's eye point of view of the virtual world, the actions of the agents was recorded and analyzed. Other virtual human swarms included a four color mapping application where each user represented a vertex on a graph. The users would then attempt to find a color that did not conflict with another vertex, thus solving the overall graph.
When materials are brought to a Naval ship, the amount of time it takes to organize the final destinations of each package can become challenging. In an effort to optimize this situation, the Carrier Cargo project used a Human Swarm interactive experiment to develop efficient algorithms. Using specially designed software and barcode labeled pizza boxes, the experiment consisted of agents bringing packages to different locations. If the location became full, the program would reassign the agent to deliver the package to another destination. By extracting the agent's methods, the carrier cargo algorithms were developed and implemented into software.
TopThe graph coloring problem provides a well known abstraction to scheduling, logistics, and register allocation problems. It is well known that finding a proper n-coloring of a graph is an NP-complete problem. Due to the inability of any algorithm to find a proper n-coloring in polynomial time, a swarm-based approach seems feasible. Although swarm-based approaches, due to their non-deterministic behavior, may not be well suited to problems in which there exist efficient algorithms, they are well suited to optimization problems.
There exist many motivations in nature for such work. Ants use swarm techniques to find the shortest path to a food source where humans would probably use Dijkstra's shortest path algorithm. With this motivation in mind, a swarm-based technique was developed for the graph coloring problem.
A one-to-one ratio between agents and vertices of the graph in question is used. Each vertex contains one agent that is in charge of its coloring. Initially, the graph is randomly colored using a user defined color palette size. Each agent then determines whether it is in conflict or not. To accomplish this goal, each agent communicates with every neighboring agent. The agents only communicate the current color of their vertex.
Once the conflicts are discovered each agent in conflict then runs through a color change algorithm. First, the agent adds up how many neighbors it is in conflict with. Second, the agent divides this number by the total number of neighboring agents. Then the agent picks a random number between zero and one, and if this number is less than the quotient of the number of conflicts divided by the total number of neighbors, then the agent randomly picks a new color. This algorithm of finding conflicts and running through the color change algorithm is repeated until either no more conflicts exist or a user defined time out value is reached.
It must be noted that there exists much randomness in this algorithm. The argument behind using a high level of randomness is to allow a solution to emerge instead of deterministically forcing a solution. As the findings in the next section show, this does prove effective, but does leave a little too much to pure randomness.
As seen in the basic graph coloring, well randomness is desirable, too much unguided randomness can leave the system in a chaotic state. To further guide the randomness, a hypothesis problem solving technique was developed. This technique harnesses both the power of the scientific method and the power of randomness to provide a platform for emergent behavior.
In similarity to the basic graph coloring algorithm there exists a one-to-one ratio between the number of agents and the number of vertices in a graph. So, if there exist n vertices then there will also exist n agents, with each agent responsible for one vertex. However, unlike the basic graph coloring algorithm these agents are not static in their position, they are allowed to move around to their neighbors.
Also, unlike the basic graph coloring algorithm the initial graph state is one of complete conflict instead of choosing purely random colors for each vertex to start with. This enables a proper solution to be built up instead of having to tear a bad solution down and then build it back up again. Initially, each agent will check to see if its vertex is in conflict, and if it is, it will then follow the color change algorithm described next.
The algorithm works by first having each agent make n hypotheses of the form Vertex A should be color [x]
with [x] ranging from 0 to n-1; n being the user defined color palette size. In conjunction with each hypothesis exists a confidence value. This value ranges from 0 to 100 with 100 being absolute confidence in the hypothesis. Initially, each hypothesis starts with a confidence value of 50.
After generating the hypotheses, each agent then moves to all neighboring vertices in a random order. With each move, the agent adjusts its confidence values according to whether or not the evidence, the current vertex's color, supports or refutes the hypotheses. For example, imagine that vertex B is color 0 and vertex B is a neighbor of vertex A. So, the hypothesis saying that vertex A should be color 0 would have its confidence value lowered while the other hypotheses would have their confidence values raised slightly.
Once an agent has moved to every one of its neighbors it returns to its responsibility vertex. Once there, it then communicates with every agent responsible for all neighboring vertices. This is done to add information regarding the hypothetical colorings of the graph. For example, if an agent was contacted and had a confidence value of 90 to change vertex B's color to color 1, then the agents responsible for vertex B's neighbors should take that into account. So, if vertex A's agent received such information, and vertex A and B are neighbors, then vertex A's agent must reduce its confidence in turning its color to color 1, since this would cause a conflict if vertex B's agent also changed its color to color 1.
This process, of determining if a conflict exists, moving randomly to all neighboring vertices, and then communicating with neighboring agents continues until all conflicts have been fixed.
For the purposes of point-to-point and broadcast transmissions, the John Carroll University swarm research team has developed a Java-callable library for general communication across a wireless network. As both a driving problem and as a proof of concept, we have implemented the firefly synchronization
algorithm on a collection of independent iMacs. This algorithm gets its name from Pteroptyx malaccae, one of several species of fireflies that can flash in unison. The library is based on the Apple Rendezvous package that provides a way of networking computers, allowing them to seamlessly join or leave at any time. Each computer connects wirelessly and represents a user-specified number of fireflies. The program, running on each computer, generates a simulated flash
for each firefly, broadcasts that information using the library, and eventually synchronizes across the whole network. The library uses the User Datagram Protocol, UDP, to allow any computer to join an execution and immediately begin sending data to all other computers. Likewise the other computers on the network are not dependent on a connection-oriented protocol so each computer may leave at any time without affecting the others. The library is now being used to support developing swarm applications.
The focus of the Martian Rover project revolved around having robots position themselves proportionately using only wind power. If a rover becomes overcrowded or isolated in a region, then that rover would move with the wind until it found a new position.
TopAn up and coming programming paradigm is Aspect-Oriented Programming(AOP). Much like how Object-Oriented programmers have the ability to encapsulate code into an object, AOP allows concerns, such as logging, synchronization, and security, that crosscut through the class structure become encapsulated inside of an aspect. The advantage of this paradigm is more concise and logical code.
In 2004, the JCU Swarm group decided to begin using AOP in its implementation of swarm projects. Currently, AOP implementations exist for the following projects: 4-color mapping, Martian rover, and the Aspect Mining Eclipse plug-in.
Building upon the 4 color mapping problem, new views were needed to be implemented to demonstrate how the emergence evolved to solve the problem. AOP was used to implement these changes as a way of testing AOP's capabilities with swarm applications.
Aspects give programmers additional control over a program. One such control is the ability to define new methods and fields into already defined classes without explicitly defining these structures in the class. This process is known as inner-type relationships. Using inner-type relationships, a data value was included in every Vertex and Edge object, allowing for the gauging of a Vertex or Edge's stability. Using these values, three views were created to demonstrate the emergence using a red to blue spectrum. Blue represents extended stability while red refers to relative instability. Also, AOP helped in the implementation of a feedback through the use of these data values.
Through this learning experience with AOP, it was determined that AOP can be very useful in reducing code size by eliminating the code for crosscutting concerns. In addition, AOP permitted for the implementation of new features without altering the original code. Because of the success of AOP with this project, new views were also added to the martian rover project.
Currently, the Swarm Team is also developing an Eclipse plug-in for automatic aspect mining refactoring. AOP offers many benefits through its implementation for crosscutting concerns. The plug-in, currently in beta, is defined to find instances where aspects could be used for more effective code structure.
The purpose of intrusion detection is simple; it is to detect, with a reasonable level of certainty, malicious activity. Although the definition comes intuitively, the methods used to accomplish this goal vary widely. Currently, many intrusion detection systems are moving to a hybrid/distributed approach. A hybrid method allows the merging of host based (such as Aide) and network based intrusion detection systems (such as Snort). A distributed method consists of having some form of intrusion detection technology running on every host on a network. Although both of these technologies, a hybrid and a distributed system, provide many advantages, they also require advanced, often complicated mathematics, to implement.
The mathematics comes into play with a technology called data fusion. Data fusion attempts to merge various disperse data sources into one coherent stream of information. In hopes of simplifying the implementation of data fusion, with regards to intrusion detection, a swarm based method has been proposed. This method would merge the HSPT algorithm with current intrusion detection technology to create a data fusion based distributed/hybrid system.
For example, imagine trying to detect a ping sweep happening over an entire subnet. Knowing that a ping sweep was occurring is very useful because it is usually one of the first indications that an attack is going to occur. It becomes difficult to detect a ping sweep, especially, with a distributed system, because each intrusion detection system will only see maybe one or two echo requests at a time. By only seeing one or two echo requests, it becomes impossible at the host level to truly understand that a ping sweep is occurring.
However, if each intrusion detection system on the host computers makes a hypothesis of the form Host A is pinging me
and then communicates this with a correlation server, it becomes possible to properly detect a ping sweep. This HSTP algorithm would work first, as seen above, at the host level, with each host forming a hypothesis and attaching a confidence value to that hypothesis. The confidence value ranges from 0 to 100 with 100 being absolute certainty in the hypothesis.
Next, these hypotheses will be sent to the correlation server for the network in question. At the correlation server, there will exist a hypothesis of the form Host A is port sweeping network A.
The confidence value in this hypothesis will be raised slightly by every host based hypothesis of the form Host A is pinging me.
Once the confidence level in the correlation server’s hypothesis reaches a certain user defined threshold it would then be reported to the network administrator.