7.1 Recall!

From the previous post, we learned that \(f(n) = h(n)\) search becomes greedy and \(f(n) = g(n)\) search grows path that is shortest from start until it encounters the goal(Dijkstra’s algorithm or Uninformed A*). Now, the A* algorithm is just the combination of both.

$$f(n) = h(n) + g(n) \tag{1}$$

Now, lets take a deeper dive in the algorithm.

7.2 A* Algorithm

I bet you remember all the terminologies.

star

Now, take a pen and a scratch paper and try to understand the algorithm by solving the following example. Assume the function $h(s)$ gives the number of nodes $s$ is away from $s_{goal}$ and $g(s) = g(s_{start}) + c(s_{start},s)$, where $c$ is the edge cost. So, $h(s_{goal}) = 0$ and $g(s_{start}) = 0$. Try it out on your own and compare it with the below table.

                   eg

Figure 7.1 Example

Table 1 Solution

Node To Expand OPEN CLOSED bp(s)
$s_{start}$ {$s_{start}$} {} -
$s_2$ {$s_2$} {$s_{start}$} $bp(s_2) = s_{start}$
$s_4$ {$s_4, s_1$} {$s_{start}, s_2$} $bp(s_4) = bp(s_1) = s_2$
$s_1$ {$s_3, s_1$} {$s_{start}, s_2, s_4$} $bp(s_3) = s_4$
$s_{goal}$ {$s_3, s_{goal}$} {$s_{start}, s_2, s_4, s_1$} $bp(s_{goal}) = s_1$
- {$s_3$} {$s_{start}, s_2, s_4, s_1, s_{goal}$} -

Finally, in order to find the least cost path, we have to just follow the backpointers all the way from $s_{goal}$ to $s_{start}$. So, in our case the path will be $s_{goal} \rightarrow s_1 \rightarrow s_2 \rightarrow s_{start}$.

7.3 Weighted A*

The name itself suggests that some weight or priority is assigned to the function.

$f(s) = g(s) + \epsilon h(s) \tag{2}$

For $\epsilon \geq 1$, there is a bias towards nodes that are closer to goal. We may regard weighted A* as greedy for a very high value of $\epsilon$. If we allow an epsilon of 5, this means that the weighted A* algorithm will return a path that is no worse than 5 times the cost of the optimal solution.

7.4 Backward A*

It is similar to conventional A* algorithm, but the difference is that one starts to search from goal to the start. Accordingly, the algorithm changes to

bstar

7.5 Conclusion

The major difference between A* and weighted A* is the tradeoff between optimal solution and computation time. In following figure, two scenarios are taken: $\epsilon = 1$ and $\epsilon = 2.5$
bstar

Figure 7.2 A* $\epsilon = 1$ vs $\epsilon = 2.5$

Here, green indicates OPEN states and yellow indicates CLOSED states. The weighted A* is able to find solution faster than A*. However, the solution given by weighted A* is sub-optimal.

</> GitHub

7.6 References

[1]. 16-350 Planning Techniques for Robotics - link

[2]. Online - http://sbpl.net/