Introduction

The second part of the course will concern "automated planning" (a.k.a. "AI planning").

Organisational Stuff

Assignement of students to topics (or topics to students):

Topic	Covered by
1. Representation	Debdeep, Jason, Yogesh
2. Search and Heuristics	Debdeep, Neil, Priscilla
3. Planning with Time and Scheduling	Amanda, Yogesh
4. Planning in the Real World	Patrik
5. The Planning Competition	Amanda, Jason
6. Learning in Planning	Neil, Priscilla

Schedule of presentations: To take place during regular lecture hours, last two weeks in october (15th - 19th; 22nd - 26th). Order of the presentations does not necessarily have to be consistent with the numbering of the topics.

Bibliography

All IJCAI papers can be found at ijcai.org.
Papers in the Journal of AI Research can be found at jair.org.
Many papers are also available from the authors webpages.

Topic 1: Representation

Planning problem description languages; expressivity and complexity; compilation and conversion between languages.

• Bylander, T., "Complexity Results for Planning". In Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI'91), 1991, pp. 274 - 279.
• Erol, K., Nau, D. and Hendler, J., "HTN Planning: Complexity and Expressivity". In "Proc. National Conference on Artificial Intelligence (AAAI'94), 1994, pp. 1123 - 1128.
• Thiebaux, S., Hoffmann, J. and Nebel, B., "In Defense of PDDL Axioms". In Proc. 18th International Conference on Artificial Intelligence (IJCAI'03), 2003, pp. 961 - 968.
• Nebel, B., "On the Compilability and Expressive Power of Propositional Planning Formalisms". Journal of AI Research vol. 12, 2000, pp. 271 - 315.
• Helmert, M., "A Planning Heuristic Based on Causal Graph Analysis". In Proc. 14th International Conference on Automated Planning \& Scheduling (ICAPS'04), 2004, pp. 161 - 170. Note: First part of the paper briefly discusses the SAS formalism and conversion from STRIPS to SAS.

Preprocessing, analysis and other kinds of inference.

• Hoffmann, J. and Koehler, J., "Handling of Inertia in a Planning System". Technical report 122, Institute for Computer Science, Albert-Ludwigs Universität, Freiburg, 2000.
• Nebel, B., Dimopoulos, Y. and Koehler, J., "Ignoring Irrelevant Facts and Operators in Plan Generation". In "Proc. 4th European Conference on Planning (ECP'97), 1997, pp. 338 - 350.
• Fox, M. and Long, D., "The Automatic Inference of State Invariants in TIM". Journal of AI Research vol. 9, 1998, pp. 367 - 421.
• Haslum, P., "Reducing Accidental Complexity in Planning Problems". In Proc. 20th International Joint Conference on AI (IJCAI'07), 2007.

Topic 2: Search and Heuristics

Heuristic state-space search.

• Bonet, B. and Geffner, H., "Planning as Heuristic Search". Artificial Intelligence vol. 129, 2001, pp. 5 - 33.
• Blum, A.L. and Furst, M.L., "Fast Planning through Graph Analysis". Artificial Intelligence vol. 90, 1997, pp. 281 - 300.
• Hoffmann, J. and Nebel, B., "The FF Planning System: Fast Plan Generation Through Heuristic Search". Journal of AI Research vol. 14, 2001, pp. 253 - 302.
• Helmert, M., "The Fast Downward Planning System", Journal of AI Research vol. 26, 2006, pp 191 - 246.
• Haslum, P. Bonet, B. and Geffner, H., "New Admissible Heuristics for Domain-Independent Planning". In Proc. 20th National Conference on AI (AAAI'05), 2005, pp. 1163 - 1168.
• Kambhampati, S. and Bryce, D., "Planning Graph Based Reachability Heuristics". Tutorial presented at ICAPS'06 and IJCAI'07. Materials available at http://rakaposhi.eas.asu.edu/pg-tutorial/.

Partial-order planning, encodings in SAT/CSP, and the like.

• McAllester, D. and Rosenblitt, D., "Systematic Nonlinear Planning". In Proc. 9th National Conference on Artificial Intelligence (AAAI'91), 1991.
• Kautz, H. and Selman, B., "Unifying SAT-based and Graph-based Planning". In Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI'99), 1999, pp. 318 - 325.
• Do, M.B. and Kambhampati, S., "Solving Planning-Graph by Compiling it into CSP". In Proc. 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00), 2000, pp. 82 - 91.
• Rintanen, J., Heljanko, K. and Niemelä, I., "Planning as satisfiability: parallel plans and algorithms for plan search". Artificial Intelligence vol. 170 (12-13), 2006, pp. 1031 - 1080.

From the cutting edge... At this years ICAPS conference (taking place 22nd - 26th of september), will be held a workshop called Heuristics for Domain-Independent Planning: Progress, Ideas, Limitations, Challenges. The workshop program contains many interesting papers, but I particularly recommend the following:

• Michael Katz and Carmel Domshlak, "Structural Patterns Heuristics".
• Emil Keyder and Hector Geffner, "Set-Additive and TSP Heuristics for Planning with Action Costs and Soft Goals".
• Malte Helmert and Robert Mattmüller, "Accuracy of Admissible Heuristic Functions in Selected Planning Domains".

Note: Papers should be available on the workshop webpage soon. If not, ask me for a copy.

Topic 3: Planning with Time and Scheduling

Planners that deal with (some aspects of) temporal planning.

• Penberthy, J.S. and Weld, D.S., "Temporal Planning with Continous Change". In Proc. 12th National Conference on Artificial Intelligence (AAAI'94), 1994, pp. 1010 - 1015.
• Jonsson, A., Morris, P., Muscettola, N., Rajan, K. and Smith, B., "Planning in Interplanetary Space: Theory and Practice". In Proc. 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00), 2000, pp. 177 - 186.
• Smith, D.E. and Weld, D.S., "Temporal Planning with Mutual Exclusion Reasoning". In Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI'99), 1999, pp. 326 - 333.
• Haslum, P. and Geffner, H., "Heuristic Planning with Time and Resources". In Proc. 6th European Conference on Planning (ECP'01), 2001, pp. 121 - 132.
• Vidal, V. and Geffner, H., "Branching and pruning: An optimal temporal POCL planner based on constraint programming". Artificial Intelligence vol. 170, 2006, pp. 298 - 335.

Temporal planning models: PDDL2.1, and it's relation to classical planning.

• Fox, M. and Long, D. "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains". Journal of AI Research vol. 20, 2003, pp. 61 - 124.
• JAIR vol. 20 also contains several short commentaries on PDDL2.1 (Bacchus, Boddy, Geffner, McDermott and Smith).
• Cushing, W., Kambhampati, S., Mausam, Weld, D.S., "When is Temporal Planning Really Temporal?". In Proc. 20th International Joint Conference on Artificial Intelligence (IJCAI'07), 2007, pp. 1852 - 1859.
• Rintanen, J., "Complexity of Concurrent Temporal Planning". To appear in Proc. 17th International Conference on Automated Planning and Scheduling (ICAPS'07), 2007. Available at http://users.rsise.anu.edu.au/~jussi/.

Scheduling.

• Brucker, P., Drexl, A., Möhring, R., Neumann, K. and Pesch, E., "Resource-constrained project scheduling: Notation, classification, models, and methods". European Journal of Operational Research vol. 112 (1), 1999, pp. 3 - 41.
• Herroelen, W., Demeulemeester, E. and De Reyck, B., "A classification scheme for project scheduling problems". Technical Report 9727, Department of Applied Economics, Katholieke Universiteit Leuven, 1997. (Looks like many cite this report, but I haven't found it on-line anywhere.)
• Smith, S.F. and Zimmerman, T.L., "Planning Tactics within Scheduling Problems". In Working Notes of the ICAPS'04 Workshop on Integrating Planning into Scheduling, 2004, pp. 83 - 90. Available at http://pst.istc.cnr.it/wipis-at-icaps-04/. (For more background on the problem described in this paper, see next paper.)
• Becker, M.A. and Smith, S.F., "Mixed-Initiative Resource Management: The AMC Barrel Allocator". In Proc. 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'00), 2000, pp. 32 - 41.

More to come...

Topic 4: Planning in the Real World

...

Topic 5: The Planning Competition

Summary papers from the first four competitions.

• Drew McDermott, "The 1998 AI Planning Systems Competition". AI Magazine vol. 21 (2), 2000, pp. 35 - 55. Available at ftp://ftp.cs.yale.edu/pub/mcdermott/papers/aimag-pub.ps.gz. (This paper is by the 1998 competition organiser.)
• Derek Long et al., "The AIPS-98 Planning Competition". AI Magazine vol. 21 (2), 2000, pp. 13 - 34. (This is a joint paper by all the 1998 competitors.)
• Fahiem Bacchus, "The AIPS'00 Planning Competition". AI Magazine vol. 22 (3), 2001, 47 - 56.
• Derek Long and Maria Fox, "The 3rd International Planning Competition: Results and Analysis", Journal of AI Research, vol. 20, 2003, pp. 1 - 59.
• Jörg Hoffmann and Stefan Edelkamp, "The Deterministic Part of IPC-4: An Overview", Journal of AI Research, vol. 24, 2005, pp. 519 - 579. (See also the JAIR special track.)
• Links to each competitions webpage can be found at icaps-conference.org.

Various kinds of analysis of benchmark domains/problems.

• Hoffmann, J., "Local Search Topology in Planning Benchmarks: An Empirical Analysis". In Proc. 17th International Joint Conference on Artificial Intelligence (IJCAI'01), 2001, pp. 453 - 458.
• Hoffmann, J., "Local Search Topology in Planning Benchmarks: A Theoretical Analysis". In Proc. 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS'02), 2002, pp. 92 - 100.
• Helmert, M, "Complexity Results for Standard Benchmark Domains in Planning". Artificial Intelligence vol. 143 (2), 2003, pp. 219 - 262. (Covers domains of the 1st and 2nd competition.)
• Helmert, M., "New Complexity Results for Classical Planning Benchmarks". In Proc. 16th International Conference on Automated Planning and Scheduling (ICAPS'06), 2006, pp. 52 - 61. (Covers domains of the 3rd and 4th competition.)
• The program of the upcomming ICAPS'07 workshop on the International Planning Competition: Past, Present and Future contains several papers that offer analyses of benchmark domains from past competitions, e.g., the papers by Will Cushing et al.; Iain Little and Sylvie Thiebaux; and myself ;) Note that papers are available from the workshop webpage: click on "Accepted Papers".

Comments and criticisms related to the competition.

• Howe, A. and Dahlman, E., "A Critical Assessment of Benchmark Comparison in Planning". Journal of AI Research vol. 17, 2002, pp. 1 - 33.
• Wilkins, D.E. and DesJardins, M., "A Call for Knowledge-Based Planning". AI Magazine vol. 22 (1), 2001, pp. 99 - 115.
• The program of the upcomming ICAPS'07 workshop on the International Planning Competition: Past, Present and Future also contains some papers providing interesting discussions on the aims and impact of the IPC series.

Topic 6: Learning in Planning

Note: I'm not an expert on machine learning, or its use in planning. I've selected the following papers because I believe they illustrate diverse possibilities for integrating learning into planning (i.e., they're about learning different things). There may be other, and better, works on these topics that I'm unaware of.

• Aberdeen, D. and Buffet, O., "Temporal Probabilistic Planning with Policy-Gradients". In Proc. 17th International Conference on Automated Planning and Scheduling (ICAPS'07), 2007 (still available from Doug's old home page).
• Yoon, S., Fern, A. and Givan, R., "Learning Heuristic Functions from Relaxed Plans". In Proc. 16th International Conference on Automated Planning and Scheduling (ICAPS'06), 2006 (available from Sungwook's home page).
• Hogg, C., and Munoz-Avila, H., "Learning Hierarchical Task Networks from Plan Traces". In ICAPS'07 workshop on AI Planning and Learning.
• Roberts, M., Howe, A. and Flom, L., "Learned Models of Performance for Many Planners". In ICAPS'07 workshop on AI Planning and Learning.
• Botea A., Enzenberger M., Müller M., and Schaeffer J., "Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators". In Journal of AI Research vol. 24, 2005, pp. 581-621.
• Vrakas, D., Tsoumakas, G., Bassiliades, N., and Vlahavas, I., "Learning rules for adaptive planning". In Proc. 13th International Conference on Automated Planning and Scheduling (ICAPS'03), 2003, pp. 82-91.

Materials

• Slides from the first meeting.
• A short guide to writing domain and problem definitions in PDDL (see also the "Modelling the Wumpus World in PDDL" example).
• Slides on temporal planning.
• Slides on planning in the real world (tm).