Escaping heuristic hollows in real-time search without learning

Carlos Hernández, Jorge A. Baier

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

Abstract

Real-time search is a standard approach to solving search problems in which agents have limited sensing capabilities and must act quickly. It is well known that real-time search algorithms like LRTA* and RTA* perform poorly in regions of the search space in which the heuristic function is very imprecise. Approaches that use look ahead or learning are used to overcome this drawback. They perform more computation in the planning phase compared to LRTA* and RTA*. In this paper we propose Path Real-Time A* (PRTA* ), an algorithm that, like LRTA*, performs little computation in the planning phase, but that, unlike LRTA*, terminates even if the problem does not have a solution. We show that our algorithm outperforms LRTA* and RTA* in standard real-time benchmark problems. Furthermore, we show that in some cases, PRTA* may also outperform lookahead-orlearning-enabled algorithms but carrying out significantly less computation.

Original languageEnglish
Title of host publicationProceedings - 29th International Conference of the Chilean Computer Science Society, SCCC 2010
Pages172-177
Number of pages6
DOIs
Publication statusPublished - 2011
Event29th International Conference of the Chilean Computer Science Society, SCCC 2010 - Antofagasta, Chile
Duration: 15 Nov 201019 Nov 2010

Other

Other29th International Conference of the Chilean Computer Science Society, SCCC 2010
Country/TerritoryChile
CityAntofagasta
Period15/11/1019/11/10

Keywords

  • Heuristic Search
  • Real-Time Pathfinding
  • Real-Time Search

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Escaping heuristic hollows in real-time search without learning'. Together they form a unique fingerprint.

Cite this