Real time search with linear temporal goals
Loading...
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In 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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023
Keywords
Heuristic Search, Real-Time Heuristic Search, LSS Learning Real-Time A*, Linear Temporal Logic, LTL formula, Temporally extended goal, Automata, Heuritics, Sub-goaling