AI: Search Methods for Problem Solving

A study of how intelligent agents solve problems through state-space search, heuristic optimization, game-playing algorithms, and automated planning.

This course explores the fundamental mechanics of how an intelligent agent navigates complex problem spaces. Starting with a philosophical look at the Turing Test, we move from “blind” search strategies to advanced heuristic methods designed to defeat combinatorial explosion. The curriculum covers a diverse range of paradigms, including stochastic local search, population-based methods like Genetic Algorithms, and optimal pathfinding with $A^*$. We also delve into competitive environments with Minimax and Alpha-Beta pruning, automated domain-independent planning, and the intersection of search and logical reasoning through Constraint Satisfaction Problems (CSP).

Instructor

Prof. Deepak Khemani, Department of Computer Science and Engineering, IIT Madras

Course Schedule & Topics

The course is structured over 12 weeks, progressing from foundational state-space search to advanced reasoning and constraint processing.

Week Primary Focus Key Topics Covered
1 Introduction & Philosophy The Turing Test, Winograd Schema, and the landscape of search in AI.
2 State Space Search Blind search: Depth First, Breadth First, and Iterative Deepening analysis.
3 Heuristic Search Heuristic functions, escaping local optima, and stochastic local search.
4 Population Based Methods Genetic Algorithms, Emergent Systems, and Ant Colony Optimization.
5 Finding Optimal Paths Algorithm $A^*$ and the formal proof of Admissibility.
6 $A^*$ Variations The Monotone Condition, space-saving versions of $A^*$, and Sequence Alignment.
7 Game Playing Minimax algorithm, Alpha-Beta pruning, and SSS* for board games like Chess.
8 Automated Planning Goal Stack Planning and Partial Order Planning (POP).
9 Problem Decomposition Goal trees and Algorithm $AO^*$ for breaking down complex problems.
10 Inference Systems Pattern directed inference, Forward chaining, and the Rete algorithm.
11 Constraint Processing Backtracking, Arc consistency, and the Waltz algorithm.
12 Advanced Reasoning Model-based diagnosis and the synthesis of search with logical reasoning.

Material used