<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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.</p></abstract>

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.

D* Extra Lite: A Dynamic A* With Search–Tree Cutting and Frontier–Gap Repairing

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

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...

D* Extra Lite: A Dynamic A* With Search–Tree Cutting and Frontier–Gap Repairing

Publié en ligne: 08 juil. 2017

Pages: 273 - 290

Reçu: 27 juil. 2016

Accepté: 25 mars 2017

DOI: https://doi.org/10.1515/amcs-2017-0020

Mots clés
shortest-path planning, incremental heuristic search, mobile robot navigation, video games

© by Maciej Przybylski

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

D* Extra Lite: A Dynamic A* With Search–Tree Cutting and Frontier–Gap Repairing

Publié en ligne: 08 juil. 2017

Pages: 273 - 290

Reçu: 27 juil. 2016

Accepté: 25 mars 2017

DOI: https://doi.org/10.1515/amcs-2017-0020

Mots clésshortest-path planning, incremental heuristic search, mobile robot navigation, video games

© by Maciej Przybylski

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
shortest-path planning, incremental heuristic search, mobile robot navigation, video games