Ant Swarm Routing

This is a laboratory for developing routing algorithms for the forklifts in an automated warehouse. The starting point is to divide the floor into a grid of cells and to mark the obstacles to the forklift, i.e. the storage racks for pallets. We then need to search for a reasonable path from the origin cell to the destination cell.

This page uses a stochastic (i.e. Monte Carlo) search algorithm where a swarm of ants move randomly starting from the origin. On each step, each ant moves one cell randomly, horizontally, vertically or diagonally, with a bias in favour of cells closer to the destination. The ant then marks the cell with its step count as follows:

• If the cell is unmarked set the cell's count to the ant's step count.
• If the cell is marked and it is more than the ant's step count, then set the cell's count to the ant's step count.
• If the cell is marked and it is less than the ant's step count, then update ant's step count with the cell's count.
• If the cell is the destination, we remove the ant from the colony.

The random walk stops a given number of steps after the destination cell has first been reached or when there are no more ants. The best path is then determined by working back from the destination to the origin. To reduce kinks, the neighbour with the shortest geometric distance to the origin is used as a tie breaker.

Comments

The Ant swarm routing algorithm is relatively costly, and not as good as routes devised by humans. Free parameters include the level of bias in the random move generator. I've used gaussian noise and control the bias via the standard deviation. Other parameters include the size of the swarm and how many time steps are taken before figuring out the path. I've set the cutoff to 50% after the first ant reaches the destination.

Another approach is to use the A-star search algorithm on a grid, see A* Grid Routing. I am more hopeful about human-inspired routing algorithms based upon semantically annotated connectivity graphs.