INTRODUCTORY SLIDES FROM THE FIRST SEMINAR MEETING on Sep 19 (see here also for practical arrangements):
The following list gives some more general background material on automated planning. See further below for the actual seminar topics.
-Handbook of Knowledge Representation, Chapter 22 on Automated Planning:
-Freely available book on planning and acting:
Malik Ghallab, Dana S. Nau, Paolo Traverso:
Automated Planning and Acting. Cambridge University Press 2016, ISBN 978-1-107-03727-4
-Overview of planning algorithms:
The model-based approach to autonomous behavior: Prospects and challenges. Intelligenza Artificiale 5(2): 163-169 (2011)
-Overview of constraint satisfaction based planning algorithms:
Alexander Nareyek, Eugene C. Freuder, Robert Fourer, Enrico Giunchiglia, Robert P. Goldman, Henry A. Kautz, Jussi Rintanen, Austin Tate:
Constraints and AI Planning. IEEE Intelligent Systems 20(2): 62-72 (2005)
-A more general overview of the "model+solve" approach to solving hard problems
Artificial Intelligence: From programs to solvers. AI Commun. 27(1): 45-51 (2014)
SEMINAR TOPICS LIST:
The seminar material consists of recent research articles on different aspects of AI planning. Each student will choose a topic, typically consisting of one research articles, and will prepare a written report and an oral presentation based on the chosen topic.
Articles available as potential seminar topics are listed below. The topics are selected on a first-come-first-served basis: in case you want to choose a topic already before the first seminar meeting, please contact to seminar organisers by email.
Topics outside this list are very welcome! In case you want to propose or consider a topic outside the list, please contact the seminar organisers by email.
Blai Bonet, Hector Geffner:
Planning as heuristic search.
Artificial Intelligence 129(1-2): 5-33 (2001)
Jörg Hoffmann and Bernhard Nebel.
The FF planning system: Fast plan generation through heuristic search.
Journal of Artificial Intelligence Research, 14:253–302, 2001.
The Fast Downward planning system.
Journal of Artificial Intelligence Research, 26:191–246, 2006.
Silvia Richter and Matthias Westphal.
The LAMA planner: Guiding cost-based anytime planning with landmarks.
Journal of Artificial Intelligence Research, 39:127–177, 2010.
Jussi Rintanen, Keijo Heljanko, Ilkka Niemelä:
Planning as satisfiability: parallel plans and algorithms for plan search.
Artificial Intelligence 170(12-13): 1031-1080 (2006)
Planning as satisfiability: Heuristics.
Artificial Intelligence 193: 45-86 (2012)
Michael Cashmore, Maria Fox, Enrico Giunchiglia:
Planning as Quantified Boolean Formula.
ECAI 2012: 217-222
Michael Cashmore, Maria Fox, Enrico Giunchiglia:
Partially Grounded Planning as Quantified Boolean Formula.
Carmel Domshlak, Erez Karpas, and Shaul Markovitch.
Online speedup learning for optimal planning.
Journal of Artificial Intelligence Research, 44:709–755, 2012.
Ethan Burns, Wheeler Ruml, Minh Binh Do:
Heuristic Search When Time Matters.
Journal of Artificial Intelligence Research 47: 697-740 (2013)
Maria Fox and Derek Long.
PDDL2.1: An extension to PDDL for expressing temporal planning domains.
Journal of Artificial Intelligence Research, 20:61–124, 2003.
Hector Palacios and Hector Geffner.
Compiling uncertainty away in conformant planning problems with bounded width.
Journal of Artificial Intelligence Research, 35:623–675, 2009.
HEURISTICS AND ABSTRACTIONS:
Automatically generating abstractions for planning.
Artificial Intelligence, 68(2):243–302, 1994
Analyzing search topology without running any search: On the connection between causal graphs and h+.
Journal of Artificial Intelligence Research, 41:155–229, 2011.
Michael Katz and Carmel Domshlak.
Implicit abstraction heuristics.
Journal of Artificial Intelligence Research, 39:51–126, 2010
Florian Pommerening, Gabriele Röger, Malte Helmert, Blai Bonet:
LP-Based Heuristics for Cost-Optimal Planning.
Malte Helmert, Patrik Haslum, Jörg Hoffmann, and Raz Nissim.
Merge & shrink abstraction: A method for generating lower bounds in factored state spaces.
Journal of the ACM 61(3), 2014.
Alfonso Gerevini, Patrik Haslum, Derek Long, Alessandro Saetti, and Yannis Dimopoulos.
Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners.
Artificial Intelligence, 173(5-6):619–668, 2009.
Wheeler Ruml, Minh Binh Do, Rong Zhou, and Markus P. J. Fromherz.
On-line planning and scheduling: An application to controlling modular printers.
Journal of Artificial Intelligence Research, 40:415–468, 2011.
Jörg Hoffmann, Ingo Weber, and Frank Michael Kraft.
SAP speaks PDDL: Exploiting a software-engineering model for planning in business process management.
Journal of Artificial Intelligence Research, 44:587–632, 2012.
COMPLEXITY OF PLANNING:
On the compilability and expressive power of propositional planning formalisms.
Journal of Artificial Intelligence Research, 12:271–315, 2000.
Christer Bäckström, Peter Jonsson:
Time and Space Bounds for Planning.
Journal of Artificial Intelligence Research 60: 595-638 (2017)
Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
A complete parameterized complexity analysis of bounded planning.
J. Comput. Syst. Sci. 81(7): 1311-1332 (2015)
Kutluhan Erol, Dana S. Nau, and V. S. Subrahmanian.
Complexity, decidability and undecidability results for domain-independent planning.
Artificial Intelligence, 76(1–2):75–88, 1995.
The course work consists of
-giving a 40 min presentation,
-writing a 10-15 page scientific report (plus references),
-acting as an opponent during on presentation, and
-peer-review of two student reports.
Hands-on project work can also be done as an alternative to peer-review. Please let the seminar organizers know if you are interested in a hands-on project!
Master's Programme in Computer Science
available to students from other degree programmes?
Course CSM12101 Design and Analysis of Algorithms, or equivalent knowledge and skills.
To continue with a Master's thesis in computer science related to the topic of the seminar.
Courses: CSM12107 Combinatorial Optimization, CSM12114 Automated Logical Reasoning.
An ability to give scientific presentations. An ability to peer-review and give feedback on written work and on presentations. Improved scientific writing skills on discrete algorithms topics in general and in AI planning in particular. In-depth theoretical and/or partical understanding of an advanced topic in discrete algorithms, especially within AI planning. Experience in implementing and experimentally evaluating AI planning techniques.
After (or in exceptional cases at the same time as) the course CSM12101 Design and Analysis of Algorithms.
The seminar is focused on fundamentals and state-of-the-art algorithmic approaches to AI planning.
Selected scientific articles on automated/AI planning.
Suggestions on supplemental works will be made available at the time the seminar starts.
Grading is 1..5. Presentation and written work of the seminar part are evaluated with a common grade. The 2-cr project part can be evaluated also as pass/fail.
The final grade is a weighted average of the parts.
The course is primarily available as a 5-cr seminar consisting of a seminar presentation, written work, peer review, and a hands-on independent project work.
The course can be separated into a 3-cr seminar part and into a 2-cr implementation project part, which can be taken independently. The seminar part typically includes a presentation, written work, and peer review. A typical project work focuses on implementing an algorithm and its empirical evaluation, reported as a (e.g. poster) presentation and short report.
Matti Järvisalo, Bernhard Bliem