Departement Informatik, Universität Basel
Departement Informatik, Universität Basel
Departement Informatik, Universität Basel
Departement Informatik, Universität Basel

CS353/4 Seminar Search and Optimization

LecturerMalte Helmert
AssistantsFlorian Pommerening,
Gabriele Röger,
Martin Wehrle
ScheduleThursday, 14.15-16.00
EvaluationSpecified in slides on Schedule and Topics. The deadlines for the software project can be found in the slides "6. Software Project".
Starting date 20 September 2012
RoomSeminar Room 205, 
Bernoullistrasse 16
ContentThe seminar will focus on informed search (search algorithms, heuristics). The software project is on the same topic, particularly emphasizing a structured approach and scientific evaluation.
Target AudienceStudents in the master program Computer Science (and related subjects) 
PrerequisiteFoundations of AI (CS205) or willingness to study the relevant topics independently; C++ programming skills (only for the software project)
RegistrationOnline Services
Credit points3 ECTS for the seminar and 3 ECTS for the (optional) software project

Schedule and Topics

20.09.2012: Search Problems
27.09.2012: Introduction to Mercurial
04.10.2012: Basic Search Algorithms
11.10.2012: No meeting
18.10.2012: Fundamentals
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 2012), pp. 25-32, 2012. (PDF)
Presentation: Christopher Scherb (slides)
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: Luca Rosetto (slides)
25.10.2012: Search Algorithms I
03 Yuima Akagi, Akihiro Kishimoto and Alex Fukunaga.
On Transposition Tables for Single-Agent Search and Planning: Summary of Results.
In Proceedings of the 3rd Annual Symposium on Combinatorial Search (SoCS 2010), pp. 2-9, 2010. (PDF)
Presentation: Christian Mächler (slides)
04 Rong Zhou and Eric A. Hansen.
Breadth-first Heuristic Search.
Artificial Intelligence, 170(4-5):385-408, 2006 (Website; PDF download available from unversity network) Presentation: Salomé Simon (slides)
01.11.2012: Search Algorithms II
05 David A. Furcy.
ITSA*: Iterative Tunneling Search with A*.
In Proceedings of the AAAI Workshop on Heuristic Search, Memory-Based Heuristics and Their Applications, pp. 21-26, 2006. (PDF)
and
Hootan Nakhost and Martin Müller.
Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement.
In Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 121-128, 2010. (PDF)
Presentation: Basil Kohler (slides)
06 David Furcy and Sven Koenig.
Limited Discrepancy Beam Search.
In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 125-131, 2005. (PDF)
Presentation: Michael Niggli (slides)
08.11.2012: Domain Studies
07 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: Sascha Scherrer (slides)
08 John Slaney and Sylvie Thiébaux.
Blocks World Revisited.
Artificial Intelligence 125(1-2):119-153, 2001. (Website; PDF download available from unversity network)
Presentation: Manuela Lütolf (slides)
15.11.2012: Abstraction Heuristics I
09 Joseph C. Culberson and Jonathan Schaeffer.
Pattern Databases.
Computational Intelligence, 14(3):318-334, 1998. (Website; PDF download available from unversity network)
Presentation: Silvan Sievers (slides)
10 Ariel Felner, Richard E. Korf and Sarit Hanan.
Additive Pattern Database Heuristics.
Journal of Artificial Intelligence Research, 22:279-318, 2004. (PDF)
Presentation: Pier Paolo Bortolouzzi (slides)
22.11.2012: Abstraction Heuristics II
11 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: David Adametz (slides)
12 Teresa M. Breyer and Richard E. Korf.
1.6-Bit Pattern Databases.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 39-44, 2010. (PDF)
Presentation: Damian Murezzan (slides)
29.11.2012: General Heuristics: Abstraction
13 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: Severin Gsponder (slides)
14 Patrik Haslum, Blai Bonet, and Hector Geffner.
New Admissible Heuristics for Domain-Independent Planning.
In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), pp. 1163-1168, 2005. (PDF)
Presentation: Kevin Urban (slides)
06.12.2012: General Heuristics: Delete-Relaxation
15 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: Lukas Probst (slides)
16 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 (PDF)
Presentation: Florian Pommerening and Silvan Sievers (slides)
13.12.2012: General Heuristics: Landmarks
17 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: Alexander Haesen (slides)
18 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: Filip-Martin Brinkmann (slides)
20.12.2012: Pruning Methods
19 Neil Burch and Robert Holte.
Automatic Move Pruning Revisited.
In Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS 2012), pp. 18-24, 2012 (PDF)
Presentation: Lukas Beck (slides)
20 Raz Nissim, Udi Apsel and Ronen Brafman.
Tunneling and Decomposition-Based State Reduction for Optimal Planning.
In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), pp. 624-629, 2012 (Website; PDF download available)
Presentation: Manuel Heusner (slides)