A* Algorithm-Artificial Intelligence

Algorithm A*

The algorithm is a first search algorithm that is both complete and optimal. It maintains two lists.
i) LIST_OPENED: It stores those nodes that have been generated and on which heuristic function have been applied. But they have not yet been examined. This is a priority list between wherein nodes with higher promising value are given higher priority.

ii) LIST_CLOSED: It stores those nodes that have been examined already, Whenever, a new node is generated, LIST_CLOSED is searched to check whether or not that node is already examined.

A* algorithm evaluates nodes using a heuristic function f(n), which is a combination of two functions i.e., 

    f(n)=g(n) + h(n)

where,

    g(n) ➝ It returns the cost of path from the starting node to node ‘n’.
    h(n) ➝ It returns the estimated cost of the most inexpensive path from node 'n' to the goal node.
    Therefore, f(n) = g(n) + h(n) will give the estimated cost of the cheapest path to the goal node (i.e, optimal solution)

A* algorithm finds the least cost path from a starting node to goal node. A* algorithm is admissible, meaning that it finds an optimal path to a goal  (if it exists), provided that h(n) never over estimates the cost to reach the goal. Admissible heuristics are always optimistic because they assume the cost of solution to be lesser than its actual cost.
The major limitation of A* algorithm is its space requirement (for storing lists). therefore, it is not used in large scale problems.

A* Algorithm

Step 1: Place the initial node in ‘LIST_OPENED’ and set LIST_CLOSED to an empty list.

Step 2: initialize g(n) = 0,

            h(n) = Heuristic estimate of distance from initial node to goal node.

            f(n) = g(n) + h(n)

Step 3: Repeat the following steps till a goal node is found. 

1. If the LIST_OPENED is empty then report failure and exit.
2. Select a node from LIST_OPENED such that its f(n) value is the lowest. Lets call it PROMISING NODE.
3. Move the PROMISING_NODE from LIST_OPENED to LIST_CLOSED.
4. Check whether PROMISING_NODE is goal node. If yes, then report solution and exit. Otherwise expand the PROMISING_NODE (i.e., generate its SUCCESSORS) and for every SUCCESSOR perform the following steps

• i) Create a pointer and make it point back to PROMISING_NODE. These back pointers will help us to trace the path once a solution is found.
• ii) Calculate g(n) for SUCCESSOR as,
• g(SUCCESSOR) = g(PROMISING_NODE) + The cost of moving from PROMISING NODE to SUCCESSOR.
• iii) Search the LIST_OPENED to determine whether the SUCCESSOR is already present in the list (i.e., if it was already generated but not examined).
• iv) If it is present then we call this node as OLD_NODE. Now, we check to see whether it is cheaper to visit to OLD_NODE via its current parent or to visit to SUCCESSOR via PROMISING_NODE. If OLD_NODE is cheaper, then nothing is performed, else if SUCCESSOR is cheaper, then we have to reset OLD_NODE’S parent link to point to PROMISING_NODE. (Note that OLD_NODE and SUCCESSOR are both same, we have given different names only because of their different paths)
• v) If SUCCESSOR is not present in LIST OPENED, then check whether it is on LIST_CLOSED. If yes, call it as OLD_NODE and add it to list of PROMISING NODE’S_SUCCESSORS. Now, here also we check whether the old path is better or the new one. If path through OLD NODE is better, then we have to propagate the improvement to OLD’s SUCCESSORS. This is done by performing a depth first traversal and calculating new cost. Otherwise, if the path through current parent is better, continue propagation from that node.
• vi) If SUCCESSOR is not present in either LIST_OPENED or LIST_CLOSED, then we move the SUCCESSOR to LIST_OPENED and add it to list of PROMISING NODE's successors. Finally, we calculate,

                    f(SUCCESSOR) =  g(SUCCESSOR) + h(SUCCESSOR).

Example: Consider the following graph.

Consider that the heuristic function h(n) is the straight line between nodes and let h(n) for various nodes as follows:

The steps below shows how A* algorithm is applied to get the optimal path. 

Step 1:

Step 2

Step 3

Desirable Properties of Heuristic Search Algorithms: Some important properties of heuristic search algorithms which evaluates its performance optimality are,

1. Admissibility Condition: An algorithm is admissible if it is guaranteed to return an optimal solution if it exists.
2. Completeness Condition: An algorithm is complete if it always terminated with a solution, if it exists.
3. Dominance Property: In two admissible algorithms A₁, (heuristic estimated value h'(1)] and A₂, [heuristic estimated value h'(2)], A₁ is said to be more dominant and more informed than A₂, if h’(1) > h'(2).
4. Optimality Property: A solution to problem is a path from the initial state to the goal state. Solution quality is measured by the path cost function and an optimal solution has the lowest path cost among all solutions.