arXiv:2603.01201cs.AI2026-03

动态添加目标时,可快速更新策略而不丢弃旧目标。

Incremental LTLf Synthesis

  • 基于自动机构造辅助结构,实现多目标增量合成。
  • 公式推进虽产生大表达式,但最小自动机大小不变。
  • 适合需要实时调整任务的智能体系统设计者。

本文研究增量LTLf合成——一种在执行过程中逐步接收新目标的反应式合成方法。当主角代理已执行某目标策略时,若收到新目标,需放弃当前策略,从当前时刻起合成新策略,同时仍满足初始目标与新增目标。本文正式定义该问题并提出解决方案:利用基于自动机合成过程中的辅助数据结构,高效完成多目标增量合成;另提出基于LTLf公式推进的替代方案。尽管公式推进可能生成指数级更大的公式,其最小自动机规模仍被原公式的自动机规模所限制。然而实验表明,若每次新目标到达时都从头计算推进公式的自动机,该方法性能不佳,不具备竞争力。

原文摘要 · Abstract (English)

In this paper, we study incremental LTLf synthesis -- a form of reactive synthesis where the goals are given incrementally while in execution. In other words, the protagonist agent is already executing a strategy for a certain goal when it receives a new goal: at this point, the agent has to abandon the current strategy and synthesize a new strategy still fulfilling the original goal, which was given at the beginning, as well as the new goal, starting from the current instant. In this paper, we formally define the problem of incremental synthesis and study its solution. We propose a solution technique that efficiently performs incremental synthesis for multiple LTLf goals by leveraging auxiliary data structures constructed during automata-based synthesis. We also consider an alternative solution technique based on LTLf formula progression. We show that, in spite of the fact that formula progression can generate formulas that are exponentially larger than the original ones, their minimal automata remain bounded in size by that of the original formula. On the other hand, we show experimentally that, if implemented naively, i.e., by actually computing the automaton of the progressed LTLf formulas from scratch every time a new goal arrives, the solution based on formula progression is not competitive.

形式化验证反应式合成LTLf智能体系统

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