Satplan

Satplan (better known as Planning as Satisfiability) is a method for automated planning. ^{[1] [2]} It converts the planning problem instance into an instance of the Boolean satisfiability problem (SAT), which is then solved using a method for establishing satisfiability such as the DPLL algorithm or WalkSAT.

The process encodes key elements of the planning problem—initial state, available actions, goal state, and a maximum plan length (horizon length)—into a logical formula. This formula is satisfiable if and only if a valid sequence of actions exists that transforms the initial state into the goal state within the given horizon. This concept is similar to Cook's theorem, where Turing machine computations are represented as SAT formulas. ^[3]

To find a plan, Satplan iteratively tests formulas with increasing horizon lengths. It starts with a horizon length of 0 (no actions) and incrementally increases it (1, 2, 3, etc.). For each horizon, a corresponding SAT formula is generated and checked by a SAT solver. If satisfiable, the solver’s output reveals the action sequence. If unsatisfiable, the process continues until a valid plan is found. While this simple approach can be inefficient, more advanced search strategies can improve performance, but the fundamental idea remains the same: reducing planning to satisfiability. ^[4]

See also

• Graphplan

References

1. Jeevanandam, Nivash (2023-11-16). "Understanding planning using logic in AI". IndiaAI. Retrieved 2025-02-19.
2. Kautz, Henry; Selman, Bart (August 1992). "Planning as Satisfiability". CiteSeerX . ECAI'92. Archived from the original on 2019-01-25.
3. Robinson, Nathan; Gretton, Charles (2009-10-16). "SAT-Based Parallel Planning Using a Split Representation of Actions". Proceedings of the International Conference on Automated Planning and Scheduling. 19: 281–288. doi:10.1609/icaps.v19i1.13368. ISSN   2334-0843.
4. "Planning as Satisfiability: state of the art". users.aalto.fi. Retrieved 2025-02-19.

• H. A. Kautz and B. Selman (1992). Planning as satisfiability. In Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI'92), pages 359–363.
• H. A. Kautz and B. Selman (1996). Pushing the envelope: planning, propositional logic, and stochastic search. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI'96), pages 1194–1201.
• J. Rintanen (2009). Planning and SAT. In A. Biere, H. van Maaren, M. Heule and Toby Walsh, Eds., Handbook of Satisfiability, pages 483–504, IOS Press. ISBN   978-1-58603-929-5.