Reconnecting with the ideal tree: An alternative to heuristic learning in real-time search

Nicolás Rivera, León Illanes, Jorge A. Baier, Carlos Hernández

Resultado de la investigación: Conference contribution

5 Citas (Scopus)

Resumen

In this paper, we present a conceptually simple, easy-toimplement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by h, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.

Idioma originalEnglish
Título de la publicación alojadaProceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013
Páginas158-166
Número de páginas9
EstadoPublished - 2013
Evento6th Annual Symposium on Combinatorial Search, SoCS 2013 - Leavenworth, WA, United States
Duración: 11 jul 201313 jul 2013

Other

Other6th Annual Symposium on Combinatorial Search, SoCS 2013
PaísUnited States
CiudadLeavenworth, WA
Período11/07/1313/07/13

ASJC Scopus subject areas

  • Computer Networks and Communications

Citar esto

Rivera, N., Illanes, L., Baier, J. A., & Hernández, C. (2013). Reconnecting with the ideal tree: An alternative to heuristic learning in real-time search. En Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013 (pp. 158-166)
Rivera, Nicolás ; Illanes, León ; Baier, Jorge A. ; Hernández, Carlos. / Reconnecting with the ideal tree : An alternative to heuristic learning in real-time search. Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013. 2013. pp. 158-166
@inproceedings{1c2da6dba06e45458045ff8032b20150,
title = "Reconnecting with the ideal tree: An alternative to heuristic learning in real-time search",
abstract = "In this paper, we present a conceptually simple, easy-toimplement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by h, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.",
author = "Nicol{\'a}s Rivera and Le{\'o}n Illanes and Baier, {Jorge A.} and Carlos Hern{\'a}ndez",
year = "2013",
language = "English",
pages = "158--166",
booktitle = "Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013",

}

Rivera, N, Illanes, L, Baier, JA & Hernández, C 2013, Reconnecting with the ideal tree: An alternative to heuristic learning in real-time search. En Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013. pp. 158-166, 6th Annual Symposium on Combinatorial Search, SoCS 2013, Leavenworth, WA, United States, 11/07/13.

Reconnecting with the ideal tree : An alternative to heuristic learning in real-time search. / Rivera, Nicolás; Illanes, León; Baier, Jorge A.; Hernández, Carlos.

Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013. 2013. p. 158-166.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Reconnecting with the ideal tree

T2 - An alternative to heuristic learning in real-time search

AU - Rivera, Nicolás

AU - Illanes, León

AU - Baier, Jorge A.

AU - Hernández, Carlos

PY - 2013

Y1 - 2013

N2 - In this paper, we present a conceptually simple, easy-toimplement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by h, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.

AB - In this paper, we present a conceptually simple, easy-toimplement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by h, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.

UR - http://www.scopus.com/inward/record.url?scp=84893377985&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84893377985

SP - 158

EP - 166

BT - Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013

ER -

Rivera N, Illanes L, Baier JA, Hernández C. Reconnecting with the ideal tree: An alternative to heuristic learning in real-time search. En Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013. 2013. p. 158-166