💻 computer science

Towards the Usage of Window Counting Constraints in the Synthesis of Reactive Systems to Reduce State Space Explosion

This paper proposes an iterative synthesis approach that utilizes window counting constraints to exploit specification monotonicity, thereby constructing automata with over- or under-approximations to significantly reduce state space explosion in the automated construction of reactive system strategies.

Original authors: Linda Feeken, Martin Fränzle

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Linda Feeken, Martin Fränzle

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "State Space Explosion"

Imagine you are trying to teach a robot how to navigate a factory floor. You give it a set of rules (a specification), like "Always avoid the red zones" or "Visit the charging station at least twice every hour."

To do this automatically, a computer program tries to build a giant map of every possible situation the robot could ever be in.

If the robot has to remember its last 5 moves, the map is small.
If the robot has to remember its last 100 moves, the map becomes astronomically huge. It grows so fast that it's like trying to map every grain of sand on Earth just to find a path to the kitchen.

This is called State Space Explosion. It makes it impossible for computers to solve complex problems because they run out of memory and time before they can find a solution.

The Paper's Solution: "Window Counting Constraints"

The authors (Linda Feeken and Martin Fränzle) propose a clever way to shrink this giant map. They focus on a specific type of rule called a Window Counting Constraint.

The Analogy: The "Sliding Window" Rule
Imagine a rule that says: "You must eat at least 2 apples out of every 5 meals."
This isn't a rule about your whole life; it's a rule about a sliding window of time. As you eat meal #6, the window slides forward, and you look at meals #2 through #6.

The paper deals with rules like:

"The robot must charge its battery at least 2 times in every 10 moves."
"The robot must avoid the red zone at most 1 time in every 5 moves."

The Magic Trick: "Climbing the Ladder" (Incremental Synthesis)

Usually, if you want to check if a robot can follow the "2 apples in 10 meals" rule, the computer tries to build the map for the full 10 meals immediately. This is hard.

The authors suggest a different approach: Start small and grow.

Step 1 (The Baby Step): Ask the computer: "Can the robot eat 2 apples in just 1 meal?" (This is impossible, so the computer quickly says "No" and learns that the robot must eat an apple immediately).
Step 2 (A Little Bigger): Ask: "Can it eat 2 apples in 2 meals?"
Step 3 (Keep Growing): Ask: "Can it eat 2 apples in 3 meals?" ... up to 10.

Why is this better?
Think of it like climbing a ladder to reach a high shelf.

The Old Way: You try to jump straight to the top shelf. You likely fall and get hurt (the computer crashes from too much data).
The New Way: You climb rung by rung.
- When you are on rung 1, you learn something.
- When you move to rung 2, you remember what you learned on rung 1. You don't have to re-learn the basics.
- If you find a winning path on rung 3, you know you don't need to build the whole map for rung 10 yet. You can skip the parts of the map that are already proven to be safe or impossible.

The "Pruning" Metaphor

Imagine you are a gardener trying to find a path through a massive, overgrown forest (the game graph).

Traditional Method: You try to map the entire forest at once. It takes forever.
This Paper's Method: You start by exploring a small, clear patch of the forest. You find a safe path.
- Then, you expand your view slightly.
- Because you already know the safe path in the small patch, you prune (cut away) the branches of the forest that lead to dead ends or unsafe areas.
- You don't need to draw the whole forest; you only draw the new parts you haven't seen yet, using your old map to guide you.

The "Rational Enemy" Twist

In these games, there is a "System" (the robot) and an "Environment" (the factory, other robots, or a tricky human).

Old Thinking: The environment is a monster trying to trick the robot into crashing. The robot has to be ready for any move the monster makes.
This Paper's Thinking: The environment is also a robot with its own rules. It won't try to break its own rules just to annoy the system.
- Example: If the environment has a rule "I must move every turn," it won't sit still just to trap the robot.
- This "Rationality" gives the system more information, making the map smaller and easier to solve.

The Results

The authors tested this on a computer. They built a "non-optimized" version of their idea (meaning it wasn't perfectly tuned yet, just a proof of concept).

The Result: In almost every test, their "climbing the ladder" method was much faster and used much less memory than the traditional method of trying to solve the whole problem at once.
The Catch: Sometimes, if the rules are very strict, you do need the full map to find the solution. But for many real-world problems (like robot fleets in factories), this shortcut works wonders.

Summary

This paper introduces a smart way to teach computers how to control complex systems. Instead of trying to memorize every possible future scenario at once (which is impossible), the computer learns step-by-step. It starts with simple versions of the rules, learns what works, and uses that knowledge to ignore the impossible parts of the complex rules. It's like learning to ride a bike with training wheels before trying to race in the Tour de France.

1. Problem Statement

The synthesis of reactive systems involves automatically constructing strategies (controllers) that guarantee a system satisfies a specification while interacting with an adversarial environment. While powerful, this process faces a severe state space explosion problem:

Complexity: Translating Linear Temporal Logic (LTL) specifications into deterministic automata for strategy synthesis is doubly exponential in the length of the specification.
Counting Constraints: Many real-world specifications (e.g., "charge the battery at least 2 times in every 10 moves") involve counting patterns. Directly encoding these constraints into the game graph requires tracking the history of moves, leading to an exponential increase in the number of states relative to the constraint window length ( $l$ ).
Limitation of Existing Methods: Current approaches either restrict the logic to simpler fragments (like GR(1)) or use bounded synthesis, but they struggle with general counting constraints that do not fit these fragments.

2. Methodology: Incremental Synthesis with Window Counting Constraints

The authors propose an incremental synthesis approach that exploits the monotonicity property of counting constraints to avoid constructing the full, massive game graph at once.

Core Concepts

Window Counting Constraints: Constraints of the form "Player $p$ plays action $a$ at least $k$ times (or at most $k$ times) out of $l$ of their own turns."
Monotonicity:
- For "At Most" ( $CC_{max}$ ): If a strategy satisfies "at most $k$ in $l$ turns," it inherently satisfies "at most $k$ in $l-1$ turns."
- For "At Least" ( $CC_{min}$ ): If a strategy satisfies "at least $k$ in $l-1$ turns," it inherently satisfies "at least $k$ in $l$ turns."
Strategy: Instead of solving the game with the full constraint length ( $l$ ) immediately, the algorithm starts with shorter window lengths (e.g., $l' < l$ ). It iteratively increases the window length, reusing information from previous iterations to prune the search space.

The Algorithm

Translation: Convert "at most" constraints into equivalent "at least" constraints (using Lemma 3.2) to unify the direction of monotonicity.
Initialization: Start with minimal constraint lengths (e.g., $l' = k$ ).
Situation Graph Construction:
- Instead of a standard game graph, the algorithm constructs a Situation Graph. A "situation" is a tuple $(s, H)$ , where $s$ is a state in the original graph and $H$ is a history vector tracking constraint fulfillment.
- Pruning: During construction, if a situation is an extension of a situation known to be in the winning region of a previous iteration, its successors are not constructed. The situation is immediately marked as winning. This prevents the exponential blowup by skipping the exploration of states that are already known to be solvable.
Winning Region Calculation: A standard synthesis algorithm (e.g., for Safety, Reachability, Büchi games) is run on the partially constructed graph to determine the winning region.
Iteration: The constraint length $l$ is increased (sequentially or round-robin). The winning region from the previous step is used to prune the new, larger graph.
Termination: The process stops when a winning strategy is found for the initial state or when the full constraint length is reached without finding a strategy.

Handling Different Winning Conditions

The paper extends the approach beyond safety games to Reachability, Büchi, co-Büchi, and Parity games.

For Reachability, a specific two-step adaptation is used: first, a safety game is played to ensure constraint satisfaction, and then a reachability game is played on the resulting winning region.

3. Key Contributions

Incremental Synthesis Framework: A novel method to handle counting constraints by iteratively refining constraint parameters rather than encoding them fully upfront.
Situation Graphs: A formal definition of "situations" that encode only the relevant history for counting constraints, allowing for positional strategies on an expanded graph.
Pruning Mechanism: Theoretical proof (Theorem 3.1) and algorithmic implementation showing how winning regions from smaller constraints can be used to prune the state space of larger constraints.
Generalization: Extension of previous work (which focused on safety games) to a broader class of games (Reachability, Büchi, co-Büchi, Parity) and support for mixed constraint types (both "at least" and "at most") within the same procedure.
Rationality Assumption: The framework assumes the environment (ALTER) is rational and will not violate its own constraints, which reduces the search space for the system (EGO).

4. Experimental Results

The authors implemented the approach in Python and tested it on synthetic grid-world games (simulating robot navigation with charging/maintenance constraints).

Performance Gains: In most experiments (6 out of 7), the incremental approach significantly outperformed direct synthesis (solving the full constraint immediately).
- Memory: The number of states in the final situation graph was often orders of magnitude smaller than the full graph. For example, in Experiment 3, the full graph had ~1.7 million states, while the incremental approach only needed to remember ~68k (sequential) or ~8k (round-robin) states from previous winning regions.
- Time: Runtime reductions were substantial (e.g., 316 seconds vs. 11 seconds in Experiment 1).
Limitations: In cases where the winning region remained empty until the very last increment (Experiment 7), the overhead of iteration made the incremental approach slightly slower than direct synthesis. This occurs when the full constraint length is strictly required to find a solution, and no intermediate pruning is possible.

5. Significance and Future Work

Significance: This work provides a heuristic solution to the state space explosion problem for a class of specifications (counting constraints) that are common in robotics and industrial automation but difficult to handle with standard LTL synthesis. It demonstrates that "less is more" by solving easier sub-problems first.
Future Directions:
- Cooperative Games: Moving from zero-sum (adversarial) settings to cooperative settings where the environment also tries to satisfy its constraints.
- Symbolic Synthesis: Transforming the explicit state representation into symbolic representations (e.g., using BDDs or antichains) to handle even larger state spaces.
- On-the-Fly Synthesis: Combining this incremental approach with forward-expansion algorithms.
- Symmetric Synthesis: Applying the method to fleets of identical systems (e.g., multiple robots) that must follow the same strategy.

In conclusion, the paper presents a robust, heuristic-driven framework that leverages the mathematical properties of counting constraints to make reactive synthesis feasible for complex, memory-intensive specifications.