Problem Solving and Search in Artificial Intelligence

Course Syllabus

Course Number: 181.190 - Lecture with Exercises (SS 2012)

Course Title: Problem Solving and Search in Artificial Intelligence

Credits: 2,0 Std. (3ECTS-Points)

Lecturer: Priv. Doz. Dr. Nysret Musliu

Course Description:

This course teaches the main artificial intelligence search techniques used for problem solving. The emphasis will be in informed search techniques, constraint satisfaction, and advanced heuristic search techniques. The course covers these topics:

· Basic Concepts

· Uninformed Search Strategies

· Informed Search Algorithms

· Constraint Satisfaction Problems

· Decomposition Techniques (Tree and Hypertree Decompositions)

· Local Search Techniques: Stochastic Hill Climbing, Simulated Annealing, Tabu Search

· Adversarial Search and Game Playing

· Genetic Algorithms, Parameter Control

· Learning in Search

The use of search methods will be illustrated by examples, which show the application of these methods for solving of different hard problems with high practical relevance. Moreover, successful use of search methods in research and industrial projects of our group will be presented.

Course Structure:

This course is combination of lectures and exercises. Exercises part consists on small project, which will be an implementation of a hybrid method that combines metaheuristic algorithms and constraint programming technique for a particular problem. Additionally, during the course discussion for solving of different logical problems and puzzles will be made. Proposals of students for discussions about problems for which they are interested are encouraged.

Literature:

Stuart Russell and Peter Norvig . Artificial Intelligence: A Modern Approach (Second Edition), 2003

Z. Michalewicz and D. B. Fogel. How to Solve It: Modern Heuristics, 2nd edition, Springer-Verlag, 2004

Additionally the key papers from the literature will be used.

…

Grading

Final (written) Exam: 60 points

Project: 40 points

For a positive grade you must have at least 50 points and in the final exam you must reach at least 30 points

Schedule of Classes

Lectures

13.03.2012 (16:00 - 18:00) (Seminarraum Zemanek)

Preliminary discussion

Basic Concepts (How to Solve It: Modern Heuristics - Chapters 1, 2 ; Artificial Intelligence: A Modern Approach (AIMA) - Chapter 3)

20.03.2012 (16:00 - 18:00) (Seminarraum Zemanek)

Uninformed Search Strategies (AIMA - Chapter 3, How to Solve It - Chapters 3)

Informed Search Algorithms (AIMA - Chapter 4, How to Solve It: Modern Heuristics - Chapters 4)

27.03.2012 (16:00 - 18:00) (Seminarraum Zemanek)

Constraint Satisfaction (AIMA - Chapter 5)

17.04.2012 (16:00 - 18:00) (Seminarraum Zemanek)

Structural Decomposition Techniques (Tree and Hypertree Decompositions) (AIMA - Chapter 5, sec. 5.4)

23.04.2012 (09:00 - 10:30) (Seminarraum Zemanek)

Local Search, Stochastic Hill Climbing, Simulated Annealing (How to Solve It - Chapters 3 (sec. 3.2), 4 (sec. 4.1) , 5 (sec. 5.1)

08.05.2012 (16:00 - 18:00) (Seminarraum Zemanek)

Tabu Serch (How to Solve It: Modern Heuristics - Chapters 5)

15.05.2012 (16:00 - 18:30) (Seminarraum Gödel)

Genetic Algorithms (How to Solve It: Modern Heuristics - Chapters 6, 7)

Game Playing (AIMA – Chapter 6)

22.05.2012 (16:00 - 18:30) (Seminarraum Gödel)

Learning in Search (Parameter Control , Algorithm Configuration, Algorithm Selection)

19.06.2012 (16:00 – 19:00) (Seminarraum Zemanek)

Presentation of projects

26.06.2012 (16:00 – 18:00) (Seminarraum Zemanek)

Final Exam

Project

Implement a hybrid search method based on combination of (meta)heuristic algorithms and constraint programming techniques for:

High School Timetabling Problems in the third International Timetabling Competition:

http://www.utwente.nl/ctit/itc2011/

2 students can work together in a group

Schedule for the Assignment:

23.05.2012:

Submit in TUWEL a short description (1-2 pages) of a method that will be used for the particular problem

18.06.2012

Submit in TUWEL your program (with the instructions for running of your program) and the final description of your method (including the results of your method in benchmark problems)

19.06.2012 (16:00 – 19:00) (Seminarraum Zemanek)

Presentation of projects

mailto: musliu@dbai.tuwien.ac.at