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":
  • S. Hanks and D. McDermott. Default reasoning, nonmonotonic logics, and the frame problem. In Proceedings of the Fifth National Conference on Artificial Intelligence, pages 328--333, 1986.
• 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

• H. A. Kautz and B. Selman. Forming concepts for fast inference. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 786-- 793, 1992
• Marco Cadoli and Francesco M. Donini. A survey on knowledge compilation. AI Communications, 1998.
• Horn Approximations of Empirical Data.  Henry Kautz, Michael Kearns, and Bart Selman. Artificial Intelligence, 74/1 (pp. 129-145) 30 March 1995.

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