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.
Tan Zhi-Xuan (Massachusetts Institute of Technology)
More from the Same Authors
2022 : Contributed Spotlight Talks: Part 1 »
David Dohan · Winnie Xu · Sugandha Sharma · Tan Zhi-Xuan
2020 : Engagement and Solidarity with Global Queer Communities »
Raphael Gontijo Lopes · Bisi Alimi · Faris Gezahegn · Ida Momennejad · Tan Zhi-Xuan