Let us start by introducing the idea of bias-optimality and by briefly reviewing general, asymptotically optimal search methods by Levin ([30]) and [20]. These methods are nonincremental in the sense that they do not attempt to accelerate the search for solutions to new problems through experience with previous problems. We will mention existing heuristic extensions for incremental search and point out their drawbacks. The remainder of the paper will describe OOPS which overcomes these drawbacks.