Posted by ljmacphee on May 30, 2007 under robotics, useful websites | 
Talking Robots Podcast from the Laboratory of Intelligent Systems features interviews with leading researchers in robotics.
The podcast is done Dario Floreano a professor at Ecole Polytechnique Federale de Lausanne in France. His main interests are in evolutionary robotics. He has also done significant work in neural systems, artificial life, evolutionary computation, swarm robotics and biomimetic electronics.
Posted by ljmacphee on May 28, 2007 under topics in artificial intelligence |
The ant algorithm was developed from real ants. Ants searching for food leave a trail of pheromones. An ant who takes the shortest path between the nest and the food leaves the most amount of pheromone since he makes more trips. The stronger the pheromone scent the more ants follow that trail.
This has been applied to the Traveling Salesman Problem, as well as to scheduling problems. Though it is an interesting solution it is not fast so may have limited applications with out modification.
This algorithm assumes a fully connected graph, otherwise your ants may quickly box them selves into corners. Each ant starts in a different city. Each ant chooses a city he has not yet visited. The choice is based on a greedy heuristic ( shortest path ) and the path with the greatest amount of pheromone.
Once a path is chosen, the ant puts down pheromone. The amount of pheromone is some constant divided by distance. This gives more pheromone to shortest paths.
The older pheromone evaporates. So each round we decrease the pheromone on each edge by a small amount.
Algorithm:
-choose a map or generate one
-generate map ( pick a specific number of cities, generate a random x,y for each to give it a position. )
-create one ant for each city
-start each ant in a different city
LOOP
for each ant {
pick city to move to
lay down pheromone along path just traveled
add this city to city list so we can see the path the ant took when we are done
update the total distance ant traveled so far
}
for each path {
decrease pheromone
}
END LOOP
Print shortest path
} //end
Pick_City( cities_ant_can_move_to ){
beta //is length or amount of pheromone most important? Use a number between 0 and 1
for each city ant may choose from this location{
Score = Amount_of_Pheromone + Length_to_City^Beta
If this score lowest keep
}
Move on path with least score
}
Lay_down_pheromone( edge ){
gamma //some constant between 0 & 1 to adjust pheromone
pheromone_on_this_edge += gamma/length_of_edge
}
Decrease_pheromone_with_time( edge ){
alpha // some number between 0 and 1
pheromone_on_this_edge *= alpha
}
Ant{
total_distance_traveled;
cities_traveled_in_order;
}
Edge{
City1;
City2;
length;
current_amount_of_pheromone;
}
More information:
The ant algorithm was developed from real ants. Ants searching for food leave a trail of pheromones. An ant who takes the shortest path between the nest and the food leaves the most amount of pheromone since he makes more trips. The stronger the pheromone scent the more ants follow that trail.
This has been applied to the Traveling Salesman Problem, as well as to scheduling problems. Though it is an interesting solution it is not fast so may have limited applications with out modification.
This algorithm assumes a fully connected graph, otherwise your ants may quickly box them selves into corners. Each ant starts in a different city. Each ant chooses a city he has not yet visited. The choice is based on a greedy heuristic ( shortest path ) and the path with the greatest amount of pheromone.
Once a path is chosen, the ant puts down pheromone. The amount of pheromone is some constant divided by distance. This gives more pheromone to shortest paths.
The older pheromone evaporates. So each round we decrease the pheromone on each edge by a small amount.
Algorithm:
-choose a map or generate one
-generate map ( pick a specific number of cities, generate a random x,y for each to give it a position. )
-create one ant for each city
-start each ant in a different city
LOOP
for each ant {
pick city to move to
lay down pheromone along path just traveled
add this city to city list so we can see the path the ant took when we are done
update the total distance ant traveled so far
}
for each path {
decrease pheromone
}
END LOOP
Print shortest path
} //end
Pick_City( cities_ant_can_move_to ){
0<beta<1 //is length or amount of pheromone most important?
for each city ant may choose from this location{
Score = Amount_of_Pheromone + Length_to_City^Beta
If this score lowest keep
}
Move on path with least score
}
Lay_down_pheromone( edge ){
gamma //some constant between 0 & 1 to adjust pheromone
pheromone_on_this_edge += gamma/length_of_edge
}
Decrease_pheromone_with_time( edge ){
alpha // some number between 0 and 1
pheromone_on_this_edge *= alpha
}
Ant{
total_distance_traveled;
cities_traveled_in_order;
}
Edge{
City1;
City2;
length;
current_amount_of_pheromone;
}
See also:
SantaFe Ant trail description and source code
More information:
Central Intelligence: From Ants to Web ( YouTube TED video )
Artificial Intelligence network load balancing using Ant Colony Optimisation ( source code and article )
Ant Colony System: A Cooperative Learning Approach to the TSP
ACO Algorithms for the TSP
Wiki, Ant colony optimization
Ants riddled with cheating and corruption ( perhaps they are not as simple as we think? )
Posted by ljmacphee on May 25, 2007 under artificial intelligence in the news |
New Scientist has an article that claims billboards can now be installed with a camera that tracks eye movements to see if you are paying attention to the billboard from 30′ away.
Previous tracking software needed to be with in a few feet of you. This package will also track several people at a time.
This technology is also being used to make hearing aids more effective by focusing them in the direction in which you are looking at a given time.
Tracking billboards could give you the eyeball
Posted by ljmacphee on May 23, 2007 under artificial intelligence in the news |
At least if someone is really, really interested in your shredded notes.
A research team in Germany developed a software system to piece back 45 million pages of shredded secret police files. At the heart of the software is an image processing and digital patterns tool they have spent years developing.
Anti-shredder aims to stick spy files back together
Posted by ljmacphee on May 21, 2007 under artificial intelligence in the news |
The WP has an interesting story on AI in chess. They note that it was ten years ago last week that a computer first beat a world chess champion. Since then 3 more computer vs grand master matches have taken place and two draws and a loss were acquired by the grand masters.
The article goes on in depth about how this interaction is making chess masters better, and all the rest of us who interact with computers or program the computers.
It’s an interesting read.
We’ve Made Our Match