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 subgoals, it first orders them with a domain independent heuristic which we call openness. Openness is used to order the subgoals to minimize interactions. Stepping-Stone'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.