Resource-Constrained Robotic Planning in the Face of Mixed Uncertainty
Yihao Yin,,, Pian Yu, Andrea Turrini, Zhiming Chi,, Yong Li, and Lijun Zhang
AI summary
Problem
Autonomous robots must execute complex temporal tasks while strictly avoiding resource exhaustion, yet existing planning methods struggle to jointly handle hard resource constraints and mixed quantifiable/unquantifiable uncertainties.
Approach
The authors model robotic systems as Consumption Markov Decision Processes with Set-valued Transitions (CMDPSTs) combined with LTLf task specifications, then synthesize optimal robust strategies using a naive unrolling method and an optimized state-space pruning technique.
Key results
- Introduction of the CMDPST framework for unified modeling of mixed uncertainty and resource constraints
- Formulation of the resource-constrained optimal robust strategy synthesis problem with LTLf specifications
- Development of a naive unrolling-based synthesis pipeline for exact strategy computation
- Demonstration that state-space pruning significantly reduces synthesis runtime while preserving correctness
Why it matters
Enables reliable, long-horizon autonomous planning for safety-critical applications like warehouse logistics and planetary exploration where energy limits and unpredictable environments coexist.
Abstract
Robots operate under significant uncertainty, from quantifiable noise to unquantifiable unknowns, and must ac- count for strict operational constraints, such as limited re- sources. In this paper, we consider the problem of synthesizing robust strategies to guide a robot’s actions in fulfilling a given task, while ensuring the system never exhausts its resources. To solve this problem, we first model the robotic system as a Con- sumption Markov Decision Process with Set-valued Transitions (CMDPST), a unified framework modelling nondeterministic actions, quantifiable and unquantifiable uncertainty, and re- source consumption. Then, we combine the CMDPST with the task specification, expressed as a Linear Temporal Logic over finite traces (LTLf) formula. Lastly, we address the resource- constrained optimal robust strategy synthesis problem, which aims to synthesize a strategy that maximizes the probability of satisfying the LTLf objective without resource exhaustion. Our solution involves two techniques: a direct unrolling- based method and a more efficient, optimized approach that leverages state-space pruning for better performance. Ex- periments on a warehouse transportation network show the effectiveness of the proposed solutions.