8.1 We need some upgrades! Why?

Planning is a repeated process. We need to consider the following situations:

  • partially known environments
  • dynamic environments
  • improper execution of plan
  • imprecise localization

As a result, we need to plan fast and repeatedly.
Let me introduce three searches:

  • Anytime heuristic search: return best plan possible within $T ms$
  • Incremental heursitic search: speed up search by reusing previous efforts
  • Real-Time heuristic search: plan few steps towards te goal and re-plan later

In this post, we will be focusing on Anytime planners: Anytime Repairing A* star.

8.2 ComputePathWithReuse()

att In this algorithm, we introduce a new set INCONSI for inconsistent nodes. Inconsistent nodes are those nodes whose $g-values$ can be smaller than what it is at current iteration. Let’s take an example of a node which is in CLOSED and revisited by expanding a new node. Now, when the $g-value$ of that node (CLOSED) satisfies our first basic condition $g(s^{‘})$ $>$ $g(s)$ + $c(s,s^{‘})$ then the node is inconsistent. So, what does it signify? It tells us that there is a better way or smaller cost to reach that node.

8.3 ARA*

att ARA* is basically efficient series weighted A* with decreasing $\epsilon$. At every iteration, the A* is repaired: it is made better by initializing the OPEN set with already OPEN nodes (overconsistent) and INCONSISTENT nodes. As a result, we get closer to optimal solution at every iteration.

Video:

Note: In [2], they have introduced $v(n)$ variable which indicates whether a node is inconsitent or overconsistent (OPEN nodes after each search). However, this variable is not used in algorithm. As a result, I haven’t introduced the variable and have explained inconsistent nodes in literature.

</> GitHub

8.4 References

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

[2]. ARA*: Anytime A* with Provable Bounds on Sub-Optimality - link