AS-RFP
A route-planning algorithm based on the foraging strategies of ants
Toby Skinner
Abstract
The recently setup AGII group proposed a programming problem to its members in order to start the ball rolling. This meant that the group could start discussing various ideas and the results could be uploaded to the agii website, as well as this it would allow different people to take different approaches to the problem and comparisons could be made between the results.
I have been recently studying decentralised models of intelligence and so I decided to try and use this knowledge (albeit basic) to solve the problem, there are many solutions to this class of problem most of which were developed years ago when 'Search' was one of the main areas of research in AI. In recent years, observations in the insect and animal kingdom have given scientists a new paradigm to explore, 'Swarm Intelligence'. Note that you can play with the applet at the bottom of the page without having to read the slightly mathy bits. Also I am not an artist or mathematician so the applet is graphically very basic.
Problem
The problem to be solved was the classic 'maze escape', a mouse is placed at one end of the maze and it has to find its' way to the cheese which is located at the exit. Initially I started writing the code for a mouse that would work a little like an SMA*, that is, the mouse could remember a few edges that it didn't follow (and information about these edges such as how strong the smell of cheese was down that edge) so that it could retrace its steps and follow alternative routes. However I then thought about why I a member of this group, it wasn't to re-write algorithms in new domains, I've done this for the past three years. I joined because I like to write algorithms that dont always work but have a theory behind them.
So I slightly altered the spec of the problem, not the type of problem but just the details. I am going to try and solve the more generic 'shortest path finding' problem, here are the details [2]
Environment
- A graph G = (V,E) where V is the set of vertices (or nodes) and E is the set of edges connecting the vertices in V.
- Each vertex can be considered an intersection in the maze and each edge is a walkway connecting two intersections.
- Useful terminology :-
- Adjancent vertices : two vertices connectd via an edge
- Degree (of a vertex) : # of adjacent vertices
- Path : sequence of vertices v1,v2,v3,...,vk such that consecutive vertices vi and vi+1 are adjacent.
- Simple path : no repeated vertices
- Cycle : simple path, except that the first and last vertex are the same
- Connected graph : any two vertices are connected by some path
- Complete graph : any two vertices are adjacent
- Subgraph : subset of vertices and edges forming a graph
- Tree : connected graph without cycles
- Forest : collection of trees
- Useful connectivity info :-
- Let n = #vertices, m = #edges
- Complete graph :
each of the n vertices is incident to n-1 edges (because all vertices are adjacent), however we dont want to count edge twice so we half the result. This means that a graph is not complete if m < n(n-1)/2
- Tree : m = (n-1)
- Spanning tree : given a graph G, the spanning tree G' of G is a subgraph which is a tree and contains all vertices of G. Removing any edge from G' results in a forest (i.e. two trees)
- Data structures :-
- Edge List : store edges in one unsorted list and vertices in another unsorted list, easy to implement but quite inefficient
- Adjacency List : adjacency list of vertex v contains sequence of vertices adjancent to v. Each vertex has a seperate list
- Adjacency Matrix : truth table with vertices along axis, where edge exists between two vertices a '1' is placed in the corresponding array index
The algorithm that controls the agents will have a single goal, "Find a tree T from the graph G", or "Find a path from one intersection of the maze to another, without ever passing through the same intersection or walkway more than once".
Solution
As I have already said, I dont want to re-write an old solution so I have opted for a newer model of 'intelligence' and/or cognition called 'Self Organisation'. In paticular I am basing my algorithm on what is known as 'Swarm Intelligence'. A nice definition of this phrase goes like this
"...any attempt to design algorithms or distributed problem-solving devices inspired by the collective behaviour of social insect colonies and other animal societies." [1]
For a thorough grounding in decentralised systems I suggest ['Swarm Intelligence'] by the SFI, it is an excellent introduction to the subject and pulls together a lot of research and studies done in this area. One thing I like about this book is that it is not intended to provide a listof problem solving algorithms, they state that they are speculating some ideas and theories which may or may not work, it provides no proofs or theorems but instead lots of very exciting ideas about the future of AI.
The 'Ant System Route Finder Problem' algorithm is an adapted version of the 'Ant System Travelling Salesman Problem', the actual algorithm in pseudocode is presented below. Essentially this is a probabilistic algorithm, at each intersection the probability of travelling to one of the adjacent nodes is equal to the amount of pheromone on that trail (to the power of alpha) multiplied by the inverse of the distance to that node (to the power of beta). This is then normalised, and possibly squared if the nodes are similar distances away from each other (as they would be in a grid-like maze). By changing alpha and beta you can alter the effect of either the pheromone or distance has on the ant, these variables have to be set carefully. An ant too sensitive to distance will act very much like greedy search, getting stuck in local optima, an ant too sensitive to pheromone will rarely search a new area of the maze.
In order to make the most of this codebase I ran a large number of performance tests on three versions of the algorithm which used slightly different node choice equations, AS-RFP ver0.1 used no pheromone data, just the inverse distance heuristic. AS-RFP ver0.2 used inverse distance and pheremone trail strengths, AS-RFP ver 0.3 is the same as 0.2 but also uses a 'global inverse distance to goal node' heuristic. The important element here is to make sure that the heuristics are relativly realistic, the local inverse distance can be analogous to the ant using local landmarks (i.e. diagonal edges of a rock, vertical edges of building etc) to navigate whilst the global inverse distance heuristic is analgous to the ant using either mountains or a celestial compass (i.e. the sun, shadow, stars etc) to navigate. I was interested to see which of these three navigation systems performed the best ('best' meaning the most number of ants to successfully navigate to the goal node after n tours) and which values of the three parameters (alpha, beta and gamma) gave the best ant navigation system.
I use the Edge List data structure because the number of vertices is quite small.
/*Initialisation*/
For every edge(i,j) in G
//Set inital pheromone level
End
For k=1 to m
Place ant k on the start node
End
Let BT be the shortest path found from the start node to the end node and BL its length
/*Main Loop*/
For t=1 to tmax
For k=1 to m
Build path Tk(t) by applying the following step n-1 times
Choose the next node j with probability
where i is the current node and g is the goal node
End
For k=1 to m
Compute the length Lk(t) of the path Tk(t) produced by ant k
End
If an improved path is found then
Update BT and BL
End
For every edge(i,j)
Update pheromone trails with following rule:
where
End
For every edge (i,j)
End
End
/*Values Used*/
Original un-altered algorithm can be found in [1] p45 ch2.
One point I should make, the algorithm is not perfect in any means, it wont always find a solution and I have set the number of iterations to 10 so that you can see the results in just under a minute.
Interestingly two extra 'features' emerge from the swarm behaviour, the first is a result of a positive feedback loop not explicity programmed into the algorithm. When an ant finds the exit it increases the pheromone levels on all the edges it traversed, this means that successive ants will be more likely to follow those edges, and when they reach the exit they too increase the pheromone on those edges. This is important when two paths to the exit are available, because of the inverse distance heuristic, more ants are likly to take the shorter routes and so the shorter route will get more pheromone resulting in the final path being the shortest tree from the start node to the end node (most of the time).
The second is that cycles emerge, multiple different paths from the start to the end node emerge because of the probabilistic nature of the algorithm. This is quite interesting because the agent that uses the final pheromone levels to navigate through the maze has the oportunity to take more than one path. This has implications when we talk about 'making AI players act more human', the same route wont always be taken, the algorithm cretes a variety of different paths which are all short. This is also an indication that this algorithm will not get stuck in local optima because the number of solutions at any one generation will be relativly diverse (see test results).
Unfortunatly this algorithm has one main flaw, it is not scalable, for local search it works nicely but the time it takes to find the path increases by a significantly large amount as the number of vertices increase. For any serious game, the map of the landscape would be much larger than 100 nodes, intelligent navigation would require a node at each intersection of the landscape (i.e. through towns or buildings) and various randomly placed nodes in wideopen spaces. I can only think that this algorithm would be good as a local search for an agent, for instance the agent may use A* to find the shortest route to the next node, but also perform AS-RFP to generate some human-like imperfections in the path.
Applet & Code
Contact Info
Email me at toby@hc2.co.uk
References
- Bonabeau, Dorigo & Theraulaz. Swarm Intelligence. 1999. Oxford University Press. Santa Fe Institute (SFI) Studies In The Sciences Of Complexity.
- Tamassia. Algorithmics notes. 1999. Unknown. Unknown.