提出新方法大幅压缩LTL规划中的自动机状态,提升算法效率。
Good-for-MDP State Reduction for Stochastic LTL Planning
- 通过链式变换优化好-为MDP自动机状态空间
- 实验显示状态数减少显著,计算速度大幅提升
- 特别适合处理G Fφ型目标,复杂度更低
我们研究在马尔可夫决策过程(MDPs)中以线性时序逻辑(LTL)指定目标的随机规划问题。当前最优方法将LTL公式转换为好-为MDP(GFM)自动机,其具有受限的非确定性形式,并与MDP复合,使智能体在策略合成时可决定非确定性。该方法的可扩展性主要受生成自动机规模影响。本文提出一种新型GFM状态空间缩减技术,显著减少自动机状态数量。方法利用近期针对对抗场景提出的博弈自动机最小化进展,构建复杂链式变换。除理论贡献外,还给出G Fφ型公式的直接构造方法(φ为共安全公式),该方法最坏情况下为单指数复杂度,优于一般双指数复杂度。实验验证了该构造在可扩展性上的优势。
原文摘要 · Abstract (English)
We study stochastic planning problems in Markov Decision Processes (MDPs) with goals specified in Linear Temporal Logic (LTL). The state-of-the-art approach transforms LTL formulas into good-for-MDP (GFM) automata, which feature a restricted form of nondeterminism. These automata are then composed with the MDP, allowing the agent to resolve the nondeterminism during policy synthesis. A major factor affecting the scalability of this approach is the size of the generated automata. In this paper, we propose a novel GFM state-space reduction technique that significantly reduces the number of automata states. Our method employs a sophisticated chain of transformations, leveraging recent advances in good-for-games minimisation developed for adversarial settings. In addition to our theoretical contributions, we present empirical results demonstrating the practical effectiveness of our state-reduction technique. Furthermore, we introduce a direct construction method for formulas of the form $\mathsf{G}\mathsf{F}φ$, where $φ$ is a co-safety formula. This construction is provably single-exponential in the worst case, in contrast to the general doubly-exponential complexity. Our experiments confirm the scalability advantages of this specialised construction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。