Image
Foundations of AI II
KI-Campus-Original
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.

Start date
from 23. August 2021
Duration
4 weeks à 3 hours
Language
English

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. 

Who is offering this course?

Sophia Saller
Dr. Sophia Saller
Deutsches Forschungszentrum für Künstliche Intelligenz
Annika Engel
Annika Engel
Deutsches Forschungszentrum für Künstliche Intelligenz
Jana Koehler
Prof. Dr. Jana Koehler
Deutsches Forschungszentrum für Künstliche Intelligenz
Universität des Saarlandes
Artificial Intelligence Group / Saarland University
Prof. Dr. Jörg Hoffmann
Prof. Dr. Jörg Hoffmann
Artificial Intelligence Group / Saarland University
Andrea Nawrath-Herz
Andrea Nawrath-Herz
Deutsches Forschungszentrum für Künstliche Intelligenz
Anastasia Salyaeva
Anastasia Salyaeva
Deutsches Forschungszentrum für Künstliche Intelligenz

The creators of the learning opportunities are responsible for their content.

What else should I know?

The creators of the learning opportunities are responsible for their content.

Learning format:
Online course
Level:
Beginner
License
CC-BY-SA 4.0