David Jack Mostow

Mechanical Transformation of Task Heuristics into Operational Procedures Degree Type: Ph.D. in Computer Science
Advisor(s): Jaime Carbonell
Graduated: May 1981

Abstract:

This dissertation characterizes the operationalization of advice as a series of problem transformations leading from the advice statement to a procedure for achieving a specified goal avoid taking points or evaluating a specified quantity decide whether an opponent is void. It describes some general operators for performing such transformations. These operators have been implemented in a program called FOO as domain-independent transformation rules that access a knowledge base of task domain concepts. They have been used to operationalize advice for the card game Hearts and a music composition task.

Some of FOOs transformation rules represent high-level strategies for operationalizing advice. Additional rules represent reasoning methods used to reformulate advice in terms of these operationalization strategies, solve the subproblems they generate, and translate their results into a usable form. Although FOO lacks a problem-solving component for choosing which of these transformation rules to apply, the dissertation shows how means-end analysis could be used to guide the search through the problem space.

The dissertation formalizes the notion of reformulating one concept in terms of another, for example, reformulating take points in terms of playing the highest card in the suit led. It describes mechanical techniques for mapping domain-specific problems onto general methods. In particular, it examines in detail the process of formulating a problem as a heuristic search, and presents domain-independent rules that improve a search procedure by deriving new heuristics based on analysis of the problem and knowledge about the task domain.

Thesis Committee:
Jaime Carbonell (Chair)
Frederick Hayes-Roth
Allan Newell
Robert Balzer (USC-ISI)

Nico Habermann, Head, Computer Science Department