Temporal Logic Guided Safe Navigation for Autonomous Vehicles

Aditya Parameshwaran, Yue Wang · 2025

Read Temporal Logic Guided Safe Navigation for Autonomous Vehicles by Aditya Parameshwaran, Yue Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13817.txt.

Introduction

Aditya Parameshwaran and Yue Wang present a 2025 method for guiding self driving cars with formal logic rules. Safety checks matter because these cars work in settings that cannot be fully predicted. Logic based tools can state safety rules in a strict form and prove that a plan obeys them.

Their method first uses one logic form to plan a route that is safe by design. A solver then works out the exact control inputs along that route while obeying limits on speed, steering, and safety stated in a second logic form. Tests in two settings compared the method with common planning tools. The logic based routes handled complex rule cases well and took about the same time to compute.

Catalog record

CREATORAditya Parameshwaran, Yue Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-13817

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Temporal Logic Guided Safe Navigation for Autonomous Vehicles Aditya Parameshwaran, Yue Wang Abstract Safety verification for autonomous vehicles (AVs) and ground robots is crucial for ensuring reliable operation given their uncertain environments. Formal language tools provide a robust and sound method to verify safety rules for such complex cyber-physical systems. In this paper, we propose a hybrid approach that combines the strengths of formal verification languages like Linear Temporal Logic (LTL) and Signal Temporal Logic (STL) to generate safe trajectories and optimal control inputs for autonomous vehicle navigation. We implement a symbolic path planning approach using LTL to generate a formally safe reference trajectory. A mixed integer linear programming (MILP) solver is then used on this reference trajectory to solve for the control inputs while satisfying the state, control and safety constraints described by STL. We test our proposed solution on two environments and compare the results with popular path planning algorithms. In contrast to conventional path planning algorithms, our formally safe solution excels in handling complex specification scenarios while ensuring both safety and comparable computation times. keywords Safety, Temporal logic, Optimal Control Theory, Unmanned Ground and Aerial Vehicles, Trajectory Tracking and Path Following 1 Introduction Safety verification techniques for autonomous vehicles (AVs) and robots has seen an unprecedented rise in demand over the past few years. Designing the correct set of rules for such complex systems is essential in maintaining the vehicle’s safety in the case of uncertainties. Temporal logic offers a formal method to help designers transform natural language rules for safety into mathematical formulae. Temporal operators have been used to express safety requirements and reach-avoid sets with the ability to time and sequence them. Formal verification is one of the most efficient methods to validate design specifications. With the help of model checking, we formally evaluate the functional properties of the system against critical design specifications to rectify any property violations [ Rao and Wang (2023) ]. Several tools like NuSMV, UPPAL, PAT, and SPIN [ Meenakshi et al. (2006) ] can achieve this. NuSMV is a satisfiability (SAT) based model checker to efficiently verify system properties by encoding them into propositional logic formulas, which are then checked for satisfiability using efficient SAT solvers. Formal specification languages like linear temporal logic (LTL) [ Kloetzer and Belta (2008) & Alur et al. (2000) ], Metric Temporal Logic (MTL) [ Koymans (1990) & Fainekos and Pappas (2006) ], signal temporal logic (STL) [ Lindemann and Dimarogonas (2017) & Saha and Julius (2016) ] have been used to verify and synthesize controllers for motion planning of dynamic autonomous systems that satisfy the predefined specifications. LTL tasks exhibit versatile applicability in standard navigation scenarios [ Fainekos et al. (2009) , Ding et al. (2014) , Guo and Dimarogonas (2015) , Ulusoy et al. (2012) ], however this leads to a highly complex transition system model based on discrete states that are difficult to generate and can lead to state space explosion [ Baier et al. (2008) ]. Our previous work on controllers based purely on STL [ Parameshwaran and Wang (2023) ] performs better for linearized systems but can have the disadvantage of high computation times due to a larger feasible set. In this work, we combine LTL and STL-based methods to synthesize robot trajectories that maintain formal guarantees and reduce computation loads compared to our previous work. Our work aims to generate formally safe trajectories and the optimal control inputs required to follow those trajectories using a mixed integer linear programming (MILP) solver. The novelty of our work is that we generate reference trajectories for the MILP solver using an SAT-based model checker based on the concept of counterexample path planning. This ensures the safety and liveness guarantees of the temporal logic specification \phi during our path planning and control sequences. The constraints on the MILP solver ensure minimum safety robustness values \rho_{min}(\phi) while calculating the optimal control inputs. The remainder of the paper is as follows: Section 2 describes the AV kinematics model and introduces STL, LTL and model checking. Section 3 discusses the problem formulation, with feedback linearization, MILP formulation and the algorithm for the solution. In Section 4 , we test our algorithm on two 2D environments and discuss the results in Section 5 . The paper concludes with Section 6 and the future work. 2 Preliminaries 2.1 Nonlinear AV Kinematics Model Similar to our previous work [ Parameshwaran and Wang (2023) ], we consider a simplified 2D unicycle kinematic model for an AV where: \displaystyle\left[\begin{array}[]{c}\dot{x}\\ \dot{y}\\ \dot{\theta}\\ \end{array}\right]=\left[\begin{array}[]{c}v\cos\theta\\ v\sin\theta\\ \omega\\ \end{array}\right] (1) The 2D pose and orientation of the AV are represented by the states [x,y,\theta]^{T} , while [v,\omega]^{T} denote the AV’s linear velocity and angular velocity, respectively. A significant challenge in many nonlinear models is the real-time computation of solutions for non-convex optimization problems [ Liu and Tomizuka (2017) ]. MILP solvers can be used for solving such complex optimization problems with both linear and discrete decision variables. However, MILP solvers can have longer computational times when combined with multiple state constraints and linear equations. Hence, we use a simple kinematic model that we linearize using feedback linearization in Section 3.1 to decrease the computation times and test out our navigation solution. 2.2 Signal Temporal Logic (STL) STL allows designers to formulate natural language rules using mathematical operators. This allows for a formal method to set constraints on signal-based systems called specifications. STL has a library of operators representing the formal language’s grammar and alphabet, as shown below. 2.2.1 STL Operators [ Donzé (2013) ]: Writing in the Backus-Naur form, an STL formula can be expressed with the following syntax: \phi::=\top\ |\ \mu\ |\ \neg\phi\ |\ \phi\land\psi\ |\ \Box_{[a,b]}\phi\ |\ \Diamond_{[a,b]}\phi\ |\ \phi\ \mathcal{U}_{[a,b]}\ \psi where \top is the Boolean operator true, \mu is a predicate of the form f(s(t))>0 , \phi and \psi are STL specifications, and s(t) is a signal concerning which we check the specifications at time t . The Boolean operators \neg signifies negation, and \land and \lor denotes conjunction and disjunction, respectively. Whereas the temporal operators, such as \mathcal{U} , \Box , and \Diamond , signify the ‘Until,’ ‘Always,’ and ‘Eventually’ operators. For a given signal s(t) , the list of temporal operators can be defined as follows: \begin{array}[]{lll}s(t)\models\mu&\Leftrightarrow&f\left(s(t)\right)>0\\ s(t)\models\neg\phi&\Leftrightarrow&\neg\left(s(t)\models\phi\right)\\ s(t)\models\phi\wedge\psi&\Leftrightarrow&\left(s(t)\models\phi\right)\wedge\left(s(t)\models\psi\right)\\ s(t)\models\phi\vee\psi&\Leftrightarrow&\neg(\neg\left(s(t)\models\phi\right)\wedge\neg\left(s(t)\models\psi\right))\\ s(t)\models\phi\Rightarrow\psi&\Leftrightarrow&\neg\left(s(t)\models\phi\right)\vee\left(s(t)\models\psi\right)\\ s(t)\models\Diamond_{[a,b]}\phi&\Leftrightarrow&\exists t^{\prime}\in[t+a,t+b]\text{ s.t. }s(t^{\prime})\models\phi\\ s(t)\models\square_{[a,b]}\phi&\Leftrightarrow&\forall t^{\prime}\in[t+a,t+b]\text{ s.t. }s(t^{\prime})\models\phi\\ s(t)\models\phi\ \mathcal{U}_{[a,b]}\psi&\Leftrightarrow&\exists t^{\prime}\in[t+a,t+b]\text{ s.t. }\left(s(t^{\prime})\models\psi\right)\\ &&\wedge\left(s(0)\models\square_{\left(0,t\right]}\phi\right)\end{array} The expression \phi \mathcal{U}{[a,b]}\psi denotes that within the time interval t^{\prime}=[t+a,t+b] , the proposition \psi will eventually hold if the proposition \phi has been continuously satisfied for time (0,t] . Here, the terms ‘Eventually’ and ‘Always’ signify that the propositions must hold TRUE at least once and persist throughout the specified period, respectively. These operators can be consistently formulated using literals in their Negation Normal Form , as demonstrated by LaValle (2006) . They are not limited in scope and can be applied to any STL operators. Specifications can be amalgamated to formulate constraints for AV models necessitating control over multiple parameters. The signal s(t) can represent any real-time state value such as linear velocity ( v ), position coordinates [x,y]^{T} , etc. 2.2.2 Robustness Semantics: To rigorously assess the fulfillment of an STL specification, robust semantics are employed to delineate real-valued functions

Read the complete text