Planning with SAT: A Hybrid Approach

Automated planning is an AI field concerned with finding sequences of actions to achieve a goal. Classical planning problems are often defined using lifted first-order representations, which offer compactness and generality. However, most planners ground these representations to simplify reasoning, which can lead to an exponential blowup in problem size.

Partially Grounded Encoding

A recent study presents an intermediate approach between fully lifted and fully grounded planning. Three SAT encodings are introduced that keep actions lifted while partially grounding predicates. Unlike previous SAT encodings, which scale quadratically with plan length, this approach scales linearly, enabling better performance on longer plans.

Performance and Scalability

Empirical results show that the best proposed encoding outperforms the state of the art in length-optimal planning on hard-to-ground domains. This suggests that partially grounded encoding can be a promising technique for tackling complex planning problems with high scalability requirements.