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.

Taught by Deepak Khemani

Code BSCS3003

Credits 4 Credits

Type Core Option II

Prerequisites None

Core Competencies

What You'll Learn

View 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.

12-Week Roadmap

Course Structure & Syllabus

For details of standard term assessment timelines and exam structures, visit our 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.

Reading List

Prescribed Books & References

Deepak Khemani. A First Course in Artificial Intelligence, McGraw Hill Education (India), 2013. (Chapters 1 – 8, some parts from Chapters 9 and 10))
Reference
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.

Faculty & Experts

About the Instructors

Deepak Khemani

Professor , Department of Computer Science and Engineering , IIT Madras

Faculty Webpage

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.

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.

Back to Academics Overview View all Degree Level courses