# Cost Optimal Planning as Satisfiability

arXiv: https://arxiv.org/abs/2103.02355 · HTML: https://mlsanity.com/paper/2103.02355/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 31 references that are in the map.
- First posted on arXiv 3 Mar 2021.

## Builds on (most cited first, 1 of 1)

- [Computing Plan-Length Bounds Using Lengths of Longest Paths](https://mlsanity.com/paper/2006.01011/) (2020)

## Abstract (arXiv)

We investigate upper bounds on the length of cost optimal plans that are valid for problems with 0-cost actions. We employ these upper bounds as horizons for a SAT-based encoding of planning with costs. Given an initial upper bound on the cost of the optimal plan, we experimentally show that this SAT-based approach is able to compute plans with better costs, and in many cases it can match the optimal cost. Also, in multiple instances, the approach is successful in proving that a certain cost is the optimal plan cost.