Avoiding and Escaping Depressions in Real-Time Heuristic Search

Simple item page
dc.contributor.authorHernandez, Carlos
dc.contributor.authorBaier, Jorge A.
dc.date.accessioned2024-01-10T13:46:16Z
dc.date.available2024-01-10T13:46:16Z
dc.date.issued2012
dc.description.abstractHeuristics 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 inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA* (k), improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding 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 propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.
dc.description.funderFondecyt
dc.description.funderPontificia Universidad Catolica de Chile
dc.format.extent48 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1613/jair.3590
dc.identifier.eissn1943-5037
dc.identifier.issn1076-9757
dc.identifier.urihttps://doi.org/10.1613/jair.3590
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/79142
dc.identifier.wosidWOS:000303929100001
dc.information.autorucIngeniería;Baier J;S/I;9477
dc.language.isoen
dc.nota.accesoSin adjunto
dc.pagina.final570
dc.pagina.inicio523
dc.publisherAI ACCESS FOUNDATION
dc.revistaJOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
dc.rightsregistro bibliográfico
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleAvoiding and Escaping Depressions in Real-Time Heuristic Search
dc.typeartículo
dc.volumen43
sipa.codpersvinculados9477
sipa.indexWOS
sipa.indexScopus
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Avoiding and Escaping Depressions in Real-Time Heuristic Search.pdf
Size:
2.95 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas