Introduction to Artificial Inteligence - Spring 2001
BGU Computer Science Department
Problem Solving and Search
- Problem solving agents
- 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
- 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.
- Searching for solutions
- General search algorithm
- Basic data-structures for search
- 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
- Repeated states during search
- Constraint satisfaction problems (CSP)