Escaping heuristic hollows in real-time search without learning

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

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaProceedings - 29th International Conference of the Chilean Computer Science Society, SCCC 2010
Páginas172-177
Número de páginas6
DOI
EstadoPublicada - 2011
Evento29th International Conference of the Chilean Computer Science Society, SCCC 2010 - Antofagasta, Chile
Duración: 15 nov 201019 nov 2010

Otros

Otros29th International Conference of the Chilean Computer Science Society, SCCC 2010
País/TerritorioChile
CiudadAntofagasta
Período15/11/1019/11/10

Áreas temáticas de ASJC Scopus

  • Ingeniería (todo)
  • Informática (todo)

Huella

Profundice en los temas de investigación de 'Escaping heuristic hollows in real-time search without learning'. En conjunto forman una huella única.

Citar esto