Artificial Intelligence Search Methods, 4 credits

Course content

This course focuses on two important tenets of Artificial Intelligence, namely Representation and Search. We explore how general uninformed and informed search techniques are used to solve combinatorial problems, and how problem structure can be leveraged to facilitate the search for a solution. The course provides an overview of the following topics:

• Uninformed systematic search (depth-first, breadth-first, uniform cost, iterative deepening search)
• Informed systematic search (greedy best-first, A*, memory-bounded variants of A*)
• Local search (e.g., hill-climbing, simulated annealing)
• Heuristically-guided backtracking search for Constraint Satisfaction Problems (CSP)
• Variable and value ordering heuristics for CSP search
• Constraint propagation
• Specific types of CSPs and specialized search and propagation methods for these (e.g., k-SAT, DPLL and unit propagation, temporal CSPs and path-consistency)