TL;DR
This paper introduces a novel algorithm for refining assumptions in reactive synthesis for GR(1) specifications. By focusing on finding minimal sets of assumptions, their approach leads to shorter, less restrictive specifications and explores the search space more efficiently, often discovering solutions missed by prior methods.
What Problem Does This Paper Address?
Reactive synthesis aims to automatically generate correct controllers from formal specifications. These specifications often take an "assume-guarantee" form, where assumptions describe the environment's behavior, and guarantees describe what the controller must achieve. When a specification is "unrealizable" (meaning no controller can satisfy the guarantees under the given assumptions), assumption refinement techniques try to strengthen the assumptions to make it realizable.
The challenge is that existing assumption refinement methods, particularly those using counterstrategies (examples of environment behavior that lead to guarantee violations), can produce overly restrictive assumptions or explore very long chains of assumptions. This increases computational overhead and can make the resulting specifications harder for humans to understand. The paper tackles the problem of finding minimal sets of assumptions that are sufficient for realizability, aiming to reduce redundancy and improve the efficiency of the refinement process.
Methods
The core contribution is the MINIMALREFINEMENT algorithm. This algorithm takes an existing, insufficient set of assumptions and a new assumption (generated to eliminate a specific counterstrategy) and produces a minimal refinement. Minimality here means that no assumption in the refined set is redundant with respect to the observed counterstrategies.
The algorithm works by:
- Identifying Redundancy: It formalizes the notion of a redundant assumption based on which counterstrategies are eliminated. An assumption is redundant if all the counterstrategies it eliminates are also eliminated by at least one other assumption in the set.
- Constructing a Bipartite Graph: It models the relationships between assumptions and the counterstrategies they eliminate as a bipartite graph.
- Removing Redundant Assumptions: It then systematically removes assumptions from the current refinement if all the counterstrategies they are connected to have a "degree" of 2 or more (meaning multiple assumptions eliminate them).
The paper also proposes a hybrid refinement generation method. This approach combines the MINIMALREFINEMENT algorithm with a standard Breadth-First Search (BFS) strategy. This hybrid approach aims to balance the benefits of exploring minimal refinements with the need to explore longer, potentially non-minimal, refinements that might be necessary to find certain solutions.
Datasets
The paper evaluates its approach on a benchmark of six case studies:
- Three versions of the AMBA-AHB protocol specification (with 2, 4, and 8 masters).
- Three JVTS (Justice Violation Transition Systems) case studies: ColorSort, GyroAspect, and Humanoid.
These are existing benchmarks used in prior work on assumption refinement.
Key Insights and Ideas
- Redundancy is Key: The paper's central insight is that assumptions can be redundant not just in terms of logical equivalence, but in terms of their effectiveness against a set of counterstrategies. An assumption might be logically distinct but functionally unnecessary if other assumptions cover its role.
- Minimality Improves Efficiency: By actively removing redundant assumptions, the MINIMALREFINEMENT algorithm prunes the search space. This leads to exploring fewer, but more informative, candidate refinements.
- Shorter Solutions are Better: Minimal refinements are inherently less constraining, which can lead to more understandable specifications and potentially controllers that are more robust or easier to synthesize.
- Hybrid Approach Balances Exploration: The hybrid strategy is crucial because a purely minimal refinement approach might miss solutions that require longer, non-minimal intermediate steps. Combining minimal refinement with BFS ensures a more comprehensive search.
Key Results
- More Efficient Exploration: The MINIMALREFINEMENT algorithm, when integrated into counterstrategy-guided approaches, explores a significantly higher number of shorter refinements compared to a standard BFS approach. For example, in the AMBA02 case study, MINIMALREFINEMENT explored 463 refinements compared to BFS's 279.
- Shorter Final Solutions: The final solutions found by the minimal refinement approach are typically shorter (fewer assumptions) than those found by BFS. For instance, the average length of solutions for AMBA02 was 1-3 assumptions for MINIMALREFINEMENT, compared to 1-5 for BFS.
- Discovery of New Solutions: The approach can find solutions that were not discovered by BFS within the same time limit. This is attributed to the more focused exploration of shorter refinements.
- Hybrid Approach Increases Coverage: The hybrid approach significantly increases the number of explored refinements and the number of solutions found, often covering more of the solutions found by a pure BFS approach. For AMBA08, the hybrid approach found solutions that covered all 10 BFS solutions.
Limitations and Future Work
- Time Complexity: While the MINIMALREFINEMENT algorithm is designed to have a low overhead, it does introduce additional computation for each refinement explored. The paper analyzes this complexity, noting that it's often dominated by the counterstrategy computation itself, especially when the number of states in counterstrategies is small.
- Potential for Missing Solutions (Pure Minimal): The paper acknowledges that a purely minimal refinement strategy might miss certain solutions that can only be found through longer, non-minimal intermediate steps. This is precisely why the hybrid approach is proposed.
- Future Work: The authors suggest exploring the effect of minimization on more recent refinement approaches, such as those using Justice Violation Transition Systems (JVTSes), and combining minimization with weakness heuristics. They also mention the need to investigate the impact of minimization on more recent refinement approaches.
Summary updated