Symbolic ltl f Synthesis: A Unified Approach for Synthesizing Winning, Dominant, and Best-Effort Strategies

Journal article

Synthesis typically focuses on finding strategies that win against all possible responses of the environment. When a winning strategy does not exist, the agent can either give up or do its best to achieve the goal. In this paper, we develop symbolic techniques to handle the latter case in the context of ltlf. Specifically, we consider winning, dominant, and best-effort strategies, which achieve the goal against all, the maximum subset, and a maximal subset of environment responses, respectively. While a unified game-theoretic technique that simultaneously solves the three synthesis problems exists, we present several symbolic refinements of such technique. Depending on key choices, such refinements behave in a radically different way. We provide an effective implementation of our symbolic techniques and show, by empirical evaluation, how they compare in practice. In particular, we show that one of them brings only a minor overhead compared to existing standard synthesis techniques for winning strategies.

Authors: De Giacomo, G; Parretti, G; Zhu, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: SN Computer Science
• Volume: 6
• Issue: 2
• Article number: 147
• Publication date: 2025-02-07
• Acceptance date: 2024-09-24
• DOI: 10.1007/s42979-024-03337-8
• EISSN: 2661-8907
• Language: English
• Keywords: Winning strategies; Dominant strategies; Symbolic synthesis; ltlf\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_f$$\end{document} synthesis; Best-effort strategies