Unifying the Theory and Algorithms of Factored State-Space Search (UTA)

Automated planning, also known as factored state-space search, is a fundamental problem in AI with numerous applications in computer science and elsewhere. There are three dominant algorithmic paradigms: heuristic search, symbolic search, and SAT planning. While important theoretical results exist to explain and improve the performance of some of these algorithms, almost nothing is known about the connections between them.

We build a unified theory of factored state-space search that identifies a common reasoning core encompassing all three algorithmic paradigms that allows us to directly relate these algorithms to each other in theory and build hybridized algorithms combining their individual strengths in practice. Identifying such a core also allows us to better understand the trade-off involved between representational expressiveness and efficiency of reasoning and design better algorithms to address this trade-off.