Click here to Skip to main content
15,860,859 members
Articles / Programming Languages / C#
Article

Path Finder

Rate me:
Please Sign up or sign in to vote.
4.10/5 (29 votes)
4 May 200419 min read 102.5K   59   13
Playing with various Artifical Intelligence theories.
  • <a href="PathFinder/PathFinderRedux.zip"> Download source files - 115 Kb

Introduction

The PathFinder application is a look into a number of different areas some of which tend to run into each other; these are mostly the topics of Intelligence, Memory, Artificial Life, Swarm Intelligence and Path Finding Algorithms, some of which will be based on ideas in the literature in the bibliography below and some of which I will make up on the spot. The main idea behind this program is not to prove any major scientific points but to in general have a look at these different areas and play around with them. It is meant to be a project that I can have fun with and develop occasionally. The program won't be developed as a series of articles but as this single article being updated whenever I add a new algorithm or creature to the mix.

This being the case, the code will be in a state of perpetual flux and will probably never manage to be pretty or possibly even well written. A lot of the ideas thrown into the mix will be purely experimental and even by the first release there is abandoned code lying around in places that contain ideas that I would like to progress further but the current attempt(s) at implementing it failed, miserably in some cases. This could be due to flaws in the ideas or in the implementation, so if you have a better implementation idea, feel free to add it on the message board at the bottom of the article and I'll take it into consideration.

For the above reasons, I don't intend to put a lot of code in this article. The code is freely available to anyone who wants to look at it, so cutting and pasting it into the article wont really serve much of a real purpose. The article will deliberately maintain a higher level of discussion looking at the problems and rules of implementation using pseudo code where I feel explanation is necessary or proves a point.

The starting premise of the PathFinder program is writing the algorithms that get the creatures to move about on the given map. The idea is that each algorithm used will be kept separate, identifiable and choose-able. This will serve two distinct purposes: one, it will show a kind of evolution of the algorithms as they start out very basic and change over time with new ideas altering the way they behave and then allowing a comparison between the previous implementation and the new implementation to be run side by side, so that the differences in effect can be readily observed. One future planned aid to this will be a reporting system that will allow the user to stop the program and generate a report of its current state. The second distinct purpose is that at a later date, when certain modes are added, the different algorithms will/should be able to compete directly with each other to perform various tasks.

The GUI

There isn't really a lot to say about the GUI at this moment in time. As every aspect is due to be rewritten, it's pointless going into a lot of detail here at the moment, so I'll briefly explain the available options and leave it at that for now.

The main page

The map

The map that the ants move around is built up of separate squares that have defined routes or paths that the ants can move along. For this release, the purple square represents the nest where the ants start out from and the green square represents the food source that they are, in theory, looking for.

The Critters options

These are the critters that you can have wandering around the map. At the moment there is a choice between ants and the amoeba. You can choose only one critter at a time and once the start button is pressed the option is disabled.

Algorithms

For the initial release, there are two algorithms available. See below for discussion on the available algorithms. As with the critters, you can currently choose one algorithm at a time and the option is disabled once the start button is pressed.

Update timer

This timer controls the speed at which the update functions are called and therefore the speed at which the ants move.

Start and Stop buttons

These are pretty obvious although stop should probably be renamed pause as it prevents the update timer from being called, effectively freezing the program until the Start button, which when the stop button is pressed is renamed the Continue button, is pressed again.

Ants General

General :- Number Of Ants

This is the number of ants that are currently running around on the map. This currently defaults to 5 and is adjustable while the program is running.

General :- Find Food

The option to find food or do something else will play a part later on, at the moment though all the ants do is, look for food.

General :- Try To Avoid Occupied Squares

This means that if a square is currently occupied, an ant will search for an alternative. This option has two interesting side effects, the first being that it appears to help the ants choose the directions to go in the first place and thus they might not find the food without it. The second effect, which is a negative effect is that when an ant has found food and is returning home (indicated by the green antennae), an ant searching for food will appear to run away from the ant with the food.

Behaviour :- Number Of Ants Affected

This is the number of ants affected by the check box option below. Note that at present this will be the first number of ants in the Critters array.

Behaviour :- Do Not Follow The Strongest Pheromone

This indicates to the ants that they should place no special emphasis on the pheromone levels of a square. Though it should be noted that once an ant has discovered the food and returned home with it, the code will change this setting as it attempts to find its way back to the food.

The Map Editor

PathFinder comes complete with a map editor that allows the user to change any of the five maps, provided this is so that the effectiveness of algorithms can be tested against different types of maps and early on showed that some of the more basic algorithms weren't up to the task of dealing with the more complex maps.

The way the map editing works is that you can enter the edit mode for the map by clicking on the "Enter Edit Mode" button or by using the menus. Once you have done this, you will be able to right click on any square in the map and a context menu will give you the option of deleting that particular square. Note though that the system is designed so that you can only edit one square at a time as the system uses the surrounding squares to place the current square. The reason for this is because I didn't want the system to have a predefined size so that later programs using the code can be of different sizes.

Once you have deleted a square, you can then right click on where the square used to be and a context menu will appear giving a selection of the available square types that can be placed at this point. In order to make life easier a blank map is provided which is just a collection of the standard square types (which means that the square has no paths and is just a background square).

When you are happy with the map you can save it with the "Save Current Map" option in the Save section of the menus. The default naming procedure is NameMap.xml although this is not enforced in any way.

Once you have finished editing a map, you must press the "Leave Edit Mode" button or choose "Leave Edit Mode" from the edit menu.

It should be noted that the only restriction placed on the maps is that they should have one nest square. There is nothing to stop you adding more nest squares but only the first one the code finds will be used.

The four maps are:

  1. DefaultMap which is the default map on loading and is pictured above.
  2. The TwoFoodsMap which is another simple map having two food sources placed on it.
  3. The SnakesNLaddersMap resembles a snakes and ladders board and
  4. The OpenMap is comprised entirely of four way squares, meaning that the critters can move anywhere.

Logging

One of the problems I run across when writing programs that either generate lots of data or run for long periods of time is the size of the log file. The problem when it came to this program is that you can generate enormous amounts of data most of which will tell you precisely nothing and could just contain information about how the ant decided which square to move to next. The way around this was to not only to be selective in the information that is actually tracked in order to be written to the log but to work out a way in which the log file wasn't constantly being updated.

My solution to is to have an individual log for each object and a main application log for the project. The size of the array is then limited or not as the user of the program chooses. This is done through the logging panel in the application and allows the user to select the number of messages that each object logs or to allow it to log all the messages that it receives.

The logs can then be written at any time by pressing the Log Data button on the main page. This will write out all the currently saved data to be written into the log. If a ant or object has no data to write then nothing about that ant will appear in the log. In order to allow multiple log files to be written during a single run each file for this program is named using the DateTime.Now.Ticks value, with the log being written as a simple text file.

Ants

The common denominator in any of the literature of this type is Ant's, for such little creatures it's quite amazing how much gets written about what they get up to. Mostly they just go around breeding, eating, occasionally fighting and then dying which makes them the perfect starting point for this type of program as they are about as simple as things can get when trying to look at a model of a living system. Well you could get simpler but then you start dealing with life forms that don't do what we as human beings would consider to be the basic requirements of life. That isn't to say that other life forms aren't valid life forms, it's just that from a human perspective we prefer things that in some ways have the same basic life requirements that we do.

Ants fulfil these requirements to a large extend by the fact that their lives are based on a clearly defined social structure with each creature having a specific role to fill within the society. Although this role can change as the requirements of the society change the specific ant has a specific role at any one time.

Amoebas

Fear the amoeba.

Algorithms

The Basic Algorithms

There are a number of simple rules for the basic algorithm, these being:

  • The ant must find the food and return it to the nest
  • The ant has no detailed knowledge of its environment
  • The ant can only remember where it previously came from. Up to four moves
  • The ant's navigation is helped through the use of pheromones

How the Basic Algorithm works

The basic algorithms both follow the points given above with one major difference between the two implementations. The first implementation which is the Basic Algorithm constantly updates the decision. That is at any point through the process of deciding which way it is going to go, the ant has an idea of which way it wants to go that may or may not end up as being the final direction. The difference between this algorithm and the Basic 2 Algorithm is that the second algorithm uses the Fuzzy Decision class in the way that it was originally envisaged. This means that throughout the decision making process, the algorithm increments or decrements its available options and decides which way to move on which available decision has the highest score once the end of the decision making process is reached.

Problems with the Basic Algorithms

Entropy

The performance of the algorithm can fail suddenly with the ants becoming stuck in certain locations, which tends to result in them shuffling backwards and forwards from one square to another. This occurs before the ants have found the food and even after they have found food. The reason for this is that the ant has very little knowledge about where it is going or even where it has been, so its movements are mostly reactionary to its immediate surroundings. To help combat this, I've given the most basic ants a short term memory about where they have been. This means that they can remember the last four moves that they made and check to see if they are repeating the same moves over and over, at which point the code tries to force a different move. At this point though, the move is not based on any knowledge of direction or purpose.

Sequential reasoning

Sequential reasoning has raised its head a couple of times in the development of the basic ant algorithm. The simplified code goes something like this:

C#
if( APossibleDirection == "TOP" )
    goToTheTop;
else if( APossibleDirection == "RIGHT" )
    goToTheRight;
else if( APosibleDirection == "BOTTOM" )
    goToTheBottom;
else
    goToTheLeft;

Now picture this code from the ant's point of view. On most squares that you are moving from, you have at least two directions to move in. The problem with the above code is that if you can move either left or right, then in the following code you are always going to move right; moving to the left will not even be considered and if you where to use straight ifs then the ant would always go left. It was this reasoning that inspired the Fuzzy Decision class which at present is a simple mechanism for rating a decision that is based on the class having no knowledge of the decision that is being made.

One of the interesting things in coding the algorithms was changing the order of the sequential logic in the program and observing what effect it had on the way in which the ants moved around the map. There may be some options that allow people to observe this for themselves at some point.

Over complicated maps

This is where Path Finding the basic algorithms break down due to the fact that map structure is too complicated for it. Prime examples of this are the basic algorithm in the SnakesNLadders map and that neither of the algorithms have an easy time finding their way back to the base, once they have found the food.

The Pheromones Algorythm

The main change with this algorythm is

  • A better implementation of the pheromone code so the ants will follow it properly

The Pheromones Algorythm is based on the idea that the ants should follow the pheromones trails laid down by previous ants that have found the food and that the pheromone trail should point the way to the food or whatever the pheromone trail is supposed to indicate. At this point only the food pheromone is implemented and the ants can follow the trail back to the food.

Problems with the Pheromone Algorythm

On its own the Pheromone Algorythm isn't enough to get the ants working properly. This is due to the fact that the Pheromone Algorythm is an extension of the Basic 2 Algorythm and that it has all the same inherent problems. These are caused by the fact that once the ant has found the food there is no improvement in it's ability to get home. This means that if an ant is trying to find it's way home and gets lost/confused then it can leave a pheromone trail that leads away from the food instead of towards it.

The Memory Algorythm

The main change with this algorythm is,

  • Ants now remember the path they took from the nest to the food

This is a simple modification to the basic algorythm in that the only change is that the ant remembers each step that it takes to get from the nest to the food.

Problems with the Memory Algorythm

As with the pheromone algorythm the memory algorythm isn't enough to get the ants working properly on it's own. This is due to a couple of reasons the first being that if the ant takes the scenic route to the find the food then it is going to take the scenic route back to the base as there is no optimisation of the way back but a reliance on blindly following each step backwards. Also in this implementation the ant retains no memory of how to get back to the food so that once it does find it's way back to the nest with the food then it starts over again searching for the food.

The Hill Climbing Algorythm

The main change with this algorythm is,

  • The Ants now remember every square that they have crossed

The Hill Climbing algorythm is based on the idea that the ants follow a path to it's end and then return to the starting point and choose a different route. This idea was too simplistic to implement as such and so the ants don't religiously track back to where they started from but use the information a bit more intelligently to explore different paths within the map.

Problems with the Hill Climbing Algorythm

Although the Hill Climbing algorythm functions better than some of the other algorythms at present this is due mainly to the fact that it explores the entire map, so it's bound to get there eventually. Also the ants tend to hang around in gangs there is no separation like there is with the other algorythms as it doesn't implement the ant specific code such as trying to avoid squares that other ants are occupying.

The Hill Climbing Algorythm Two

The Hill Climbing Two algorythm uses the standard Hill Climbing code from the previous algorythm but influences the decision with data provided by the pheromone trails. Although this is only done during the search for the food and the algorythm uses the standard Hill Climbing code to try and find it's way back to the nest. It was this algorythm that inspired the Hill Climbing Three algorythm that has a more natural result.

Problems with the Hill Climbing Two Algorythm

Despite it's relative simplicity this algorythm is surprisingly functional although it does tend to have cases of wandering, where the ants just decide that they want to go off an see what is in some other direction.

The Hill Climbing Algorythm Three

The main changes for the third Hill Climbing algorythm are that the ants now use the pheromone trails to find the food effectively and the code now considers the pheromone values and not just if the square has a pheromone signature. This is done so that the ants will follow the most popular trail to the food and then use the memory algorythm to find their way back to the nest. This has the effect that the ants now follow a more natural pattern in that once a popular trail to and from the food is established the ants will religiously follow it. The path that they follow will not necessarily be the fastest path too or from the food but the most popular.

This was done by rewriting the Hill Climbing algorythm and placing the emphasis on moving forwards, away from any squares that have been previously visited at any point by a specific ant rather than on the idea of was only visited on the previous move.

Problems with the Hill Climbing Algorythm Three

At present there aren't any real problems that can be associated with the algorythm itself at this stage. Although things have turned up such as the code not resetting the pheromone counts properly and confusing the ants but this is an implementation problem of mine and nothing to do with the actual algorythm.

Thunks

With the implementation of the Hill Climbing Three algorythm the question of how intelligent ants actually are in the real world is starting to come into play any will of course require more research. One of the reasons for this is that I am currently using a simple memory system in which the ants find their way back to the nest by remembering exactly where they have been, yet from my admittedly limited reading on the subject ants in the real world are able to take short cuts back to the nest once they have decided to return home.

The main question here will be one of implementation as I will need to do this in a way that does not involve having an overview of the map other than what the ant in question has seen.

Things to fix

Implement better algorithm management.

Things to implement

Implement new board control

References

  • Tom Archer ( 2001 ) Inside C#, Microsoft Press
  • Jeffery Richter ( 2002 ) Applied Microsoft .NET Framework Programming, Microsoft Press
  • Charles Peltzold ( 2002 ) Programming Microsoft Windows With C#, Microsoft Press
  • Robinson et al ( 2001 ) Professional C#, Wrox
  • Bart Kosko ( 1994 ) Fuzzy Thinking, Flamingo
  • Buckley & Eslami ( 2002 ) An Introduction To Fuzzy Logic And Fuzzy Sets, Physica-Verlag
  • Earl Cox ( 1999 ) The Fuzzy Systems Handbook, AP Professional
  • Steven Johnson ( 2001 ) Emergence, The Penguin Press
  • John H. Holland ( 1998 ) Emergence From Chaos To Order, Oxford University Press
  • Mark Ward ( 1999 ) Virtual Organisms, Pan
  • Bonabeau, Dorigo, Theraulaz ( 1999 ) Swarm Intelligence From Natural To Artificial Systems, Oxford University Press

History

  • 21 September 2003 - Initial release with Ants, Amoeba and two basic algorithms.
  • 30 October 2003 - Added Map Editor and four maps
  • 17 December 2003 - Added the Pheromones, Memory and Hill Climbing algorythms.
  • 29 April 2004 - Added Logging and Two more Hill Climbing Algorythms.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
United Kingdom United Kingdom
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionMissing source code ??? Pin
JammiM1916-Mar-13 6:55
JammiM1916-Mar-13 6:55 
GeneralMy vote of 4 Pin
Kanasz Robert10-Nov-10 2:02
professionalKanasz Robert10-Nov-10 2:02 
GeneralThanks Pin
nc.vinh20-May-10 16:26
nc.vinh20-May-10 16:26 
GeneralNice Work Pin
Amro Ibrahim21-Apr-08 1:35
Amro Ibrahim21-Apr-08 1:35 
Questionhow do you run the program? Pin
o_OGolixO_o16-May-04 9:37
o_OGolixO_o16-May-04 9:37 
QuestionWhy did you bother? Pin
Brojon24-Sep-03 2:43
Brojon24-Sep-03 2:43 
AnswerRe: Why did you bother? Pin
martininick5-May-04 5:12
martininick5-May-04 5:12 
GeneralRe: Why did you bother? Pin
Brojon5-May-04 6:09
Brojon5-May-04 6:09 
Generalyou ve got it: it isn't about the matrix DVD goodies Pin
elnino15-Jun-04 21:20
elnino15-Jun-04 21:20 
GeneralRe: you ve got it: it isn't about the matrix DVD goodies Pin
Brojon16-Jun-04 2:52
Brojon16-Jun-04 2:52 
GeneralSome of us are busy *doing*. Pin
pseudonym6718-Jun-04 18:33
pseudonym6718-Jun-04 18:33 
GeneralRe: Some of us are busy *doing*. Pin
Brojon21-Jun-04 7:31
Brojon21-Jun-04 7:31 
GeneralRe: Some of us are busy *doing*. Pin
pseudonym6721-Jun-04 8:45
pseudonym6721-Jun-04 8:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.