SATPlan¶

An automated-planning method that encodes the existence of a bounded-length action sequence as a Boolean satisfiability formula, calls a SAT solver, and decodes any satisfying assignment into a valid plan.

Version: v1 · 2026-09-28 · History
Domain-specific #: 11880
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Automated Planning, Artificial Intelligence, Boolean Satisfiability → Computer Science & Software Engineering
Aliases: Planning as Satisfiability, SAT-Based Planning, Satplan

Core Idea¶

SATPlan treats a plan as a satisfying assignment to time-indexed facts and actions. Logic clauses make illegal transitions impossible, so a SAT solver becomes the search engine for bounded planning.

Correctness resides in the translation. Horizon, frame axioms, concurrency, mutex conditions, and decoder must preserve the original planning semantics; an impressive solver result cannot compensate for missing constraints.

Structural Signature¶

Sig role-phrases:

Planning domain and instance — Supply state propositions, actions, initial condition, and goal. It is source problem. Counterfactual: An incomplete transition model yields invalid plans.
Horizon — Bounds the number of sequential or parallel time steps. It is search parameter. Counterfactual: Unsatisfiable at one horizon does not imply no longer plan.
Propositional variables — Represent facts and action occurrences at indexed times. It is encoding vocabulary. Counterfactual: Variable meaning must survive decoding.
Transition and frame clauses — Enforce preconditions, effects, persistence, and action compatibility. It is semantic constraint. Counterfactual: Missing frame axioms permit magical state changes.
SAT solver — Decides the generated formula and returns a model if one exists. It is decision engine. Counterfactual: Solver correctness does not repair an incorrect encoding.
Plan decoder and validator — Turns true action variables into an ordered plan and checks it against domain semantics. It is output guard. Counterfactual: A raw assignment is not yet an executable plan.

What It Is Not¶

Any use of a SAT solver is not planning as satisfiability.
Unsatisfiable at horizon h does not rule out longer plans.
A satisfying assignment is not a plan until decoded and validated.
Parallel and sequential horizon semantics should not be mixed.
Closest near-miss. Graphplan builds a planning graph and extracts plans through graph constraints; it influenced SAT encodings but is not identical to submitting a propositional formula to a SAT solver.

Scope of Application¶

Classical planning. Finds bounded action sequences.
Plan optimality. Increases horizon to seek shortest makespan under conditions.
Verification research. Relates transition systems and bounded logical encodings.
Solver engineering. Uses incremental SAT, learned clauses, and domain invariants.

Clarity¶

Report planning formalism, state variables, action semantics, horizon meaning, sequential or parallel plan convention, frame and mutex encoding, goal clauses, SAT solver and settings, incremental reuse, decode rule, validation, and optimality claim.

Manages Complexity¶

The method replaces combinatorial action search with combinatorial Boolean inference. Its power comes from exposing planning structure to mature SAT propagation and learning while keeping the translation auditable.

Abstract Reasoning¶

Normalize the planning instance into explicit states, actions, initial facts, and goals.
Choose horizon and sequential or parallel semantics.
Encode initial, transition, frame, compatibility, and goal constraints.
Solve incrementally or independently under documented SAT settings.
Decode and simulate the candidate plan; increase horizon when unsatisfiable and the search policy requires it.

Knowledge Transfer¶

Bounded transition encoding transfers to scheduling and verification, but SATPlan identity requires actions and goals under planning semantics. Domain-specific concurrency and costs need new clauses rather than analogy.

Examples¶

Canonical¶

For a finite STRIPS task, variables encode each fluent and action at times zero through h; clauses assert the initial state, legal transitions, persistence, mutexes, and goal, and a SAT model decodes to a validated plan.

Mapped back: source → STRIPS instance; bound → h; formula → state/action clauses; solver → SAT; output → validated plan.

Applied / In Practice¶

A SAT solver choosing a static assignment to resources is constraint solving, not SATPlan when there is no action sequence, transition semantics, or planning horizon.

Mapped back: variables → resource choices; time transitions → absent; plan → absent; verdict → not SATPlan.

Structural Tensions¶

T1 — Strong Encoding versus Formula Size. Additional invariants and mutex clauses can accelerate propagation while increasing generation and memory cost.

Diagnostic: Which constraints improve total solve time for this domain?

T2 — Incremental Horizons versus Repeated Work. Shortest-plan search gains certainty by increasing h while naive regeneration discards learned structure.

Diagnostic: Can clauses and solver state be reused soundly?

Structural–Framed Character¶

SATPlan is structural as bounded plan existence encoded into SAT and framed by a planning formalism.

Structural Core vs. Domain Accent¶

The general pattern is reducing a structured search to satisfiability. Planning contributes actions, frames, goals, horizons, mutexes, and plan validation.

This entry is a kind of Planning.

Approved planning-method root. No current parent entails the planning-instance-to-SAT-to-plan pipeline.
Related — Graphplan, bounded model checking, DPLL, STRIPS, and incremental SAT. They are an influence, neighboring reduction, solver family, source formalism, and optimization.

Relationships to Other Abstractions¶

Current abstraction SATPlan Domain-specific

Parents (1) — more general patterns this builds on

SATPlan is a kind of Planning Prime

SATPlan is a strict kind of Planning: its frozen identity entails the parent's defining structure while adding domain-specific restrictions.

Hierarchy path (1) — routes to 1 parentless root

SATPlan → Planning → Foresight

Neighborhood in Abstraction Space¶

SATPlan sits in a crowded region of the domain-specific corpus (31^st percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Decision & System Modeling Frameworks (30 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Graphplan. Tell: Searches and extracts through a planning graph.
Bounded model checking. Tell: Searches for counterexample paths to a property.
SAT solving. Tell: Is the generic decision engine, not the planning reduction.
Constraint programming. Tell: Can solve plans through other constraint domains.

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Satplan (revision 1369043480).
Preserved source candidate: https://users.aalto.fi/~rintanj1/satplan.html
Preserved source candidate: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.9443&rep=rep1&type=pdf
Preserved source candidate: https://www.researchgate.net/profile/Bart_Selman/publication/2471954_Pushing_the_Envelope_Planning_Propositional_Logic_and_Stochastic_Search/links/549673960cf29b9448241893/Pushing-the-Envelope-Planning-Propositional-Logic-and-Stochastic-Search.pdf
Preserved source candidate: https://books.google.com/books?id=YVSM3sxhBhcC&q=%22planning+and+SAT%22

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.