Kaisa_2012_3_photo by Veikko Somerpuro

Planning is the reasoning side of acting, aiming at realizing strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles, in order to achieve some prestated objectives. Automated planning (or AI planning) is a central and active area of artificial intelligence (AI) research that aims at developing in-depth computational understanding of planning and algorithms for different forms of computationally hard, i.e., NP-hard, planning tasks.

In this MSc level seminar, we will get acquainted with recent advances in AI planning, covering topics such as central algorithmic approaches to planning, planning heuristics, representations aspects, and computational complexity of different types of planning tasks. The course is based on recent research articles on AI planning, and consists of writing a scientific report and giving a presentation based on a chosen research article, as well as acting as an opponent and peer-reviewer for other students. Hands-on project work is also possible as an alternative to peer-review.

A certain level of algorithmic/mathematical maturity is expected from the participants. Please consult some of the research articles listed under "MATERIAL" for an impression of the seminar contents.

The seminar is intended for MSc students interested in algorithmic and computational aspects of artificial intelligence. PhD students are also welcome. Attendance is limited to at most 12 students due to the organization of the seminar.

For practical arrangements and the introductory slides from the first meeting on Sep 19, see under "MATERIAL".

For the actual seminar presentation schedule, see under "TIMETABLE".

Enrol

Timetable

SEMINAR SCHEDULE

November 14:
-student presentation 1 (opponent: ?)
-student presentation 2 (opponent: ?)

November 21:
-student presentation 3 (opponent: ?)
-student presentation 4 (opponent: ?)

November 28:
-student presentation 5 (opponent: ?)
-student presentation 6 (opponent: ?)

December 5:
-student presentation 7 (opponent: ?)
-student presentation 8 (opponent: ?)

December 12: final report deadline
December 18: final peer-review deadline

DateTimeLocation
Wed 19.9.2018
12:15 - 14:00
Wed 7.11.2018
14:15 - 16:00
Wed 14.11.2018
14:15 - 16:00
Wed 21.11.2018
14:15 - 16:00
Wed 28.11.2018
14:15 - 16:00
Wed 5.12.2018
14:15 - 16:00
Wed 12.12.2018
14:15 - 16:00

Material

INTRODUCTORY SLIDES FROM THE FIRST SEMINAR MEETING on Sep 19 (see here also for practical arrangements):
http://cs.helsinki.fi/matti.jarvisalo/planning-seminar18-intro.pdf

BACKGROUND MATERIAL:
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:
http://dai.fmph.uniba.sk/~sefranek/kri/handbook/chapter22.pdf

-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
http://projects.laas.fr/planning/
Slides: http://www.cs.umd.edu/~nau/planning/slides/

-Overview of planning algorithms:
Hector Geffner:
The model-based approach to autonomous behavior: Prospects and challenges. Intelligenza Artificiale 5(2): 163-169 (2011)
https://content.iospress.com/articles/intelligenza-artificiale/ia024

-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)
https://ieeexplore.ieee.org/document/1413173/

-A more general overview of the "model+solve" approach to solving hard problems
Hector Geffner:
Artificial Intelligence: From programs to solvers. AI Commun. 27(1): 45-51 (2014)
https://pdfs.semanticscholar.org/6d3a/f79df633b5e8c576fa0c1d6aaf5cf859cd...

====================================================================================================

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.

PLANNING ALGORITHMS:

Blai Bonet, Hector Geffner:
Planning as heuristic search.
Artificial Intelligence 129(1-2): 5-33 (2001)
https://www.sciencedirect.com/science/article/pii/S0004370201001084?via%...

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.
https://jair.org/index.php/jair/article/view/10276

Malte Helmert.
The Fast Downward planning system.
Journal of Artificial Intelligence Research, 26:191–246, 2006.
https://jair.org/index.php/jair/article/view/10457

Silvia Richter and Matthias Westphal.
The LAMA planner: Guiding cost-based anytime planning with landmarks.
Journal of Artificial Intelligence Research, 39:127–177, 2010.
https://jair.org/index.php/jair/article/view/10667

Jussi Rintanen, Keijo Heljanko, Ilkka Niemelä:
Planning as satisfiability: parallel plans and algorithms for plan search.
Artificial Intelligence 170(12-13): 1031-1080 (2006)
https://www.sciencedirect.com/science/article/pii/S0004370206000774?via%...

Jussi Rintanen:
Planning as satisfiability: Heuristics.
Artificial Intelligence 193: 45-86 (2012)
https://www.sciencedirect.com/science/article/pii/S0004370212001014?via%...

Michael Cashmore, Maria Fox, Enrico Giunchiglia:
Planning as Quantified Boolean Formula.
ECAI 2012: 217-222
http://ebooks.iospress.nl/publication/6975

Michael Cashmore, Maria Fox, Enrico Giunchiglia:
Partially Grounded Planning as Quantified Boolean Formula.
ICAPS 2013
http://www.aaai.org/ocs/index.php/ICAPS/ICAPS13/paper/view/5991

Carmel Domshlak, Erez Karpas, and Shaul Markovitch.
Online speedup learning for optimal planning.
Journal of Artificial Intelligence Research, 44:709–755, 2012.
https://jair.org/index.php/jair/article/view/10776

Ethan Burns, Wheeler Ruml, Minh Binh Do:
Heuristic Search When Time Matters.
Journal of Artificial Intelligence Research 47: 697-740 (2013)
https://jair.org/index.php/jair/article/view/10831

REPRESENTATIONS:

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.
https://jair.org/index.php/jair/article/view/10352

Hector Palacios and Hector Geffner.
Compiling uncertainty away in conformant planning problems with bounded width.
Journal of Artificial Intelligence Research, 35:623–675, 2009.
https://jair.org/index.php/jair/article/view/10618

HEURISTICS AND ABSTRACTIONS:

Craig Knoblock.
Automatically generating abstractions for planning.
Artificial Intelligence, 68(2):243–302, 1994
https://www.isi.edu/integration/papers/knoblock94-aij.pdf

Jörg Hoffmann.
Analyzing search topology without running any search: On the connection between causal graphs and h+.
Journal of Artificial Intelligence Research, 41:155–229, 2011.
https://jair.org/index.php/jair/article/view/10709

Michael Katz and Carmel Domshlak.
Implicit abstraction heuristics.
Journal of Artificial Intelligence Research, 39:51–126, 2010
https://jair.org/index.php/jair/article/view/10666

Florian Pommerening, Gabriele Röger, Malte Helmert, Blai Bonet:
LP-Based Heuristics for Cost-Optimal Planning.
ICAPS 2014
https://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7892

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.
https://dl.acm.org/citation.cfm?id=2559951

PLANNING COMPETITIONS:

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.
https://doi.org/10.1016/j.artint.2008.10.012

APPLICATIONS:

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.
https://jair.org/index.php/jair/article/view/10693

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.
https://jair.org/index.php/jair/article/view/10773

COMPLEXITY OF PLANNING:

Bernhard Nebel.
On the compilability and expressive power of propositional planning formalisms.
Journal of Artificial Intelligence Research, 12:271–315, 2000.
https://www.jair.org/index.php/jair/article/view/10258

Christer Bäckström, Peter Jonsson:
Time and Space Bounds for Planning.
Journal of Artificial Intelligence Research 60: 595-638 (2017)
https://jair.org/index.php/jair/article/view/11092

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)
https://www.sciencedirect.com/science/article/pii/S002200001500029X?via%...

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.
https://doi.org/10.1016/0004-3702(94)00080-K

Conduct of the course

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!

Description

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