Mechanical transformation of task heuristics into operational procedures

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).

Abstract

Advice about how to perform a task can often be expressed in the language of the task domain quite simply. For example, advice for how to play the card game Hearts includes avoid taking a trick with points, try to flush out the Queen of spades, and don't lead a high card in suit where an opponent is void. However, such advice is not operational because it is not expressed in terms of the basic capabilities of the task agent--it doesn't tell what card to play next. Developing a procedure to implement the advice (operationalizing the advice) can be difficult due to limitations imposed by the structure of the task and the environment in which the task is performed. Advice may recommend an action that cannot be directly executed--a Hearts player cannot flush the Queen by snatching it from an opponent's hand. Advice may be expressed in terms of unobservable information--a Hearts player cannot peek at opponents' cards to see who's void, or look into the future to find out if a trick will have points. 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. The operators have been implemented in a program called FOO as domain-independent transformation rules that access a knowledge base of task domain concepts, and have been used to operationalize advice for the card game Hearts and a music composition task. Some of FOO's 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.