next up previous
Next: Building Abstract Components Up: Component Abstraction Previous: Component Abstraction

Building the Static Graph of a Problem

A static graph models static relationships between constant symbols of a problem. Nodes are constant symbols, and edges correspond to static facts in the problem definition. Following standard terminology, a fact is an instantiation of a domain predicate, i.e., a predicate whose parameters have all been instantiated with constant symbols. A fact $f$ is static for a problem $p$ if $f$ is part of the initial state of $p$ and no operator can delete it.

Each constant that is an argument of at least one static fact defines a node in the static graph. All constants in a fact are linked pairwise. All edges in the graph are labeled with the name of the corresponding predicate.

Figure 3: Static graph of a Rovers problem.
\includegraphics[width=.8\linewidth]{rovers2.eps}

We use a Rovers problem as an example of how component abstraction works. In this domain, rovers can be equipped with cameras and stores where rock and soil samples can be collected and analyzed. Rovers have to gather pictures and data about rock and soil samples, and report them to their base. For more information about the Rovers domain, see the work of Long and Fox [19]. Figure 3 shows the static graph of the sample problem. The nodes include two stores (STORE0 and STORE1), two rovers (ROVER0 and ROVER1), two photo cameras (CAM0 and CAM1), two objectives (OBJ0 and OBJ1), two camera modes (COLOUR and HIGH-RES), and four waypoints (POINT0,... POINT3). The edges correspond to the static predicates (STORE-OF ?S - STORE ?R - ROVER), (ON-BOARD ?C - CAMERA ?R - ROVER), (SUPPORTS ?C - CAMERA ?M - MODE), (CALIBRATION-TARGET ?C - CAMERA ?O - OBJECTIVE), and (VISIBLE-FROM ?O - OBJECTIVE ?W - WAYPOINT).

The two marked clusters in the left are examples of abstract components generated by this method. Each component is a rover equipped with a camera and a store. A more detailed and formal explanation is provided in the following paragraphs.

To identify static facts necessary to build the static graph, the set of domain operators ${\cal O}$ is used to partition the predicate set ${\cal P}$ into two disjoint sets, ${\cal P} = {\cal P}_F \cup {\cal P}_S$, corresponding to fluent and static predicates. An operator $o \in {\cal O}$ is represented as a structure

\begin{displaymath}o = (V(o), P(o), A(o), D(o)),\end{displaymath}

where $V(o)$ is the variable set, $P(o)$ is the precondition set, $A(o)$ is the set of add effects, and $D(o)$ is the set of delete effects. A predicate $p$ is fluent if $p$ is part of an operator's effects (either positive or negative):

\begin{displaymath}p \in {\cal P}_F \Leftrightarrow \exists o \in {\cal O} : p \in A(o) \cup D(o).\end{displaymath}

Otherwise, $p$ is static, denoted by $p \in {\cal P}_S$.

In a domain with hierarchical types, instances of the same predicate can be both static and fluent. Consider the Depots domain, a combination of Logistics and Blocksworld, which was used in the third international planning competition [19]. This domain has such a type hierarchy. Type LOCATABLE has four atomic sub-types: PALLET, HOIST, TRUCK, and CRATE. Type PLACE has two atomic sub-types: DEPOT and DISTRIBUTOR. Predicate (AT ?L - LOCATABLE ?P - PLACE), which indicates that object ?L is located at place ?P, corresponds to eight specialized predicates at the atomic type level. Predicate (AT ?P - PALLET ?D - DEPOT) is static, since there is no operator that adds, deletes, or moves a pallet. However, predicate (AT ?C - CRATE ?D - DEPOT) is fluent. For instance, the LIFT operator deletes a fact of this type.

To address the issue of hierarchical types, we use a domain formulation where all types are expressed at the lowest level in the hierarchy. We expand each predicate into a set of low-level predicates whose arguments have low-level types. Similarly, low-level operators have variable types from the lowest hierarchy level. Component abstraction and macro generation are done at the lowest level. After building the macros, we restore the type hierarchy of the domain. When possible, we replace a set of two or more macro operators that have low-level types with one equivalent macro operator with hierarchical types. In this way, macros respect the same definition style (with respect to hierarchical types) as the rest of the domain operators. For planners that pre-instantiate all operators, such as FF, the existence of hierarchical types is not relevant. Before searching for a solution, all operators are instantiated into ground actions whose arguments have low-level types.

Facts corresponding to static predicates are called static facts. In our current implementation we ignore static predicates that are unary 1or contain two or more variables of the same type. The latter kind of facts are often used to model topological relationships, and can lead to large components.


next up previous
Next: Building Abstract Components Up: Component Abstraction Previous: Component Abstraction
Adi Botea 2005-08-01