Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty

[YLPK25] Pian Yu, Yong Li, David Parker and Marta Kwiatkowska. Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty. In Proc. IEEE International Conference on Robotics and Automation (ICRA'25), pages 3940-3946, IEEE. May 2025. pdf bib

Downloads
PDF 912 KBBibTeX
Search for this paper
Google · Google Scholar

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 optimal robust strategy synthesis of MDPSTs with LTL specifications. To improve efficiency, our work leverages limit-deterministic B"uchi 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.