### 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()

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*

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