Abstract
Stochastic satisfiability (SSAT) and decision-theoretic planning in finite horizon partially observable Markov decision processes (POMDPs) are both PSPACE-Complete. We describe constructive reductions between SSAT and flat POMDPs that open the door to comparisons and future cross-fertilization between the solution techniques of those problems. We also propose a new SSAT solver called Prime that incorporates recent advances from the SAT and #SAT literature. Using our reduction from POMDP to SSAT, we demonstrate the competitiveness of Prime on finite horizon POMDP problems.
Introduction
In the field of artificial intelligence, planning under uncertainty and Boolean satisfiability have traditionally been treated as distinct domains. Partially Observable Markov Decision Processes (POMDPs) serve as a robust framework for decision-theoretic planning, while Stochastic Satisfiability (SSAT) extends SAT to include probabilistic variables. Despite their different origins, both problems share the same computational complexity: they are PSPACE-Complete. This research establishes a formal bridge between these two frameworks, providing constructive reductions that allow for the cross-application of solution techniques.
Methods and Reductions
The authors propose two primary mathematical recipes to transform problems between these domains:
- SSAT to POMDP: This reduction maps clauses in a SAT formula to states in a flat POMDP. The planning horizon is determined by the number of variables in the formula. This mapping reveals a "state-clause duality" that challenges the intuition that SAT solvers must always operate in an exponentially large state space.
- POMDP to SSAT: This reduction encodes the transition, observation, and reward functions of a POMDP into a Boolean formula. Crucially, this encoding is polynomial in size, avoiding the exponential blow-up typically associated with such translations.
To implement these findings, the authors developed Prime, a state-of-the-art SSAT solver. Prime integrates advanced techniques from the SAT community, including Watch Literals for constant-time satisfaction checking, Component Decomposition for breaking problems into independent sub-problems, and Symmetry Detection to eliminate redundant work.
Empirical Evaluation
The researchers evaluated Prime against standard SAT benchmarks and classic POMDP problems (e.g., tiger, aloha, hallway). These benchmarks were converted into SSAT format to facilitate a head-to-head comparison with native exact solvers like Walraven and Incremental Prune.
Prime demonstrated significant competitiveness, winning on 8 out of 13 POMDP benchmarks. The implementation of an improved "Unit-Rule" (UR) scheme, utilizing watch literals, provided speedups of up to 5.36x on specific problems. Furthermore, symmetry detection techniques like "Component Projection" yielded up to a 10x speedup on planning tasks, suggesting that many POMDPs contain repetitive structures that SSAT solvers are uniquely equipped to exploit.
Conclusion and Future Work
This research demonstrates that translating POMDPs into the language of SAT allows planners to benefit from the explosive progress in high-performance SAT solving. While the SSAT-to-POMDP direction currently faces numerical precision challenges due to floating-point math in traditional planners, the success of the Prime solver highlights the potential of direct policy search in structured state spaces. Future work points toward hybrid solvers that combine the pruning strengths of POMDP algorithms with the decomposition and symmetry-handling capabilities of SSAT solvers.
Summary updated