[YLPK25]
Pian Yu, Yong Li, David Parker, Marta Kwiatkowska.
Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty.
In Proc. at IEEE International Conference on Robotics and Automation (ICRA). To appear.
2025.
[pdf]
[bib]
https://arxiv.org/abs/2502.19603
|
Available from:
https://arxiv.org/abs/2502.19603
|
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¨uchi automata (LDBAs) as the automaton representation for LTL to take advantage of their efficient constructions. To tackle the inherent nondeterminism in MDPSTs, which complicates the reduction of 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.
|