Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty
Pian Yu *, Yong Li, David Parker, Marta Kwiatkowska · 2025
Read Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty by Pian Yu *, Yong Li, David Parker, Marta Kwiatkowska (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-2502-19603.txt.
Introduction
A robot told to patrol, wait, then deliver faces two kinds of doubt: odds it can measure and fog it cannot. Pian Yu and co-authors build a planner for both in a 2025 paper, using logic formulas that state tasks over time. Their model lets each move branch into a set of possible outcomes rather than one known lottery.
The method marks the region of states from which the task can still be won, then improves choices inside it step by step. A special automaton keeps the logic side cheap to build. A test robot on a hexagon world showed the approach working with promising speed.
Catalog record
| CREATOR | Pian Yu *, Yong Li, David Parker, Marta Kwiatkowska |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19603
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty Pian Yu *, Yong Li, David Parker, Marta Kwiatkowska Abstract This work studies the planning problem for robotic systems under both quantifiable and unquantifiable uncertainty. The objective is to enable the robotic systems to optimally fulfill high-level tasks specified by Linear Temporal Logic (LTL) formulas. To capture both types of uncertainty in a unified modelling framework, we utilise Markov Decision Processes with Set-valued Transitions (MDPSTs). We introduce a novel solution technique for the optimal robust strategy synthesis of MDPSTs with LTL specifications. To improve efficiency, our work leverages limit-deterministic Büchi automata (LDBAs) as the automaton representation for LTL to take advantage of their efficient constructions. To tackle the inherent nondeterminism in MDPSTs, which presents a significant challenge for reducing the LTL planning problem to a reachability problem, we introduce the concept of a Winning Region (WR) for MDPSTs. Additionally, we propose an algorithm for computing the WR over the product of the MDPST and the LDBA. Finally, a robust value iteration algorithm is invoked to solve the reachability problem. We validate the effectiveness of our approach through a case study involving a mobile robot operating in the hexagonal world, demonstrating promising efficiency gains. I Introduction Uncertainty in planning can be categorised into two types based on the effects of actions: probabilistic and nondeterministic. In probabilistic planning, uncertainty is quantified using probabilities, with Markov Decision Processes (MDPs) and their generalisations serving as the standard modelling frameworks [ 1 , 2 ] . Nondeterministic planning, on the other hand, addresses unquantifiable uncertainty (such as ambiguity and adversarial environments), typically exploiting the fully observable nondeterministic domain (FOND) as a modelling framework [ 3 , 4 , 5 ] . Both probabilistic and nondeterministic planning have been extensively studied, leading to significant advances in the field. Robotic systems are susceptible to many different types of uncertainty, such as sensing and actuation noise, unpredictability in a robot’s perception, and dynamic environments [ 6 , 7 ] . Some sources of uncertainty, such as sensing and actuation noise, can be quantified probabilistically using statistical methods. However, ambiguous uncertainties, such as unpredictable perception and dynamic environments, are often more challenging to quantify. Existing works in robot planning mainly focus on addressing either quantifiable or unquantifiable uncertainty. However, in scenarios such as human-robot collaboration [ 8 ] , both quantifiable and unquantifiable uncertainties are present. Quantifiable uncertainties may arise from robotic actuation errors, while unquantifiable uncertainties often stem from the unpredictable nature of human behavior. To the best of our knowledge, approaches that can effectively handle both types of uncertainty simultaneously have, however, been less explored. In light of this, we propose to utilise MDPs with set-valued transitions (MDPSTs) [ 9 , 10 ] as our unified modelling framework. They are attractive because they admit a simplified Bellman equation compared to (more general) MDPs with imprecise probabilities (MDPIPs) [ 11 , 12 , 13 ] and Uncertain MDPs (UMDPs) [ 14 , 15 , 16 ] , and thus stochastic games [ 17 ] . Recently, MDPSTs have been employed to formalise the trembling-hand problem in nondeterministic domains [ 18 ] , where the term “trembling-hand” refers to the phenomenon in which an agent, due to faults or imprecision in its action selection mechanism, may mistakenly perform unintended actions with a certain probability, potentially leading to goal failures. Specifically, this approach demonstrates that the human-robot co-assembly problem can be modelled using MDPSTs, yielding more efficient solution techniques compared to the stochastic game formulation. In this work, Linear Temporal Logic on finite traces ( ltl f ) [ 19 ] was used as the task specification language. ltl f shares the same syntax as Linear Temporal Logic (LTL) [ 20 ] but is interpreted over finite rather than infinite traces [ 19 ] . However, in many robotic applications, such as persistent surveillance and repetitive supply delivery, it is necessary to define the robot’s tasks over infinite trajectories. Indeed, LTL has been widely applied in robotics research for specifying complex temporal objectives over infinite traces, such as [ 21 , 22 , 23 , 24 , 25 , 26 ] , including MDPs with LTL objectives, e.g., [ 27 , 28 , 29 ] . A typical approach involves converting the LTL specification into a Deterministic Rabin Automaton (DRA) and then taking the product of the MDP and the DRA [ 30 ] . This reduces the problem to a planning problem with a reachability goal over the product space. In this paper, we propose to formalise the planning problem for robotic systems under both quantifiable and unquantifiable uncertainty with temporal objectives as the strategy synthesis problem for MDPSTs with (full) LTL objectives. We highlight that MDPSTs with LTL objectives are studied for the first time in this paper. Due to the presence of unquantifiable uncertainty in MDPSTs, computing the end components [ 31 ] of an MDPST becomes nontrivial. As a result, the conventional procedure for MDPs with LTL objectives based on conversion to DRAs does not apply, necessitating new solution techniques developed in this work. The main contributions are summarised as follows. (i) We propose using MDPSTs as the modelling framework for robot planning under both quantifiable and unquantifiable uncertainty. Although the model has been relatively little studied since it was initially proposed in 2007 [ 9 ] , recent findings highlight its advantages, particularly in terms of computational efficiency [ 18 ] . (ii) A novel solution technique is proposed for the optimal robust strategy synthesis for MDPSTs with LTL specifications. This technique addresses the inherent nondeterminism in MDPSTs, which complicates the reduction of the LTL planning problem to a reachability problem, by introducing the concept of a Winning Region (WR). To further improve efficiency, we leverage limit-deterministic Büchi automata (LDBAs) [ 32 , 33 , 34 ] , which are typically smaller than conventional DRAs thanks to their efficient construction from LTL. We devise an algorithm for computing WR over the product of the MDPST and the LDBA, and its correctness is demonstrated formally. II Preliminaries This section provides preliminaries for LTL [ 20 ] and its equivalent LDBA [ 34 ] representation. LTL [ 20 ] extends propositional logic with temporal operators. The syntax of an LTL formula over a finite set of propositions \mathtt{Prop} is defined inductively as: \varphi::=\mathsf{true}|p\in\mathtt{Prop}|\neg\varphi|\varphi\wedge\varphi|\varphi\vee\varphi|\bigcirc\varphi|\varphi\mathsf{U}\varphi, (1) where \bigcirc (Next) and \mathsf{U} (Until) are temporal operators. As usual, additional Boolean and temporal operators are derived as follows: \varphi_{1}\Rightarrow\varphi_{2}\equiv\neg\varphi_{1}\vee\varphi_{2} (Implies), \lozenge\varphi\equiv\mathsf{true}\mathsf{U}\varphi (Eventually), and \square\varphi=\neg(\lozenge\neg\varphi) (Always). The detailed semantics of LTL can be found in [ 20 , 30 ] . A trace \pi=\pi_{0}\pi_{1}\ldots is a finite or infinite sequence of propositional interpretations (sets), where for every i\geq 0 , \pi_{i}\in 2^{\mathtt{Prop}} is the i -th interpretation in \pi . Intuitively, \pi_{i} is interpreted as the set of propositions that are \mathsf{true} at instant i . For a finite trace \pi\in(2^{\mathtt{Prop}})^{*} , we denote the interpretation at the last instant (i.e., index) by {\sf{lst}}(\pi) , and we write \pi\models\varphi when an infinite trace \pi\in(2^{\mathtt{Prop}})^{\omega} satisfies LTL formula \varphi . The language of \varphi , denoted by \mathtt{L}(\varphi) , is the set of infinite traces over 2^{\mathtt{Prop}} that satisfy \varphi . Every