Foundations of Artificial Intelligence (FAI) Group


Seminar: Heuristic Search Algorithms
Organization. The seminar will take place on Mondays,
14:1515: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
problemsolving 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 wellknown 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.
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:
 You read the paper.
 At least 2 weeks prior to your seminar slot, you meet with your
supervisor to discuss the paper.
 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.
 At least 1 week prior to your seminar slot, you meet with your
supervisor to discuss your slides and summary.
 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.
 In your seminar slot, you give the presentation, and lead the
discussion on your paper.
 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 35 pages long (in the
doublecolumn 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 

CHRISTMAS BREAK 
Santa :) 
Mon, 07.01. 
Breadth First Heuristic Search 
Michael Katz 
Mon, 14.01. 
LifeLong Planning A* 
Joerg Hoffmann 
Mon, 21.01. 
LRTA* 
Joerg Hoffmann 
 GSAT.
Selman, Levesque, Mitchell: "A New Method for Solving Hard
Satisfiability Problems", AAAI, 1992.
Short Description: Hillclimbing procedure for SAT. Extremely
competitive at the time, spawned a huge body of followup research
that dominated the SAT scene during the middle 90s.
 WalkSAT.
Selman, Kautz, Cohen: "Noise Strategies for Improving Local Search",
AAAI, 1994.
Short Description: Hillclimbing procedure for SAT. Extremely
competitive at the time, spawned a huge body of followup 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
suboptimality, 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 remainingcost
estimator and a remainingdistance estimator, for finding bounded
suboptimal solutions quickly.
 A* performance upper bounds. (Scanned version (large file).)
Gaschnig: "Exactly how good are heuristics? Toward a realistic
predictive theory of bestfirst 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: "Depthfirst IterativeDeepening: An Optimal Admissible Tree
Search", Artificial Intelligence, 1985.
Short Description: Linearmemory version of A*, using depthfirst
search and using a heuristic for pruning.
 BreadthFirst Heuristic Search.
Zhou, Hansen: "BreadthFirst Heuristic Search", ICAPS, 2004.
Short Description: Breadthfirst 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 divideandconquer
manner.
 LRTA*.
Korf, "RealTime 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 reuse
previous search information on modified problems.