This section describes function composition, how the transformation is applied successively to the series of subgraphs extracted from the composite graph. Function composition uses a slightly modified form of Dijkstra's algorithm (Dijkstra 1959) to traverse the edges between doorway nodes. The left hand side of Figure 21 shows the composite graph after moving the goal in the robot navigation example of Section 2.2. The right hand side shows the graph traversed by Dijkstra's algorithm.
To begin the process, the subgraph which contains the goal is extracted and the best matching isomorphic subgraph is found. The edge lengths in the composite graph are then updated using the scaled length of the corresponding edge in the matching isomorphic subgraph, d1 and d2 in Figure 21. As d2 is less than d1, the next subgraph extracted, Gr2, is the one sharing the doorway node with the edge of length d2. The best matching isomorphic subgraph is found and the edge of length d3 updated. The shortest path is again determined. As d1 is less than d2 + d3 subgraph, Gr3 is extracted. The process is repeated until all subgraphs have been updated. At each stage when a subgraph is matched, the corresponding transformed function is retrieved and added to the new function in the appropriate region.
In this example, there is only a single path to the goal from each room. Often there will be multiple paths. Suppose room 5 had an additional doorway in the lower left corner of the room, labeled ``B'' on the left hand side of Figure 22, in addition to the original doorway labeled ``A''. The graph, shown on the right hand side of Figure 22, would result. There are now two possible paths to the goal of lengths d4 and d5. If the length across room 5, d6, is greater than the absolute difference between d4 and d5, the choice of path from this room will be determined by a decision boundary inside the room. This is produced by taking the maximum of two functions as shown in Figure 23: one for entering by doorway ``A'' and leaving by doorway ``B''; one for entering by doorway ``B'' and leaving by doorway ``A''. This principle can be repeated if there are more than two paths to the goal from a given room.
If the cross-room distance, d6, had been smaller than the difference (|d4-d5|) the decision boundary would have to be in another room. In general, we want to find the room in which the cross-room distance is larger than the difference between the incident paths. This is repeated for every cycle in the path graph. A cycle is detected when a node is visited twice, indicating that it is reachable by two separate paths. Let us suppose this is node n3 in the graph of Figure 22. As Dijkstra's algorithm is being used, we know that all previous nodes, on either path, such as n1 and n2 are already closed. This must be true for both paths to have reached n3. All the rooms on paths up to these nodes cannot contain the decision boundary, so it must be in either room 4 or 5. To decide which remaining room it is in, we compare the two path lengths. If d4 is longer than d5 + d6 then the decision boundary will be in room 4; otherwise it will be in room 5.
Whichever room is selected, the decision boundary is produced from the maximum of two functions. The heights of the two functions, when adjusted for their path lengths, determine where the decision boundary occurs within the room. If the paths are of equal length, taking the maximum will correctly put the decision boundary at the doorway. If there are no such functions in the case base, functions that already include decision boundaries may be used. This technique produces a correct decision boundary if the difference in the path lengths entering the room is less than the difference between the heights of the function at the ``out'' doorways. On the left hand side of Figure 24 there is a room with two doorways. As path 1 is significantly longer than path 2, the decision boundary is far to the left. The shortest path to the goal from most of the room is via the right hand doorway. If this function is combined with a mirror image of itself, it will produce a decision boundary in the middle of the room, as shown on the right hand side of Figure 25. This could be used for the new problem shown on the left hand side of Figure 25 where the two paths are the same length. Again the heights of the two functions can be changed to move the decision boundary. But it cannot be moved to anywhere in the room. The decision boundary can be moved no closer to a particular doorway than in the original function shown in Figure 24
