Com S 490: Simulation of

The goal of this independent study is to use an AI approach to simulate the collective intelligence of ant colonies in a virtual 3D environment. Collective intelligence is defined as the ability of a group to solve more problems than its individual members [1]. This is also called “Swarm Intelligence” or “emergent behavior” [4]. The term “collective behavior” refers to groups that exhibit this kind of problem-solving intelligence.

Some examples that occur in nature are schools of fish, flocks of birds, and colonies of termites and ants [2]. In each case, each individual member possesses some form of communication that enables them to gather local data from their peers, and then act according to a simple set of rules. This results in a global organization and adaptation which increases the group’s collective intelligence as it grows in number.

The teamwork of ants is a canonical example of collective behavior in simple organisms. Communication is achieved through the release and detection of pheromones. Ants use pheromones for finding food, attracting mates, finding their way back to the anthill, and attacking threats to the colony. They are also able to distinguish between their own pheromones and those from ants of other nests [3].

Finding and transporting food is their most complex problem, but it is one for which they are best suited because it can be broken down into smaller subproblems. If an ant comes across a piece of food that it cannot move by itself, it begins releasing a pheromone to call for assistance. Other ants detect and follow the pheromone trail, each also releasing pheromone, until enough ants have come to move the food back to the anthill. As soon as the food is home, they disperse and search again.

This method of problem solving is becoming more relevant to the world of computing, particularly when the problem can be broken down into smaller subproblems. The food-gathering problem is analogous to other Artificial Intelligence searching problems, such as finding the shortest path in a network [4]. Algorithms like this have already been successfully applied in telecommunications routing.

Simulation Overview

Our 3D simulation environment currently consists of an open field surrounded by mountains, one anthill, and scattered food. The “food” is symbolized by varying sizes of light-gray cubes. The volume of each cube is directly proportional to its weight, which is measured in units of ants (see Figure 1).

Each ant can carry 20 times its own bodyweight. The smallest pieces of food are currently 20 units, so it only takes one ant to carry them. The largest piece of food is 100 units, so it takes five ants to carry it. If an ant collides with a piece of food that is already on its way home, it will grab on and help lighten the load.

Ants can smell some kinds of food from a short distance and change course to intercept it, but they can sense pheromones from a much greater distance. To more clearly illustrate which ants are following the pheromones in this simulation, the ants cannot smell the simulated food. They must come upon the food either randomly or by following pheromones.

Ants also have a sense of duration. If they have been releasing pheromone by a piece of food for over a certain amount of time with no response, they give up and move on to search elsewhere [2]. In this simulation, their stagnation period is 30 seconds.

Figure 1

The Finite State Machine

Since the agents’ actions are governed by a simple set of rules, it is possible to implement their behavior using a Finite State Machine (FSM). The state transition diagram is illustrated below in Figure 2. This FSM has four states:

1. Searching for Food

2. Following Pheromone

3. Budging Food

4. Returning Food Home

The ants are spawned into the searching state, at which point they spread out randomly and look for food. If they collide with a wall or another ant, they turn and continue searching. If they find a piece of food, they attach to it and if it is now movable, they transition to the returning food home state. If the food is still not moving, then they transition to the budging food state and begin releasing their pheromone.

Figure 2

If a pheromone is detected, the ant transitions to the following pheromone state. In the following pheromone state, the ants face the direction of the source of the pheromone, and continue until they hit the food. If the food is moving, they transition to the returning food home state. If the food is not moving, they transition to the budging food state.

Occasionally the food has already moved by the time they get to the source of the pheromone. It is unclear what real ants do in such a situation, so currently they just continue on the same path. If another piece of food is found, they will continue as usual. If a wall is hit, they will transition back to the searching for food state.

While in the budging food state, the ants attached to the same piece of food will wait for 30 seconds for more ants to come and help them. If the time limit is exceeded, they turn away from the food and transition to the searching for food state. The ants constantly check the movability of the food and continue releasing pheromone until there are enough ants attached. When there are, the food starts moving and they transition to the returning food home state. It could be that the food is stuck behind another piece of food, in which case they transition back to the budging food state, but do not release pheromones.

In the returning food home state, the ants will continue pushing/pulling the food until an obstacle is encountered or until it reaches their anthill. As soon as the food is within range of the anthill, it disappears down the hole and the ants transition back to the searching for food state. In some cases, food will jam up at the anthill, but after a while the ants usually clear it and take turns putting the food in. When the field is cleared of food, the ants continue in the searching for food state indefinitely.

For more information on the Finite State Machine, see Appendix B: AntSim.java.

Class Descriptions

All classes but the State class use WildTangent objects. WildTangent’s “Web Driver” works on top of Microsoft DirectX, an advanced suite of multimedia application programming interfaces (APIs), to provide a set of programming functions, currently implemented in Java, that allow a user to create, display and maintain objects in a 3D environment.

The Ant Class

Each instance of the Ant class consists of a boolean indicating whether or not it is releasing pheromone, an integer that represents its current state in the FSM, a WTActor that points to its WildTangent body, a Food object that indicates which piece of food the ant is attached to, an Anthill object that indicates which anthill the ant belongs to, and a constructor that takes that Anthill. The FSM function takes an Ant object and determines its behavior based on these properties.

The Anthill Class

Each Anthill object consists of integers for its x and y coordinates, a WTActor that points to its WildTangent body, and a constructor that takes the x and y coordinates.

The Food Class

Each Food object consists of a boolean indicating whether or not the food is budging, a boolean indicating whether or not the food is down the hole, an integer that contains the number of ants attached to it, a WTGroup that points to its WildTangent body, an Anthill object that indicates which anthill the food is heading towards, an integer indicating the weight and a constructor that takes that weight.

The State Class

The State Class is used to make it easier to read the code in the FSM. It consists of four integers, each representing a state. The values are: SearchingForFood = 1, FollowingPheromone = 2, BudgingFood = 3, ReturningFoodHome = 4.

The AntSim Class

The AntSim class implements the simulation environment and the Finite State Machine of the ants. It extends the Java Applet, and implements the WTEventCallback interface (WildTangent’s event handler). Arrays are created that will hold Ant, Anthill and Food objects. When the applet is loaded, the first step is setting up the virtual world, including the ground, grass, mountains, light, the color of the sky, and the camera that will be controlled by the user. Next, the Anthills are created and the field is populated with food. The wt.start() function sets the world in motion.

The function createAnthill( int x, int y ) takes the x and y coordinates of where to place the anthill. Similarly, the createFood( int weight, int x, int y, int hillIndex ) function places food on the field. Its weight will determine its size, and the hillIndex variable refers to which anthill the food is/will be heading towards.

The function spawnAnt( Anthill hill ) is called through user input. Each Ant’s anthill property refers to the Anthill that is passed as a parameter. This is so the ant knows which anthill to bring the food back to. The new Ant leaves its hole in some random direction. The name of each ant begins with “Ant” and ends with the number of its position in the Ant array. This is used to determine whether an ant is releasing pheromone in the searching for food state. In this simulation, the ‘A’ key creates up to MAXANTS ants from the only anthill. However multiple anthills could be added, each with a key assigned to it that would spawn ants from it.

The onRenderEvent( WTEvent e ) function is called every time the screen refreshes. It is responsible for all updating all objects in the virtual world. First it moves the camera depending on user input, then moves each piece of food if it is movable and there are no obstacles, then it passes every Ant in the antColony array to the FSM function where its behavior is determined. See the code in Appendix B for a further breakdown of the FSM function. See Appendix A for a further description of user input in the simulation.

Modifying the Simulation

To modify the code you must have a Java integrated development environment (IDE), Eclipse for example, and you must have installed the Java 2 software developer's kit (SDK) and the Wild Tangent software developer's kit (SDK). You must also add two JAR files to the build path of your project. In Eclipse, you go to Project Properties – Java Build Path – Libraries – Add JARs… Then add these paths (Note that paths may differ depending on your version):

· C:\j2sdk1.4.2_01\jre\lib\plugin.jar (for netscape.javascript.*)

· C:\Windows\wt\webdriver\wildtangent.jar (for wildtangent.webdriver.*)

The code in AntSim.java has comments indicating which variables for the ants, food and anthills can be easily changed. These include the maximum number of each, the positions of the anthill(s) and food, and the weights of the food. There are also comments for every decision and action of the ants in every state of the FSM function.

When the simulation begins, the camera is oriented facing downward on the field such that the coordinate system is standard, i.e., positive y is up and positive x is right. The default size of the field is 1000 X 1000 and the origin is at the center, so the range of x and y is -500 to 500. When placing either anthills or food onto the field, their coordinates refer to their center point, so an x and y range of -450 to 450 or so should be used to ensure that they will not be embedded into a wall.

Future Work

Many definitions of intelligence have been proposed. One of them is that, given a domain, a system's intelligence can be measured by the number of problems that it can solve in that domain within a finite amount of time and using a limited set of resources. One of my goals in this Independent Study was to create a framework for further development by others who want to experiment with Artificial Intelligence in a 3D environment. The section contains some examples of how my ants could be made more intelligent according to the above definition.

Figure 3 shows a sample of how many minutes it may currently take for 5 to 15 ants to clear the present food scenario. There must be at least 5 in this case because the largest piece of food requires 5 ants to move. The minimal amount of ants take 75 minutes to clear the food, however efficiency increases rapidly with only a few more ants. A more intelligent ant colony should be able to clear the present food scenario in less time and/or with fewer ants.

The experiment that is almost ready to implement is multiple team competitions for food. AntSim.java contains comments indicating where the changes need to be made. In summary, first the anthills must be created, and the key that will be used for spawning the ants from that anthill must be specified in the onKeyboardEvent( WTEvent e ) function. The most important aspect is how the competition itself will take place. They could try pulling it in different directions and the speed and direction could depend on the number of ants from each colony

Figure 3

and/or the strength of each ant. Another state could be added, the competing for food state, where the ants could either have a tug-of-war, or actually fight one another. A dead state could also be added if they are given the ability to kill each other.

The competing for food state could also have sub states itself. This implementation is called a hierarchical Finite State Machine. The sub states belong to their own FSM, which could implement any variety of different behaviors. For instance, they could have a pheromone that is recognized as a possible threat to the ant colony. As each ant senses the pheromones it leaves whatever its doing, starts releasing pheromone, and moves in to help fight. With every fighting ant constantly releasing this pheromone, they would call others en route to the battle. This would start a chain reaction that would not stop until it was somehow determined that the threat had been defeated.

Another possible addition is a path-finding algorithm that the ants could use to move food around obstacles. Path finding is one of the most frequently implemented forms of AI in 3D games. Invisible mapnodes are placed on the ground, and the ants follow the paths between them. A straight-line distance heuristic could be used in an A* search algorithm. Mapnodes could be used to emulate behavior more like real ants. In reality, ants leave a pheromones trail back to the anthill. Currently the ants just know where their anthill is, but with mapnodes, they could mark a path that they could follow back later.

This approach could also be used to enable ants return to their anthill and gather a team to help them move the food. Some species of ants return to their anthill while leaving a trail of pheromone back to the food. They then release a different pheromone until they are completely covered by other ants. The lead ant then brings the team with it on the path back to the food.

If a genetic algorithm was used in the spawning of ants, the mating pheromone could also be implemented. Certain traits that are beneficial to the efficiency of the colony could be favored, for example strength or pheromone detection range, until the less favorable traits are bred out.

Other implementation changes could include changing the food cubes to leaves or grasshoppers that hop into the field and die, or having a timeout period in the searching state indicating how long it has been since more food has been found, after which they could return to the anthill and disappear down the hole.

Conclusion and Lessons Learned

During this Independent Study, I have demonstrated how collective behavior allows simple intelligent agents to perform complex tasks by simulating the food-gathering behavior of ant colonies. I have also provided a framework for the implementation of other AI algorithms in a virtual 3D environment.

When I first began my intent was to create something that would be practically useful to AI developers in the gaming industry. As I researched, I found that game AI is applied as a final addition to most commercial games because it is completely dependent on their implementation of the agents and the game environment itself.

I also discovered that deductive reasoning capabilities are not nearly as useful in game AI as behavioral algorithms. The appearance of teamwork is important because its helps create enemies that are more believable and difficult to beat. Finite State Machines are the most common implementation of game agents, so I decided to create one that would emulate collective behavior.

Of course, I still needed a 3D environment in which to create my agents. WildTangent’s 3D engine and web driver was one answer to that problem. I was able to build an environment in Java and import my 3D Studio Max models of the ants and anthills. However, by the time that I had the environment set up and the agents ready to program, the semester was almost over.

I already had the FSM planned out so I was able to implement it rather quickly. Most of the time that I spent coding was related to tweaking the sensors and actuators (movement, collision detection, etc.) of the agent in the virtual environment. I have found that most game AI programmers spend most of their time dealing with similar technical issues.

Creating this simulation has given me the opportunity to see how Finite State Machines can be used to produce realistic collective behavior in intelligent agents. I hope that I have also created a useful framework for others interested in AI to quickly start programming their own agents in a 3D environment.

References

1. Heylighen, Francis. “Collective Intelligence and its Implementation on the Web: algorithms to develop a collective mental map.” http://pespmc1.vub.ac.be/Papers/CollectiveWebIntelligence.pdf

2. Cornett, Kyle. “Modeling Collective Behavior.” http://www.stetson.edu/departments/mathcs/students/research/cs/cs498/2000/kylecornett.pdf

3. “Argentine Ants.” Insecta Inspecta World. http://www.insecta-inspecta.com/ants/argentine/

4. Gordon, David. “Collective Intelligence in Social Insects.”

http://ai-depot.com/Essay/SocialInsects.html

Appendix A: Simulation Controls

A Button Spawn an ant

Up Button Move Forward

Down Button Move Backward

Left Button Strafe Left

Right Button Strafe Right

Left Click and Drag Up Rotate camera up

Left Click and Drag Down Rotate camera down

Left Click and Drag Left Rotate camera left

Left Click and Drag Right Rotate camera right

Appendix B: Java Code

Ant.java:

import wildtangent.webdriver.*;

public class Ant

{

public boolean pheromone;

public int state;

public WTActor body;

public Food attached;

public Anthill anthill;

public Ant(Anthill hill)

{

pheromone = false;

state = 1;

body = null;

attached = null;

anthill = hill;

}

Anthill.java:

import wildtangent.webdriver.*;

public class Anthill

{

public int xPos;

public int yPos;

public WTActor body;

public Anthill(int x, int y)

{

xPos = x;

yPos = y;

body = null;

}

Food.java:

import wildtangent.webdriver.*;

public class Food

{

public boolean budged;

public boolean downhole;

public int attachedAnts;

public WTGroup body;

public Anthill anthill;

public int weight;

public long timeStamp;

public Food(int setWeight)

{

budged = false;

downhole = false;

attachedAnts = 0;

body = null;

anthill = null;

weight = setWeight;

timeStamp = System.currentTimeMillis();

}

State.java:

public class State

{

public static final int SearchingForFood = 1;

public static final int FollowingPheromone = 2;

public static final int BudgingFood = 3;

public static final int ReturningFoodHome = 4;

}

AntSim.java:

import java.applet.*;

import wildtangent.webdriver.*;

import netscape.javascript.*;

/**

* Com S 490: Simulation of<br>

* Food-gathering in Ant Colonies<br>

* Steve Tangeman <br>

* Spring 2004

public class AntSim extends Applet implements WTEventCallback

{

/** The WT object that is located on the HTML page. */

WT wt;

/** The camera object that serves to show the