Foundations of Artificial Intelligence (FAI) Group

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:

• Your brief paper summary.
• Your technical talk + following discussion.
• Participation in discussions of other papers.
• Your seminar paper.

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:

• Summarize the three most important points of the paper.
• Summarize the contribution of the paper.
• Indicate problems / flaws of the paper.
• Indicate further research directions.

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.

• GSAT. Selman, Levesque, Mitchell: "A New Method for Solving Hard Satisfiability Problems", AAAI, 1992. Short Description: Hill-climbing procedure for SAT. Extremely competitive at the time, spawned a huge body of follow-up research that dominated the SAT scene during the middle 90s.
• WalkSAT. Selman, Kautz, Cohen: "Noise Strategies for Improving Local Search", AAAI, 1994. Short Description: Hill-climbing procedure for SAT. Extremely competitive at the time, spawned a huge body of follow-up research that dominated the SAT scene during the middle 90s.
• Local search topology. Frank, Cheeseman, Stutz: "When Gravity Fails: Local Search Topology", JAIR, 1997. Short Description: Analysis of the search space surface in random SAT problems.
• A*. Hart, Nilsson, Raphael: "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 1968. Short Description: The quintessential optimal heuristic search algorithm.
• Weighted A*. Pohl: "Heuristic Search Viewed as Path Finding in a Graph", Artificial Intelligence, 1970. Short Description: Version of A* that allows for bounded sub-optimality, by weighting the heuristic.
• Optimistic Search. Thayer, Ruml: "Faster Than Weighted A*: An Optimistic Approach to Bounded Suboptimal Search", ICAPS, 2008. Short Description: Version of Weighted A* that is initially more greedy than the requirement (higher weight), then does some search after solution found to ensure optimality.
• Explicit Estimation Search. Thayer, Ruml: "Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates", IJCAI, 2011. Short Description: Version of Weighted A* with both a remaining-cost estimator and a remaining-distance estimator, for finding bounded sub-optimal solutions quickly.
• A* performance upper bounds. (Scanned version (large file).) Gaschnig: "Exactly how good are heuristics? Toward a realistic predictive theory of best-first search", IJCAI, 1977. Short Description: Upper bounds on performance of A* when logarithmically bounding the difference between the heuristic and the perfect heuristic h*.
• A* performance lower bounds. Helmert, Roeger: "How Good is Almost Perfect?", AAAI, 2008. Short Description: Lower bounds on performance of A*, with constant bound on the difference between the heuristic and the perfect heuristic h*, but in search spaces with many transpositions (states reached by several different paths).
• IDA*. Korf: "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search", Artificial Intelligence, 1985. Short Description: Linear-memory version of A*, using depth-first search and using a heuristic for pruning.
• Breadth-First Heuristic Search. Zhou, Hansen: "Breadth-First Heuristic Search", ICAPS, 2004. Short Description: Breadth-first search enhanced by using a heuristic for pruning.
• Frontier Search. Korf, Zhang, Thayer, Hohwald: "Frontier Search", Journal of the ACM, 2005. Up to including Section 5, i.e., first 13 pages. Short Description: Safes memory by remembering only the current frontier, recovering the actual solution in a divide-and-conquer manner.
• LRTA*. Korf, "Real-Time Heuristic Search: New Results", AAAI, 1988. Short Description: Local version of A*, with learning that converges to perfect heuristic.
• Lifelong Planning A*. Koenig a, Likhachev, Furcy: "Lifelong Planning A*", Artificial Intelligence, 2004. Up to including Section 5, i.e., first 18 pages. Short Description: Incremental version of A* that allows to re-use previous search information on modified problems.