Reactive Synthesis of Dominant Strategies

Benjamin Aminof, Giuseppe De Giacomo, Sasha RubinAAAI 2023 · DOI

Introduction

In the field of reactive synthesis, the objective is to automatically generate a system—an agent—that interacts with an environment to satisfy a specific goal, typically expressed in Linear Temporal Logic (LTL). Traditionally, researchers have focused on two types of strategies: enforcing strategies, which guarantee success against all possible environment behaviors, and best-effort strategies, which aim to succeed against a maximal set of environment behaviors when an absolute guarantee is impossible.

However, both approaches have drawbacks. Enforcing strategies are often too restrictive and frequently do not exist in unpredictable environments. Conversely, best-effort strategies lack "interchangeability." Two different best-effort strategies might succeed in entirely disjoint sets of environment scenarios, forcing a designer to "gamble" on which environment behaviors are more likely to occur. This paper, presented at AAAI-23, introduces dominant strategies as a robust middle ground that eliminates this uncertainty.

The Problem: The Best-Effort Gamble

When an enforcing strategy does not exist, a best-effort strategy $\sigma$ is chosen such that the set of environment behaviors it wins against is maximal. The critical issue is that maximality does not imply uniqueness or optimality across all scenarios. If strategy $\sigma_1$ wins in environment scenario $A$ but fails in $B$, and $\sigma_2$ wins in $B$ but fails in $A$, both are "best-effort" if no strategy wins in both $A$ and $B$.

Dominant strategies address this by ensuring the agent always achieves the best possible outcome. A strategy is dominant if it performs at least as well as any other strategy against every environment behavior that conforms to the system's specifications. If a dominant strategy exists, it is effectively the "best" possible version of a best-effort strategy, succeeding in the maximum possible set of scenarios.

Theoretical Framework and Characterization

The authors utilize formal logic and automata theory to characterize dominance. They define a preorder of strategies based on their performance across different environment histories.

Local Characterization

A key contribution of the paper is the "local" identification of dominant strategies. By analyzing the history of interactions, states are categorized as:

  • Winning: The agent can force a win.
  • Losing: The agent is guaranteed to fail regardless of its moves.
  • Pending: The outcome is not yet determined.

A strategy is considered dominant if it only enters a "losing" state when winning is mathematically impossible from that point forward. This leads to the "Hopeful View": a strategy is dominant if and only if it achieves the goal against every "hopeful" environment—one that does not explicitly force the agent to lose.

Key Properties: Interchangeability and Monotonicity

Dominant strategies possess two highly desirable properties that best-effort strategies lack:

  1. Interchangeability: All dominant strategies for a specific goal are equivalent in terms of the environment scenarios they satisfy. This removes the "gamble" inherent in selecting between multiple best-effort plans.
  2. Monotonicity: Dominant strategies are stable under refinement. If the environment specification is tightened (restricting the environment's possible moves), a strategy that was dominant remains dominant. Interestingly, best-effort strategies do not necessarily maintain this property.

Algorithmic Synthesis

To compute these strategies, the authors translate LTL goals into Deterministic Parity Automata (DPA) or Deterministic Finite Automata (DFA). They propose a unified synthesis algorithm that uses fixed-point iterations on a product automaton.

The algorithm follows a hierarchical search:

  1. It first attempts to find an enforcing strategy.
  2. If no enforcing strategy exists, it checks for the existence of a dominant strategy.
  3. If a dominant strategy is also unavailable, it falls back to a best-effort strategy.

Computational Complexity

A significant finding is that the complexity of deciding the existence of and synthesizing a dominant strategy is 2EXPTIME-complete. This matches the complexity of standard LTL synthesis. Consequently, designers can seek dominant strategies without incurring a higher computational cost than they would for traditional enforcing strategies.

Limitations and Conclusion

While dominant strategies provide a superior alternative to best-effort approaches, they are not a universal solution. The primary limitation is that a dominant strategy is not guaranteed to exist for every specification. In such cases, the agent must still rely on best-effort strategies. Additionally, while 2EXPTIME-completeness is standard for LTL, it remains a challenge for real-time, large-scale applications.

In summary, this research formalizes a critical "sweet spot" in agent design. By filling the gap between strict enforcement and loose best-effort success, dominant strategies provide a more reliable and predictable framework for reactive synthesis in uncertain environments.

Summary updated

BibTeX
@inproceedings{aminof2023reactive,
  author = {Benjamin Aminof and Giuseppe De Giacomo and Sasha Rubin},
  title = {{Reactive Synthesis of Dominant Strategies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25767},
}
Figure