CS 227
Reasoning Methods in Artificial Intelligence
Handout #3: Reading List

Core 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.cornell.edu/selman/papers/pdf/96.kr.plan.pdf
  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://rakaposhi.eas.asu.edu/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. 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. http://www.inra.fr/mia/T/schiex/Export/ocs.ps.gz
  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

Model-based Diagnosis and Control

  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