Problem Solving in AI
Searching, Optimization, Planning,
Game Theory
Objectives
• Understand key areas of problem-solving in AI:
Searching, Optimization, Planning, Game
Theory.
• Recognize the types of problems each area
can address.
• Apply basic methods for problem-solving with
real-world examples.
Introduction to Problem Solving in
AI
• Problem-solving in AI involves algorithms to
tackle complex tasks.
• Four key areas:
- Searching: Exploring state spaces to find solutions.
- Optimization: Finding the best solution among many.
- Planning: Generating sequences of actions for goals.
- Game Theory: Strategic decision-making in multi-agent
systems.
Searching
• Searching is used to explore state spaces.
• Types of search:
- Uninformed: BFS, DFS.
- Informed: A* search.
• Examples of problems solved by searching:
Pathfinding in navigation (e.g., GPS).
Puzzle-solving (e.g., the 8-puzzle, Rubik’s Cube).
• Example Problem: Pathfinding in a 5x5 grid.
• Solution: Use A* search with Manhattan distance
Optimization
• Solves problems where goal is to maximize or
minimize a function.
• Types of optimization:
• - Gradient Descent: Iterative minimization.
• - Genetic Algorithms: Evolutionary
optimization.
• Examples of problems solved by optimization:
• Resource allocation (e.g., scheduling tasks).
• Machine learning (e.g., training a neural network).
Planning
• Generates action sequences to move from
initial to goal state.
• Types of planning:
• - State-Space: Search in all possible states.
• - Partial-Order: Search in partial plans.
• Examples of problems solved by planning:
Robotics (e.g., navigating a robot in a warehouse).
Logistics (e.g., delivery scheduling).
• Example: Robot navigation in a warehouse.
Game Theory
• Models strategic interactions among agents.
• Key terms:
• - Players: Decision-makers in the game.
• - Strategies: Choices available to players.
• - Payoffs: Rewards based on strategies.
Examples of problems solved by game theory:
• Competitive games (e.g., chess, tic-tac-toe).
• Strategic pricing in business.