Ant colony simulation - optimizing the path [closed]

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 9 years ago.

I am trying to build a simple ant colony simulation. The world is grid of squares; each one of them can consist of some level of pheromone and any number of ants. There are 2 types of pheromone: food pheromone and nest pheromone. Ants know nothing about the environment, but ants that return to nest follow nest pheromone (in the sense that they almost always choose to move to the cell with the maximum pheromone level, among all nearby cells) and leave food pheromone, and vice versa.

From time to time the ants make random moves not in the direction of maximum pheromone. Each tick of the simulation the ant checks the level of the pheromone in 8 nearby cells, and if the pheromone level in the current cell is less then the maximum of pheromone level in all nearby cell, it adds some pheromone.

The current simulation works pretty well, but the path found is not the optimal one. I have 2 problems that I don't know how to solve:

1. How do I simulate the fact that the diagonal move is longer than the non-diagonal move (up,down left or right)?

1. How should I simulate the diffusion of the pheromone? Right now, the pheromone evaporates over time but there is no diffusion. I have tried to transfer some amount of the pheromone from each cell, each tick of the simulation, to the 8 nearby cells, but the result was a total mess - the whole environment was full with pheromone - I think it was because of the mechanism the ants use to adjust the pheromone level.

Answer 1

On a square grid, it is probably going to be difficult to simulate that the diagonal moves are longer than the horizontal and vertical moves, assuming that ants always move one square per tick (or none). Since the diagonal distance is longer, the ants would effectively have to "run faster" than for the horizontal/vertical moves. This is probably not what you want.

Instead of a square grid, you may therefore want to consider a grid or network of nodes all with equal distance, i.e. a hexagonal grid. This will also change the number of neighboring cells but that is the whole point.

Regarding diffusion: This is a matter of getting the parameters right. Sounds like diffusion per tick was too high. Also it should be in the right proportion relative to the pheromone production by ants. Note that the type of grid also affects diffusion.