|
Foundations of Artificial Intelligence (FAI) Group
|
|
Seminar: Admissible Search Enhancements
Basics. Seminar, 7 graded ECTS points.
The seminar will be run in a block format. There will be an initial meeting on Wednesday, October 18, 16:15--17:45. All student presentations will be given on a single day after the end of term. A detailed schedule is given below.
All meetings will take place in room 3.06, Building E1 1. The seminar language is English throughout.
All papers in the seminar will be supervised by Prof. Dr. Jörg Hoffmann.
Your task will be to read and understand a piece of research, to write a summary paper in your own words, to give a presentation, and to provide detailed feedback for the paper and presentation of a fellow student.
All email interaction must be pre-fixed with "[SEARCH17-18]" in the email subject.
No plagiarism. It is Ok (and encouraged!) to use web resources to further your understanding of your assigned topic. However, it is inadmissible to use pieces of such material for your summary paper or presentation. Any plagiarism will result in disqualification from the seminar.
Content. State space search is a basic method for analyzing reachability in large deterministic transition systems, across several areas of CS including in particular automatic planning, model checking, and game playing. To tackle the state space explosion -- the systems to be analyzed are exponentially large in the size of their description, and practical systems may have billions of states or more -- one kind of technique that has been instrumental is what we entitle admissible search enhancements here: Techniques that allow to ignore part of the state space without changing the reachability property being analyzed, i.e., preserving the completeness/optimality of the underlying search. Using automatic planning as a uniform framework, we consider four major families of admissible search enhancements, namely partial-order reduction, symmetry reduction, dominance pruning, and decoupled search.
Prerequisites. Participants must have successfully completed an introductory course in Artificial Intelligence. They should be familiar with automatic planning at least to the extent of the material covered in the Artificial Intelligence course; successful participation in one of our Automatic Planning courses will be an advantage, but is not absolutely necessary to follow the seminar.
Registration. The seminar has 8 participation slots, for 8 students. Registration for the seminar will be open from October 1 until October 16 (midnight). Please do not try to register ahead of time; we will only consider applications reaching us within the given time window!
To apply for registration, send an email to Joerg Hoffmann. In the email, give a brief description of your relevant background. In particular, say whether you got a BSc and from which university, and describe previous lectures/seminars you completed in the areas of Artificial Intelligence, Automatic Planning, and Model Checking. For each relevant course, state the grade you obtained in that course. Say a few words regarding why you are interested in participating in the seminar.
You will be notified by email on October 17, informing you whether or not you are registered.
Attention! As there always are more students than we have places, to be fair towards your fellow students please do only sign up if you're really interested in following the seminar through to the end. In particular, according to the new study regulations, you are only allowed to withdraw within three weeks after the briefing of the seminar, i.e., until November 03. Later withdrawal counts as "failed".
Grading. The final grading will be based on:
Summary Paper. For the summary paper, you must use this tex template. Note in particular that you are required to read at least 2 related papers, for the related work section.The seminar paper should be about 4 pages long (not counting the literature list, and in the double-column format of the template). This is a rough guideline, not a strict rule. If you need, say, 5-6 pages to do your paper justice then definitely do so.
Schedule and Deadlines (tentative!).
Note that each topic is associated with a mentor student, who will provide feedback to you, see the following deadlines. If you want to team up with someone specific, do state that in your email.
Read the material associated with your topic carefully, and prepare an initial version of your summary paper, using the tex template given above.
NOTE: The following deadlines marked with "(ca.)" are meant as a guideline. You are required to do these things, but if you do them 3-4 days earlier or later, that is no problem.
Topics. Each participant will be assigned one topic, each of which consists of one paper (in the single case of area 2.2, one paper and a short amendment to that paper). The overall amount and difficulty of the material associated with each topic is roughly balanced.
Area 1: Partial-Order Reduction. (The papers 1. and 2. in this area will be presented in inverse order in the seminar, i.e., first 1.2 then 1.1)
Area 2: Symmetry Reduction.
Area 3: Dominance Pruning.
Area 4: Star-Topology Decoupling.