In this movie the robot successfully plans a route to the goal using A* and
arrives at the goal.
Successful movie
In this movie the A* planning fails as the goal is unreachable.
Failure movie
A note on the movies:
The Blue nodes are unvisited nodes.
The Black nodes are those that are unreachable
since they are within a C-space obstacle.
The Red node is the goal node.
The Green node is the one that is currently being
expanded by the A* algorithm. When A* is finished, it is also used to
represent the start node.
The Orange nodes are those that are currently in
the Open List priority queue.
The Grayish nodes are those that have already been
expanded and are thus on the Closed list.
The Teal nodes show the shortest path to the goal
once A* is complete.
For this assignment I implemented the A* path planning algorithm to find a path from start to finish. After a few false starts with priority queues, I ended up using my friend Matt McNaughton's priority queue template class with a few minor adaptations and one bug fix to work with my code.
With regards to cost functions, I decided to keep it simple and as close to "reality" (reality in a simulator?) as possible. The cost between nodes was just their Euclidean distance, and the heuristic cost was the straight distance from the node to the goal. I chose this heuristic because it is an admissible heuristic, meaning it ensures that you can find the optimal path to the goal since the heuristic cost is less than or equal to the actual cost (in the plane). It also happens to be the one used in the text. :-)