Escaping heuristic depressions in real-time heuristic search

Carlos Hernández, Jórge A. Baier

Resultado de la investigación: Conference contribution

2 Citas (Scopus)

Resumen

Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA* will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA*, a new RT search algorithm based on LSS-LRTA* that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better-quality solutions than LSS-LRTA* for equal values of lookahead in standard RT benchmarks.

Idioma originalEnglish
Título de la publicación alojada10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
EditorialInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Páginas1197-1198
Número de páginas2
Volumen2
EstadoPublished - 2011
Evento10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China
Duración: 2 may 20116 may 2011

Other

Other10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
PaísTaiwan, Province of China
CiudadTaipei
Período2/05/116/05/11

ASJC Scopus subject areas

  • Artificial Intelligence

Citar esto

Hernández, C., & Baier, J. A. (2011). Escaping heuristic depressions in real-time heuristic search. En 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 (Vol. 2, pp. 1197-1198). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).
Hernández, Carlos ; Baier, Jórge A. / Escaping heuristic depressions in real-time heuristic search. 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011. Vol. 2 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2011. pp. 1197-1198
@inproceedings{6044279b9aa547cebc2ed301f4f1b7f7,
title = "Escaping heuristic depressions in real-time heuristic search",
abstract = "Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA* will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA*, a new RT search algorithm based on LSS-LRTA* that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better-quality solutions than LSS-LRTA* for equal values of lookahead in standard RT benchmarks.",
keywords = "Agent Reasoning::Planning (single and multi-agent), Path Planning, Robot Reasoning::Planning",
author = "Carlos Hern{\'a}ndez and Baier, {J{\'o}rge A.}",
year = "2011",
language = "English",
volume = "2",
pages = "1197--1198",
booktitle = "10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011",
publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

}

Hernández, C & Baier, JA 2011, Escaping heuristic depressions in real-time heuristic search. En 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011. vol. 2, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 1197-1198, 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011, Taipei, Taiwan, Province of China, 2/05/11.

Escaping heuristic depressions in real-time heuristic search. / Hernández, Carlos; Baier, Jórge A.

10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011. Vol. 2 International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2011. p. 1197-1198.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Escaping heuristic depressions in real-time heuristic search

AU - Hernández, Carlos

AU - Baier, Jórge A.

PY - 2011

Y1 - 2011

N2 - Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA* will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA*, a new RT search algorithm based on LSS-LRTA* that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better-quality solutions than LSS-LRTA* for equal values of lookahead in standard RT benchmarks.

AB - Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA* will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA*, a new RT search algorithm based on LSS-LRTA* that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better-quality solutions than LSS-LRTA* for equal values of lookahead in standard RT benchmarks.

KW - Agent Reasoning::Planning (single and multi-agent)

KW - Path Planning

KW - Robot Reasoning::Planning

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

M3 - Conference contribution

AN - SCOPUS:84899452132

VL - 2

SP - 1197

EP - 1198

BT - 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

ER -

Hernández C, Baier JA. Escaping heuristic depressions in real-time heuristic search. En 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011. Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2011. p. 1197-1198