- <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:
- DefaultMap which is the default map on loading and is pictured
above.
- The TwoFoodsMap which is another simple map having two food
sources
placed on it.
- The SnakesNLaddersMap resembles a snakes and ladders board and
- 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:
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 if
s
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.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.