CS353 Search & Optimization

Lecturer Malte Helmert
Assistants Florian Pommerening
Gabriele Röger
Jendrik Seipp
Silvan Sievers
Martin Wehrle
Lecture Thursday 15:15 - 17:00; Informatik, Seminarraum 205
Starting Date 19-9-2013
Content The seminar focuses on informed state-space search (search algorithms, heuristics).

In addition to the seminar, interested students can participate in the optional software project (CS354). The project deals with the same topics as the seminar, with an emphasis on a structured approach to developing strong problem solvers and on the scientific evaluation of search algorithms.
Audience Students in the master program Computer Science (and related subjects).
The number of participants is limited to 16. Places are allocated on a first come, first served basis.
Prerequisites Foundations of AI (CS205) or willingness to study the relevant topics independently; C++ programming skills (only for the software project)
Registration Registration
Credit Points 3 ECTS Points
Consulting By appointment
Lectures List No. 31706-01

Schedule and Topics

19.09.2013: Organization, Schedule & Seminar Topics
26.09.2013: Background: Search Problems & Project Topics
03.10.2013: Background: Basic Search Algorithms
10.10.2013: Background: Mercurial
17.10.2013: Fundamentals I
01 Ethan Burns, Matthew Hatem, Michael J. Leighton and Wheeler Ruml.
Implementing Fast Heuristic Search Code.
In Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS 2013), pp. 25-32, 2013. (PDF)
Presentation: Gabi Röger (slides; screen), (slides; printer)
24.10.2013: Fundamentals II
02 Robert C. Holte.
Common Misconceptions Concerning Heuristic Search.
In Proceedings of the 3rd Annual Symposium on Combinatorial Search (SoCS 2010), pp. 46-51, 2010. (PDF)
Presentation: Claudio Marxer (slides; screen), (slides; printer)
31.10.2013: Domain Study
03 Andreas Junghanns and Jonathan Schaeffer.
Sokoban: Enhancing General Single-Agent Search Methods Using Domain Knowledge.
Artificial Intelligence, 129(1-2):219-251, 2001. (Website; PDF download available from unversity network)
Presentation: Pascal Düblin (slides)
07.11.2013: Abstraction Heuristics I
04 Joseph C. Culberson and Jonathan Schaeffer.
Pattern Databases.
Computational Intelligence, 14(3):318-334, 1998. (Website; PDF download available from unversity network)
Presentation: Patrick von Reth (slides)
14.11.2013: Abstraction Heuristics II
05 Fan Yang, Joseph C. Culberson, Robert Holte, Uzi Zahavi and Ariel Felner.
A General Theory of Additive State Space Abstractions.
Journal of Artificial Intelligence Research, 32:631-662, 2008. (PDF)
Presentation: Jendrik Seipp (slides)
21.11.2013: General Heuristics: Abstraction
06 Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet and Sven Koenig.
Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning.
In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), pp. 1007-1012. 2007. (PDF)
Presentation: Silvan Sievers (slides)
Due date Project phase 1: Uninformed search
28.11.2013: General Heuristics: Delete-Relaxation I
07 Blai Bonet and Héctor Geffner.
Planning as Heuristic Search.
Artificial Intelligence, 129(1-2):5-33, 2001 (Website; PDF download available from unversity network)
Presentation: Stefano Branco
05.12.2013: General Heuristics: Delete-Relaxation II
08 Emil Keyder and Héctor Geffner.
Heuristics for Planning with Action Costs Revisited.
17th European Conferenceon Artificial Intelligence (ECAI 2008), pp. 588-592. 2008. (PDF download available from unversity network)
Presentation: Behrouz Tajoddin (slides)
12.12.2013: General Heuristics: Landmarks I
09 Silvia Richter and Matthias Westphal.
The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.
Journal of Artificial Intelligence Research, 39:127-177, 2010 (PDF)
Presentation: Martin Wehrle
19.12.2013: General Heuristics: Landmarks II
10 Erez Karpas and Carmel Domshlak.
Cost-optimal Planning with Landmarks.
In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 1728-1733, 2009. (PDF)
Presentation: Florian Pommerening
Due date Project phase 2: Informed search
Due date Project phase 3: Improvements