# Time-Optimal Navigation in Uncertain Environments with High-Level Specifications

arXiv: https://arxiv.org/abs/2103.01476 · HTML: https://mlsanity.com/paper/2103.01476/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2021.

## Built on by (most cited first, 2 of 2)

- [Risk-Averse Decision Making Under Uncertainty](https://mlsanity.com/paper/2109.04082/) (2021)
- [SIT-LMPC: Safe Information-Theoretic Learning Model Predictive Control for Iterative Tasks](https://mlsanity.com/paper/2602.16187/) (2026)

## Abstract (arXiv)

Mixed observable Markov decision processes (MOMDPs) are a modeling framework for autonomous systems described by both fully and partially observable states. In this work, we study the problem of synthesizing a control policy for MOMDPs that minimizes the expected time to complete the control task while satisfying syntactically co-safe Linear Temporal Logic (scLTL) specifications. First, we present an exact dynamic programming update to compute the value function. Afterwards, we propose a point-based approximation, which allows us to compute a lower bound of the closed-loop probability of satisfying the specifications. The effectiveness of the proposed approach and comparisons with standard strategies are shown on high-fidelity navigation tasks with partially observable static obstacles.