My earlier plans for path-finding programs felt awfully stifled. The initial plan in which a single entity would "sniff" completely random squares and eventually develop a path based on separate criteria did, at least for me, seem to indicate some kind of learning. However, when I tried to expand it to deal with branching and dead-ends, it seemed to me to be a dead-end itself. I could not come up with any satisfying way to have it learn how to do that better with continued repetitions. I'm still working on that.

However, I decided to consider some other approaches to "path-finding". In one line of thought it occurred to me that ants in a new location would want to find food and bring it back to their home. Ideally a group of ants would find new food sources and come up with reasonably efficient paths between the location of the food and their home.

My goal is to try to develop a program that shows some kind of learning, some kind of ability to achieve a goal using means that "evolve" or "emerge" from simple behavior. For that reason I have tried to find a set of assumptions that (a) lend themselves to that approach and (b) don't seem completely unrealistic possibilities for real ants. I don't mean to imply that I think that real ants exhibit this particular behavior. Rather, I am trying to make assumptions that imply a behavior no more complex than that of real ants, and, almost certainly, much simpler. .

Here are my initial assumptions:

The environment for my ants will be a grid of squares, like a checker board. Initially it will be relatively small, say 12 x 12 or smaller. The "food" will be placed on a square and another square will be designated as "home".

Initially ants will enter the environment at the "home" square and can move one square in any direction, including the diagonal, that keeps them in the defined grid. For an ant in a square that is not on the edge of the grid this would mean 8 possible squares it could move to.

The simulation will be such that in each "cycle" every ant in the simulation will move one square. Initially ants will not be allowed to stay on the same square for a cycle, though that is something that could be explored later.

I assume that my virtual ants have no sense of direction, no built in compass or GPS.

I assume that each ant can play two roles, be in two different operating modes. When they leave the home they are "seekers" out looking for food. Once they find food they become "carriers" and are looking for their home. An ant would enter the grid at the home square and continue moving on the grid until it had found food and brought it home.

Here is BIG assumption. I assume that when an ant steps into a square it puts a piece of data into that square and that any ant stepping on that square at the same time, or any future time, has access to the data stored on that square . The data will reflect the following".

" I am a "seeker" on my way to get food and I am xx moves from home.
" I am a "carrier" on my way to take food home and I am yy moves from the location of the food.

I have thought about adding one additional piece of data, the time that the ant stepped on the square, but I am going to leave that out initially.

I would like to create assumptions that can be programmed such that a group of ants would exhibit the following behavior:

The ants would initially seek food by following completely random paths around the grid. The only rule related to this initial seeking process, before any food is discovered, might be that an ant would have some sort of preference for not following a path (i.e. not going to an adjacent square) that it, or another seeker had followed. A seeker would continue moving around the board till it found food.

If and when an ant found food it would then cease to be a "seeker" and become a "carrier". A carrier would continue moving around the grid till it found its home.

A successful simulation would be one in which (a) the ants initially wandered around the board randomly till one or more found food and (b) once food was found the ants would eventually come up with efficient (i.e. reasonably direct) paths between home and the location of the food.

The above is the essence of what I want to accomplish. What follows are some initial thoughts on how I might approach this goal.

It seems to me that I might get this to work using the following approach:

THE SEEKER'S RULE:
In each cycle of the simulation each seeker ant would examine the 8 squares around it. It would look to see if any of those squares held data put there by a "carrier" ant. If one or more adjacent squares had such data the seeker would move to the square with data indicating that it was the closest (as measured by how many squares the carrier had stepped on since starting to carry the food back) to the food source.

If no adjacent square had been stepped on by a carrier ant, the seeker ant would choose one of the 8 squares at random, with some sort of preference to NOT choose one already stepped on by a seeker.

THE CARRIER'S RULE:
Similarly, in each cycle of the simulation, each carrier ant would examine the 8 squares around it. It would look to see if any of those squares held data put there by a "seeker" ant. If one or more adjacent squares had such data the carrier would move to the square with the data indicating it was the closest to home.

If no adjacent square had been stepped on by a seeker, a carrier would choose one of the 8 adjacent squares at random, with some sort of preference to NOT choose one already stepped on by a carrier.

If an ant has to choose between two or more equally preferable squares, the choice will be made at random.

I can see that this would indeed establish a path to between the home and the location of the food. However, it would initially be a pretty much random, inefficient, path reflecting the first few ants to find food and the paths they happen to initially find in carrying the food home. My best guess is that the path would not evolve after the first few ants brought food back. All future seeker ants would follow one of the initial, somewhat random, trails home from the food and all the carrier ants would follow one of the initial, also somewhat random, trails from the home to the food. I can see that the process might evolve to use one specific trail for both seekers and carriers. However that trail is unlikely to be efficient and it will not improve over time.

Here is where it get's interesting. I can see that I need to introduce some random behavior in the ants, so that they do not always follow a beaten path. This is necessary so that they can, over time, come up with more efficient paths between home and food.

One question that interests me is whether (a) I should cause an occasional ant to behave significantly different from the others or (b) every ant should be identical and that every one of them would have some chance of choosing to move to a square other than the ones implied by the "SEEKER" and "CARRIER" rules above. Initially I choose that all ants should be identical.

This presents the possibility of a higher order of learning than I had initially considered. The question I see is "How probable should it be that a particular ant would choose to not follow the "SEEKER" or "CARRIER" rules? Should it 1 in 100, 1 in 10, 1 in 2? It seems to me that this variable will determine how quickly the ants evolve to find more efficient routes between home and food. I will call this probability the "WANDER" probability, i.e the probability that an ant will wander rather than follow the beaten path. I might end up with different "WANDER" values for carriers and seekers, but my initial assumption is that they will be the same.

Here's the higher order of learning: Could I make the system such that the value used for the "WANDER" probability was itself randomly chosen for each ant and then let the system seek to determine how to manage this so as to evolve the most efficient path finding system.

Initially I will simply manually set the probability and determine where the apparent optimum fixed value is. I will think about whether there is a "learn/discover" approach to determining this value.

By introducing "wandering" I can also introduce the possibility of having more than one location for food, and the possibility of adding new locations in the middle of the simulation. If the ants do enough wandering they will eventually discover new food sources.

However, it may be that the system will work better with some sort of distribution of probabilities so that most ants are fairly conservative but an occasional ant is much less restricted. This implies additional roles such as "explorer". Also there is the possibility that the WANDER factor should vary during the life of the ant colony. When the colony is in a new location it would need lots of explorers. Similarly, if the current food sources dry up it would need more explorers. That suggests the possibility of defining a food source to have a limited life. For example, a new food source could sustain 100 visits from seekers before ending. I will call this "VISIT-CAPACITY". The distribution of VISIT-CAPACITIES would probably affect the optimum value, or pattern, for the WANDER factor.

I would like to create a system that would evolve a reasonably optimum value for WANDER when given a particular distribution for "VISIT-CAPACITY" and occurance of new food locations. I can see that this can get fairly messy fairly quickly and my initial plans are as follows:

1. Assume one food location that can sustain an unlimited number of visits. Given this, experiment with settings to find a reasonably good value for the WANDER factor.
2. Assume all food locations have a set value for "VISIT-CAPACITY" and that new ones occur at some interval of cycles.

There is also the possibility of introducing some additional communication when two ants end up on the same square at the same time, or on adjacent squares.

I think I have the basis for an interesting simulation that would exhibit some problem solving/learning behavior. It certainly strikes me as more interesting that my previous approach. Comments?