Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives

Can Zhou, Yulong Gao, Pian Yu · 2026

Read Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives by Can Zhou, Yulong Gao, Pian Yu (2026) 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-2605-12581.txt.

Introduction

Zhou, Gao and Yu give agents a sound way to act in fog while meeting time-logic goals. Linear Temporal Logic can state complex tasks, yet checking its success in partly seen Markov decision steps cannot be decided, making reward design for rough solvers hard. Their tool shapes rewards from beliefs, grounded in checked logic success, and plugs into an enhanced Monte Carlo planning setup. Tests show it succeeds where old solvers fail and keeps working across varied foggy cases.

Catalog record

CREATORCan Zhou, Yulong Gao, Pian Yu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66802
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.12581

Browse the full library · About the Tower of Babel

Full text

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

Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives Can Zhou, Yulong Gao, Pian Yu Abstract Synthesising autonomous agents that can navigate uncertain environments while adhering to complex temporal constraints remains a fundamental challenge. While Linear Temporal Logic (LTL) provides a rigorous language for specifying such tasks, the inherent undecidability of qualitatively verifying LTL satisfaction in partially observable Markov decision processes renders quantitative synthesis difficult, especially when designing reliable reward signals for approximate solvers. In this paper, we bridge this gap with a novel, sound reward-shaping mechanism that dynamically generates belief-dependent rewards grounded in certified LTL satisfaction. By integrating this mechanism into an enhanced Monte Carlo Planning framework, we empower agents to navigate the ‘fog’ of partial observability with a search process focused on maximising verifiable success. Our experiments demonstrate that this approach not only thrives in scenarios where existing solvers fail but also maintains effectiveness and scalability across diverse benchmark domains. 1 Introduction Partially Observable Markov Decision Processes (POMDPs) provide a principled framework for sequential decision-making amidst the fog of uncertainty, accounting for both stochastic dynamics and incomplete state information 13 ; 22 . When coupled with \omega -regular properties like Linear Temporal Logic (LTL) 21 , they allow for the synthesis of policies that satisfy complex, temporally extended goals over infinite traces in uncertain, partially observable environments. Therefore, POMDP-LTL synthesis has attracted considerable interest across AI, robotics, and control 23 ; 4 ; 15 . Despite its potential, quantitative POMDP-LTL synthesis, aiming to maximise satisfaction probability, remains notably challenging. Optimal policy synthesis for general planning tasks in infinite-horizon POMDPs is undecidable, even for simple reachability objectives, as it necessitates reasoning over an uncountable belief space and may require unbounded memory 8 . Practical approaches therefore rely on tractable approximations that reformulate the problem as reward maximisation, with reward functions encoding task satisfaction, and apply approximate solvers such as Point-Based Value Iteration (PBVI) 20 and Partially Observable Monte Carlo Planning (POMCP) 25 . However, constructing appropriate reward signals for full LTL is non-trivial, since its semantics concern non-terminating behaviour over infinite traces. Existing approaches either restrict attention to finite-trace LTL (LTL f ), which reduces satisfaction to a one-shot reachability problem 14 ; 18 , or apply optimistic reward shaping based on state-space accepting maximal end components (AMECs) 4 . Nevertheless, due to partial observability, POMDP policy synthesis must operate over the belief space, and many objectives such as recurrence and persistence require full LTL. Furthermore, an optimistic reward for POMDP-LTL may assign a positive satisfaction signal to a belief state even when no single belief-based policy (defined as a policy shared by all states within the belief’s support) can realise the implied satisfaction probability. This challenge, which we term the common policy issue , is illustrated in the following example. Figure 1 : A POMDP where states sharing the same observation are indicated by a common background colour. This colour-coding convention is maintained throughout all subsequent figures. Example 1 . Consider the POMDP in Figure 1 with action set \{a,c\} and initial belief b_{0}=\{s_{1}:1.0\} . The LTL objective \varphi=\square\lozenge(s_{2}\lor s_{3}) , requiring the system to visit states s_{2} or s_{3} infinitely often. Under full observability, two AMECs exist: 1. \{s_{0},s_{3}\} , which achieves almost-sure satisfaction (i.e. probability one) by alternating actions a and c , and 2. \{s_{2},s_{5}\} , which succeeds by repeatedly playing a . This suggests that all beliefs supported on AMECs yield satisfaction with probability one. However, with partial observability, no belief-based policy supported on \{s_{0},s_{3}\} can satisfy \varphi almost surely: state s_{0} requires action c , but taking c in s_{3} leads to the sink s_{4} . Conversely, beliefs supported on \{s_{2},s_{5}\} can still satisfy \varphi almost surely by playing a . Furthermore, assigning positive reward one to all states within the state-space AMECs (i.e., \{s_{0},s_{2},s_{3},s_{5}\} ) incorrectly suggests that actions a and c are equally optimal at b_{0} . In reality, c is the uniquely optimal action. More fundamentally, encoding exact LTL satisfaction as a reward signal is undecidable for POMDPs because of the probability leakage inherent in belief transitions, as shown in Example 1 for beliefs supported on \{s_{0},s_{3}\} . For such beliefs, deciding whether a policy with positive satisfaction probability exists is undecidable 2 . These theoretical barriers make it difficult to construct sound reward signals. Without these, approximate solvers struggle to converge on reliable, belief-based policies for LTL objectives. Contributions. We bridge the theoretical and practical gaps in quantitative POMDP-LTL synthesis by introducing a novel mechanism for sound reward shaping. In contrast to fixed scalar reward structures, our approach defines reward assignment rules that integrate with an enhanced online POMCP planner. This allows the system to dynamically evaluate rewards and guide the search toward maximising certified satisfaction, thereby enabling reliable belief-based policy synthesis. To the best of our knowledge, this is the first sound and practical anytime synthesis algorithm for full LTL in POMDPs. Our main contributions are summarised as follows: 1) Sound Reward Shaping: We introduce a sound reward shaping mechanism over the belief space by leveraging belief support structures, grounded in the insight that almost-sure satisfaction is the only certifiable property in POMDP-LTL. A pruning strategy streamlines reward construction, and the resulting rewards provide a certified lower bound on the true LTL satisfaction probability. 2) Sound Anytime Synthesis: We integrate our reward assignment rules into an enhanced POMCP algorithm specialised for anytime LTL synthesis. Once the search reaches a certified belief region, the agent may continue exploring for higher satisfaction or switch to a verified policy that guarantees satisfaction. This offers the first sound and practical method for real-time POMDP-LTL synthesis. 3) Empirical Validation: We show that our method synthesises reliable belief-based policies in scenarios where existing approaches fail. We further show its effectiveness and scalability on three standard POMDP benchmarks with diverse LTL tasks. Related Work. Owing to the undecidability of quantitative synthesis for POMDPs with LTL, prior work has turned to tractable approximations. One possible approach is to restrict policies to randomised finite-state controllers (FSCs) 7 ; 23 ; 1 ; 5 ; 6 . However, such finite-memory restrictions impose key limitations: optimisation remains only locally optimal for any fixed memory size, and while performance is highly sensitive to that size, the minimal required memory is undecidable 19 . A complementary line of work 18 ; 14 ; 15 considers belief-based policies for finite-trace LTL (LTL f ). However, many complex planning tasks require infinite-horizon recurrence and persistence, necessitating full LTL. 4 addresses this by applying PBVI with reward signals derived from state-based AMECs. As illustrated in Example 1 , such state-based reward shaping can be overly optimistic under partial observability. A detailed discussion of related work is provided in Appendix A. 2 Preliminaries and Problem Statement This section first outlines the preliminaries of LTL and its equivalent Limit-Deterministic Büchi Automaton (LDBA) representation. We then provide the foundations of POMDPs and the POMCP algorithm for online planning. Finally, the problem under consideration is formulated. 2.1 Linear Temporal Logic LTL 21 extends propositional logic by introducing temporal operators that enable the specification of task requirements over time. The syntax of an LTL path formula over a finite set of atomic propositions ( \mathtt{AP} ) is

Read the complete text