Ant Simulator - BSc Computer Science Project

Last Meeting

Thursday 26/04/2007, 07:00 PM

Project has gone very well. Sebastian is pleased with the report progress so far. Almost complete. Software not completely functional yet.

Problems with Ants 2.0

Friday 16/03/2007, 07:00 PM

After lengthy discussion during this meeting we came across a problem with the algorithm.

It is entirely possible that ants will go the long way round initially, and therefore lay a trail the long way to the food. The shortest path will not be found. After some different variations we came up with breadth-first search as the solution! Something wasn't quite right!

It was decided to do some more research into the MUTE application, to learn more about their implementation

Addition: I realised that MUTE uses a discovery algorithm, akin to breadth-first search to establish a route before using ant based algorithms for routing.

Ants 2.0

Thursday 8/03/2007, 08:10 PM

I spent the last week working on part 2.0 of my project - implementing a graph and getting ants to find the shortest path between two points.

I've implemented a gui that allows a user to create a graph on screen by placing nodes and creating edges between those nodes. Nodes and edges can be added and removed, and nodes can be dragged around. The length of the edges are calculated and shown. Printing is also available by pressing 'p'.

Sebastian was pleased with the graph application and we discussed what to do next, in terms of getting ants to move around the graph and find the shortest path between two points.

Wed decided to base the idea on the one from the MUTE application previously described. The algorithm involves two kinds of trails - those going from nest to food, and those going from food to nest. Ants looking for food will like to follow nest to food trails, while those carrying food will like to follow food to nest trails. Trails evaporate over time and the strength is determined by how many ants have laid some trail.

We realised there could be difficulty implementing this for a general weighted graph, and decided to first implement where all weights are 1.

The difficulty is caused because ants should take longer to reach nodes that are further away, but this means that after each iteration an ant cannot instantaneously move from its current node to the next node as this would ignore the distances. An idea to implement this would be to have ants actually move along edges at a constant speed. Ants travelling along longer edges will take longer to reach their destination nodes, whereas ants travelling along shorter nodes will reach their destination quicker. To simplify this problem for the first version, we decided to have all weights equal to one so that each ant can travel the same distance in the same time.

Project Direction

Thursday 1/03/2007, 08:00 PM

Showed Sebastian the latest version of the ant simulator. There are many problems with it!

Sebastian was worried about the direction of the project and suggested that we move on to graph algorithms, as most of what is happening now is tweaking the existing movement algorithm to stop it getting stuck at obstacles!

We realised that implementing a graph structure and developing an ant algorithm using this should be simpler, as there are no obstacles involved.

We discussed the MUTE P2P routing algorithm description and decided to based the new ant algorithm on this idea.

Tasks for next week: implement a graph data structure, explain the new ant algorithm.

Not much progress

Thursday 8/02/2007, 08:00 PM

Many movement algorithm rewrites, but not much progress. Discussed possible improvements to the algorithm.

Last Meeting of Term 1

Friday 15/12/2006, 07:00 PM

Prolog took most of my time this week again!

We discussed what should be done over the Christmas break. The aim is to finish the main programming over this time, in order to have time to experiment and write up over the next term.

One of the main tasks is to re-write the move() method, in the Ant class. It needs some thought before actually being implemented to get it right.

Another, less important, task is to create a smoother moving animation. I believe the main problem causing this is the amount of 'work' each ant has to do every time it moves e.g. it looks at the surrounding squares, sorts them etc. The use of Vector's for this probably slows it down, and it may be needed to use arrays instead. This is not as important though as it does not effect the algorithms, it would just make the simulation look more like real ants (Am I trying to create realistic ants, or model ant behaviour? I'd say the latter - the model doesn't have to be super-realistic, just borrow ideas from nature).

Next will be to implement some kind of graph system; a maze like system - where the graph will be 'where the obstacles are not'. This can't really work until the ants are actually behaving some-what like real ants.

Some problems solved

Thursday 7/12/2006, 07:00 PM

I showed Sebastian the implementation of new movement algorithm - he especially liked how the ants walked around each other.

There are still some problems with the algorithm and the move() method in the Ant class needs rewriting.

I showed Sebastian another ant simulation and he liked how the ants on the other simulation move a lot smoother than mine which makes them look more like ants. I will try to make the movement of my ants smoother.

We also took note that there is no use of Food Strengths in the other simulation and pheromones spread further and dissipate quicker than in mine. There version works very well.

Meeting

Friday 1/12/2006, 07:00 PM

We discussed problems encountered with my first implementation of the pheromone trail following. See Split Trail Problem and Bouncing Ant Problem

We discussed solutions and came up with the idea that ants only see ahead of them not in all directions. See changing ant movement for more details.

Ants Get Stuck!

Friday 24/11/2006, 07:00 PM

Showed Sebastian my latest version with the new FoodStrength calculations.

Sebastian and I agreed this works much better.

I explained the problem of ants getting stuck against obstacles. Sebastian suggested introducing randomness, so that if an ant encounters and obstacle they randomly choose another direction instead of just turning around - with this version they are turning around and then going back the same way because it is the 'best' square for them to choose.

Tasks for next week

Fix the dancing ant problem
Get ants to return food to collect food and return it to the nest - Sebastian suggested ants know where the nest is
Implement Pheromone trails (this was partially working before and need to get it working again

See simulation(s): Version 8.0

A Little Progress

Friday 17/11/2006, 07:00 PM

Had been distracted by a Prolog assignment, so hadn't much to show Sebastian!

The FoodClusters was not well recieved by Sebastian. I agree after he told me why.

I will change the Food Strength value to be calculated by each GridSquare individually instead of using clusters.

See simulation(s): Version 6.0 Version 7.0

Progress

Friday 3/11/2006, 07:00 PM

Showed Sebastian latest Ant Simulator: Ants tend to move towards the food due to a food strength value radiating outward from the food source.

This uses an inverse square law so ants tend to move towards the center.

I've implemented this by having the ants ask the GridSquare for all the surrounding GridSquare's with a radius of 1 GridSquare. The Ant then sorts these based on Food Strength, and moves the the GridSquare with the highest Food Strength.

Some problems include ants getting trapped between food sources, and clusters maybe too strong.

I need to implement controls to change values such as the radius of the food strength as the program is running.

We also discussed the direction the project is going to take after this section is complete. My idea is the use the Ants to solve shortest path problems. And to do this I will add Obstacles to the Grid, such that the graph is where the obstacles aren't. It should be possible to draw graphs onto the grid and have to see the ants move around the grid and hopefully find the shortest path from their nest to the food source.

See simulation(s): Version 5.0

Meeting with Sebastian

Friday 27/10/2006, 07:00 PM

We discussed further how to make the ants seem more real.

I showed Sebastian two books that I have been using for research and a research paper about the use of ant systems for web searching: neither of us understood this - we will try to for next week!

See simulation(s): Version 4.0

Progress

Friday 20/10/2006, 07:00 PM

Showed Sebastian some new versions of the simulation.

Sebastian suggested that the ants are not moving realistically yet. He suggested ants could 'smell' for a certain radius and food produces a smell for a certain radius around it. This way ants will tend to move towards food.

The food smell could possible use an inverse square law to determine density as it gets further from the food.

See simulation(s): Version 2.0 Version 3.0

First meeting with Sebastian

Friday 13/10/2006, 07:30 PM

Discussed how to start project. We decided I should concentrate on the simulation of ants and decide whether to continue the project on as a way of solving graph path problems later.

Showed Sebastian my first version, and he suggested the next version ants should come out from a 'nest' and pick up food, then continue walking around randomly until the find the nest where they will drop off the food.

Sebastian advised to create a skeleton project report in LaTeX to fill in as I progress with the project.

See simulation(s): Version 1.0











Last Meeting Thursday 26/04/2007, 07:00 PM Project has gone very well. Sebastian is pleased with the report progress so far. Almost complete. Software not completely functional yet. Problems with Ants 2.0 Friday 16/03/2007, 07:00 PM After lengthy discussion during this meeting we came across a problem with the algorithm. It is entirely possible that ants will go the long way round initially, and therefore lay a trail the long way to the food. The shortest path will not be found. After some different variations we came up with breadth-first search as the solution! Something wasn't quite right! It was decided to do some more research into the MUTE application, to learn more about their implementation Addition: I realised that MUTE uses a discovery algorithm, akin to breadth-first search to establish a route before using ant based algorithms for routing. Ants 2.0 Thursday 8/03/2007, 08:10 PM I spent the last week working on part 2.0 of my project - implementing a graph and getting ants to find the shortest path between two points. I've implemented a gui that allows a user to create a graph on screen by placing nodes and creating edges between those nodes. Nodes and edges can be added and removed, and nodes can be dragged around. The length of the edges are calculated and shown. Printing is also available by pressing 'p'. Sebastian was pleased with the graph application and we discussed what to do next, in terms of getting ants to move around the graph and find the shortest path between two points. Wed decided to base the idea on the one from the MUTE application previously described. The algorithm involves two kinds of trails - those going from nest to food, and those going from food to nest. Ants looking for food will like to follow nest to food trails, while those carrying food will like to follow food to nest trails. Trails evaporate over time and the strength is determined by how many ants have laid some trail. We realised there could be difficulty implementing this for a general weighted graph, and decided to first implement where all weights are 1. The difficulty is caused because ants should take longer to reach nodes that are further away, but this means that after each iteration an ant cannot instantaneously move from its current node to the next node as this would ignore the distances. An idea to implement this would be to have ants actually move along edges at a constant speed. Ants travelling along longer edges will take longer to reach their destination nodes, whereas ants travelling along shorter nodes will reach their destination quicker. To simplify this problem for the first version, we decided to have all weights equal to one so that each ant can travel the same distance in the same time. Project Direction Thursday 1/03/2007, 08:00 PM Showed Sebastian the latest version of the ant simulator. There are many problems with it! Sebastian was worried about the direction of the project and suggested that we move on to graph algorithms, as most of what is happening now is tweaking the existing movement algorithm to stop it getting stuck at obstacles! We realised that implementing a graph structure and developing an ant algorithm using this should be simpler, as there are no obstacles involved. We discussed the MUTE P2P routing algorithm description and decided to based the new ant algorithm on this idea. Tasks for next week: implement a graph data structure, explain the new ant algorithm. Not much progress Thursday 8/02/2007, 08:00 PM Many movement algorithm rewrites, but not much progress. Discussed possible improvements to the algorithm. Last Meeting of Term 1 Friday 15/12/2006, 07:00 PM Prolog took most of my time this week again! We discussed what should be done over the Christmas break. The aim is to finish the main programming over this time, in order to have time to experiment and write up over the next term. One of the main tasks is to re-write the move() method, in the Ant class. It needs some thought before actually being implemented to get it right. Another, less important, task is to create a smoother moving animation. I believe the main problem causing this is the amount of 'work' each ant has to do every time it moves e.g. it looks at the surrounding squares, sorts them etc. The use of Vector's for this probably slows it down, and it may be needed to use arrays instead. This is not as important though as it does not effect the algorithms, it would just make the simulation look more like real ants (Am I trying to create realistic ants, or model ant behaviour? I'd say the latter - the model doesn't have to be super-realistic, just borrow ideas from nature). Next will be to implement some kind of graph system; a maze like system - where the graph will be 'where the obstacles are not'. This can't really work until the ants are actually behaving some-what like real ants. Some problems solved Thursday 7/12/2006, 07:00 PM I showed Sebastian the implementation of new movement algorithm - he especially liked how the ants walked around each other. There are still some problems with the algorithm and the move() method in the Ant class needs rewriting. I showed Sebastian another ant simulation and he liked how the ants on the other simulation move a lot smoother than mine which makes them look more like ants. I will try to make the movement of my ants smoother. We also took note that there is no use of Food Strengths in the other simulation and pheromones spread further and dissipate quicker than in mine. There version works very well. Meeting Friday 1/12/2006, 07:00 PM We discussed problems encountered with my first implementation of the pheromone trail following. See Split Trail Problem and Bouncing Ant Problem We discussed solutions and came up with the idea that ants only see ahead of them not in all directions. See changing ant movement for more details. Ants Get Stuck! Friday 24/11/2006, 07:00 PM Showed Sebastian my latest version with the new FoodStrength calculations. Sebastian and I agreed this works much better. I explained the problem of ants getting stuck against obstacles. Sebastian suggested introducing randomness, so that if an ant encounters and obstacle they randomly choose another direction instead of just turning around - with this version they are turning around and then going back the same way because it is the 'best' square for them to choose. Tasks for next week Fix the dancing ant problem Get ants to return food to collect food and return it to the nest - Sebastian suggested ants know where the nest is Implement Pheromone trails (this was partially working before and need to get it working again See simulation(s): Version 8.0 A Little Progress Friday 17/11/2006, 07:00 PM Had been distracted by a Prolog assignment, so hadn't much to show Sebastian! The FoodClusters was not well recieved by Sebastian. I agree after he told me why. I will change the Food Strength value to be calculated by each GridSquare individually instead of using clusters. See simulation(s): Version 6.0 Version 7.0 Progress Friday 3/11/2006, 07:00 PM Showed Sebastian latest Ant Simulator: Ants tend to move towards the food due to a food strength value radiating outward from the food source. This uses an inverse square law so ants tend to move towards the center. I've implemented this by having the ants ask the GridSquare for all the surrounding GridSquare's with a radius of 1 GridSquare. The Ant then sorts these based on Food Strength, and moves the the GridSquare with the highest Food Strength. Some problems include ants getting trapped between food sources, and clusters maybe too strong. I need to implement controls to change values such as the radius of the food strength as the program is running. We also discussed the direction the project is going to take after this section is complete. My idea is the use the Ants to solve shortest path problems. And to do this I will add Obstacles to the Grid, such that the graph is where the obstacles aren't. It should be possible to draw graphs onto the grid and have to see the ants move around the grid and hopefully find the shortest path from their nest to the food source. See simulation(s): Version 5.0 Meeting with Sebastian Friday 27/10/2006, 07:00 PM We discussed further how to make the ants seem more real. I showed Sebastian two books that I have been using for research and a research paper about the use of ant systems for web searching: neither of us understood this - we will try to for next week! See simulation(s): Version 4.0 Progress Friday 20/10/2006, 07:00 PM Showed Sebastian some new versions of the simulation. Sebastian suggested that the ants are not moving realistically yet. He suggested ants could 'smell' for a certain radius and food produces a smell for a certain radius around it. This way ants will tend to move towards food. The food smell could possible use an inverse square law to determine density as it gets further from the food. See simulation(s): Version 2.0 Version 3.0 First meeting with Sebastian Friday 13/10/2006, 07:30 PM Discussed how to start project. We decided I should concentrate on the simulation of ants and decide whether to continue the project on as a way of solving graph path problems later. Showed Sebastian my first version, and he suggested the next version ants should come out from a 'nest' and pick up food, then continue walking around randomly until the find the nest where they will drop off the food. Sebastian advised to create a skeleton project report in LaTeX to fill in as I progress with the project. See simulation(s): Version 1.0