Search Methods in Artificial Intelligence

For an autonomous agent to behave intelligently, it must be able to solve problems: arriving at decisions that transform a given situation into a desired goal state, and anticipating the consequences of those decisions to identify ones that work. This course covers a wide variety of search methods that agents can employ for problem-solving.

We begin the history of AI and look at philosophical perspectives.

Then we look how to formalize search problems in the state space and in the solution space.

We look at the idea of heuristic functions. We then move on to stochastic local search methods to address the fact that search and optimization can be hard problems.

Following that we look at finding optimal solutions and look at algorithm A* and its variations.

Then we look at goal trees which are a different approach to defining search spaces. We also look at algorithms for playing board games like chess and observe their relation with goal trees.

The next module looks at how the activity of planning is posed as search, and study different algorithms for planning.

We study how forward chaining rule-based systems have been deployed for capturing expert knowledge and business rule management systems.

Towards the end we see how deduction in logic is posed as a search problem, and finally how constraint satisfaction is a unified approach to solve problems with a combination of search and reasoning.

• Define the domain functions to pose a problem as a search problem.
• Evaluate the benefit of a heuristic function for guiding a search algorithm.
• Study the travelling salesperson problem and choose an appropriate algorithm to solve it within given time constraints.
• Implement a program to play board games like chess (in our case Othello).
• Understand how a rule-based system works.
• Become familiar with automated planning approaches.
• Get a glimpse of a unifying problem solving approach in the form of constraints processing.

• Deepak Khemani, Search Methods in Artificial Intelligence, Cambridge University Press, 2024.

1. Deepak Khemani. A First Course in Artificial Intelligence, McGraw Hill Education (India), 2013. (Chapters 1–8, some parts from Chapters 9 and 10).
2. Stefan Edelkamp and Stefan Schroedl. Heuristic Search: Theory and Applications, Morgan Kaufmann, 2011.
3. John Haugeland. Artificial Intelligence: The Very Idea, A Bradford Book, The MIT Press, 1985.
4. Pamela McCorduck. Machines Who Think: A Personal Inquiry into the History and Prospects of Artificial Intelligence, A K Peters/CRC Press; 2nd edition, 2004.
5. Eugene Charniak and Drew McDermott. Introduction to Artificial Intelligence, Addison-Wesley Publ., 1985.
6. Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer; 2nd edition, 2004.
7. Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
8. Elaine Rich and Kevin Knight. Artificial Intelligence, Tata McGraw Hill, 1991.
9. Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice Hall, 2009.
10. Patrick Henry Winston. Artificial Intelligence, Addison-Wesley, 1992.