Applications Open now for January 2025 Batch | Applications Close: January 02, 2025 | Exam: February 23, 2025
Applications Open now for January 2025 Batch | Applications Close: January 02, 2025 | Exam: February 23, 2025
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.
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*.
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))
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.
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.
