marina@ai.toronto.edu (Marina Haloulos) (11/14/89)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
ARTIFICIAL INTELLIGENCE SEMINAR
GB119, at 11:00 a.m., Thursday 23 November 1989
Dr. Michael R. Lowry
Kestrel Institute
"Problem Reformulation through Abstraction,
Design, then Implementation"
The effectiveness of intelligent problem-solving systems is highly
dependent on their representation of knowledge and formulation
of problems. An intelligent system which automatically
reformulates problems and changes representation is more
effective at problem-solving than current AI systems which work
within a fixed representation.
This talk will present a theory of problem reformulation and a
prototype reformulation system, STRATA, whose domain is
algorithm synthesis. STRATA synthesizes algorithms in three
steps. First it abstracts a problem by discovering problem
properties and incorporating them into the domain theory.
Second, it designs an abstract algorithm to solve the abstracted
problem. Third, STRATA constructs an efficient implementation
for the abstract algorithm. The end result of these three steps is a
change of representation.
This talk will emphasize an algebraic theory of problem
abstraction. Abstraction is defined semantically on the problem
domain rather than syntactically on the representation of the
problem domain. This algebraic framework stresses both the
abstraction of objects and the abstraction of operations in a
problem domain. Problem abstraction is a specialized type of
abstraction in which essential information is preserved while
inessential information is thrown away.
The semantic definition of problem abstraction is independent of
representation system. This talk will describe how semantic
abstraction can be realized as syntactic transformations of logical
theories. A formal logic which is sound with respect to the
semantics of abstraction has been developed. A method for
calculating within this logic called Ontological Reasoning has been
implemented. STRATA employs ontological reasoning to generate
problem reformulations which represent problem abstractions.
The mathematical foundation for this theory of problem
reformulation is based on recent work in theoretical computer
science, particularly abstract data types. This will be briefly
described in the talk and is detailed in the thesis.