P18: Abstract Interpretation for Generalized Heuristic Search in Model-Based Planning

Authors: Tan Zhi-Xuan, Joshua B. Tenenbaum, Vikash Mansinghka

Abstract: Domain-general model-based planners often derive their generality by constructing search heuristics through formal analysis of symbolic world models. One approach to constructing these heuristics is to plan in a relaxed or abstracted model: by computing the cost of a solution in a relaxed model, it can be used as an (optimistic) estimate of the true cost, providing guidance in heuristic search algorithms. Some of the abstractions used by these heuristics are also used in model checking, while others are similar to those used in abstract interpretation of program semantics. However, they have typically been limited to propositional variables, with a few numeric extensions. Here we illustrate how abstract interpretation can serve as a unifying framework for these abstraction-based heuristics, extending the reach of heuristic search to richer world models that make use of more complex datatypes (e.g. sets), functions (e.g. trigonometry), and even models with uncertainty and probabilistic effects.