Real time search with linear temporal goals

Simple item page
dc.catalogadoraba
dc.contributor.advisorBaier Aranda, Jorge Andrés
dc.contributor.advisorToro Icarte, Rodrigo Andrés
dc.contributor.authorMiddleton Moreno, Jaime Andrés
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2024-03-27T14:46:22Z
dc.date.available2024-03-27T14:46:22Z
dc.date.issued2023
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023
dc.description.abstractIn Real-Time Heuristic Search (RTHS) we are given a search graph G, a heuristic, and an objective, which is to find a path from a start node to a given goal node in G. As such, one does not impose any trajectory constraints on the path, besides reaching the goal. In this work we consider a version of RTHS in which temporally extended goals can be defined on the form of the path. Such goals are specified in Linear Temporal Logic over Finite Traces (LTLf), an expressive language that has been considered in many other frameworks, such as Automated Planning, Synthesis, and Reinforcement Learning, but has not yet been studied in the context of RTHS. We propose a general automata-theoretic approach for RTHS, whereby LTLf goals are supported as the result of searching over the cross product of the search graph and the automaton for the LTLf goal; specifically, we describe LTL-LRTA*, a version of LSS LRTA*. Second, we propose an approach to produce heuristics for LTLf goals, based on existing goal-dependent heuristics. Finally, we propose a greedy strategy for RTHS with LTLf goals, which focuses search to make progress over the structure of the automaton; this yields LTL-LRTA*A. In our experimental evaluation over standard benchmarks we show LTL-LRTA*A may outperform LTL-LRTA* substantially for a variety of LTLf goals.
dc.fechaingreso.objetodigital2024-03-27
dc.format.extent75 páginas
dc.fuente.origenAutoarchivo
dc.identifier.doi10.7764/TesisUC/ING/84868
dc.identifier.urihttps://doi.org/10.7764/TesisUC/ING/84868
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/84868
dc.information.autorucEscuela de Ingeniería; Baier Aranda, Jorge Andrés; 0000-0002-6280-5619; 9477
dc.information.autorucEscuela de Ingeniería; Toro Icarte, Rodrigo Andrés; 0000-0002-7734-099X; 170373
dc.language.isoen
dc.nota.accesocontenido completo
dc.rightsacceso abierto
dc.subjectHeuristic Search
dc.subjectReal-Time Heuristic Search
dc.subjectLSS Learning Real-Time A*
dc.subjectLinear Temporal Logic
dc.subjectLTL formula
dc.subjectTemporally extended goal
dc.subjectAutomata
dc.subjectHeuritics
dc.subjectSub-goaling
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleReal time search with linear temporal goals
dc.typetesis de maestría
sipa.codpersvinculados9477
sipa.codpersvinculados170373
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TESIS_JMiddleton_Firma Final.pdf
Size:
640.72 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster