The background algorithm at work in this system is a recursive descent planner. It traverses the input tree, at each node picks one rule, instantiates it, and moves on to the next node in a depth-first manner. If a situation is ever encountered where a node has no rules left, backtracking occurs.
This is a modified recursive descent algorithm in that it takes advantage of all of the above processes to reduce the search space, prevent backtracking, and automatically propagate constraints. As explained several times above, the algorithm works like this:
At each node, the first active rule is instantiated
. All of its island constraints are
implemented, effectively failing all the rules that conflict with it. At this point,
the soundness and island conditions of each of the nodes that had rules failed is
checked and acted upon, which in turn may fail other rules, etc.. When equilibrium
is reached, the next node in the tree is visited in a depth-first traversal.
There are two exceptions to this general mode of operation. First, if the node is already
an island, nothing needs to be done. This is true because all of the island constraints
were implemented at the time the node first became an island. Secondly, if as a result of instantiating the rule (and the subsequent
island and soundness processing) a node in the tree has all of its rules failed, then backtracking commences.
If there are other rules in this node, they are tried. If all the rules in this node lead
to failure, then we backtrack up to the previous node, and try the next rule there.
It should be noted that backtracking is minimized by the system. The soundness and island processing work to eliminate conflicting sets of rules without the need to try them out, fail, and backtrack. Also, the optimizing techniques identify all of the nodes that must be failed every time a rule is instantiated. Thus, it is not necessary to traverse the tree down to where the failure occurs in order to detect the failure. This eliminates much of the wasted processing associated with backtracking.