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 , called the seed type. For each node with type 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:
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. contains all types of the constant symbols used as nodes in . Given a type , is the set of all static predicates that have a parameter of type . Given a static predicate , includes the types of its parameters. are all facts instantiated from .
Each iteration of the main loop tries to build components starting from a seed type . The sets , , , and are initialized to . Each graph node of type becomes the seed of an abstract component (method ). The components are greedily extended by adding new facts and constants, such that no constant is part of any two distinct components. The method verifies if any fact merges two distinct abstract components in .
Method extends the existing components using all static facts . For simplicity, assume that a fact is binary and has constants and as arguments. Given a component , let be its set of constants (subgraph nodes) and its set of static facts (subgraph edges). In the most general case, four possible relationships can exist between the abstract components and elements , , and :
Consider the case when a static graph has two disconnected (i.e., with no edge between them) subgraphs and such that . 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.
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 is a predicate whose variables have been instantiated to constants .
Two abstract components and have identical structure if: