Digital Library of Zielona Góra contains 9 272 digital objects
Object
Title: D* Extra Lite: A dynamic A* with search-tree cutting and frontier-gap repairing
Contributor:
Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.
Group publication title:
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.
Publisher:
Zielona Góra: Uniwersytet Zielonogórski
Resource Identifier:
DOI:
Pages:
Source:
AMCS, volume 27, number 2 (2017) ; click here to follow the link
Language:
License CC BY 4.0:
Rights:
Biblioteka Uniwersytetu Zielonogórskiego
Object collections:
- Repository > Faculties > Faculty of Computer, Electrical and Control Engineering
- Repository > Types of work > Articles
- Repository > Scientific journals and UZ publishing series > International Journal of Applied Mathematics and Computer Science (AMCS) > International Journal of Applied Mathematics and Computer Science (AMCS) (2017)
Last modified:
Jul 14, 2025
In our library since:
Jul 3, 2025
Number of object content hits:
116
All available object's versions:
https://zbc.uz.zgora.pl/repozytorium/publication/100612
Show description in RDF format:
Show description in OAI-PMH format:
-
-
-
-
-
-
-
-
-
-
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 27, number 1 (2017)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 27, number 2 (2017)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 27, number 3 (2017)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 27, number 4 (2017)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
| Edition name | Date |
|---|---|
| D* Extra Lite: A dynamic A* with search-tree cutting and frontier-gap repairing | Jul 14, 2025 |
