EBL of Search Control Knowledge

Search is an endemic problem in AI (iow, AI is search). But, often the spaces we search are huge.
Search problem:

S: set of possible search states
O: set of operators that transform one state into another
G: is predicate over S. G(s) is true if s is a goal state.
The largest scale attempts to apply EBL have addressed the problem of learning to control search, AKA "speedup" learning.
Specifically, for each operator o learn "the set of states for which o leads toward a goal state".