Problem Solving and Search in Artificial Intelligence

 

Course Syllabus

 

 

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

Course Title:  Problem Solving and Search in Artificial Intelligence

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

Lecturer: Priv. Doz. Dr. Nysret Musliu

Email: musliu@dbai.tuwien.ac.at

 

 

 

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, advanced heuristic search techniques, and application of machine learning in search. The course covers these topics: 

·        Basic Concepts  

·        Uninformed Search Strategies  

·        Heuristic Algorithms

·        Constraint Satisfaction Problems

·        Constraint Programming Techniques

·        Decomposition Techniques (Tree and Hypertree Decompositions)

·        Metaheuristic Algorithms (Simulated Annealing, Tabu Search, Genetic Algorithms…)

·        Adversarial Search and Game Playing

·        Application of Machine Learning in Search (Automated Algorithm Selection, Hyperheuristics)

·        Algorithm Configuration (Automated Parameter Tuning)

 

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 a combination of lectures and exercises. Students will implement constraint programming and metaheuristic techniques for a particular problem. Additionally, during the course different logical problems and puzzles will be discussed. Students are encouraged to introduce new problems during the lectures.   

 

 

Literature:

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

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 obtain at least 50 points and in the final exam you must reach at least 30 points

 

 

Schedule of Classes

 

Lectures

 

06.03.2014 (10:00 - 11:30) (Seminarraum Gödel)

Preliminary discussion

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

 

13.03.2014 (10:00 - 12:00) (Seminarraum Gödel)

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)

 

20.03.2014 (10:00 - 12:00) (Seminarraum Gödel)

Constraint Satisfaction (AIMA - Chapter 5)

 

03.04.2014 (10:00 - 12:00) (Seminarraum Gödel)

Constraint Programming Techniques (AIMA - Chapter 5)

 

10.04.2014 (10:00 - 12:00) (Seminarraum Gödel)

Structural Decomposition Techniques (Tree/Hypertree Decompositions)

 

08.05.2014 (10:00 - 12:00) (Seminarraum Gödel)

Structural Decomposition Techniques (Tree/Hypertree Decompositions)

Metaheuristic Algorithms

 

15.05.2014, 23.05.2013 (10:00 - 12:00) (Seminarraum Gödel)

Metaheuristic Algorithms:

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

       Tabu Search (How to Solve It: Modern Heuristics - Chapters 4,5,6)

Iterated Local Search

Evolutionary Algorithms (slides for Chapters 1, 2, 3 in http://www.cs.vu.nl/~gusz/ecbook/ecbook-course.html )  or

(How to Solve It: Modern Heuristics - Chapter 6, Chapter 7(optional))

 

22.05.2014 (10:00 - 12:00) (Seminarraum Gödel)

Application of Machine Learning in Search (Automated Algorithm Selection)

Algorithm Configuration (Automated Parameter Tuning)

Optional: Adversarial Search and Game Playing (AIMA – Chapter 6)

 

05.06.2014/12.06.2014 (10:00 – 12:00) (Seminarraum Gödel)

Presentation of projects

 

13.06.2014  (16:00 – 18:00) (EI 9 Hlawka HS)

Final Exam

 

 

Project

You will implement methods that will be considered in this class for the Rotating Workforce Scheduling Problem.

More information for this problem can be found in the papers below:

 

N. Musliu, J. Gärtner, W. Slany. Efficient generation of rotating workforce schedules. Discrete Applied Mathematics, Vol. 118 (1-2), pp. 85-98, 2002.

 

N. Musliu. Heuristic Methods for Automatic Rotating Workforce Scheduling. International Journal of Computational Intelligence Research, Volume 2, Issue 4, pp. 309-326, 2006.

 

Benchmark problems: http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks/workforceScheduling.zip

 

Additional information for this problem will be given during the class.

 

The project consists of two phases.

Phase I: Implementation of a constraint programming technique for Rotating Workforce Scheduling

Phase II: Implementation of a metaheuristic technique (or a hybrid technique) for Rotating Workforce Scheduling

 

2 students can work together in a group

 

Schedule for the Assignment:

 

03.05.2014:

Submit in TUWEL your implementation (source code and the description of your method) for Phase I

 

03.06.2014

Submit in TUWEL your implementation (source code and the description of your method) for Phase II

 

05.06/12.06.2014 (10:00 – 12:00) (Seminarraum Gödel)

Presentation of projects

 

 

mailto: musliu@dbai.tuwien.ac.at