Multipath Adaptive A∗: Factors That Influence Performance in Goal-Directed Navigation in Unknown Terrain
Cargando...
Archivos
Fecha
2020
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
Institute of Electrical and Electronics Engineers Inc.
Nombre de Curso
Licencia CC
Attribution 4.0 International (CC BY 4.0)
Licencia CC
Resumen
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.
Notas
Indexación: Scopus.
Palabras clave
D, D ExtraLite, DLite, goal-directed navigation, incremental heuristic search, MPAA
Citación
IEEE Access, Volume 8, Pages 116724 - 116732, 2020, Article number 9120005
DOI
DOI: 10.1109/ACCESS.2020.3003344