Planning: Navigating with A*

A* is a search method that can be used to find the shortest path between two locations in a mapped area. It has some nice qualities that make it appropriate for route finding in the context of a mobile robot:

• It's guaranteed to find a path, if one exists
• If there are multiple paths between the two locations, none of the others will be shorter than the one A* returns.

Source code, in Java, to implement A* on a grid map, along with an online applet that uses this code, is available here.