Foundations of Artificial Intelligence (FAI) Group
divider line

Seminar: Heuristic Search Algorithms

Organization. The seminar will take place on Mondays, 14:15--15:45, in room 3.06, Building E1 1.

Seminar, 7 graded ECTS points.

The seminar language is English throughout (summaries/talks/seminar papers).

Each seminar participant will be supervised by either of Prof. Dr. Joerg Hoffmann, Dr. Michael Katz, or Dr. Peter Kissmann.

The seminar is fully booked, please do not send us emails inquiring for open slots.

If you're participating in the seminar, have a look at the slides giving an overview of the seminar and what we expect from you.

Abstract. Heuristic Search is one of the most prominent problem-solving methods in Artificial Intelligence, and is used widely also in other areas of Computer Science. The technique has two key ingredients: the heuristic function, which estimates the remaining cost of any given search state, and the search algorithm, which specifies how to use these estimates during search. The seminar is concerned with that latter ingredient. While a few well-known algorithms, such as A*, are part of the regular Computer Science curriculum, there is an entire universe of different search algorithms to choose from, and that choice typically has a large impact on performance. The seminar will cover instances of the most important search algorithm groups, and important observations about their properties.

Prerequisites. Participants should have successfully completed an introductory course in Artificial Intelligence, and should be familiar specifically with the basics of Search, i.e., the A* algorithm etc.

Expectations/Grades. Each participant will be assigned one seminar session, in which he/she will give a 30 minute presentation on one paper. Before the presentation, you are required to send a brief summary (half a page by email), that your fellow students will read to prepare themselves for your talk. After the talk, you will write a seminar paper giving a more detailed summary. Participation in all talks is obligatory.

Your final grade will be based on:

ATTENTION! Plagiarism is absolutely disallowed. For some of the papers, you will be able to find resources in the web. It is Ok to use these to further your understanding of the paper. However, it is completely inadmissible to use pieces of such material for your summary, talk, or seminar paper. Any plagiarism will result in disqualification from the seminar.

Procedure for your seminar work. Each seminar participant, will, together with the supervisor of his/her paper, follow the following procedure:

  1. You read the paper.
  2. At least 2 weeks prior to your seminar slot, you meet with your supervisor to discuss the paper.
  3. At least 10 days prior to your seminar slot, you send your supervisor the first version of your presentation slides (remember that your presentation should be 30 minutes long), as well as the first version of your brief paper summary. The slides MUST be in PDF format.
  4. At least 1 week prior to your seminar slot, you meet with your supervisor to discuss your slides and summary.
  5. At least 2 days prior to your seminar slot, you send your supervisor the final version of your slides, as well as your final brief paper summary. Your supervisor will take care of sending the paper summary to all seminar participants.
  6. In your seminar slot, you give the presentation, and lead the discussion on your paper.
  7. Before the end of term, you send your supervisor your seminar paper summarizing the paper in more detail.

ATTENTION! It is YOUR responsibility to make sure you comply with these deadlines. Your supervisor will not prompt you to act; you need to contact your supervisor to arrange the meetings etc.

The brief paper summary should be prepared in plain text (as a .txt file or in an email), and should be up to 1 page long. Its structure should be:

For the seminar paper, you must use this tex template. The seminar paper should be 3-5 pages long (in the double-column format of the template). The deadline for seminar papers is March 15, 2013. We encourage you to submit your seminar paper earlier.

Seminar Material. Each participant's task will be to understand and present one scientific publication introducing or analyzing a particular heuristic search algorithm. We next give the provisional ordered list of dates and algorithm names; a more detailed listing of the papers is given below.

Date Algorithm Name/Description Supervisor
Mon, 15.10. GSAT Joerg Hoffmann
Mon, 22.10. WalkSAT Joerg Hoffmann
Mon, 29.10. Local Search Topology Joerg Hoffmann
Mon, 05.11. A* Peter Kissmann
Mon, 12.11. Weighted A* Peter Kissmann
Mon, 19.11. Optimistic Search Peter Kissmann
Mon, 26.11. Explicit Estimation Search Peter Kissmann
Mon, 03.12. A* Performance Upper Bounds Michael Katz
Mon, 10.12. A* Performance Lower Bounds Michael Katz
Mon, 17.12. IDA* Peter Kissmann
Mon, 07.01. Breadth First Heuristic Search Michael Katz
Mon, 14.01. LifeLong Planning A* Joerg Hoffmann
Mon, 21.01. LRTA* Joerg Hoffmann