Building Abstract Components

Abstract components are built as connected subgraphs of the static graph of a problem. Clustering starts with abstract components of size 1, containing one node each, that are generated based on a domain type $t$, called the seed type. For each node with type $t$ in the static graph, a new abstract component is created. Abstract components are then iteratively extended with a greedy approach.

Next we detail how the clustering procedure works on the example, and then provide a more formal description, including pseudo-code. As said before, Figure 3 shows the two abstract components built by this procedure. The steps of the clustering are summarized in Table 1, and correspond to the following actions:

Table 1: Building abstract components for the Rovers example.

Step	Current Predicate	Used Predicate	COMPONENT0		COMPONENT1
			Constants	Facts	Constants	Facts
1			CAM0		CAM1
2	(SUPPORTS ?C - CAMERA ?M - MODE)	NO	CAM0		CAM1
3	(CALIBR-TARGET ?C - CAMERA ?O - OBJECTIVE)	NO	CAM0		CAM1
4	(ON-BOARD ?C - CAMERA ?R - ROVER)	YES	CAM0	(ON-BOARD CAM0 ROVER0)	CAM1	(ON-BOARD CAM1 ROVER1)
			ROVER0		ROVER1
5	(STORE-OF ?S - STORE ?R - ROVER)	YES	CAM0	(ON-BOARD CAM0 ROVER0)	CAM1	(ON-BOARD CAM1 ROVER1)
			ROVER0	(STORE-OF STORE0 ROVER0)	ROVER1	(STORE-OF STORE1 ROVER1)
			STORE0		STORE1

1. Choose a seed type (CAMERA in this example), and create one abstract component for each constant of type CAMERA: COMPONENT0 contains CAM0, and COMPONENT1 contains CAM1. Next, iteratively extend the components created at this step. One extension step uses a static predicate that has at least one variable type already encoded into the components.

2. Choose the predicate (SUPPORTS ?C - CAMERA ?M - MODE), which has a variable of type CAMERA. To avoid ending up with one large component containing the whole graph, merging two existing components is not allowed. Hence a check is performed whether the static facts based on this predicate keep the existing components separated. These static facts are (SUPPORTS CAM0 COLOUR), (SUPPORTS CAM0 HIGH-RES), (SUPPORTS CAM1 COLOUR), and (SUPPORTS CAM1 HIGH-RES). The test fails, since constants COLOUR and HIGH-RES would be part of both components. Therefore, this predicate is not used for component extension (see the third column of Table 1).

3. Similarly, the predicate (CALIBRATION-TARGET ?C - CAMERA ?O - OBJECTIVE), which would add the constant OBJ1 to both components, is not used for extension.

4. The predicate (ON-BOARD ?C - CAMERA ?R - ROVER) is tried. It merges no components, so it is used for component extension. The components are expanded as shown in Table 1, Step 4.

5. The predicate (STORE-OF ?S - STORE ?R - ROVER), whose type ROVER has previously been encoded into the components, is considered. This predicate extends the components as presented in Table 1, Step 5.

After Step 5 is completed, no further component extension can be performed. There are no other static predicates using at least one of the component types to be tried for further extension. At this moment the quality of the decomposition is evaluated. In this example it is satisfactory (see discussion below), and the process terminates. Otherwise, the decomposition process restarts with another domain type.

The quality of a decomposition is evaluated according to the size of the built components, where size is defined as the number of low-level types in a component. In our experiments, we limited size to values between 2 and 4. The lower limit is trivial, since an abstract component should combine at least two low-level types. The upper limit was set heuristically, to prevent the abstraction from building just one large component. These relatively small values are also consistent with the goal of limiting the size and number of macro operators. We discuss this issue in more detail in Section 2.2.

Figure 4 shows pseudo-code for component abstraction. $\mathit{Types}(g)$ contains all types of the constant symbols used as nodes in $g$. Given a type $t$, $\mathit{Preds}(t)$ is the set of all static predicates that have a parameter of type $t$. Given a static predicate $p$, $\mathit{Types}(p)$ includes the types of its parameters. $\mathit{Facts}(p)$ are all facts instantiated from $p$.

Figure 4: Component abstraction in pseudo-code.

Each iteration of the main loop tries to build components starting from a seed type $t \in \mathit{Types}(g)$. The sets $Open$, $Closed$, $Tried$, and $AC$ are initialized to $\emptyset$. Each graph node of type $t$ becomes the seed of an abstract component (method $\mathit{createComponent}$). The components are greedily extended by adding new facts and constants, such that no constant is part of any two distinct components. The method $\mathit{predConnectsComponents}(p, AC)$ verifies if any fact $f \in \mathit{Facts}(p)$ merges two distinct abstract components in $AC$.

Method $\mathit{extendComponents}(p, AC)$ extends the existing components using all static facts $f \in \mathit{Facts}(p)$. For simplicity, assume that a fact $f$ is binary and has constants $c_1$ and $c_2$ as arguments. Given a component $ac$, let $Nodes(ac)$ be its set of constants (subgraph nodes) and $Facts(ac)$ its set of static facts (subgraph edges). In the most general case, four possible relationships can exist between the abstract components and elements $f$, $c_1$, and $c_2$:

1. Both $c_1$ and $c_2$ already belong to the same abstract component $ac$:
   
   $$\exists (ac \in AC): c_1 \in \mathit{Nodes}(ac) \wedge c_2 \in \mathit{Nodes}(ac).$$
   
   
   In this case, $f$ is added to $ac$ as a new edge.
2. Constant $c_1$ is already part of an abstract component $ac$ (i.e., $c_1 \in \mathit{Nodes}(ac)$) and $c_2$ is not assigned to a component yet. Now $ac$ is extended with $c_2$ as a new node and $f$ as a new edge between $c_1$ and $c_2$.
3. If neither $c_1$ nor $c_2$ are part of a previously built component, a new component containing $f$, $c_1$ and $c_2$ is created and added to $AC$.
4. Constants $c_1$ and $c_2$ belong to two distinct abstract components:
   
   $$\exists (ac_1, ac_2): c_1 \in \mathit{Nodes}(ac_1) \wedge c_2 \in \mathit{Nodes}(ac_2) \wedge ac_1 \neq ac_2.$$
   
   
   While possible in general, this last alternative never occurs at the point where the method $\mathit{extendComponents}$ is called. This is ensured by the previous test with the method $\mathit{predConnectsComponents}$.

Consider the case when a static graph has two disconnected (i.e., with no edge between them) subgraphs $sg_1$ and $sg_2$ such that $\mathit{Types}(sg_1) \cap \mathit{Types}(sg_2) = \emptyset$. In such a case, the algorithm shown in Figure 4 finds abstract components only in the subgraph that contains the seed type. To perform clustering on the whole graph, the algorithm has to be run on each subgraph separately.

Figure 5: Abstract type in Rovers.

Following the standard of typed planning domains, abstract components are assigned abstract types. Figure 5 shows the abstract type assigned to the components of our example. As shown in this figure, the abstract type of an abstract component is a graph obtained from the component graph by changing the node labels. The constant symbols used as node labels have been replaced with their low-level types (e.g., constant CAM0 has been replaced by its type CAMERA).

Our example also shows that components with identical structure have the same abstract type. Identical structure is a strong form of graph isomorphism, which preserves the edge labels as well as the types of constants used as node labels. A fact $f = f(c^1, ..., c^k) \in Facts(ac)$ is a predicate whose variables have been instantiated to constants $c^i \in Nodes(ac)$.

Two abstract components $ac_1$ and $ac_2$ have identical structure if:

1. $\vert Nodes(ac_1)\vert = \vert Nodes(ac_2)\vert$; and
2. $\vert Facts(ac_1)\vert = \vert Facts(ac_2)\vert$; and
3. there is a bijective mapping $p:Nodes(ac_1) \rightarrow Nodes(ac_2)$ such that
   • $\forall c \in Nodes(ac_1) : \mathit{Type}(c) = \mathit{Type}(p(c))$;
   • $\forall f(c^1_1, ..., c^k_1) \in Facts(ac_1) : f(p(c^1_1), ..., p(c^k_1)) \in Facts(ac_2)$;
   • $\forall f(c^1_2, ..., c^k_2) \in Facts(ac_2) : f(p^{-1}(c^1_2), ..., p^{-1}(c^k_2)) \in Facts(ac_1)$;