D* Extra Lite swMATH ID: 20992 Software Authors: Przybylski, Maciej; Putz, Barbara Description: D* Extra Lite: a dynamic A* with search-tree cutting and frontier-gap repairing. Searching for the shortest-path in an unknown or changeable environment is a common problem in robotics and video games, in which agents need to update maps and to perform re-planning in order to complete their missions. D* Lite is a popular incremental heuristic search algorithm (i.e., it utilizes knowledge from previous searches). Its efficiency lies in the fact that it re-expands only those parts of the search-space that are relevant to registered changes and the current state of the agent. In this paper, we propose a new D* Extra Lite algorithm that is close to a regular A*, with reinitialization of the affected search-space achieved by search-tree branch cutting. The provided worst-case complexity analysis strongly suggests that D* Extra Lite’s method of reinitialization is faster than the focused approach to reinitialization used in D* Lite. In comprehensive tests on a large number of typical two-dimensional path-planning problems, D* Extra Lite was 1.08 to 1.94 times faster than the optimized version of D* Lite. Moreover, while demonstrating that it can be particularly suitable for difficult, dynamic problems, as the problem-complexity increased, D* Extra Lite’s performance further surpassed that of D*Lite. The source code of the algorithm is available on the open-source basis. Homepage: https://www.degruyter.com/downloadpdf/j/amcs.2017.27.issue-2/amcs-2017-0020/amcs-2017-0020.pdf Keywords: shortest-path planning; incremental heuristic search; mobile robot navigation; video games Related Software: D*Lite Cited in: 2 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year D* Extra Lite: a dynamic A* with search-tree cutting and frontier-gap repairing. Zbl 1367.93407Przybylski, Maciej; Putz, Barbara 2017 Cited by 5 Authors 1 Khaksar, Weria 1 Przybylski, Maciej 1 Putz, Barbara 1 Torresen, Jim 1 Uddin, Md Zia Cited in 1 Serial 2 International Journal of Applied Mathematics and Computer Science Cited in 3 Fields 2 Systems theory; control (93-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year