Automatically Generating Abstractions for Planning

An effective hierarchical decomposition of a problem would solve a task at lower level without violating the conditions in more abstract/higher levels of the hierarchy. Knoblock (1994) formalizises this intuition as ordered monotonicity property. This post briefly explains that property and describes how to learn the hierarchy using the sufficient condition for that property.

A problem space is defined as $\Sigma = \langle L, S, O \rangle$, consisting of $L$ is set of first-order literals, $S$ is the set of finite states (described using literals), and $O$ is the set of operators in the domain. The authors propose to assign a $Level(l), \forall l \in L$, which indicates the hierarchy-level of the literal. Level 0 is the complete ground state and the i > 0 is an abstraction. Any plan at abstraction level $i$ can only access literals with level $i$ or higher.

An ordered monotonicity property says:

  • For any abstract plan $\Pi^i$ at level $i$ with operators $\alpha$, the order of operator will remain same for plan at level $i-1$. $$\forall \alpha, \alpha^{\prime} \in \Pi^{i}, \alpha \preceq \alpha^{\prime} \implies \forall c(\alpha), c(\alpha^{\prime}) \in \Pi^{i-1} c(\alpha) \preceq c(\alpha^{\prime})$$
  • Any addition of an operator at level $i-1$ is allowed only if that operator achieves some precondition $p$ for some other operator which existed at level $i$, and $Level(p)=i-1$. $$\exists \beta \in \Pi^{i-1}, \beta \neq c(x) , \forall x \in \Pi^{i} \implies \exists \alpha \in \Pi^{i}, \exists p \in P_{\alpha}, p \in E_{\beta}, Level(p)=i-1$$
  • If any operator at $i-1$ changes a literal with level $i$, then that operator should exist at level $i$. $$\exists \beta \in \Pi^{i-1}, p \in e_{\beta}, Level(p) \geq i \implies \exists x \in \Pi^{i}, \beta = c(x) $$

This heuristic property of hierarchy is motivated from the below observation.

An effective partitioning of a problem requires that the subproblems can be solved without violating the conditions that were already achieved in the more abstract levels of the abstraction hierarchy. In other words, a hierarchical planner ideally finds a solution at one level and then maintains the structure of that solution while the remaining parts of a solution are filled in.

Authors note that following are some sufficient condition for the ordered monotonicity property:

  • All the relevant effects (that are required for goal or for some preconditions) have equal or higher level than other effects.
  • All the relevant effects have equal or higher level than the preconditions.

$$ \begin{aligned} \forall \alpha \in O, \forall e, e^{\prime} \in E_{\alpha}, \forall p \in P_{\alpha}, e \in Relevant \implies Level(e) \geq Level(e^{\prime}) \\ \wedge \ Level(e) \geq Level(p) \\ \end{aligned} $$

Although these conditions are not necessary, they are sufficient to ensure the ordered monotonicity property. Hence given the problem and description of the domain, the literals can be organized in an topological order. This order is an abstraction hierarchy.