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.
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.
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
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$
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/