Real-time heuristic search with depression avoidance

Carlos Hernández, Jorge A. Baier

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

12 Citas (Scopus)

Resumen

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is exceedingly low compared to the actual cost to reach a solution. Real-time search algorithms easily become trapped in those regions since the heuristic values of states in them may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms like LSS-LRTA*, LRTA*(k), etc., improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding or escaping depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We apply the principle to LSS-LRTA*producing aLSS-LRTA*, a new real-time search algorithm whose search is guided towards exiting regions with heuristic depressions. We show our algorithm outperforms LSS-LRTA*in standard real-time benchmarks. In addition we prove aLSS-LRTA*has most of the good theoretical properties of LSS-LRTA*.

Idioma originalInglés
Título de la publicación alojadaIJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
Páginas578-583
Número de páginas6
DOI
EstadoPublicada - 2011
Evento22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 - Barcelona, Catalonia, Espana
Duración: 16 jul 201122 jul 2011

Otros

Otros22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
País/TerritorioEspana
CiudadBarcelona, Catalonia
Período16/07/1122/07/11

Áreas temáticas de ASJC Scopus

  • Inteligencia artificial

Huella

Profundice en los temas de investigación de 'Real-time heuristic search with depression avoidance'. En conjunto forman una huella única.

Citar esto