Wednesday, November 02, 2011

Using collaborative diffusion rather than path finding for the Google AI ant challenge.

For the 2011 Google Ants AI Challenge rather than doing the typical solution of choosing direction for each ant based upon the shortest path to some goal I used a diffusion based approach which was simpler, faster to code and resulted in some nice emergent behavior with very little work.


A while back I read the paper Collaborative Diffusion: Programming Antiobjects.  The 2011 Ants AI Challenge seemed like a perfect test for it.  Rather than having each ant, hill, water etc be its own object, the map is the only object.  The map computes the diffusion values for agents (such as food and searching) on each square and then each decide where to have each ant go not based upon any path finding algorithm, but simply based upon the diffusion values surrounding the square.

Each square on the board has several agents or diffused values (food, explore, hill, etc).  On every turn the program would loop through the map setting or diffusing all of the squares and then loop through the ants using the diffused values at the ant's square and some very basic logic to decide which way the ant should move.

When running it against the test bots even the simplest version would get neat emergent behavior such as in a maze when two ants follow each other down a hall when they reach a fork they will naturally go separate ways or when there are five bad guys against the one good guy the diffusion value wont say to attack until you have six guys.

The two simplest things ants want to do are get food and explore.  To make the ants go after food we first have to diffuse the food value and then have the ants go to the neighboring square with the highest FOOD value.

A snippet of slightly modified code from my diffusion function which is run on each square on the map.

void Map::diffusion(int r, int c) {
    std::vector goalsToDiffuse;

    Square *square = &grid[r][c];
    // water blocks everything
    if (square->isWater) {
        square->agents[EXPLORE] = 0;
        square->agents[FOOD] = 0;
            return;
    }


    // FOOD
    if (square->isFood) {
        square->agents[FOOD] = INT_MAX;
    } else {
        goalsToDiffuse.push_back(FOOD);
    }


    // EXPLORE
    if (!square->isVisible) {
        square->agents[EXPLORE] = INT_MAX - ((200 - square->lastSeen) * 300);
    } else {
        goalsToDiffuse.push_back(EXPLORE);
    }


    ...

        foreach (goal,  goalsToDiffuse) {

        double up = upSquare->agents[goal];
        ...
        square->agents[goal] = 0.25 * (up + down + left + right);
    }


To diffuse food when a square is water it should set the food diffused value to 0 so ants never want to go into the water when looking for food, otherwise when a square has food set the food diffused value to a large value.  This large value is the final goal for the ants.  Lastly if we are not water nor food we simply diffused value to the diffusion value of the neighboring squares.  

To diffuse exploration I include in the information of when we last saw the square into the diffusion value so my ants always go to the part of the map that has been least explored and where they can potentially find hills.  This prevents them from bouncing up and down, but always moving forward.


After diffusing you want to output the moves.  This is where the real logic comes into play.  My first version was similar to the following pseudo code:


foreach(ant, myants) {
    food = valueOfFoodAt(ant);
    if (food != 0)
        goal = FOOD;
    else
        goal = EXPLORE;
    outputMove(ant, goal);
}


outputMove will chose the neighboring square (N, S, E, W) with the highest goal value.  In effect the ants will move to the food/explore/hill/etc via the shortest route.


The results are are fun to watch and with just the above code the ants will explore maps of any shape be it mazes or open lands eating up food and and as more and more ants are born they will naturally separate across the board waiting for new food to appear always moving to the squares that it saw least recently.  Adding a HILL to the above diffusion would be similar to FOOD, and the logic for the ant movement is as simple as giving it a higher precedence than FOOD.  And once the diffused HILL value reaches the ants again the map doesn't matter be it a maze or open land, the ants will march to the hill via the shortest route.

The diffusion approach to the ant problem was simple to code (no shortest path algorithms) and I was able to get the first version up and working in about an hour.  The runtime is O(rows*cols) (notice it isn't dependent upon the number of ants), the cpu time is extremely small compared to other solutions, and the memory overhead is pretty much non-existant compared to other solutions.

Given both the ease at which this is implemented and the small number of lines it would be nice if a basic diffusion based solution with goals for food, explore and hill were included with the stock python bots that the aichallenge package includes.  It would be both a great starting point for making more advanced diffusion bots and as a stronger test bot, but one that still used very little cpu.

Anti-objects are a neat concept that I don't hear too much about and something I wish I had explored sooner.  If I was introducing someone to programming the ants problem combined with a diffusion solution would definitely be a small effort, huge reward way to go.  The simplicity of the algorithm combined with the low memory and cpu overhead also was an aspect that I had not looked at before and could probably be utilized to make some great cheap behavior for AI in games, demos and other places.

2 comments:

Curious Attempt Bunny said...

Hi Benjamin,

I'm using something similar to what you describe for part of my ant. I've been calling them Contours. Can you provide a link to your ant profile page? I'd like to see it in action.

Mine is at http://aichallenge.org/profile.php?user=5108

I've also just blogged about a way to approach fighting:

http://www.curiousattemptbunny.com/2011/11/cheating-at-prime-directive.html

Cheers,
Merlyn

Amit said...

I love influence maps and have used them for something similar to food-finding. However one thing that I had trouble with was coordination. If there's 2 food in the west and 1 food in the east and 3 ants, then all 3 ants go to the west instead of splitting up. Even if you make the ant immediately claim one of the food particles, it takes too long for the information to propagate across.

Goblin Camp uses the Kuhn-Munkres algorithm for coordinating the activities of the goblins, but they then have to use A* to make the goblins get where they need to go. It's quite a bit more expensive than influence maps but it's a tradeoff to look at.

You might find this article on influence maps interesting reading.

Popular Posts