Improved search-tree reinitialization for an incremental heuristic search domains with long actions

Incremental heuristic search algorithms, such as D* Lite, are commonly used for mobile robot motion planning. The main disadvantage of D* Lite and similar algorithms is that the reinitialization requires a computation of all actions affected by changes in an environment. In case of long actions (motion primitives intersecting multiple map cells), a number of affected actions can be extremely large. Therefore, in this paper a new incremental search algorithm D* State Cut based on the recent D* Extra Lite algorithm is proposed. In comparison to D* Extra Lite, D* State Cut does not require affected actions to be computed; it is sufficient to compute only successors of changed actions with annotations about a change type (cost increase or decrease). In the tests, for domains with a significant number of long actions, D* State Cut was up-to two times quicker than D* Extra Lite.

---

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).