Algorithms For Dummies

  Considering Heuristics 

     385

Shakey  fully  autonomous,  its  developers  came  up  with  the  A*  algorithm,  the 

Hough transform (an image-processing transformation to detect the edges of an 

object), and the visibility graph method (a way to represent a path as a graph). 

The article at 

http://www.ai.sri.com/shakey/

 describes Shakey in more detail 

and even shows it in action. It is still surprising watching what Shakey was capa-

ble of doing; go to 

https://www.youtube.com/watch?v=qXdn6ynwpiI

 to take a 

look.  The  A*  algorithm  is  currently  the  best  available  algorithm  when  you’re 

looking for the shortest route in a graph and you must deal with partial informa-

tion and expectations (as captured by the heuristic function guiding the search). 

A* is able to