Ants Applet Summary

The Ants simulator is a Java application/applet that can animate the movements of any number of agents in a 2-dimensional world.

The initial problem we solved with it (also, the problem shown in the demo applet) was that of assigning follower agents to target agents. That is, we assume that there are a number of target agents moving randomly in a field and we want a fixed (e.g. 2) number of follower agents to follow each target at every single time. Since the followers are slower than the target agents, often a follower will need to "hand-off" a target to another follower that is on the target's path. Also, we do not want more follower agents than needed following a target.

The physics of the world are such that the follower agents can only detect other agents that are within a small radius around them. The agents can communicate with each other, but only within a certain (different) radius.

We solved this problem using the following "BlackList" algorithm.

Follower.java agent algorithm:

The purpose of these algorithms is for, at most, K Follower to 
follow every single Target agent. We try to dynamically re-allocate
the resources (Follower agents) as the Target agents move around.

A Follower always follows the closest target to it, as long as this
target is not in its blackList. Targets get into the blackList by
sending the agent a "doNotFollow" message.

worldMap; //a map of everything I know about the world.
blackList; //a set of targets I will NOT folllow
currentTarget; // the target that Follower is currently following
               // null if none

worldMap.add(getInputs); //add any new observations
foreach (msg = msgsReceived) { //for each msg I receive
if (msg.type == "tell") { //if its a message from another follower
   worldMap.add(msg.info); //add the info that agent told us.
}
else if (msg.type == "doNotFollow") { //if its from
     blackList.addAgent(msg.sender);
     if (msg.sender == currentTarget)
        currentTarget = null;
}

broadcast("tell", worldMap); //tell everyone everything I know 
                             //about the world

//get rid of old observations and agents that were added a long
// time ago.
worldMap.expireOldObservations(); 
blackList.expireOldAgents();

closestTarget = closest target agent that is not on blackList;
if (closestTarget == currentTarget) {
    Send currentTarget a new "following" message if one has not been
    sent in a while;
}
else{
    currentTarget = closestTarget;
    Send currentTarget a "following" message;
}
if (currentTarget == null){
   if (closest agent from blackList is very close to me)
      move away from that agent
   else
      move randomly;
else
    Follow currentTarget;


Target.java algorithm.

worldMap.add(getInputs); //add any new observations
followers; //the set of agents following me.
foreach (msg = msgsReceived) { //for each msg I receive
    if (msg.type == "following") {
       if (followers.isIn(msg.sender))  //if I already know that
           continue; //get next message
       if (followers.size() < maxNumFollow) { //not enough following me
           following.addAgent(msg.sender);
           continue;
       }
       if (msg.sender is closer to me than some agent x in followers){
          sendmsg("tell", x, "doNotFollow");
          followers.remove(x);
          followers.add(msg.sender);
       } else {
          sendmsg("tell", msg.sender, "doNotFollow");
       }
    } 
}

Note that, since the RadSim simulator came out, we decided to (temporarily?) abandon development of this simulator and Radsim instead. This required us to rewrite a lot of the agent code in order to adhere to the new architecture. Also, the Radsim challenge problem is different from Ants.