A* ALGORITHM BASICS FOR PATH FINDING & HEURISTICS METHODS : ARTIFICIAL INTELLIGENCE

 A* ALGORITHM BASICS FOR PATH FINDING

A*, widely used  known form of best-first search & path planning algorithm nowadays in mobile robots,games.

this is the function for A*,

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

g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal

This will find cheapest f(n) value in neighbor nodes to archive goal node.

check below image  A to B path finding with g(n),h(n),f(n) value

In the final level check below image

Now we will check the Algorithm

// A* Search Algorithm
1.  Initialize the open list
2.  Initialize the closed list
    put the starting node on the open 
    list (you can leave its f at zero)
3.  while the open list is not empty
    a) find the node with the least f on 
       the open list, call it "q"
    b) pop q off the open list
    c) generate q's 8 successors and set their 
       parents to q
    d) for each successor
        i) if successor is the goal, stop search
          successor.g = q.g + distance between 
                              successor and q
          successor.h = distance from goal to 
          successor (This can be done using many 
          ways, we will discuss three heuristics- 
          Manhattan, Diagonal and Euclidean 
          Heuristics)
          successor.f = successor.g + successor.h
        ii) if a node with the same position as 
            successor is in the OPEN list which has a 
           lower f than successor, skip this successor
        iii) if a node with the same position as 
            successor  is in the CLOSED list which has
            a lower f than successor, skip this successor
            otherwise, add  the node to the open list
     end (for loop)
    e) push q on the closed list
    end (while loop)  

Properties of A*

On finite graphs with non-negative edge weights A* is guaranteed to terminate and is complete.
A search algorithm is said to be admissible if it is guaranteed to return an optimal solution .
Algorithm A is optimally efficient with respect to a set of alternative algorithms .
 

check below for the easy understanding of A*

HEURISTICS METHODS 

1) Manhattan Distance –
It is nothing but the sum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively, 

i.e., h = abs (current_cell.x – goal.x) + abs (current_cell.y – goal.y)

When to use this heuristic? – When we are allowed to move only in four directions only (right, left, top, bottom)

 

2) Diagonal Distance-
It is nothing but the maximum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively, 

i.e., h = max { abs(current_cell.x – goal.x), abs(current_cell.y – goal.y) }

When to use this heuristic? – When we are allowed to move in eight directions only (similar to a move of a King in Chess)

 

3) Euclidean Distance-
As it is clear from its name, it is nothing but the distance between the current cell and the goal cell using the distance formula 

h = sqrt ( (current_cell.x – goal.x)2 + (current_cell.y – goal.y)2 )

When to use this heuristic? – When we are allowed to move in any directions.