14. A-Star

• We have seen how Dijkstra’s algorithm can help to find the shortest path in a graph.

• However, it requires to visit every node which is time consuming.

• We will now introduce a new concept heuristic search.

14.1. Heuristic search

• Heuristic search is the name given to algorithms that are using a heuristic function to find the solution.

Definition

Heuristic function or heuristic is a function that provides an estimation of the unknown solution.

• Using heuristic functions allow us to prune suboptimal solution, thus saving time.

14.2. A-Star

• The \(A^*\) algorithm was created to solve path planning problem for robots in environments that could contain obstacles.

• It was the first algorithm implementing tree pruning.

• Instead of search in order of closeness from the source, it searches in order of closeness to the goal.

• We had two arrays, \(h[v]\) and \(f[v]\):

  • \(h[v]\) will contain the distance to the node \(v\) calculated by the heuristic function.

  • \(f[v] = d[v]+h[v]\) is the estimated distance from \(s\) to \(v\).

• It selects the node with the smallest \(f\).

14.2.1. How is it working?

• We will consider the following graph:

• The source node is \(A\) and the goal is \(J\).

• Using \(A^*\), we will start from \(J\).

• We explores the adjacent edges.

• We visit the closest node \(D\) and explore the adjacent edges.

• The smallest value \(f\) is for the node \(I\).

• We visit \(I\) and check the edges.

• We update \(H\), because it’s new value \(465\) is smaller than the previous \(610\).

• The smallest value is \(776\) for the node \(H\).

• We visit this node and check the edge leading to \(F\).

• The new value \(590\) is smaller than the previous value \(615\).

• Now, the node with the smallest estimated distance is going through \(C\).

• We are updated the adjacent nodes that are not visited yet, so \(A\) and \(B\).

• Since the distance to \(A\) is smallest that the other estimation, we stop.

14.2.2. Algorithm

• Now, we can discuss the pseudocode:

Initialize V–S with all vertices except the starting vertex s.
for all v in V–S:
    p[v] = s
    if there is an edge (s, v):
        d[v] = w(s, v)
        f[v] = d[v] + h(v)
    else:
        d[v] = inf
        f[v] = inf

while V–S is not empty:
    u = find the smallest f[u]
    if u == destination:
        break
    Remove u from V–S
    Add u to S
    for all v adjacent to u in V–S:
        if d[u] + w(u, v) < d[v]:
            d[v] = d[u] + w(u, v)
            f[v] = d[v] + h(v)
            p[v] = u