Reasoning Methods in Artificial Intelligence (CS329A)

Course: Reasoning Methods in Artificial Intelligence (CS329A)
Instructor: P. Pandurang Nayak  (nayak@ptolemy.arc.nasa.gov)
Quarter: Winter
Time: TTh 9:30-10:45
Location: Gates B08
TA:  Todd Neller (neller@ksl.stanford.edu)

Table of contents

Abstract

The last five years of research in Artificial Intelligence (AI) has produced dramatic advances in core reasoning methods. The identification of phase transitions in constraint satisfaction and propositional satisfiability has generated renewed interest in these problems and has spawned research leading to the development of new classes of algorithms that perform dramatically better than previous ones. Concurrently, research in classical planning has significantly clarified the issues in generating partially ordered plans, which has led to a new class of least commitment planners for plan representations with differing expressive power. More recently, the development of the GraphPlan algorithm, and the connection between planning and propositional satisfiability, has led to algorithms that dramatically outperform previous planning algorithms. Finally, the theory and algorithms for model-based diagnosis have matured to a point where these techniques can successfully provide real-time performance in significant real-world domains.

This course will provide the student with an in-depth understanding of these recent developments. It is designed to be useful both for students wanting to apply these methods as pieces of a larger system, and for those wanting to get a solid grounding as a basis for further research in these areas. Much of  the evaluation of the above work is based on extensive experimentation on problem repositories and random problems. Students will be expected to implement a selected set of algorithms and empirically evaluate them in a similar manner. This is expected to provide the student with a finer appreciation for the strengths and weaknesses of particular algorithms, and to teach them the art of carrying out empirical evaluations.

Prerequisites

Students are assumed to have taken basic courses in AI, algorithms, data structures, and programming, or to have equivalent background in these areas. The course is appropriate for graduate students (both Masters and PhD students), and for advanced undergraduates with a special interest in AI.

Syllabus

Course work

Students will be expected to read all papers in the reading list.  In addition, there will be three programming assignments.  Each assignment will involve implementing an algorithm, running a set of experiments to evaluate the algorithm, and writing up a report on the experiments.  Assignments may be done in groups of 2-3 students.  You may choose any programming language for implementation purposes (C or C++ for maximum efficiency, Java for Web portability and visual display of results, or Common Lisp for flexibility).  Please discuss the choice of algorithms and experiments with the instructor before starting work on it.  The three assignments are:

Tentative schedule

Jan  6 Propositional satisfiability: Phase transition phenomena, stochastic search algorithms (GSAT, GenSAT, WalkSAT), and the Davis-Putnam procedure [1, 2, 3, 4, 5]
8
  
13
  
15
 CSP algorithms: Introduction and local consistency algorithms [6,7]
20
  
22
  CSP algorithms: Conflict-directed backjumping, forward checking, backmarking, dynamic variable ordering [8, 9, 12]
27
  
29
  
Feb
  3
 Dyamic backtracking  [10]
5
 Min-conflicts [11]
10
 Structure-based methods [13]
12
 Graphplan [14]
17
 Satplan [15,16]
19
 Partial-order planning: SNLP and UCPOP [17,18]
24
  
26
 Model-based diagnosis: Conflict-directed best first search and truth maintenance algorithms [19,20, 21]
Mar
  3
5
10
 Dead week: Catch up and program demonstrations
12
 

Reading List

Selected material from the following papers will be covered in the course.  All these papers are included in the CS329A course reader available from the Stanford Bookstore.
  1. Selman, B. Mitchell, D., and Levesque, H. (1996). Generating Hard Satisfiability Problems. Artificial Intelligence 81, 17-29.
  2. Crawford, J. and Auton, L. (1996). Experimental Results on the Crossover Point in Random 3SAT. Artificial Intelligence 81, 31-57.
  3. Selman, B., Levesque, H., and Mitchell, D. (1992). A New Method for Solving Hard Satisfiability Problems. In Procs. of AAAI-92, 440-446.
  4. Gent, I., and Walsh, T. (1993). Towards an Understanding of Hill-climbing Procedures for SAT. In Procs. of AAAI-93, 28-33.
  5. Selman, B., Kautz, H., and Cohen, B. (1994). Noise Strategies for Improving Local Search. In Procs. of AAAI-94, 337-343.
  6. Van Hentenryck, P., Deville, Y., and Teng, C. (1992). A Generic Arc-Consistency Algorithm and its Specializations. Artificial Intelligence 57, 291-321.
  7. Freuder, E. and Elfe, C. (1996). Neighborhood Inverse Consistency Preprocessing. In Procs. of AAAI-96, 201-208.
  8. Prosser., P. (1993). Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence 9(3), 268-299.
  9. Kondrak, G. and van Beek, P. (1997). A Theoretical Evaluation of Selected Backtracking Algorithms. Artificial Intelligence 89, 365-387.
  10. Ginsberg, M. (1993). Dynamic Backtracking. JAIR 1, 25-46.
  11. Minton, S., Johnston, M., Philips, A., and Laird, P. (1992). Minimizing Conflicts: A Heuristic Method for Constraint-Satisfaction and Scheduling Problems. Artificial Intelligence 58, 161-205.
  12. Bacchus, F. and van Run, P. (1995). Dynamic Variable Ordering in CSPs. Principles and Practice of Constraint Programming--CP-95 (Springer Verlag Series, LNCS, #976), 258-275.
  13. Dechter, R. (1992). Constraint Networks. In Encyclopedia of Artificial Intelligence, second ed., 276-285. Wiley and Sons.
  14. Blum, A. and Furst, M. (1997). Fast Planning through Planning Graph Analysis. Artificial Intelligence 90, 281-300.
  15. Kautz, H. and Selman, B. (1996). Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. In Procs. of AAAI-96, 1194-1201.
  16. Ernst, M., Millstein, T., and Weld, D. (1997). Automatic SAT-Compilation of Planning Problems. In Procs. of IJCAI-97, 1169-1176.
  17. McAllester, D. and Rosenblitt, D. (1991). Systematic Nonlinear Planning. In Procs. of AAAI-91, 634-639.
  18. Weld, D. (1994). An Introduction to Least Commitment Planning. AI Magazine 15(4), 27-61.
  19. de Kleer, J. and Williams, B. (1989). Diagnosis with Behavioral Modes. In Procs. of IJCAI-89, 1324-1330.
  20. Williams, B. and Nayak, P. (1996). A Model-based Approach to Reactive Self-Configuring Systems. In Procs. of AAAI-96, 971-978.
  21. Nayak, P. and Williams, B. (1997). Fast Context Switching in Real-time Propositional Reasoning. In Procs. of AAAI-97, 50-56.

Handouts

Assignments