Examinando por Autor "Baier, J."

Mostrando 1 - 2 de 2
  • Miniatura
    Ítem
    Multipath Adaptive A∗: Factors That Influence Performance in Goal-Directed Navigation in Unknown Terrain
    (Institute of Electrical and Electronics Engineers Inc., 2020) Hernandez Ulloa, C.; Baier, J.; Asin-Acha, R.
    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.
  • Miniatura
    Ítem
    The 2k neighborhoods for grid path planning
    (AI Access Foundation, 2020) Rivera, N.; Hernández, C.; Hormazábal, N.; Baier, J.
    Grid path planning is an important problem in AI. Its understanding has been key for the development of autonomous navigation systems. An interesting and rather surprising fact about the vast literature on this problem is that only a few neighborhoods have been used when evaluating these algorithms. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2k-neighborhoods; that is, neighborhoods that admit 2k neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k− 1-neighborhood. Second, we derive distance functions, for any k ≥ 2, which allow us to propose admissible heuristics that are perfect for obstacle-free grids, which generalize the well-known Manhattan and Octile distances. Third, we define the notion of canonical path for the 2k-neighborhood; this allows us to incorporate our neighborhoods into two versions of A*, namely Canonical A* and Jump Point Search (JPS), whose performance, we show, scales well when increasing k. Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially. Used with the 2k-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta∗ both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. Our main practical conclusion is that standard, well-understood grid path planning technology may provide an effective approach to any-angle grid path planning.