Escaping heuristic depressions in real-time heuristic search

Carlos Hernández, Jórge A. Baier

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publication10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1197-1198
Number of pages2
Volume2
Publication statusPublished - 2011
Event10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China
Duration: 2 May 20116 May 2011

Other

Other10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
Country/TerritoryTaiwan, Province of China
CityTaipei
Period2/05/116/05/11

Keywords

  • Agent Reasoning::Planning (single and multi-agent)
  • Path Planning
  • Robot Reasoning::Planning

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this