Question

5. Please explain how D* lite saves computation

Answer 1

Answer:

D* lite is an algorithm developed by Sven Koenig and Maxim Likhachev. It is an incremental heuristic search algorithm based on LPA* and Focussed D. It implements the same navigation strategy of D* but is algorithmically different. It makes use of the best features of LPA* and the best features of Focused D* to create an algorithm that could be used by a robot or an agent traversing a graph under changing edge costs. It can replan and complete searches from scratch using an incremental heuristic search i.e. it remembers information from previous searches and uses heuristic knowledge to focus the search thus speeding it up.

There are several ways how D* lite saves computation time and effort. They are:

1. D* lite has fewer lines of code in comparison to Focused D

2. It is easier to understand, easier to analyze, easier to extend than Focussed D.

3. It is simpler than Focussed D.

4. It is efficient since it does not expand any vertices whose goal values were already equal to their respective goal distances

5. It uses only one tie-breaking property when comparing priorities thus simplifying the maintenance of priorities.

6. Does not need nested if-else statements with complex conditions thus simplifying the analysis of program flow

7. Speeds up the planning time over incremental or heuristic searches individually.

8. Recalculates the shortest path from its current vertex to the goal vertex by recalculating as the edge cost of the graph changes while the agent moves towards the goal.

9. It only calculates relevant paths.

10. Can be used to solve goal-directed navigation problems in unknown terrain.

Thus D* lite saves computation by constantly improving the path information from the current point to goal vertex without recalculating everything from scratch every time.