arXiv:2608.02454cs.AIcs.FL2026-08

将复杂的时间逻辑LTL转换为更易处理的LTLf+,提升AI规划效率。

Infinite Trace Objectives with Finite Trace Techniques: Translating LTL to LTLf+

  • 将LTL公式转化为LTLf+的结构化形式,利用有限词自动机方法。
  • 实现线性翻译,保持双指数复杂度不变,计算效率更高。
  • 让原本仅适用于LTLf+的技术可直接用于传统LTL问题,如强化学习。

线性时序逻辑(LTL)是人工智能中指定时序目标最广泛使用的语言,应用于反应式综合、马尔可夫决策过程中的随机规划及强化学习等领域。传统方法需将LTL公式转换为无限词上的非确定性自动机并进行确定化,该步骤在理论和实践中均极困难。近期提出的LTLf+将有限迹逻辑LTLf扩展至无限迹,表达能力与LTL相同,但保留了LTLf在有限词自动机上的优势:存在唯一最小表示和高效确定化算法。本文首次提出从LTL到LTLf+的完整翻译方法:先将LTL公式归约为曼纳-普内利层次中的语法反应片段,再对各组件进行线性翻译。由此,大量针对LTLf+开发的技术可直接应用于原属LTL的问题。此外,该流程的渐近复杂度仍为双指数,未增加额外开销。

原文摘要 · Abstract (English)

Linear Temporal Logic (LTL) is one of the most widely adopted languages for specifying temporal extended objectives in AI, with applications ranging from reactive synthesis to stochastic planning in Markov decision processes and reinforcement learning. Traditionally, solving any of these problems requires translating the LTL specification to a nondeterministic automata on infinite words and then determinizing it, a step that is notoriously difficult in theory and in practice. Recent work has introduced LTLf+, which lifts the finite-trace logic LTLf to infinite traces. LTLf+ has the same expressive power as LTL, yet it retains most of the crucial advantages of its base logic LTLf. Most reasoning in LTLf+ rests on finite automata on finite words, for which we have not only a canonical minimal representation but also an efficient determinization procedure. In this work we present the first translation from LTL to LTLf+. We first normalize an LTL formula into the syntactic reactivity fragment of the Manna-Pnueli hierarchy, to create the general fragment-based shape of LTLf+. We then present linear translations for each individual component of that fragment. As a consequence of this translation, the expanding body of techniques developed for LTLf+ now becomes available to many AI problems currently formulated in LTL. We further show that this comes at no asymptotic cost, as the pipeline from LTL to automaton via LTLf+ remains doubly exponential.

时序逻辑自动机AI规划形式验证

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。