Readings for CSE 574 - Winter 2001 - KRR
Schedule
- feb 6 - Default reasoning: Morgenstern (Sec 1-2), B&L Ch 12
- feb 8 - Planning as theorem proving: Morgenstern (finish), GOLOG paper
- feb 13 - planning as CSP: Blum & Furst, Kautz & Selman 1996
- feb 15 (peter stone)
- feb 20 - planning as CSP: Kautz & Selman 1998, Gerevini et al 1998
- feb 22 - Planning A* Search: Bacchus & Kabanza 1996, Haslum & Gefner 2000;
Huang, Selman, and Kautz 2000.
- feb 27 - diagnosis: reiter & deKleer 1987, B&L Ch 13
- mar 1 - autonomous systems: Williams & Nayak 1996/1997;
Nayak lecture slides
- mar 6 - project presentations and/or Commensense papers
- mar 8 - project presentations
Foundations of KR
-
Ron Brachman and Hector Levesque, Knowledge
Representation and Reasoning, Chapter 1 (Introduction). Draft,
not yet published, 2000.
This book provides a good overview of the logical foundations of knowledge
representation, but covers little about complexity or algorithms.
The introduction describes the "knowledge representation hypothesis", namely
that the behavior of any intelligent system will be causally connected
to a declarative representation of its beliefs.
-
Hector Levesque and Ron Brachman,
"A Fundamental Tradeoff in Knowledge Representation and Reasoning (revised
version)", in Readings in Knowledge Representation, R. Brachman
and H. Levesque, eds., Morgan-Kaufman, 1985.
One of the first papers in AI to seriously apply the basics of complexity
theory to KRR.
SAT: Threshhold Phenomena and Local Search
-
Stephen A. Cook and David G. Mitchell, "Finding
Hard Instances of the Satisfiability Problem: A Survey", in Dingzhu
Du, Jun Gu, and Panos M. Pardalos, editors, The Satisfiability Problem:
Theory and Application, volume 35 of DIMACS Series in Discrete Mathematics
and Theoretical Computer Science, pages 1-17. American Mathematical Society,
1997.
Excellent overview of both the phase transition phenomena and the GSAT/Walksat
local search algorithms.
The following three papers are summarized in the previous paper:
-
D. Mitchell, B. Selman, and H. Levesque,
"Hard and Easy Distributions of SAT Problems, in Proc. 10-th National
Conf. on Artificial Intelligence, pages 459--465, AAAI Press, 1992.
-
Bart Selman, Hector Levesque, and David Mitchell,
"A New Method for Solving Hard Satisfiability Problems", in Procs.
of AAAI-92, 440-446, 1992.
-
Bart Selman, Henry Kautz, and Bram Cohen,
"Noise Strategies for Improving Local Search", in Proc. AAAI-94.,
1994.
-
"Evidence for Invariants in Local Search",
David McAllester, Bart Selman, and Henry Kautz. Proc. AAAI-97, Providence,
RI, 1997.
Shows that different strategies for escaping from minima in Walksat work
best at the point where the ratio of the variance to the mean number of
unsatisfied clauses is minimized. This may lead to self-turning versions
of local search.
-
Schuurmans, D. and Southey, F. (2000). Local
search characteristics of incomplete SAT procedures. In Proceedings
of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000).
Shows that a factor called "mobility" is important for determining the
success of a local search strategy. Also, the paper contains an error.
There is a claimed proof that the expected run time of an algorithm with
restarts is never worse than the expected run time of the algorithm without
restarts. The proof given is incorrect, but there is an updated appendix
that provides the correct conditions under which this claim is true. In
particular, if the algorithm has a heavy tailed distribution, and we choose
the optimal restart cutoff, then we never lose (in expectation). The details
are in this 4 page excerpt.
Intelligent Systematic Search
Clause Learning
-
R. J. Bayardo Jr. and R. Schrag. Using
CSP look-back techniques to solve exceptionally hard SAT instances. In
Proc. of the Second Int'l Conf. on Principles and Practice of Constraint
Programming (Lecture Notes in Computer Science 1118) , 46-60, Springer,
1996.
First system to make depedency-directed backtracking work on SAT, by limiting
the number of extra clauses learned.
-
João P. Marques-Silva, An Overview
of Backtrack Search Satisfiability Algorithms, in Fifth International
Symposium on Artificial Intelligence and Mathematics, January 1998.
Covers both dependency directed backtracking and related techniques.
Smart Variable Selection
-
Heuristics based on unit propagation for
satisfiability problems. Chu Min LI & Anbulagan, in proceedings
of 15th International Joint Conference on Artificial Interlligence (IJCAI'97),
Morgan Kaufmann Publishers, ISBN 1-55860-480-4, Page 366-371, Japan, 1997.
Describes the heuristic used in one of the fastest DPLL based SAT solvers.
-
The Constrainedness of Search. Ian
Gent, Patrick Prosser, and Toby Walsh, under review for Journal
of the ACM.
Shows how a branching heuristic can be based on a heuristic measure
(kappa) of the expected number of solutions to a subproblem.
Randomized Systematic Methods
-
Boosting Combinatorial Search Through Randomization.
Carla Gomes, Bart Selman, and Henry Kautz. Proc. AAAI-98, Madison,
WI, July 1998.
This paper identified that the run time distributions of systematic
backtracking algorithms are often heavy tailed. In this case significant
gains can be obtain on particular problem instances by randomization and
restarting.
-
Luís Baptista and João
P. Marques-Silva, Using Randomization and Learning to Solve Hard Real-World
Instances of Satisfiability, in Proceedings of the 6th International
Conference on Principles and Practice of Constraint Programming (CP), September
2000.
Shows that a portfolio of different SAT algorithms can solve very hard
SAT encodings of real-world verification problems.
Planning
Planning as Theorem Proving
-
McCarthy, J., and Hayes, P. J., "Some Philosophical
Problems from the Standpoint of Artificial Intelligence, " in Meltzer,
B., and Michie, D. (Eds.), Machine Intelligence 4, pp. 463-502, Edinburgh:
Edinburgh University Press, 1969.
Introduced the situation calculus, the first logical account of reasoning
about a changing world.
-
Leora Morgenstern: "The Problem with Solutions to the Frame
Problem," Draft. Discusses temporal reasoning, especially the
frame problem and its solutions in nonmonotonic logic. Summarizes
much of the work initiated by the famous "Yale Shooting Paper":
-
Ron Brachman and Hector Levesque, Knowledge
Representation and Reasoning, Chapters 10 Inheritance (skim
this); 12 (Defaults) - good background on all the major systems of
nonmontonic logic; and 14 (Actions) - shows a solution to the frame
problem (called "explanation closure" axioms) that does not make
explicit use
of nonmonotic logic - except perhaps implicitly by the human writing
the axioms!
-
H. Levesque, R. Reiter, Y. Lesperance,
F. Lin, and R. Scherl. GOLOG: A logic programming language for dynamic
domains. The Journal of Logic Programming, 31:59--84, 1997.
The situation calculus as a programming language. More detailed
version of the material summarized in B and L Chapter 14.
Planning as Constraint Satisfaction
-
A. Blum and M. Furst. Fast planning through
plan-graph analysis. Artificial Intelligence, 90:281--300, 1997.
Introduced Graphplan, which revolutionized the world of STRIPS-type planning.
-
Kautz, H., & Selman, B. (1996). Pushing
the envelope: Planning, propositional logic and stochastic search.
Proceedings of the 13th National Conference on Artificial Intelligence,
1194--1201.
Showed that planning as satisfiability testing was competitive with specialized
planning algorithms.
-
Kautz, H., & Selman, B. (1999).
Blackbox: Unifying sat-based and graph-based planning. In Proc. IJCAI-99.
Combines Graphplan and satisfiability testing.
-
Gerevini, A. and Schubert,
L. 1998. Inferring state constraints for domain-independent planning.
Proc AAAI-98, Madison, WI.
Constraint based planning can be speeded by adding "lemmas" which help
to prune the search space; this paper shows one way of inferring a useful
class of such lemmas.
-
"Learning Declarative Control Rules for Constraint-Based
Planning".
Yi-Cheng Huang, Bart Selman, and Henry Kautz.
Proc. ICML-2000 (Seventeenth International Conference on
Machine Learning), Stanford, CA.
Planning as A* Search
-
Fahiem Bacchus and Froduald Kabanza. Using
Temporal Logic to Control Search in a Forward Chaining Planner. In
M. Ghallab and A. Milani, editors, New Directions in Planning, pages 141-153.
IOS Press, 1996.
Hand-encoded control information specified in a temporal logic makes simple
forward-chaining search a competitive planning strategy.
-
P. Haslum and H. Geffner, Admissible
heuristics for optimal planning, in AIPS, pp. 140--149, (2000).
Shows how such control information can be automatically derived from STRIPS
operators.
From Nonmonotonic Logic to Autonomous Systems
Default reasoning
-
Ron Brachman and Hector Levesque, Knowledge
Representation and Reasoning, Chapters 12: Defaults.
-
Reiter, R. and de Kleer, J. (1987)
Foundations of Assumption-Based Truth Maintenance Systems: Preliminary
Report, AAAI-87, Morgan Kaufmann.
Diagnosis
-
Ron Brachman and Hector Levesque, Knowledge
Representation and Reasoning, Chapters 13: Abduction.
-
J. de Kleer and B.C. Williams. Diagnosis
with behavioral modes. In Proceedings of IJCAI-89, pages 1324--1330,
August 1989.
Autonmous Systems
-
Brian C. Williams and P. Pandurang
Nayak. 1996. A Model-based Approach to Reactive Self-Configuring Systems.
In Proceedings of AAAI-96.
-
Brian C. Williams and P. Pandurang Nayak.
1997. A Reactive Planner for a Model-based Executive. In Proceedings
of IJCAI-97.
-
Lecture overheads by Pandu Nayak on diagnosis and autonomous systems.
Three lectures:
handout-13.pdf,
handout-14.pdf,
handout-15.pdf.
Knowledge Compilation
Commonsense Revisited
-
Hayes, P. J. 1985. The Second Naive Physics
Manifesto. In Formal Theories of the Commonsense World, 1-36, eds.
J.R. Hobbs & R.C. Moore. Norwood, NJ: Ablex Publishing Corp. Also reprinted
in Brachman & Levesque 1985, 468-485.
-
Ernest Davis, The Naive Physics Perplex AI
Magazine, vol. 19, no. 4, Winter 1998, pp. 51-79.
-
Matt Ginsberg, Do Computers need Common Sense?
Proc.1996 KR-96 (1996). common.ps.gz
Back to my the 574 home page.
kautz@cs.washington.edu