Best Effort Reactive Synthesis for Unrealizable Specifications

50 concepts36 papers

In traditional reactive synthesis, we ask an automated tool to construct a system controller that is guaranteed to satisfy a temporal logic specification against every possible move of an environment. This problem is conventionally framed as a zero-sum, two-player game. If the environment possesses even a single sequence of actions that can force a violation, the specification is declared unrealizable, and the synthesis engine returns a binary failure.

As noted by Alessandro Cimatti et al. in their development of the requirements analysis tool RATSY, specifications are frequently unrealizable not because the system's internal logic is flawed, but because the external environment is insufficiently constrained. In the real world, this binary realizability constraint creates a severe usability bottleneck. A robot or a network configuration protocol facing an unpredictable or unaligned environment will simply refuse to generate a strategy, choosing to do nothing rather than executing a "best-effort" plan.

To bridge this gap, a major research direction focuses on breaking this all-or-nothing paradigm. By shifting from worst-case pessimism to approximate, conditional, and robust synthesis, recent frameworks ensure that systems can still generate functional, high-quality implementations when perfect guarantees are mathematically impossible.

The Pessimism of Antagonistic Environments

The core limitation of classical synthesis is its assumption of a perfectly malicious adversary. As Guillermo Perez et al. argue in Reactive synthesis without regret, treating the environment as purely antagonistic is overly conservative. Real-world environments are often indifferent, stochastic, or bound by physical limitations that the designer simply neglected to write down.

When a specification is strictly unrealizable, a physical controller typically ceases to function entirely. Matías Brizzio highlights this vulnerability in Automated Repair of Unrealisable LTL Specifications Guided by Model Counting: if a human operator can theoretically block a robot's path indefinitely, a standard synthesis tool concludes that the robot cannot guarantee reaching its goal, and fails to output any controller at all.

To counter this, researchers have introduced alternative success criteria that relax the requirement for a universal guarantee.

Good-Enough and Dominant Strategies

If a system cannot win against every environment, how should it choose its actions? One intuitive approach is to fulfill the specification only when the environment behaves reasonably.

Yong Li 0031 et al. formalize this intuition as Good-Enough (GE) synthesis for finite traces in Synthesizing Good-Enough Strategies for LTLf Specifications. Instead of forcing a system to satisfy its goals under all environment behaviors, a GE strategy guarantees satisfaction provided that the environment's inputs have not already made the goal impossible. By transforming this problem into a Deterministic Büchi Automaton (DBA) game, the authors bypass the computational complexity of traditional parity games while preventing synthesis failure when the environment holds a unilateral winning move.

Traditional Synthesis:
[Environment Actions] ---> Must guarantee success across ALL paths ---> If 1 fails: UNREALIZABLE

Good-Enough Synthesis:
[Environment Actions] ---> Identify paths where success is still possible ---> Guarantee success on THOSE paths

Similarly, Benjamin Aminof et al. explore best-effort reactive synthesis by looking for dominant strategies in Reactive Synthesis of Dominant Strategies. A dominant strategy ensures that for any environment behavior where some controller could have succeeded, this controller will succeed. This protects the system from making a gamble that closes off viable paths to victory.

When exact symbolic methods are too rigid or computationally expensive, approximate reasoning can provide a functional starting point. For instance, in complex domains like network configuration, Luca Beurer-Kellner et al. demonstrate in Learning to Configure Computer Networks with Neural Algorithmic Reasoning that graph neural networks can generate best-effort configurations that satisfy the vast majority of requirements, bypassing the hard crash of traditional SMT solvers when constraints conflict.

Quantitative Satisfaction and Regret Minimization

Another way to escape the binary realizability constraint is to quantify how well a specification is satisfied.

In Maximum Realizability for Linear Temporal Logic Specifications, Mahsa Ghasemi et al. partition system requirements into "hard" constraints (e.g., safety) and "soft" properties (e.g., performance optimizations). By leveraging MaxSAT solvers, their framework guarantees that hard constraints are never violated while maximizing the number of soft properties satisfied over time.

Alternatively, we can minimize the system's regret. In Reactive synthesis without regret, the authors define regret as the difference between the performance of the chosen strategy and the performance of an omniscient strategy that knew the environment's actions in advance. Minimizing regret ensures that the system performs as close to optimally as possible, even when it cannot force a win against a worst-case adversary.

For scenarios where specifications must hold over finite behaviors, Bernd Finkbeiner et al. propose a model-counting approach in Synthesizing Approximate Implementations for Unrealizable Specifications. By restricting the environment to bounded-length input sequences (lassos), they use quantitative model counting to synthesize approximate implementations that are mathematically guaranteed to work for a specified majority of environment behaviors.

Refining Environment Assumptions and Diagnosing Failure

When a specification is unrealizable, the fault often lies in a failure to properly model the environment's constraints. Instead of weakening the system's goals, we can automatically tighten our assumptions about the environment.

Krishnendu Chatterjee et al. pioneered this approach in Environment Assumptions for Synthesis by introducing a two-step algorithm to automatically compute the weakest environment assumptions—covering both safety and liveness—needed to make a reactive system realizable. Crucially, these generated assumptions are non-restrictive, meaning they preserve the system's original flexibility while blocking only the environment behaviors that make failure unavoidable.

To automate this "debugging" process, Rajeev Alur et al. developed a framework described in Counter-Strategy Guided Refinement of GR(1) Temporal Logic Specifications. When synthesis fails, the tool extracts an environment counter-strategy (a proof of how the environment can force a win) and uses it to suggest missing assumptions to the designer. This diagnostic paradigm is also explored by Dorsa Sadigh et al. in Diagnosis and Repair for Synthesis from Signal Temporal Logic Specifications, which applies minimal "slack" adjustments to conflicting constraints, and is implemented in probabilistic game solvers like Gist (Barbara Jobstmann et al., Gist: A Solver for Probabilistic Games).

Robustness and Environmental Friendliness

A common pitfall of assuming a perfectly constrained environment is that a single, transient environment violation can cause a system to fail permanently. For example, a sensor glitch might violate an environment assumption for one time-step, causing a traditional controller to stop performing useful actions indefinitely.

To handle these anomalies, Hans-Jürgen Gamauf et al. extend the synthesis pipeline in Synthesizing Robust Systems with RATSY to generate robust systems. These controllers are mathematically guaranteed to recover and resume fulfilling their guarantees once the environment returns to a valid state.

Similarly, Benjamin Aminof et al. propose a dual-model framework in Synthesizing strategies under expected and exceptional environment behaviors. The controller strictly guarantees system goals under "expected" environment behaviors, while simultaneously maintaining a "best-effort" response to handle "exceptional" or faulty environment behaviors without any performance trade-offs between the two modes.

Finally, researchers have recognized that systems can sometimes "win" games vacuously by behaving aggressively. In standard reactive synthesis, a system can satisfy its specification by intentionally forcing the environment's assumptions to become false—effectively sabotaging the environment to win on a technicality.

To prevent this, Rupak Majumdar et al. introduce environmentally-friendly synthesis in Environmentally-Friendly GR(1) Synthesis. They enforce a branching-time property called non-conflictingness, which dictates that a system's strategy must always leave open a valid path for the environment to fulfill its own liveness requirements. This ensures that cooperative or best-effort systems do not achieve their goals by rendering their surroundings non-functional.

Vacuous Winning (Standard Synthesis):
System blocks Environment ---> Environment Assumptions become FALSE ---> System wins vacuously (Useless in practice)

Environmentally-Friendly Synthesis:
System acts ---> Enforces Non-Conflictingness ---> Environment retains a path to fulfill its goals

By moving away from strict binary realizability, this body of work transforms reactive synthesis from an fragile, all-or-nothing mathematical exercise into a flexible framework capable of producing robust, cooperative, and best-effort controllers for unpredictable real-world environments.

Key Foundational Work

Environment Assumptions for Synthesis (2008) — contributed 3 concept elements to this direction.
Extracting FSMs from Object-Z Specifications with History Invariants (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_all_or_nothing_synthesis_e63c4934,
  title = {all-or-nothing synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/all-or-nothing-synthesis/rdr_e63c4934f565467b9c8661de9cb45fed},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_all_or_nothing_synthesis_e63c4934_v1,
  title = {all-or-nothing synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/all-or-nothing-synthesis/rdr_e63c4934f565467b9c8661de9cb45fed/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake