Automatically Generating Abstractions for Planning
Craig Knoblock, AIJ 1994
This paper highlights a heuristic property called ordered monotonicity property of hierarchical domains and provides a way to learn the hierarchy using the sufficient condition for that property.
A problem space is defined as , consisting of is set of first-order literals, is the set of finite states (described using literals), and is the set of operators in the domain. The authors propose to assign a , 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 can only access literals with level or higher.
An ordered monotonicity property says:
- For any abstract plan at level with operators , the order of operator will remain same for plan at level .
- Any addition of an operator at level is allowed only if that operator achieves some precondition for some other operator which existed at level , and .
- If any operator at changes a literal with level , then that operator should exist at level .
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.
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.