📄 Selectively Generalizing Plans for Problem-Solving

Summary

Systems that store generalized plans (macro-operators), as STRIPS did with Macrops, risk being overwhelmed by their own experience. As stored macros multiply, matching and choosing among them can cost as much as searching the original space, and the ordering bias that made them useful fades. Minton presents MORRIS, a best-first heuristic problem solver in the STRIPS tradition that keeps only plan fragments judged worth their cost. It retains two kinds. S-macros ("scripts") are short subsequences that recur across solutions; their number is capped, and the least-used are dropped. T-macros ("tricks") are sequences that looked unpromising under the heuristic H_diff but still led to success, including goal reorderings forced by interacting goals. In a 26-operator robot world, MORRIS was compared with MAX, a STRIPS-style learner that saves every usable macro, and with a non-learning baseline. MORRIS evaluated fewer branches than MAX and generally beat the non-learner. MAX was usually slower than the baseline whenever the baseline could solve a problem. The work frames "what to learn" as a central question for learning problem solvers.

Key points

• MORRIS learns selectively using two utility criteria: frequency of use (s-macros) and usefulness on hard, heuristically misleading subproblems (t-macros, which help escape local maxima of H_diff).
• The comparison system MAX copies STRIPS's practice of generalizing whole solutions and treating every composable subsequence as a potential macro. Its search procedure is otherwise identical to MORRIS's.
• The test domain is a robot world with 26 operators and 5 rooms. It includes doors, boxes, lights, tools and food, and many of its problems involve interacting goals. The evaluation used a series of 25 problems ordered from easier to harder, with a 100 CPU-second cutoff.
• T-macros gave the larger gains. S-macros helped more often but by smaller margins, and their applicability tests sometimes made MORRIS slower than the non-learner.
• The reported timings cover search only, not macro generalization. The author notes that learning time was typically much smaller than search time.