next up previous
Next: Random Restarts Up: Experimental Results Previous: Learning and Backjumping

Splitting Heuristic

Line 7 of the LPSAT pseudocode (Figure 3) makes a nondeterministic choice of variable v before the recursive call, and the splitting heuristic used to guide this choice can bias performance. We expected the standard RELSAT heuristic to perform poorly (due to a overly strong preference for trigger variables) for two reasons: 1) the trigger itself is an implicit clause which is resolved when a trigger variable is set, and 2) each time the solver modifies a trigger variable, it may call CASSOWARY, and these calls often dominate runtime. We tried several methods of including information about the trigger variables in the splitting heuristic, including adding and multiplying the score of trigger variables by a user-settable preference value. To our surprise, however, we were unable to achieve significant improvement (although increasing the preference for trigger variables did slow execution). These results lead us to suspect that either that LCNF problems are generally insensitive to our heuristics or that our compilation of metric planning domains already encodes information about trigger variables in the structure of the problem. Further experiments will decide the issue.




2000-02-24