Efficient AI Programming (IAIP), Fall 2005

[News] [Schedule] [Course description] [Exercise Sessions]

News

14.01.2006	The exam will be in 4A14 and 4A16 on Thursday 19 Jan 2006 from 9am to 1pm. All written and printed supplementary materials are allowed. Please contact the exam office for further details about the exam. The exam questions are written in English, but you may answer in Danish if you like.
13.01.2006	We will have a question lecture on Monday in auditorium 3 (not in 2A12 if that was earlier mentioned) from 9a-12. If you want to be sure to get good answers to your questions then please send them to me
22.12.2005	A new version of the erratum for Dechter has been made for chapter 1-6. You can access it here
25.11.2005	Please find the curriculum here
30.09.2005	A seperate webpage with information about the exercises and exercise sessions has been made available here.
07.09.2005	Errata list has been created for the Rina Dechter's, Constraint Processing book. You can access it here.
31.08.2005	Schedule update, please notice links to exercises
05.08.2005	First version of the home page introduced. Please note that the course schedule is still tentative and could change in next few weeks.

Schedule

Lectures: Thursdays 9-12: 4A 14
Recitations: Thursdays 13-16: 3A52

Schedule (subject to change):

Lec#	Date	Teacher	Content	Lecture notes	Readings	Exercises
1	01-sep	RMJ	Introduction to IAIP and AI 1. overview of IAIP 2. overview of AI 3. Intelligent agents 4. Math Background	slides1 Roman Tutor slides	RN 1 RN 2 D 1.3	None
2	08-sep	RMJ	Search I: Uninformed Search and Adversarial Search 1. Breadth-first search 2. Depth-first search 3. Depth limited search 4. Bidirectional search 5. Minimax 6. Alpha-beta pruning	slides2	RN 3 (except 3.6) RN 6.1, 6.2, and 6.3	week2
3	15-sep	RMJ	Search II: Informed Search 1. Best-first search (BFS) 2. Greedy search, A*, RBFS, BFHS 4. Heuristic functions 5. Local search 6. Hill climbing, simulated annealing, local beam search, genetic algorithms	slides3 Zhou, R and Hansen, E, Breadth-First Heuristic Search, ICAPS04, 2004	RN 4 (except 4.4 and 4.5)	week3
4	22-sep	SS	Knowledge Representation I: Propositional Logic 1. Syntax and semantics 2. Logical equivalence 3. Resolution 4. Normal forms 5. Horn clauses 6. SAT solving	slides4	RN 7 (except 7.7)	week4 Impl. task 1: A* A* java code
5	29-sep	RMJ	Knowledge Representation II: Binary Decision Diagrams 1. Classical representations: truth tables, two-level and multi-level representations 2. INF normal form 3. Binary Decision Diagrams (BDDs) 4. BDD-based all-SAT 5. Quantified Boolean formulas (QBF) 6. BDD-based search	slides5	HRA BDD notes (except 4.4, 4.5,4.6,8) RMJ QBF notes	week5 Impl. task 2: DPLL: Code
6	06-oct	RMJ	Knowledge Representation III: First Order Logic 1. Syntax and semantics 2. Knowledge engineering Constraint Satisfaction I: Introduction 1. Constraint networks 2. Properties of constraint networks	slides6	RN 8 D1 (except 1.3) D2	week6 Impl. task 3: BDD Search: code
7	13-oct	TH	Constraint Satisfaction II: Constraint Propagation 1. Arc consistency 2. i-consistency 3. Directional consistency	slides7	D3 (except 3.3, 3.5.2, 3.5.3, 3.6 and 3.7) D4 (except 4.2.2, 4.2.4)	week7
	20-oct		Fall break
8	27-oct	RMJ	Constraint Satisfaction III: Look-Ahead Strategies 1. State space search 2. Backtracking 3. Look-ahead for value selection: forward-checking, arc-consistency look-ahead, maintaining arc-consistency full and partial look-ahead 4. Look-ahead for variable ordering: dynamic variable forward-checking	slides8	D5 (except backtracking, 5.3.3, 5.3.4, and 5.4)	week8
9	03-nov	RMJ	Constraint Satisfaction IV: Look-Back Strategies 1. Conflict sets 2. Backjumping techniques: Gaschnig's, graph-based, conflict-directed 3. Learning algorithms: graph- based, conflict-directed 5. BDD-based online constraint satisfaction	slides9	D6 (except 6.3 and 6.5)	week9 Impl. task 4: Forward Checking
10	10-nov	RMJ	Planning I: STRIPS Planning 1. STRIPS and ADL planning language 2. Progression and regression planning 3. Partial order planning 4. Graphplan	slides10	RN 11 (except the graphplan algorithm)	week10 Impl. task 5: Interactive Configuration Model
11	17-nov	RMJ	Planning II: Planning in the real world 1. Hierarchical Task Network (HTN) planning 2. Conditional planning 3. Continuous planning 4. Strong, strong cyclic, and weak planning	slides11	RN 12 (except 12.1, conditional planning in partial observable environments, 12.6 and 12.7)	week11
12	24-nov	RMJ	Repetition			week12

Mandatory Exercises: Each recitation session will have a number of exercises for students to work on. All stared (*) exercises are mandatory. Individual answers to these mandatory exercises are to be handed in no later than the following lecture. To sign up to the exam at least 80% of the maximum score of the mandatory exercises must have been obtained. It is allowed to work in groups to solve these exercises, but individual answers must be given.

Literature:

RN: Stuart Russell and Peter Norvig, "Artificial Intelligence. A Modern Approach. Second Edition", Prentice Hall, 2003.
D: Rina Dechter, "Constraint Processing", Morgan Kaufmann, Elsevier, 2003.
Articles and notes to be handed out.

Manning of course

Rune Møller Jensen (RMJ)
Course manager
Office: 4D 22
Email: rmj

Tarik Hadzic (TH)
Teaching Assistant
Office: 4D 24
Email: tarik

Peter Tiedemann (PT)
Teaching Assistant
Office: 4D25
Email: petert

Sathiamoorthy Subbarayan (SS)
Teaching Assistant (on leave)
Office: 4D 25
Email: sathi

Related courses at ITU

AI in Game Programming : This course focuses on AI techniques for game programming. The concrete approaches that will be studied fall into a subfield of AI called Machine Learning (e.g., neural nets, genetic algorithms, Bayesian learning, and decision trees). Since IAIP only spends the last lecture on these techniques (decision trees), there is almost no overlap between the courses.

Rule-Based AI Programming for I3D and Games: This course focuses on building believable characters in games using rule-based systems. The course most likely will cover logics for knowledge representation and inference rules, but the focus is on application of these techniques in I3D and games. So again, there is little overlap with IAIP.