TY - JOUR
T1 - Multipath Adaptive A∗
T2 - Factors That Influence Performance in Goal-Directed Navigation in Unknown Terrain
AU - Hernandez Ulloa, Carlos
AU - Baier, Jorge A.
AU - Asin-Acha, Roberto
N1 - Funding Information:
This work was supported in part by Fondecyt under Grant 1150328 and Grant 1161526.
Publisher Copyright:
© 2013 IEEE.
PY - 2020
Y1 - 2020
N2 - Incremental heuristic search algorithms are a class of heuristic search algorithms applicable to the problem of goal-directed navigation. D∗ and D∗Lite are among the most well-known algorithms for this problem. Recently, two new algorithms have been shown to outperform D∗Lite in relevant benchmarks: Multi-Path Adaptive A∗ (MPAA∗) and D∗ExtraLite. Existing empirical evaluations, unfortunately, do not allow to obtain meaningful conclusions regarding the strengths and weaknesses of these algorithms. Indeed, in the paper introducing D∗ExtraLite, it is shown that D∗Lite outperforms MPAA∗ in benchmarks in which the authors of MPAA∗ claim superiority over D∗Lite. The existence of published contradictory data unfortunately does not allow practitioners to make decisions over which algorithm to use given a specific application. In this paper, we analyze two factors that significantly influence the performance of MPAA∗, explaining why it is possible to obtain very different results depending on such factors. We identify a configuration of MPAA∗ which, in the majority of the benchmark problems we use, exhibits superior performance when compared to both D∗Lite and D∗ExtraLite. We conclude that MPAA∗ should be the algorithm of choice in goal-directed navigation scenarios in which the heuristic is accurate, whereas D∗ExtraLite should be preferred when the heuristic is inaccurate.
AB - Incremental heuristic search algorithms are a class of heuristic search algorithms applicable to the problem of goal-directed navigation. D∗ and D∗Lite are among the most well-known algorithms for this problem. Recently, two new algorithms have been shown to outperform D∗Lite in relevant benchmarks: Multi-Path Adaptive A∗ (MPAA∗) and D∗ExtraLite. Existing empirical evaluations, unfortunately, do not allow to obtain meaningful conclusions regarding the strengths and weaknesses of these algorithms. Indeed, in the paper introducing D∗ExtraLite, it is shown that D∗Lite outperforms MPAA∗ in benchmarks in which the authors of MPAA∗ claim superiority over D∗Lite. The existence of published contradictory data unfortunately does not allow practitioners to make decisions over which algorithm to use given a specific application. In this paper, we analyze two factors that significantly influence the performance of MPAA∗, explaining why it is possible to obtain very different results depending on such factors. We identify a configuration of MPAA∗ which, in the majority of the benchmark problems we use, exhibits superior performance when compared to both D∗Lite and D∗ExtraLite. We conclude that MPAA∗ should be the algorithm of choice in goal-directed navigation scenarios in which the heuristic is accurate, whereas D∗ExtraLite should be preferred when the heuristic is inaccurate.
KW - D
KW - D ExtraLite
KW - DLite
KW - goal-directed navigation
KW - incremental heuristic search
KW - MPAA
UR - http://www.scopus.com/inward/record.url?scp=85087873233&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2020.3003344
DO - 10.1109/ACCESS.2020.3003344
M3 - Article
AN - SCOPUS:85087873233
SN - 2169-3536
VL - 8
SP - 116724
EP - 116732
JO - IEEE Access
JF - IEEE Access
M1 - 9120005
ER -