A * Search

A * Search AI Method

Given a network of nodes, with connections between them, were each connection has a "cost" of moving from one node to the next, the A* algorithm efficiently finds the lowest cost route from a starting node to a goal node. It does this by following the lowest cost path from the starting node, and increasing the length of that path until it is no longer the lowest cost path. A* moves from path to path, extending only the lowest cost option, and adding the additional cost into the total cost of the path. If that causes the path to no longer be the lowest cost, it is abandoned (for now) and the new lowest cost path is extended next instead.

Pseudocode:

push startNode onto openList while(openList is not empty) { currentNode = find lowest f in openList if currentNode is final, return the successful path push currentNode onto closedList and remove from openList foreach neighbor of currentNode { if neighbor is not in openList { save g, h, and f then save the current parent add neighbor to openList } if neighbor is in openList but the current g is better than previous g { save g and f, then save the current parent } }

A* was written in 1968 at SRI as part of the Shakey Robot project.