EUVIMEDEUVIMED entdecken
Crossref

Incremental LTLf Synthesis

Giuseppe De Giacomo, Yves Lespérance, Gianmarco Parretti, Fabio Patrizi, Moshe Y. Vardi

Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 57-66

DOI: 10.1609/icaps.v36i1.42814 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Giuseppe De Giacomo und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 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 formulas at each step, this formula progression-based solution is not competitive.

Zitieren

APA

Giacomo, G. D., Lespérance, Y., Parretti, G., Patrizi, F., & Vardi, M. Y. (2026). Incremental LTLf Synthesis. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 57-66. https://doi.org/10.1609/icaps.v36i1.42814

Vancouver

Giacomo GD, Lespérance Y, Parretti G, Patrizi F, Vardi MY. Incremental LTLf Synthesis. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):57-66. doi:10.1609/icaps.v36i1.42814

BibTeX
@article{Giacomo2026,
  author = {Giacomo, Giuseppe De and Lespérance, Yves and Parretti, Gianmarco and Patrizi, Fabio and Vardi, Moshe Y.},
  title = {Incremental LTLf Synthesis},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {57--66},
  doi = {10.1609/icaps.v36i1.42814}
}
Kostenlos starten →