Artificial Intelligence I

[Dates] [Contents] [References] [Slides] [Assessment] [Review]

Dates

Contents

Module Objective

Students will explore the state of the art in Artificial Intelligence.

Module Content

Topics will be selected from the following and others: advanced AI search; natural language processing; randomised search heuristics (e.g. swarm intelligence; evolutionary computation); multi-agent systems.

Learning Outcomes

On successful completion of this module, students should be able to:

• Demonstrate a broad knowledge of modern AI theory and applications, including a sense of the successes and failures
• Apply advanced AI search techniques
• Assess if a problem is amenable for solution by specific AI techniques
• Decide where the application of randomised search heuristics is appropriate for solving a problem
• Adapt general randomised search heuristics to a specific search problem

References

• S. Russell, P. Norvig: Artificial Intelligence. A Modern Approach. Third Edition. Pearson, 2010.
• T. Jansen: Analyzing Evolutionary Algorithms. Springer, 2013.
• R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics. Addison Wesley, 1998.
• W. Feller: An Introduction to Probability Theory and Its Applications. Third Edition. Wiley, 1968.

Slides

1. 2012-09-26, slides 1-20 (long version) [introduction; artificial intelligence; (types of) rational agents; task environments (PEAS description)]
2. 2012-09-28, slides 21-44 (long version) [task environments (PEAS description); rational agents; search problems; uninformed search: state space, search tree]
3. 2012-10-03, slides 45-66 (long version) [algorithms for uninformed search: breadth-first search, uniform-cost search, depth-first search, backtracking, depth-limited search, iterative deepening depth-first search, bidirectional search; analysis and comparison of algorithms for uninformed search]
4. 2012-10-05, slides 67-92 (long version) [algorithms for informed search: heuristic functions; greedy best-first search; A^* search; variants of A^* search (iterative-deepening A^* search, recursive best-first search, simplified memory-bounded A^* search), heuristic functions for the 8-puzzle, domination]
5. 2012-10-10, slides 93-119 (long version) [heuristics for A^* search: relaxation, combinations, subproblems, learning; adversarial search: introduction to game theory; example Take(n, k), minimax search, alpha-beta pruning, move ordering]
6. 2012-10-12, slides 120-136 (long version) [adversarial search: transposition tables, real-time game play (evaluation functions, cut off, forward pruning, lookup), stochastic games (chance nodes, properties and general hints), partially observable games (example, general remarks)]
7. 2012-10-17, slides 137-154 (long version) [introduction randomised search heuristics: optimisation, local search, stopping criteria, Metropolis algorithm, simulated annealing, evolutionary algorithms: selection, variation (crossover, mutation)]
8. 2012-10-19, slides 155-170 (long version) [some concrete evolutionary algorithms; upcoming attractions; introduction to probability: probability space, probability measure, independence, random variables, expected values]
9. 2012-10-24, slides 171-187 (long version) [introduction to probability: random variables, expected values, linearity of expectation, Markov inequality, binomial distribution, geometric distribution, Chernoff bounds, conditional probabilities, law of total probability]
10. 2012-10-26, slides 188-209 (long version) [Markov chains, stopping times, martingales, fair random walk, gambler's ruin]
11. 2012-10-31, slides 210-233 (long version) [coupon collector's problem; assessment of randomised search heuristics: no free lunch]
12. 2012-11-02, slides 234-252 (long version) [assessment of randomised search heuristics: no free lunch, classes of functions that are c.u.p. (and those which are not), almost no free lunch]
13. 2012-11-07, slides 253-265 (long version) [almost no free lunch; black box complexity: definition, comparison with computational complexity, general upper bounds]
14. 2012-11-09, slides 266-284 (long version) [black box complexity: Yao's minimax principle, black box complexity of Needle, OneMax, and unimodal functions]
15. 2012-11-14, slides 285-311 (long version) [black box complexity of unimodal functions; analysing mutation: local and global mutations on OneMax; fitness-based partitions; local and global mutations in local optima]
16. 2012-11-16, slides 312-330 (long version) [analysing mutation: local and global mutations on OneMax; long k-paths; trapping global mutations; comparing local and global mutations; applying randomised search heuristics]
17. 2012-11-21, slides 331-351 (long version) [designing and analysing mutation: asymmetric mutations: basic properties, performance on OneMax, performance on generalised OneMax, Plateau]
18. 2012-11-23, slides 352-372 (long version) [asymmetric mutations: shifted Plateau; crossover: steady state GA, 1-point crossover and uniform crossover: general properties, example functions]
19. 2012-11-28, slides 353-394 (long version) [crossover: steady state GA with uniform crossover: example function and result; parametrisation: offspring population size: (1+λ) EA; number of generations vs. number of function evaluations; (1+λ)EA on LeadingOnes]
20. 2012-11-30, slides 395-396 [in-class test]
21. 2012-12-05, slides 397-422 (long version) [in-class test: results and solutions; parametrisation: offspring population size: (1+λ) EA on OneMax; super-linear speedup; parametrisation: mutation probability: 1/n is not always optimal]
22. 2012-12-07, slides 423-439 (long version) [parametrisation: mutation probability: comparing smaller and larger mutation probabilities; usefulness of larger mutation probabilities; dynamic mutation probabilities; the dynamic (1+1) EA]
23. AIS Tutorial slide used December 7, December 12, and December 14

Continuous Assessment

• weekly assignments handed out each Friday, due the following Wednesday, discussed the next Wednesday
• assignment 1
• assignment 2
• assignment 3
• assignment 4
• assignment 5
• assignment 6
• assignment 7
• assignment 8
• assignment 9
• assignment 10
• In-Class Test 30.11.2012 (sample test and solutions for it)

Tutorial/Review/Open QA Sesstion

Several students have asked me if we could have a tutorial for certain aspects of CS4618, a review of the contents so far, or something in that direction. I plan to offer an open question/answer session to reply to this request. The idea is that I'll be present to take questions and answer those as good as possible.

last change: 07.12.2012