Introduction to Artificial Inteligence - Spring 2001

Problem Solving and Search

1. Problem solving agents
2. Formulating problems (through example - vacuum cleaning world)
   • Knowledge and problem types: single/multiple state, contingency, interleaving, exploration.
   • Well-defined problems and solutions: states (initial, goal), operators, path cost.
   • Measuring problem-solving performance
   • Choosing states and actions
3. Example problems
   • Toy problems: 8 puzzle, N queens, vaccuming, missionaries and cannibals.
   • Application problems: route planning (and TSP), VLSI layout and routing, navigation, assembly planning.
4. Searching for solutions
   • General search algorithm
   • Basic data-structures for search
5. Search strategies
   • Criteria for evaluating search: completeness, space/time complexity, optimality of solution.
   • Breadth-first search (BFS)
   • Uniform-cost search
   • Depth-first search (DFS)
   • Depth-limited search
   • Iterative deepening search
   • Biderectional search
6. Repeated states during search
7. Constraint satisfaction problems (CSP)