[For the entire collection see Zbl 0707.68001.] The paper introduces a new representation for problem-solving knowledge by sequences of intermediate subgoals (stepping stones) between problem and goal states. The underlying problem solver is called SteppingStone. While previous learning problem solver have acquired knowledge as macros, control knowledge or cases, SteppingStone improves its performances by learning subgoal sequences. The problem solving part of SteppingStone is based on a combination of means-ends analysis and brute-force search. Before attempting to solve any of the problem subgoals, SteppingStone makes a subgoal ordering with a domain-independent heuristic called openness, which minimizes subgoal interactions. When reaching an impasse, SteppingStone indexes memory by testing whether a characterization in the memory is contained within the current context defined by the subgoal being attempted and previously solved subgoals. After successfully indexing the memory, SteppingStone is recursively applied to the ordered sequence of subgoals to resolve the impasse. Experimental results on SteppingStone, applied on different size puzzles with different search strategies proved that openness heuristic is surprisingly effective to system performance improvement when this type of learning-training of the problem-solver is considered.
Reviewer: N.Curteanu