Introduction
In the design of autonomous systems, formal specifications are used to define the desired behavior of a controller. However, real-world requirements are frequently contradictory or overly ambitious, leading to "unrealizable" specifications where no possible controller can satisfy all constraints simultaneously. Traditionally, this forces designers into a tedious manual refinement loop. This paper introduces a framework for maximum realizability, which automates this process by synthesizing controllers that strictly satisfy "hard" requirements while minimizing the violation of "soft" preferences.
The Problem of Unrealizability
Reactive synthesis aims to automatically generate a controller (e.g., robot logic) from Linear Temporal Logic (LTL) properties. In a standard binary model, if a single conflict exists—such as a robot being commanded to both "never enter the office" and "always pick up mail from the office"—the specification is declared unrealizable. The authors propose a shift from binary satisfaction to a quantitative approach, allowing designers to prioritize requirements and find the "best possible" implementation.
Methodology: Bounded Synthesis and MaxSAT
The proposed framework combines Bounded Synthesis with Maximum Satisfiability (MaxSAT) through several key technical components:
- Quantitative Semantics: The authors define a value function for safety properties. Instead of a simple true/false, they quantify satisfaction levels: Is the property satisfied always, eventually always, infinitely often, or only for a finite duration?
- Lexicographic Ordering: These levels are organized into a priority-based system. For instance, satisfying a property "always" is weighted more heavily than satisfying it "infinitely often."
- Partial Weighted MaxSAT Encoding: Bounded synthesis searches for a controller of a fixed size $b$ by encoding the problem into a SAT instance. This framework extends that to MaxSAT:
- Hard Clauses: These encode the system's transition logic and mandatory LTL specifications.
- Soft Clauses: These represent the various relaxation levels of the soft specifications, weighted to ensure the solver prefers higher levels of satisfaction.
- Iterative Search: The algorithm starts with a small controller bound and iteratively increases it until a strategy is found that meets the satisfaction threshold or resource limits are reached.
Case Studies and Evaluation
The approach was evaluated using two complex case studies:
- Robotic Museum Guide: A robot must navigate a museum in a specific order (hard) while attempting to avoid staff, stay out of the library, and avoid occupied passages (soft).
- Power Distribution Network: A grid must ensure critical loads are powered (hard) while attempting to power non-critical loads and minimizing relay switching frequency (soft).
Key Insights and Results
- Automata-Based Relaxation: A central contribution is the realization that LTL satisfaction levels can be mapped to specific states and transitions in a universal co-Büchi automaton. By tracking "rejecting" states, the framework can mathematically quantify the degree of violation.
- Feasibility: The tool successfully synthesized "least-violating" controllers for both scenarios. In the robotic navigation task, it identified a valid strategy with a controller size of 8 states in approximately 16 minutes.
- Scalability Bottlenecks: The experiments revealed that the number of soft specifications is the primary bottleneck. As the count of soft requirements increases, the number of variables in the MaxSAT instance grows significantly, eventually leading to solver timeouts (e.g., instances with 23 soft specs timed out at a bound of 6).
Limitations and Future Directions
While the framework provides a solid theoretical foundation for "bounded optimality," it currently struggles with very large state spaces or high numbers of concurrent soft requirements. Furthermore, while the theory generalizes to all LTL formulas, the current detailed encoding and experimental results focus primarily on safety properties. Future work aims to integrate this framework with "learning from demonstrations" and develop specialized MaxSAT search heuristics tailored for synthesis structures.
Summary updated