Foundations of Artificial Intelligence II
Search algorithms in AI
This course is part of the course series "Foundations of Artificial Intelligence I-VI" that covers a variety of algorithms and methods that are of central importance in AI and of major practical relevance.
Overview
The course "Foundations of Artificial Intelligence II" introduces key search algorithms developed in the field of artificial intelligence. The thorough theoretical treatment of these algorithms is complemented with numerous examples illustrating search mechanisms and practical application scenarios.
The three modules of the course are devoted to systematic search algorithms, heuristic search, and algorithms for local and stochastic search, respectively.
The course is based on the textbook by Stuart Russell and Peter Norvig: Introduction to Artificial Intelligence - A Modern Approach, 3rd edition, 2012, or 4th edition 2020. The 3rd edition is also available in German: Stuart Russell und Peter Norvig: Künstliche Intelligenz - Ein Moderner Ansatz, 3. aktualisierte Auflage, Pearson 2012.
The course is based on the textbook by Stuart Russell and Peter Norvig: Introduction to Artificial Intelligence, 3rd edition, 2012 or 4th edition, 2020. The 3rd edition is also available in German: Stuart Russell und Peter Norvig: Künstliche Intelligenz - Ein Moderner Ansatz, 3. aktualisierte Auflage, Pearson 2012.
The course is held in English language with German subtitles.
Which topics will be covered?
Module Systematic Search
- Basic terminology and concepts
- Definition of a state space
- Search problem and reachability of states
- Solutions of search problems
- Modeling a search problem
- Concept of a search tree
- Redundant and duplicate states, frontier
- Blackbox, whitebox, and explicit formulations of search problems
- Systematic search strategies
- Tree search vs. graph search
- Soundness, completeness, optimality, time and space complexity
- Algorithms
- Breadth-first search
- Depth-first search
- Depth-limited search
- Iterative deepening search
- Uniform cost search
Module Heuristic Search
- Using knowledge during search
- Heuristic functions
- Admissible and consistent heuristics
- Heuristic search algorithms
- Greedy (Best-First) search
- A*
- IDA*
- Bidirectional search and the MM algorithm
- Finding good heuristics
- Effective branching factor in a search tree
- Example heuristics for the8-Puzzle
- Pattern databases
Module Local and Stochastic Search
- Searching very large search spaces
- Local extrema & plateaus
- Randomized search strategies
- Random restarts and moves
- Tabu search
- Algorithms
- Hill climbing
- Simulated annealing
- UCT: Upper confidence bounds for trees
- Metaheuristic search methods
- Genetic algorithms
- Ant colony optimization
What will I achieve?
By the end of the course, you‘ll be able to
- understand and explain systematic, heuristic, local, and stochastic search algorithms,
- select and evaluate a search algorithm to solve a search problem,
- apply these algorithms to search problems occurring in practice.
Which prerequisites do I need to fulfill?
None.
