CSE 574 - Artificial Intelligence II - Winter 2001
Knowledge Representation and Reasoning
NOTE ROOM CHANGE!
Class meets: Tuesdays & Thursdays, 12:00-1:20, Mary
Gates Hall Room 253
417 Sieg Hall, (206) 543-1896
Office Hours: Send email to make an appointment
In this course we will study knowledge representation languages and efficient
reasoning algorithms. Attention will be paid to tradeoffs between the expressive
power and computational tractability of different representation languages.
Topics will include local search based inference algorithms, phase-transition
phenomena, logic-based planning and temporal reasoning, dependency-directed
backtracking, knowledge compilation, speedup learning, and model-based
diagnosis. Our study will be motivated by problems in plan synthesis, commonsense
and scientific reasoning.
Selections from Brachman & Levesque, “Knowledge Representation
and Reasoning” (draft), and and other classic and recent papers.
Please read the papers before class (I don't intend to do all the
talking!). Links to the readings appear below.
First k-th weeks: a weekly “reaction essay” to one of the readings,
about 2 pages in length. Compare the paper with other readings, argue
for or against point of view, relate to other areas of CS, etc.
Students will do a project and give a seminar on the project. Projects
can be done individually or in teams. Projects can be chosen from
the list below, or proposed by the students. Many of the problems below
are open-ended research questions, so it is important that the students
create and discuss a detailed "plan of attack" with the instructor no later
than February 1st. The projects will generally involve both a implementation
and a written report, but a project with no implementation but some interesting
theorems is also possible.
The project seminars will be presented during the last 2 weeks of class
(Feb 27th – Mar 8th) or earlier. (Your project does not have to be
completely finished before you talk about it). The final project
reports are due Mar 12th (first day of exam week).
The class grade will be based on the project grade (largest component),
the reaction essays and class participation.
Here is the schedule of readings
and links to the papers themselves.
Possible Project Topics
Reimplement and evaluate a reasoning algorithm – e.g., study the variations
of dependency-directed backtracking discussed in the paper by Marquis Silva
on different benchmarks problems.
Create an interesting new set of benchmark problems – e.g., encode some
problems you are familiar with from systems, verification, computational
biology, coding theory, cryptography, etc. For example, factoring
numbers can be encoded in small, hard SAT problems. How many bits
can various state of the art SAT solvers factor?
Create a high-quality, in depth literature review (of publishable quality)
on a topic related to the course.
The performance of the Walksat local search algorithm for satisfiability
testing is highly sensitive to the setting of the parameter that determines
the frequency of random moves. McAllester, Selman, and Kautz (AAAI 1997)
suggest that the optimal setting of this parameter minimizes the ratio
of the "noise" level to its variance. Design, build, and test such a "self-tuning"
version of Walksat.
There is a growing interest in e-commerce and in AI in solving combinatorial
auction problems - an NP-hard problem. In order to evaluate proposed algorithms
it is important to have good random problem generators where one can control
problem hardness. Design a problem generator (e.g., for the class of problems
studied in Hoos (AAAI 2000)) and determine if the problem distribution
exhibits the kind of easy/hard/easy pattern seen in domains such as k-SAT.
Schuurmans and Southey (AAAI 2000) describe a variation of Walksat that
solves hard problems in many fewer steps - but the higher cost of each
step in their algorithm makes it slower in the end. Reimplement and optimize
their approach (e.g., replace real-valued arithmetic with an integer approximation),
and try to make it faster in practice than Walksat.
The SATPLAN framework encodes planning as satisfiability in propositional
logic; the GOLOG framework (Levesque et. al. 1999) encodes planning as
deduction in first-order logic programming. GOLOG has greater expressive
power and more flexibility for closed-loop planning, but cannot quickly
search large combinatorial spaces as can SATPLAN. Design a way to combine
the two approaches (perhaps by adding predicates to GOLOG that are implemented
as external calls to SATPLAN). A team of students could implement the strategy
for a domain such as control of package-delivery robot.
Knowledge compilation attempts to speed up problem solving by rewriting
a knowledge base into a more computationally attractive form. While "exact"
knowledge compilation usually results in an exponential increase in the
size of the KB, compilation to a smaller approximate KB (e.g., a 2-SAT
or k-HORN KB) can prevent the blow-up. Design and run experiments to test
the usefulness of approximate knowledge compilation, for example, for speeding
Baptista and Marques-Silva (CP 2000) show that a portfolio of different
randomized dependency-directed backtracking search algorithms can outperform
any other method on a suite of hard SAT encodings of hardware verification
problems. Replicate their experiments, but add local search (Walksat) into
Model-based diagnosis attempts to account for differences in the predicted
and observed behavior of devices. A diagnosis is developed by reasoning
"from first principles" about a model of the device, rather than by using
expert-system type rules that directly map observed faults to a diagnosis.
This field of research has traditionally dealt with man-made devices such
as photocopiers or spacecraft control systems that can be modeled (at a
very abstract level!) as Boolean circuits. The emerging area of systems
biology deals with creating and using computational models of natural
devices, such as DNA or cells. This project would involve exploring some
potential connections between model-based diagnosis and systems biology,
in particular, in the area of qualitative models of gene expression. (This
is the least well-defined project, because it is an area I am just learning
about myself; so this project would be appropriate for someone who either
has a background in computational biology or would like to explore this
area with me.)
Department of Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to kautz]