Artificial Intelligence for Robotics

The A* algorithm

Honestly, you can’t really write a book about robotics without mentioning the A* algorithm. A* has its origins with Shakey the Robot at Stanford University back in 1968. This was one of the first map navigating robots. Nils Nilsson and his team were trying to find a method to navigate Shakey around the hallways at Stanford, and started trying different algorthms. The first was called “A1”, and so forth. After several iterations, the team decided that a combination of techniques worked best. In computer science, A* means the letter A followed by anything else, and thus the A-Star was named.

The concept of the A-Star process is very much like what we have already been doing with our other path planners. Like the wavefront planner, ...