Path Planning Using A* Algorithm

The A* Algorithm is a widely popular graph traversal path planning algorithm that works similarly to Dijkstra’s algorithm. But it directs its search toward the most promising states, potentially saving time. For approaching a near-optimal solution with the available data-set/node, A* is the most widely used method. It is commonly used in static environments but also dynamic environments. In the gaming industry, the A* algorithm is widely used. Thanks to artificial intelligence (AI), the A* algorithm has been improved and tailored for robot path planning, intelligent urban transportation, graph theory, and automatic control applications. It is less computationally intensive and simpler than many other path planning algorithms, and its efficiency makes it suitable for use on constrained and embedded systems.

The A* algorithm is a heuristic algorithm that finds the best path using heuristic information. The A* algorithm must search the map for nodes and apply appropriate heuristic functions to provide guidance. The two factors that govern an algorithm are the efficient resources used to perform the task and the response time or computation time taken to perform the task. When using the A* algorithm, there is a trade-off between speed and accuracy. We can reduce the algorithm’s time complexity in exchange for more memory or consume less memory for slower executions. We find the shortest path in both cases. The A* algorithm can be used to find the shortest path to an empty parking space in a crowded parking lot.

Explanation

Consider a square grid having many obstacles and we are given a starting cell and a target cell. We want to reach the target cell (if possible) from the starting cell as quickly as possible. Here A* Search Algorithm comes to the rescue. What A* Search Algorithm does is that at each step it picks the node according to a value-‘f’ which is a parameter equal to the sum of two other parameters – ‘g’ and ‘h’. At each step it picks the node/cell having the lowest ‘f’, and process that node/cell.

We define ‘g’ and ‘h’ as

g = the movement cost to move from the starting point to a given square on the grid, following the path generated to get there.?

h = the estimated movement cost to move from that given square on the grid to the final destination. This is often referred to as the heuristic, which is nothing but a kind of smart guess.

Algorithm?

Create Open List and Closed List (Dijkstra 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
        
        ii) else, compute both g and h for successor
          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
        iii) if a node with the same position as 
            successor is in the OPEN list which has a 
           lower f than successor, skip this successor
        iV) 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)        

Consider the below figure if we want to reach the target cell from the source cell, then the A* Search algorithm would follow path as shown below. Note that the below figure is made by considering Euclidean Distance as a heuristics.

Heuristics?

The h function can be calculated using the following techniques:

Exact Heuristics – Either calculate the exact value of h (which is certainly time consuming).?????????????

OR?

Manhattan Distance – Approximate the value of h using some heuristics (less time consuming).

Exact Heuristics

This method helps to find the exact values of h, however this is very time consuming.

1) Pre-compute the distance between each pair of cells before running the A* Search Algorithm.

2) If there are no blocked cells/obstacles then we can just find the exact value of h without any pre-computation using the distance formula/Euclidean Distance.

Approximation Heuristics

1) Manhattan Distance –??

• Sum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively.

 h = abs (current_cell.x – goal) + 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)

The Manhattan Distance Heuristics is shown by the below figure (assume red spot as source cell and green spot as target cell).?

2) Diagonal Distance-?

• 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.,

dx = abs(current_cell.x – goal.x)
dy = abs(current_cell.y – goal.y)
 
h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
where D is length of each node(usually = 1) and D2 is diagonal distance between each node (usually = sqrt(2) ).         

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

The Diagonal Distance Heuristics is shown by the below figure (assume red spot as source cell and green spot as target cell).

3) Euclidean Distance-

• 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.

The Euclidean Distance Heuristics is shown by the below figure (assume red spot as source cell and green spot as target cell).

Implementation?

We can use any data structure to implement open list and closed list but for best performance, we use a set data structure of C++ STL(implemented as Red-Black Tree) and a Boolean hash table for a closed list. The implementations are similar to Dijkstra’s algorithm. If we use a Fibonacci heap to implement the open list instead of a binary heap/self-balancing tree, then the performance will become better (as Fibonacci heap takes O(1) average time to insert into open list and to decrease key)

Also to reduce the time taken to calculate g, we will use dynamic programming.??

https://github.com/Shashankrishna/AMR/blob/main/Program%20to%20implement%20A*%20Search%20Algorithm

Advantages:

1. Optimality: A* is guaranteed to find the shortest path if the heuristic used is admissible (i.e., it never overestimates the actual cost to reach the goal). This ensures an optimal solution.
2. Completeness: A* is complete, meaning it will always find a solution if one exists, assuming the search space is finite.
3. Efficiency: A* combines the benefits of both Dijkstra’s algorithm (for shortest path finding) and Best-First Search (for heuristic guidance), which makes it more efficient than purely uninformed search algorithms like BFS or DFS.
4. Heuristic Flexibility: The heuristic can be tailored to the problem at hand, providing more control over the search process. A better heuristic will speed up the algorithm without sacrificing optimality.
5. Widely Applicable: A* can be used in various domains such as game AI, robotics, navigation systems, and network routing, due to its efficiency in pathfinding problems.
6. Guaranteed Optimal Solution: If both the heuristic is admissible and consistent, A* not only finds the optimal solution but does so more efficiently than some other search algorithms.

Disadvantages:

1. High Memory Consumption: A* stores all explored nodes, making it memory-intensive, especially for large search spaces. This can lead to scalability issues in complex environments.
2. Computationally Expensive: Even though A* is efficient compared to uninformed searches, its time complexity can still be high in large problem spaces. If the heuristic is not well-designed, it may take longer to find a solution.
3. Heuristic Dependency: The performance of A* heavily relies on the quality of the heuristic function. A poorly designed heuristic may cause the algorithm to explore unnecessary paths, leading to inefficiency.
4. Slower in Some Cases: When the heuristic is weak or if no heuristic is available (similar to Dijkstra’s algorithm), A* may not outperform simpler algorithms, especially in cases where exhaustive search is needed.
5. Not Ideal for Dynamic Environments: In dynamic environments where the search space changes over time (such as with moving obstacles), A* may need to recompute paths frequently, which can be computationally costly.
6. Difficulty in Heuristic Design: Designing an admissible and consistent heuristic that balances speed and accuracy can be challenging for complex problems, particularly those with many constraints.