Abstract
GSAT is a randomized local search procedure for solving propositional satisfiability problems. GSAT can solve hard, randomly generated problems that are an order of magnitude larger than those that can be handled by more traditional approaches such as the Davis-Putnam procedure. GSAT also efficiently solves encodings of graph coloring problems, N-queens, and Boolean induction. However, GSAT does not perform as well on handcrafted encodings of blocks-world planning problems and formulas with a high degree of asymmetry. We present three strategies that dramatically improve GSAT's performance on such formulas. These strategies, in effect, manage to uncover hidden structure in the formula under considerations, thereby significantly extending the applicability of the GSAT algorithm.
Introduction
In the early 1990s, the GSAT algorithm revolutionized Boolean Satisfiability (SAT) solving. By employing a randomized greedy local search instead of systematic backtracking, it could solve random formulas significantly larger than traditional methods like the Davis-Putnam (DP) procedure. However, a significant limitation emerged: while GSAT excelled at random formulas, it struggled with "structured," handcrafted problems common in planning and circuit design.
Structured problems often contain "gerrymandered" constraints where a large group of variables can "out-vote" a critical single constraint. This leads greedy search into deep local minima where it remains trapped, unable to find the global solution. This paper introduces three domain-independent strategies to help GSAT escape these traps and uncover the underlying structure of complex formulas.
Methods: Strategies for Escaping Local Minima
The authors propose three distinct enhancements to the basic GSAT procedure to prevent it from getting stuck in local minima:
Strategy I: Clause Weights
In this strategy, every clause is initially assigned a weight of 1. At the conclusion of a failed search try, the algorithm increments the weight of any clause that remains unsatisfied. In subsequent tries, the cost of violating these clauses increases. This effectively "fills in" local minima, forcing the search into unexplored regions of the state space.
Strategy II: Averaging in Previous Near Solutions
Rather than restarting each search try from a completely random assignment, the algorithm begins at the "bitwise average" of the previous starting point and the best assignment found so far. Inspired by genetic algorithms, this approach helps the search stay within promising regions of the state space.
Strategy III: Random Walk
With a fixed probability $p$ (typically 0.35), the algorithm ignores the greedy move. Instead, it selects a variable at random from a currently unsatisfied clause and flips it. This targeted noise is more effective than the global noise used in simulated annealing because it focuses specifically on the "problem spots" within the formula.
Evaluation and Results
The strategies were evaluated on several challenging benchmarks, including asymmetrical graph coloring, large graph instances, Boolean induction, and blocks-world planning tasks.
The results demonstrated dramatic improvements over basic GSAT:
- Asymmetric Coloring: While basic GSAT failed to find solutions, the weighting strategy solved these problems in an average of 1.3 seconds.
- Boolean Induction: The random walk strategy reduced search time on specific instances (e.g., "16A1") from 1650 seconds to just 19 seconds.
- Planning: Combining all three strategies enabled GSAT to solve "Towers of Hanoi" and other planning formulas previously considered inaccessible to local search, achieving performance competitive with highly optimized backtracking procedures.
Discussion and Future Work
These extensions are domain-independent; they do not require prior knowledge of the problem type (e.g., planning vs. coloring). Instead, they discover the underlying structure through search dynamics. While these improvements are significant, the authors note that highly optimized systematic backtrackers can still outperform GSAT on certain planning tasks. Future work should explore more robust logical representations for planning that are better suited for local search techniques, rather than relying solely on classic McCarthy and Hayes encodings.
Summary updated