Learning in Problem Solving::: Utility Problem
Utility problem[Minton, 1988] in learning is first introduced in PRODIGY[Carbonell et al] explicitly. While learned rules may reduce problem solving time by directing the search more carefully, they may also increase problem solving time by forcing the problem solver to consider them. To minimize the total number of node expansions in the search space, the more control rules we learn, the better. But, to minimize the total CPU time required to solve a problem, we must trade-off.
Factors of performance degradation
- Low application frequency i.e. overly specific rules
- High match cost in production systems
- Low benefit
In SOAR, utility problem is used for a discussion of how to deal with large, expensive chunks.