Learning Subgoal Sequences for Planning

Abstract

A learning problem solver consists of three components: (1) a problem solver, (2) a memory of problem-solving knowledge , and (3) a learning component for deriving new problemsolving knowledge from experience. Previous learning problem solvers have acquired knowledge as macros, control knowledge, or cases. SteppingStone is a general learning problem solver that improves its performance by learning subgoal sequences. The underlying problem solver for SteppingStone is a combination of means-ends analysis and brute-force search. It depends primarily upon means-ends analysis and its problem-solving knowledge to solve the subgoals of the problem. Learning occurs only when this approach fails. Upon failure, search is applied and a new subgoal sequence is derived and added to its problem-solving knowledge. Before SteppingStone attempts to solve any of the problem sub goals, it first orders them with a domain independent heuristic which we call openness. Openness is used to order the subgoals to minimize interactions. SteppingStone's ability to improve its performance and scale to difficult problems is demonstrated with an implemented system. We show that a small memory of appropriate subgoals yields multiple orders of magnitude savings in problem-solving cost.