CS227: Reasoning Methods in Artificial Intelligence

Stanford University - Spring 2008

 

Instructor:              Neil Yorke-Smith

Office hours: by arrangement before class

Time:                     Tue Thu 9:30-10:45

Location:                260-003

Co-Instructor:        Dan Bryce

Office hours: by arrangement before class

TA:                        David Underhill

                             Office hours: Tue 11-12:30, Fri 9-11, myth lab

Website:                 http://www.stanford.edu/class/cs227/

Newsgroup:           su.class.cs227

Topics

Propositional satisfiability: phase transition phenomena, DPLL algorithm, stochastic local search, discrete Lagrangian methods.

Constraint satisfaction: arc consistency, forward checking, backmarking, backjumping, conflict-directed backjumping, dynamic backtracking, dynamic variable ordering.  Decomposition methods.  Modelling.  Symmetry-breaking.

Temporal reasoning: Simple Temporal Networks, constraint-based scheduling, propagating resource constraints.

Planning: causal link planning, state space planning, Hierarchical Task Networks, planning graphs, reachability heuristics, SAT and CSP-based planning.  Time and resources, uncertainty.  Integrative SAT and CSP planning.  Combined planning and scheduling.

Additional topics (as time permits): preferences, complexity results.  Execution: plan execution and recognition, model-based diagnosis and control.

Prerequisites

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

Assessment by coursework

Students will be expected to read all papers in the reading list.  In addition, there will be four 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.

 

1.      Propositional satisfiability: Evaluate stochastic search algorithms or the DPLL algorithm.  Assigned 8 April, due 23 April.

2.      Constraint satisfaction: Evaluate conflict-directed backjumping or dynamic backtracking with arc consistency, dynamic variable ordering, and forward checking.  Assigned 22 April, due 5 May.

3.      Constraint-based scheduling: Evaluate constraint-based scheduling using simple temporal networks. Assigned 1 May, due 21 May.

4.      Planning: Design one planning domain. Evaluate three planners, including at least one of FF, Graphplan, or Satplan. Assigned 15 May, due 5 June.

Policy on late assignments

Assignments are due by noon on the specified due date.  While you are encouraged to turn in assignments on time, we do have a liberal late policy.  You have a total of 7 ‘late’ days that can be used among the four assignments without any penalty.  Each additional late day will result in a penalty of a third of a grade (i.e., an A becomes an A−, an A− becomes a B+, etc.).  For example, you may submit each assignment a day late, for a total of four late days, without any penalty; if you submit each assignment two days late, the fourth assignment will be assessed a one day penalty.  In any case, assignments will not be accepted more than 7 days after their due dates.

Contacting course staff

Questions about course material should be sent to the class newsgroup su.class.cs227. The course staff can be contacted at cs227-help@lists.stanford.edu. Assignment submissions should be sent to cs227-submit@lists.stanford.edu. Using these lists rather than emailing the staff directly will ensure a speedy response.

Tentative schedule

Apr

01

03

08

Introduction.  Propositional satisfiability, phase transitions and heavy-tailed behaviour.  Stochastic search, DPLL algorithm, discrete Lagrangian methods [1-7]

 

10

Introduction to CSPs and local consistency algorithms [8]

 

15

17

Classical CSP algorithms: conflict-directed backjumping, forward checking, backmarking, dynamic variable ordering [9,10]

 

22

Dynamic backtracking [11,12].  Decomposition methods [13]

 

 

24

29

Simple Temporal Networks and constraint-based scheduling [14,15]

May

01

Resource Temporal Networks [16,17]

 

06

08

Classical Planning: Causal Link, State Space, HTN, SAT, CSP, and GraphPlan planning [18-22].  Reachability heuristics [23]

 

13

Temporal and resource-based planning [24-26]

 

15

Planning under uncertainty [27-29]

 

20

Integrative SAT and CSP planning; combined planning and scheduling [30-32]

 

22

27

Modelling, symmetry, preferences [33-36].  Complexity results.  Model-based diagnosis and control [37].

 

29

Guest lecturer from Xerox PARC

Jun

03

Student presentations

 

05

No lecture

Reading list

 

Satisfiability

  1. Mitchell, D., Selman, B., and Levesque, H. (1992).  Hard and Easy Distributions of SAT Problems.  In Proc. of AAAI-92, 459-465. http://www.cs.sfu.ca/~mitchell/papers/ai92-hsat.ps
  2. Gomes, C., Selman, B., Crato, N. and Kautz, H. (2000).  Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems. Journal of Automated Reasoning 24, 67-100. http://www.cs.cornell.edu/gomes/jar.pdf
  3. Selman, B., Levesque, H., and Mitchell, D. (1992).  A New Method for Solving Hard Satisfiability Problems. In Proc. of AAAI-92, 440-446. http://www.cs.sfu.ca/~mitchell/papers/ai92-gsat.ps
  4. Gent, I., and Walsh, T. (1993).  Towards an Understanding of Hill-climbing Procedures for SAT.  In Proc. of AAAI-93, 28-33. http://verify.stanford.edu/cs359a/READINGS/walsh.ps
  5. Selman, B., Kautz, H., and Cohen, B. (1994).  Noise Strategies for Improving Local Search.  In Proc. of AAAI-94, 337-343.  http://www.cs.cornell.edu/home/selman/papers-ftp/94.aaai.loc.ps
  6. Li, C. and Anbulagan. (1997). Heuristics Based on Unit Propagation for Satisfiability Problems.  In Proc. of IJCAI-97, 366-371.  http://users.rsise.anu.edu.au/~anbu/papers/IJCAI97Anbulagan.pdf
  7. Wu, Z. and Wah, B. (1999).  Trap Escaping Strategies in Discrete Lagrangian Methods for Solving Hard Satisfiability and Maximum Satisfiability Problems.  In Proc. of AAAI-99, 673-678.  http://www.manip.crhc.uiuc.edu/Wah/papers/C122/C122.ps.gz

Constraint Satisfaction

  1. Van Hentenryck, P., Deville, Y., and Teng, C. (1992).  A Generic Arc-Consistency Algorithm and its Specializations. Artificial Intelligence 57, 291-321.  http://www.cs.brown.edu/~pvh/ac5.ps
  2. Prosser, P. (1993). Hybrid Algorithms for the Constraint Satisfaction Problem.  Computational Intelligence 9(3), 268-299.  http://www.dcs.gla.ac.uk/publications/paperdetails.cfm?id=8104
  3. Bacchus, F. and van Run, P. (1995).  Dynamic Variable Ordering in CSPs.  In Proc. of CP-95, 258-275.  http://www.cs.toronto.edu/~fbacchus/Papers/BvRCP95.pdf
  4. Ginsberg, M. (1993). Dynamic Backtracking.  Journal of AI Research 1, 25-46.  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume1/ginsberg93a.pdf
  5. Bayardo, R. and Schrag, R. (1997).  Using CSP Look-back Techniques to Solve Real-world SAT instances. In Proc. of AAAI-97, 203-208.  http://www.cs.berkeley.edu/~russell/classes/cs289/f04/readings/Bayardo+Schrag:1997.pdf
  6. Jegou, P. and Terrioux, C. (2003). Hybrid Backtracking Bounded by Tree-Decomposition of Constraint Networks. Artificial Intelligence 146 43-75.  http://www.lsis.org/~terriouxc/publis/aij2003.pdf

Temporal and Resource Reasoning

  1. Dechter, R., Meiri, I., and Pearl, J. (1991).  Temporal Constraint Networks.  Artificial Intelligence 49, 61-95. http://www.ics.uci.edu/~csp/r10.pdf
  2. Smith, S. and Cheng, C. (1993). Slack-based Heuristics for Constraint Satisfaction Scheduling.  In Proc. of AAAI-93, 139-144.  http://rakaposhi.eas.asu.edu/cse574/smith-cheng-slack-aaai93.pdf
  3. Laborie, P. (2003). Algorithms for Propagating Resource Constraints in AI Planning and Scheduling. Artificial Intelligence 143, 151-188.  http://www.cs.nmsu.edu/~tson/classes/spring04-579/laborie-resources-aij.pdf
  4. Muscettola, N. (2002).  Computing the Envelope for Stepwise-Constant Resource Allocations.  In Proc. of CP'02, 139-154.  http://ic.arc.nasa.gov/publications/pdf/2001-0308.pdf

Classical Planning

  1. Weld, D. (1994). An Introduction to Least Commitment Planning.  AI Magazine 15(4), 27-61. http://www.cs.washington.edu/homes/weld/papers/pi.pdf (Sections 1-4)
  2. Kautz, H., McAllestar, D., and Selman, B. (1996). Encoding Plans in Propositional Logic.  In Proc. of KR'96, 374-384. http://www.cs.rochester.edu/~kautz/papers/plankr96.ps
  3. Nau, D., Au, T., Ilghami, O., Kuter, U., Murdock, J., Wu, D., and Yaman, F. (2003). SHOP2: An HTN Planning System. Journal of AI Research 20, 379-404. http://www.jair.org/papers/paper1141.html (Sections 2-3.2)

GraphPlan and Heuristics

  1. Bonet, B. and Geffner, H. (1999). Planning as Heuristic Search: New Results. In Proc. of ECP-99, 360-372.  http://www.tecn.upf.es/~hgeffner/html/reports/hsp-r.ps
  2. Blum, A. and Furst, M. (1997).  Fast Planning Through Planning Graph Analysis.  Artificial Intelligence 90, 281-300.  http://www.cs.cmu.edu/~avrim/Papers/graphplan.pdf (Sections 1-5)
  3. Bryce, D. and Kambhampati, S. (2007). A Tutorial on Planning Graph Based Reachability Heuristics.  AI Magazine, 28(1), 47-83.  http://www.ai.sri.com/~bryce/papers/pgSurvey.pdf (Sections 1-4)

Temporal and Resource Planning

  1. Gerevini, A., Saetti, A., and Serina, I. (2003). Planning Through Stochastic Local Search and Temporal Action Graphs in LPG.  Journal of AI Research 20 239-290.  http://www.jair.org/media/1183/live-1183-2194-jair.pdf (Sections 1-3)
  2. Do, M. and Kambhampati, S. (2003). SAPA: A Multi-objective Metric Temporal Planner.  Journal of AI Research 20, 155-194.  http://www.jair.org/media/1156/live-1156-2174-jair.pdf (Sections 1-2)
  3. Hoffmann, J. (2003). The Metric-FF Planning System: Translating "Ignoring Delete Lists" to Numeric State Variables.  Journal of AI Research 20, 291-341. http://www.jair.org/media/1144/live-1144-2158-jair.pdf (Sections 3-5)

Planning Under Uncertainty

  1. Boutilier, C., Dean, T., and Hanks, S. (1999).  Decision-Theoretic Planning: Structural Assumptions and Computational Leverage.  Journal of AI Research 11, 1-94. http://www.jair.org/media/575/live-575-1777-jair.pdf (Sections 1-3)
  2. Smith, D. and Weld, D. (1998).  Conformant Graphplan.  In Proc. of AAAI-98, 889-896  http://ic.arc.nasa.gov/people/de2smith/publications/AAAI98-cgp.pdf
  3. Bonet, B. and Geffner, H. (2000). Planning with Incomplete Information as Heuristic Search in Belief Space.  In Proc. of AIPS-00, 52-61. http://www.ldc.usb.ve/~bonet/reports/aips00-incomplete.ps

Integrative SAT and CSP Planning, and Combined Planning and Scheduling

  1. Smith, D., Frank, J., and Jónsson, A. (2000). Bridging the Gap Between Planning and Scheduling.  Knowledge Engineering Review 15(1), 61-94.  http://ic.arc.nasa.gov/people/de2smith/publications/KER00.pdf
  2. Frank, J. and Jónsson, A. (2003). Constraint-Based Attribute and Interval Planning. Constraints 8, 339-364.  http://ic.arc.nasa.gov/publications/pdf/0313.pdf
  3. R-Moreno, M.D., Oddi, A, Borrajo, D., and Cesta, A. (2006).  IPSS: A Hybrid Approach to Planning and Scheduling Integration.  IEEE Transactions on Knowledge and Data Engineering 18, 1681-1695.  http://atc1.aut.uah.es/~mdolores/Docs/2006/MDRMoreno-IPSS-06.pdf

Advanced Topics

  1. Smith, B. (2006).  Modelling.  In Rossi, van Beek, and Walsh, editors, Handbook of Constraint Programming, chapter 11.  Elsevier. http://www.comp.leeds.ac.uk/bms/Papers/chapter11.pdf
  2. Boddy, M. and Goldman, R. (2005). Tutorial on Domain Modeling for Planning. Tutorial given at ICAPS'05. http://icaps05.uni-ulm.de/documents/tut-material/tu4-allpapers.pdf
  3. Gent, I. and Smith, B. (2003). Symmetry Breaking During Search in Constraint Programming. In Proc. of ECAI-2000, 599-603.  http://www.dcs.st-and.ac.uk/~apes/papers/ecai2000.ps.gz
  4. Larrosa, J. and Schiex, T. (2006).  Soft Constraint Processing.  Tutorial given at CP'06.  http://www.inra.fr/mia/T/schiex/Export/TutorialCP06.pdf
  5. Williams, B. and Nayak, P. (1996). A Model-based Approach to Reactive Self-Configuring Systems. In Proc. of AAAI-96, 971-978.  http://www.qrg.northwestern.edu/papers/Files/qr-workshops/QR96/Williams_1996_Model-Based_Approach_Self-Configuring_Systems.pdf

Optional and additional reading

 

Propositional Satisfiability

  1. Walsh, T. (1998). The Constrainedness Knife-Edge. In Proc. of AAAI-98, 406-411. http://www.cse.unsw.edu.au/~tw/waaai98.ps
  2. Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S. (2001). Chaff: Engineering an Efficient SAT Solver.  In Proc. of DAC'01, 530-535.  http://www.princeton.edu/~chaff/publication/DAC2001v56.pdf

Constraint Satisfaction

  1. Chen, X. and Van Beek, P. (2001). Conflict-directed Backjumping Revisited. Journal of AI Research 14 53-81.  http://www.jair.org/media/788/live-788-1933-jair.pdf
  2. Kondrak, G. and van Beek, P. (1997).  A Theoretical Evaluation of Selected Backtracking Algorithms.  Artificial Intelligence 89(1-2), 365-387 http://ai.uwaterloo.ca/~vanbeek/Publications/ai97.pdf

Planning

  1. Fox, M. and Long, D.  (2003). PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains, Journal of AI Research 20, 61-124.

http://www.jair.org/media/1129/live-1129-2132-jair.pdf

Advanced Topics

  1. Bistarelli, S., Fargier, H., Montanari, U.. Rossi, F., Schiex, T., and Verfaillie, G. (1996). Semiring-based CSPs and Valued CSPs: Basic Properties and Comparison.  In Over-Constrained Systems, 111-150.  LNCS 1106.  Springer. ftp://ftp.cert.fr/pub/verfaillie/ocs.ps
  2. Cohen, D. and Jeavons, P. (2006).  The Complexity of Constraint Languages.  In Rossi, van Beek, and Walsh, editors, Handbook of Constraint Programming, chapter 8.  Elsevier. http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/ComplexityLanguages.pdf
  3. Bylander, T. (1994).  The Computational Complexity of Propositional STRIPS Planning.  Artificial Intelligence 69(1-2), 165-204.  http://www.cs.utsa.edu/~bylander/pubs/artificial-intelligence94.ps.gz
  1. Williams, B., Ingham, M., Chung, S., and Elliott, P. (2003).  Model-based Programming of Intelligent Embedded Systems and Robotic Space Explorers. Proceedings of the IEEE 91(1), 212-237. http://mers.csail.mit.edu/papers/WILLIAMS_IEEE_final_jan03.pdf
  2. Nayak, P. and Williams, B. (1997). Fast Context Switching in Real-time Propositional Reasoning. In Proc. of AAAI-97, 50-56.  http://mers.csail.mit.edu/papers/aaai97.ps

Books