Applications Open now for September 2024 Batch | Applications Close: Sep 15, 2024 | Exam: Oct 27, 2024

Applications Open now for September 2024 Batch | Applications Close: Sep 15, 2024 | Exam: Oct 27, 2024

Degree Level Course

AI: Search Methods for Problem Solving

We look at how an intelligent agent solves new problems. Starting with blind search we quickly move on to heuristic search, and look at several variations designed to combat the combinatorial explosion that search has to face. We study how board games like Chess and Go are played; how search facilitates logical reasoning; and approaches to domain independent planning of actions to achieve a goal. We end with looking at an alternative formulation that combines search and reasoning as constraint processing.

by Deepak Khemani

Course ID: BSCS3003

Course Credits: 4

Course Type: Core Option II

Pre-requisites: None

What you’ll learnVIEW COURSE VIDEOS

Get a historical and philosophical perspective on artificial intelligence.
The ability to formulate problems in a general problem solving framework.
Knowledge of domain independent search based problem solving algorithms.
Knowledge of stochastic, local, and population based search algorithms.
The foundations of problem decomposition and rule based methods.
Ability to implement game playing algorithms.
An understanding of the relation between search methods and other with other formulations including planning, constraints and logical reasoning.

Course structure & Assessments

12 weeks of coursework, weekly online assignments, 2 in-person invigilated quizzes, 1 in-person invigilated end term exam. For details of standard course structure and assessments, visit Academics page.

WEEK 1 Introduction and philosophy. The Turing Test. The Winograd Schema Challenge. Placing search in the landscape of AI.
WEEK 2 Search spaces. Examples. State space search. Depth First, Breadth First, Iterative Deepening. Analysis.
WEEK 3 Heuristic search. Heuristic functions. Solution space search. Escaping local optima. Stochastic local search.
WEEK 4 Population based methods. Genetic Algorithms, emergent systems, Ant Colony Optimization.
WEEK 5 Finding optimal paths. Algorithm A*. Admissibility of A*.
WEEK 6 The monotone condition. Space saving versions of A*. Sequence alignment.
WEEK 7 Game playing. Board games. Algorithms Minimax, Alpha-Beta, and SSS*.
WEEK 8 Automated domain independent planning. Goal Stack Planning, Partial Order Planning.
WEEK 9 Problem decomposition with goal trees. Algorithm AO*.
WEEK 10 Pattern directed inference systems. Forward chaining inference engine. The Rete algorithm.
WEEK 11 Constraint processing. Algorithm Backtracking. Arc consistency. Combining search and reasoning. Waltz algorithm. Model based diagnosis.
+ Show all weeks

Prescribed Books

The following are the suggested books for the course:

Deepak Khemani. A First Course in Artificial Intelligence, McGraw Hill Education (India), 2013. (Chapters 1 – 8, some parts from Chapters 9 and 10))


John Haugeland, Artificial Intelligence: The Very Idea, A Bradford Book, The MIT Press, 1985.

Pamela McCorduck, Machines Who Think: A Personal Inquiry into the History and Prospects of Artificial Intelligence, A K Peters/CRC Press; 2nd  edition, 2004.

Eugene Charniak and Drew McDermott, Introduction to Artificial Intelligence, Addison- Wesley Publ., 1985.

Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer; 2nd edition, 2004.

Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving,  Addison-Wesley, 1984.

Elaine Rich and Kevin Knight. Artificial Intelligence, Tata McGraw Hill, 1991.

Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice Hall, 2009.

Patrick Henry Winston. Artificial Intelligence, Addison-Wesley, 1992.

Stefan Edelkamp and Stefan Schroedl. Heuristic Search: Theory and Applications,  Morgan Kaufmann,  2011.

About the Instructors

Deepak Khemani
Professor, Department of Computer Science and Engineering, IIT Madras

Deepak Khemani is a Professor in the Department of Computer Science and Engineering, IIT Madras, India. He graduated with three degrees from IIT Bombay, including two in Computer Science. His areas of research are broadly in Artificial Intelligence.He is the author of a text book ‘A First Course in Artificial Intelligence’. He has three online courses on Swayam developed as part of the NPTEL program, covering problem-solving using search, knowledge representation and reasoning, and constraint satisfaction.

...  more

His research focus is in the areas of knowledge, memory, reasoning and planning. He plans to employ these to build articulate systems that can take a problem-solving approach to teaching by a machine, especially in the areas of high school mathematics and science. More recently he has worked in the domain of multi-agent systems where an agent has to reason with what other agents know and believe. He is working towards implementing a contract bridge playing program that reasons like a human expert.The human-level contract bridge playing agent will be required to do epistemic planning while collaborating with a team member and competing against opponents in an environment of incomplete information.