Abstract Interpretation for
Generalized Heuristic Search in Model-Based Planning

Assignment can be assumed to follow the standard semantics for imperative languages. Predicates and functions used in planning domains typically include testing if a Boolean variable is false or true, along with arithmetic operations (Fox & Long, 2003), but can be defined for new datatypes as necessary (Gregory et al., 2012). Since assignments in the effect $\texttt{eff}(a)$ of an action $a$ must be non-conflicting, $\texttt{eff}(a)$ corresponds to parallel execution of each assignment. We can hence specify a denotational semantics for $a$ by identifying it with a relation over states $(S,T)\in a$, where $\texttt{pre}(a)\models S$, and $T$ is the result of applying $\texttt{eff}(a)$ to $S$. This is equivalent to the semantics for atomic actions in concurrent programs by Lamport (1990). Alternatively, actions can be seen as (guarded) primitive commands in a domain specific imperative language, with semantics defined by condition-checking and assignment as sub-primitives. Two example actions are shown in Figure 1.

Common approaches to solving symbolic planning problems include backward search from the goal $G$, or forward best-first search from the initial state $I$ (Bonet & Geffner, 2001), with the fastest planners typically relying on variants of forward A* search guided by highly informative heuristics (Helmert, 2006), along with compilation techniques for speed and memory efficiency (Helmert, 2009; Zhi-Xuan, 2022). Heuristic-guided search can also be extended to probabilistic and partially observable domains, using algorithms such as Real Time Dynamic Programming (RTDP) (Bonet & Geffner, 2003) and Trial-based Heuristic Tree Search (THTS) (Keller & Helmert, 2013).

Cartesian Abstraction. One approach to abstracting states is to assign an abstract value to each variable $v\in V$, representing a set of concrete values $v$ could take. For example, the numeric variable fuel1 in Figure 1 could be assigned the interval value $[0,1000)$. Doing this for each variable produces a Cartesian abstraction: Given the values in an abstract state $\mathcal{S}^{\sharp}$, the corresponding set of concrete states $\gamma(\mathcal{S}^{\sharp})$ is just the Cartesian product of sets associated with each abstract value (Ball et al., 2001).

Predicate Abstraction. Another approach is to consider the set of all predicates $\mathcal{P}$ that feature in action preconditions $\texttt{pre}(a)$ for all $a\in A$, or the goal specification $G$. We define abstract states to be sets of these predicates $\mathcal{S}^{\sharp}\subseteq\mathcal{P}$, corresponding to the set of concrete states where every predicate in the abstract state holds true. The advantage of this abstraction is that it can be easily used to determine if an action is executable, of if the goal is achieved.

State-Induced. Given abstraction and concretization functions $\alpha$ and $\gamma$, this induces a corresponding abstract action $a^{\sharp}$ for each action $a$: Given an abstract state $\mathcal{S}^{\sharp}$, we have $(\mathcal{S}^{\sharp},\mathcal{T}^{\sharp})\in a^{\sharp}$ where $\mathcal{T}^{\sharp}:=\alpha(\{T\ |\ S\in\gamma(\mathcal{S}^{\sharp}),(S,T)\in a\})$. This can be efficiently implemented for Cartesian abstractions when the right-hand-side of all assignments in an action is constant, since the result of applying such an action is a specific concrete state which can then be abstracted.

Widening-Based. Given a Cartesian state abstraction, a more relaxed abstraction is to replace each assignment $v:=E$ in a concrete action $a$ with $v:=v\triangledown E$, where $E$ is an expression and $\triangledown$ is a choice of widening operator associated with the value abstraction for variable $v$ (Gregory et al., 2012). In the case where $v$ is Boolean or has a finite domain, a natural abstraction for $v$ is to replace the domain of $v$ with its powerset (e.g., allowing a Boolean $v$ to be true and false at the same time), using the join operator $\sqcup$ as a widening. Other choices are necessary when $v$ is numeric and unbounded, e.g. delayed widening (Miné, 2017).

Widening-based abstract actions can be directly applied to Cartesian state abstractions, since they modify each state variable independently. They can also be extended to combined Cartesian and predicate abstractions, where each abstract state $\mathcal{S}^{\sharp}=(X^{\sharp},P)$ comprises both abstract assignments $X^{\sharp}$ and predicates $P$. The successor of applying some action $a^{\sharp}$ is then $(\triangledown_{a}X^{\sharp},Q)$, where $\triangledown_{a}X^{\sharp}$ is the widened set of assignments, and $Q$ is the largest set of predicates in $\mathcal{P}$ which hold true for at least some concrete $s\in\gamma(\triangledown_{a}X^{\sharp})$. Note that $P\subseteq Q$ by construction (widening can only cause more predicates to be true), and $Q$ can be computed efficiently from $P$ and $\texttt{eff}(a^{\sharp})$ by checking and adding only the predicates in $\mathcal{P}$ that are affected by $\texttt{eff}(a^{\sharp})$.

As shown in Figure 2, determining the reachability of a goal condition in symbolic planning can be viewed as analogous to determining the reachability of an error in program verification. This analysis can be performed by imagining a non-deterministic search procedure that repeatedly applies all executable actions at once, then over-approximating that search process by merging the results of all actions. As noted by Gregory et al. (2012), this is equivalent to repeatedly applying widened versions of the actions until a goal condition or fixpoint is reached (though they do not describe it in terms of abstract interpretation). The number of iterations required serves as a lower bound on the true number of steps to the goal, and hence an optimistic heuristic estimate that can guide search. Indeed, when all variables are propositional, this is equivalent to the $h_{\text{max}}$ delete relaxation heuristic introduced by Bonet & Geffner (2001).

One issues with this analysis is that it may not terminate if variables have infinite domains and the widening operator $\triangledown$ is not appropriately chosen. To address this, Gregory et al. (2012) employ an equivalent of delayed widening. However, many other widening strategies have been used in abstract interpretation, such as widening with thresholds (Miné, 2017), that could lead to improved trade-offs between informativeness and convergence time when computing the heuristic.

An alternative formulation of the widening-based reachability analysis is to consider planning over predicate sets using the predicate abstraction described earlier. More specifically, consider the (abstract) state space graph induced by the combined Cartesian and predicate abstraction, with states $\mathcal{S}^{\sharp}=(X^{\sharp},P)$. Following Haslum & Geffner (2000), finding the shortest path to a goal-satisfying state in the original problem is equivalent to finding the shortest path to an abstract state $(X^{\sharp},P)$ where $P=G$ (we assume w.l.o.g. that the goal $G$ is a conjunction of predicates).

Now we perform several relaxations on this state space graph. First, we add edges corresponding to the widened actions described earlier, such that $(X^{\sharp},P)$ connects to $(\triangledown_{a}X^{\sharp},Q)$ for a widened action $a^{\sharp}$. Next, for every node $(X^{\sharp},P)$ that has $(\triangledown_{a}X^{\sharp},Q)$ as a successor, we add an edge from $(X^{\sharp},P)$ to each node $(\cdot,R)$ where $Q\to R$. Finally, for each node $(X^{\sharp},Q)$, we add a zero-cost edge from every single-predicate node $(\cdot,R)$ s.t. $R\subseteq Q$ and $|R|=1$. These relaxations achieve the following facts:

• •

  The cost of the shortest path in the relaxed graph $C$ is now less than the cost of the shortest path in the original problem $C^{*}$.

• •

  By the second relaxation, we can reach every single-predicate node $(\cdot,R)$, $|R|=1$ with less than or equal cost to reaching a multi-predicate node.

• •

  By the third relaxation, we can compute the cost of reaching any multi-predicate node $C(\cdot,Q)$ as the max over costs of achieving each predicate in that node:

  $$C(\cdot,Q)=\max_{R\subseteq Q,|R|=1}C(\cdot,R)$$

When all variables $V$ are propositional, and the right hand sides of all assignments are constant, this again recovers the $h_{\text{max}}$ heuristic, reformulated as the the $h^{1}$ heuristic in Haslum & Geffner (2000). However, by incorporating the widening-based abstraction from earlier, this generalizes the heuristic to numeric variables, or any other datatype with an effective abstraction (e.g. approximating geometric sets with zonotopes (Bogomolov et al., 2019)). Furthermore, this derivation allows for a number of simple modifications, such as computing the cost of achieving a multi-predicate node as the sum instead of the maximum over the costs of each individual predicate. This gives a generalized version of the widely used additive heuristic $h_{\text{add}}$, subsuming existing work on numeric subgoaling heuristics (Scala et al., 2020). While the result heuristic is non-admissible, it is generally much more informative and useful for search.

A final class of abstraction heuristics enabled by abstract interpretation is counter-example guided abstraction refinement (CEGAR) (Seipp & Helmert, 2018). Starting with a coarse-grained Cartesian abstraction, one can solve for abstract plans to estimate the distance to the goal, and then iteratively refine the abstraction when counterexamples to the correctness of the abstraction are found. Each time after refinement, heuristic values obtained from the previous iteration can be used to guide search in the current iteration, leading to a rapid iterative approach that automatically constructs useful abstractions for planning.

However, CEGAR heuristics have so far been limited to problems with propositional variables, and CEGAR-like algorithms have only recently been explored in symbolic-geometric contexts for task and motion planning (Thomason & Kress-Gazit, 2021). By leveraging abstract semantics introduced for other datatypes in program analysis, it may be possible to extend the reach of such heuristics to a broader array of problems and domains.

As noted earlier, heuristics can be used within algorithms such as Real Time Dynamic Programming (RTDP) (Bonet & Geffner, 2003) and Trial-based Heuristic Tree Search (THTS) (Keller & Helmert, 2013) that operate over stochastic domains, using them to initialize an estimate of the value function for the underlying Markov Decision Process. To derive these heuristics from formal analysis of domains with probabilistic effects, the simplest abstraction would be to assume that all branches of a (discrete) probabilistic choice occur at once. This would effectively relax the problem, enabling the computation of admissible heuristics that guarantee eventual convergence to the true value function (Barto et al., 1995). For continuous probability distributions with bounded support, it would also be possible to abstract distributions with their upper and lower bounds.

Using abstraction heuristics to initialize value functions is closely related to the idea of using heuristics as a learning target for neural network estimators of expected value (Shen et al., 2020; Gehring et al., 2021). This would allow agents to jumpstart planning in novel world models via abstraction-derived information that is later refined by experience.

Abstract interpretation can be executed in reverse (Hughes, 1987; Monniaux, 2001), allowing for generalizations of backward search and heuristic construction to domains with non-propositional variables. This might allow for novel combinations of (abstract) backwards search with (concrete) forward search, as has been explored in robotics (Garrett et al., 2018) and program analysis (Dinges & Agha, 2014).

Generalized plans, or policies, often take the form of imperative programs with control flow (Andre & Russell, 2002; Jiménez et al., 2019; Segovia-Aguas et al., 2021). This suggests that abstraction-guided program synthesis methods (Solar-Lezama, 2008; Srivastava et al., 2010; Wang et al., 2017) can also be used for generalized planning.

This extended abstract presents only an initial foray into the manifold connections between abstract interpretation (AI) and artificially intelligent (AI) planning. We hope that illustrating some of these connections lays the ground for future interdisciplinary work.