Search is a strategy used to solve many problems in artificial intelligence, as well as many other branches of computer science and mathematical optimization. Many sequential decision problems, such as planning and scheduling, can be solved by finding shortest paths in graphs. For many NP-complete problems, such as traveling salesman, algorithms such as backtracking, branch-and-bound and greedy search give some of the best approximate and exact solutions.
In this course, we will introduce a variety of exact heuristic search algorithms, such as A*, and apply them to solving complex optimization problems. Although the algorithms we discuss will be quite generic, applying them to real problems often require specific tailoring. To motivate these practical matters, we will consider a variety of applications, including puzzle solving (sliding tile, Rubik's cube), bioinformatics (sequence alignment), model checking (hardware and software verification), and planning (robotics, video games, decision theory).
In this seminar course, students are expected to read papers from the literature, participate in class discussion, and complete a semester research project. Class participation will include presenting research papers to the rest of the class. The semester project will likely involve surveying a specific branch of heuristic search and developing a deeper understanding of the state of the art algorithms in that area.
For course information, please see the syllabus.
After each presentation, we will provide feedback to the presenter using the oral presentation rubric. This does not affect the grade of the presenter, but it is a way to give feedback on what you thought worked and what could use improvement about their presentation.
There are many areas of active research in heuristic search, so there are many opportunities to extend the work of this seminar into an MSc thesis.
Class meeting: Exactum C220, Thursdays, 14:15 - 16:00 (see below)
Office hourse: Wednesday, 10:00 - 12:00, or by appointment
Tentative Schedule and Deadlines
September 5: Introduction
September 12: Basic search algorithms for solving puzzles
“Depth-first iterative-deepening: an optimal admissible tree search,” Korf, AIJ 1985 (Simo Linkola, slides)
“Breadth-first heuristic search,” Zhou and Hansen, AIJ 2006 (Mohamad Mubarok, slides)
September 19: Memory-efficient algorithms for multiple sequence alignment
September 26: External-memory algorithms for model checking and verification
“Directed explicit-state model checking in the validation of communication protocols,” Edelkamp et al., International Journal on Software Tools for Technology Transfer 2004 (Ella Peltonen, slides)
“I/O efficient directed model checking,” Jabbar and Edelkamp, Verification, Model Checking and Abstract Interpretation 2005 (Joel Rybicki, slides)
October 3: Planning
“Planning as heuristic search,” Bonet and Geffner, AIJ 2001. (Arturs Polis)
“Anytime search in dynamic graphs,” Likhachev et al., AIJ 2008. (Eric Andrews, slides)
October 10: Other topics, Research paper must be selected and approved.
“Linear-time disk-based implicit graph search,” Korf, JACM 2008 (Onni Koskinen)
“Weighted A* search - unifying view and application,” Ebendt and Drechsler, AIJ 2009 (Kustaa Kangas)
November 14: Draft of research report (at least 4 pages) is due. Latex and Word formatting templates.
November 22 (at noon, Helsinki time): Reviews of research reports are due. Reviewing assignments. Review template.
November 28: 4 research presentations
December 5: 5 research presentations, Final research report (at least 5 pages) is due.
Possible Topics, Venues for Research Report
Topics
State of the art in any of the topics covered in the first term in the course
Pattern databases, a general technique for constructing good heuristics
Value iteration, a dynamic programming algorithm for solving Markov decision processes
AND/OR graph search, a strategy for solving Markov decision processes and competitive games
Graphical model applications, such as learning Bayesian networks or performing inference in Bayesian networks
Optimization applications, such as branch-and-cut for solving integer programs or DPLL-based algorithms for SAT
Counter-example guided abstraction refinement
Venues to search for new topics
Journal of Artificial Intelligence Research (JAIR)
Artificial Intelligence Journal (AIJ)
Journal of the ACM (JACM)
International Joint Conference on Artificial Intelligence (IJCAI)
International Conference on Automated Planning and Scheduling (ICAPS)
AAAI Conference on Artificial Intelligence (AAAI)
Symposium on Combinatorial Search (SoCS)
... others...