Temporal-Logic-Aware Frontier-Based Exploration

Azizollah Taheri; Derya Aksaray

cs.ROFeb 21, 2026

Temporal-Logic-Aware Frontier-Based Exploration

Authors: Azizollah Taheri, Derya Aksaray

Organizations: Department of Electrical and Computer Engineering at Northeastern University.

Abstract

This paper addresses the problem of temporal logic motion planning for an autonomous robot operating in an unknown environment. The objective is to enable the robot to satisfy a syntactically co-safe Linear Temporal Logic (scLTL) specification when the exact locations of the desired labels are not known a priori. We introduce a new type of automaton state, referred to as commit states. These states capture intermediate task progress resulting from actions whose consequences are irreversible. In other words, certain future paths to satisfaction become not feasible after taking those actions that lead to the commit states. By leveraging commit states, we propose a sound and complete frontier-based exploration algorithm that strategically guides the robot to make progress toward the task while preserving all possible ways of satisfying it. The efficacy of the proposed method is validated through simulations.

Figures & tables

Fig. 1 : The DFA

\mathcal{A}

corresponding to formula

\phi_{0}

Fig. 2 : A portion of $\bar{\mathcal{A}}$ showing all states reachable from the initial state $\bar{s}_{0}=(3,1)$ .

Fig. 3 : A portion of $\bar{\mathcal{A}}$ showing all states reachable from the initial state $\bar{s}^{\prime}_{0}=(3,2)$ .

Fig. 4 : Summary of the proposed method.

Fig. 5 : Snapshots from a video, starting at (a) and ending at (e), illustrating the robot executing our algorithm to satisfy the task $\phi_{1}$ . The robot’s starting position is marked by a red circle in the top-left corner, while the lower-level region, person, and safe exit are represented by yellow, green, and blue squares, respectively. The robot’s traversed trajectory is shown by black arrows.

Fig. 6 : Trajectory traversed by the robot when following the method in [ 13 ] , which shows that it gets stuck and fails to satisfy the task.

Panel of Figure 7 — Fig. 7 : Trajectories generated by our algorithm that satisfy $\phi_{1}$ under different maps.

$\bm{n}$	Method	Avg. Trajectory Length	Satisfaction Rate
$0$	Our Algorithm	46.20	100.0 %
$0$	[ 13 ]	56.47	100.0 %
$5$	Our Algorithm	48.07	100.0 %
$5$	[ 13 ]	31.43	35.00 %

TABLE I : Comparison between [ 13 ] and our proposed algorithm with respect to average trajectory length and success rate, evaluated over 500 maps.

STL Motion Planning

See all 19 papers

Signal Temporal Logic Motion Planning via Graphs of Convex Sets
May 22, 2026Yu Chen, Ancheng Hou, Mingyang Feng +2Constrained Motion Planning Trajectory Generation
School of Automation & Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China · Institute of Artificial Intelligence, Xiamen University, Xiamen, China
Composing Learned Robot Behaviors with Temporal Logic at Runtime
Aug 13, 2026Moritz Zoellner, Anastasios Manganaris, Ahmed H. Qureshi +1Robot Task Planning Robot Policy Learning
Department of Computer Science, Purdue University
Logic of Fuzzy Paths
Apr 27, 2026Kush Grover, Pratham Gupta, Jan KřetínskýTemporal Reasoning Signal Temporal Logic
Fondazione Bruno Kessler · Indian Institute of Science · Masaryk University

May 22, 2026J/K move · Enter open · S save

Signal Temporal Logic Motion Planning via Graphs of Convex Sets

Yu Chen, Ancheng Hou, Mingyang Feng, Xiao Yu+1

School of Automation & Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China · Institute of Artificial Intelligence, Xiamen University, Xiamen, China

Constrained Motion Planning Trajectory Generation STL Motion Planning Motion Planning Robot Motion Planning STL Planning

Open paper AskPDF arXiv

This paper investigates continuous-time motion planning under Signal Temporal Logic (STL) specifications. The goal is to generate smooth robot trajectories that satisfy high-level logical and timing requirements while respecting low-level motion constraints. To this end, we propose an efficient framework that combines timed-automata reasoning with graphs of convex sets (GCS). An STL specification is first represented by a timed automaton, which is then coupled with a convex decomposition of the configuration space to form a joint transition system encoding both task progress and region occupancy. Based on this joint transition system, the STL motion-planning problem is reformulated as a shortest-path problem over a GCS, whose solution induces a smooth Bézier-spline trajectory satisfying the STL specification, smoothness requirements, and velocity bounds. We establish the soundness of the proposed formulation and analyze its computational complexity, showing that, once the timed automaton and convex decomposition are fixed, the convex relaxation scales polynomially with the configuration-space dimension and the Bézier degree. We further develop a compact timed-automaton construction for an expressive STL fragment using dedicated templates and Boolean composition. Numerical experiments on low-dimensional benchmarks, a

3

-D quadrotor, a

30

-DoF humanoid, and a hardware experiment on a UR-3 robot arm demonstrate that the proposed method efficiently solves complex STL motion-planning problems and produces smooth executable trajectories.

Abstract

STL Motion Planning

Explore similar work

Signal Temporal Logic Motion Planning via Graphs of Convex Sets

Composing Learned Robot Behaviors with Temporal Logic at Runtime

Logic of Fuzzy Paths