Seminar - Decomposition for Hierarchical Problem Solving (Rutgers)

[KAP...@red.rutgers.edu.uucp]

PhD Oral Qualifying Examination for Mr. S. Mahadevan

Mr. Mahadevan's examination is scheduled for Wednesday, April 1 at 10:30 AM
in Hill 423. The examination committee is chaired by T. Mitchell, and includes
T. McCarty, J. Mostow, and L. Steinberg. DCS faculty are welcome to attend;
graduate students are invited to the public portion of the examination. Mr.
Mahadevan's dissertation proposal is abstracted below:

LEARNING DECOMPOSITION METHODS TO IMPROVE HIERARCHICAL
PROBLEM-SOLVING PERFORMANCE

Previous work in machine learning on improving problem-solving
performance has usually assumed a state-space or "flat"
problem-solving model. However, problem-solvers in complex domains,
such as design, usually employ a hierarchical or problem-reduction
strategy to avoid the combinatorial explosion of possible operator
sequences. Consequently, in order to apply machine learning to
complex domains, hierarchical problem-solvers that automatically
improve their performance need to designed. One general approach is
to design an interactive problem-solver -- a learning
apprentice -- that learns from the problem-solving activity of expert
users. In this talk we propose a technique, VBL, by which such a
system can learn new problem-reduction operators, or decomposition
methods, based on a verification of the correctness of example
decompositions. We also discuss two important limitations of the VBL
technique -- intractability of verification and specificity of
generalization -- and propose solutions to them. Finally, we present
a formalization of the problem of learning decomposition methods based
on viewing actions and problems as binary relations on states.

-------