Problem Space and Search - Lecture Notes

Introduction

  • Topic: Problem Space and Search in AI (Lecture 5).
  • Focus: formal representation of problems, state spaces, and search strategies to find solutions under constraints.

What is a Problem in AI?

  • A problem is a particular task that calls for decision-making or solution-finding.
  • Central idea: identify a pathway from an initial condition to a desired goal using permissible actions.

Core Components of Problems in AI

  • Initial State: The problem's starting condition.
  • Goal State: The desired outcome or solution.
  • Operators: Actions that transition the system from one state to another.
  • Restrictions: Rules or constraints that limit permissible actions or states.

Example: Chess Game

  • Initial State: Starting positions of all chess pieces.
  • Objective State: Achieving checkmate.
  • Operators: Permissible moves for each piece.
  • Constraints: Rules governing chess gameplay.

Problem Space

  • A PROBLEM SPACE IS A FORMAL REPRESENTATION OF ALL POSSIBLE STATES AND ACTIONS.
  • Understanding the framework involves:
    • DEFINE THE PROBLEM
    • IS THE PROBLEM CLEAR? (YES/NO)
    • If YES: IDENTIFY POSSIBLE STATES; EXPLORE POTENTIAL ACTIONS
    • If NO: CLARIFY THE PROBLEM

Problem Formulation by State Space Search

1) State space formally defines problem structure.
2) Graph (V, E) represents state space.
3) Nodes (V) correspond to problem states.
4) Arcs (E) represent applicable actions.
5) Directed arcs connect parent and child nodes.
6) Parent precedes, child succeeds in graph.

Components of Problem Spaces

  • States: Possible scenarios within the problem.
  • State Space: All reachable states from the start.
  • Paths: Connections between states via operators.

Example: Maze-Solving Problem

  • State Space: The maze structure itself.
  • States: All possible positions in the maze.
  • Paths: Routes connecting start to the exit.
  • Example 1: Maze-Solving Problem with START and END.

Example 2: Puzzle Solving

  • This example illustrates a sliding puzzle scenario with a current state and a target state.
  • Current State: displayed as a grid (example excerpt shows numbers arranged in a 3x3-like layout).
  • Target State: the goal grid layout (numbers arranged in a different configuration).
  • Possible moves (examples from the slide):
    • Slide 1 right
    • Slide 4 up
    • Slide 7 up
    • Slide 2 left
  • The slide sequence shows intermediate states evolving toward the target configuration.
  • This example demonstrates how operators (slides) generate successor states in the state space.

Example 3: Tic-Tac-Toe

  • Approaches:
    • Approach 1: Table Based
    • Approach 2: Magic Square
    • Approach 3: Uses three sub procedures: Make 2, Posswin(p), Go(n)
  • These illustrate different strategic representations and procedures to determine moves or winning paths in a simple game.

Search in AI

  • Definition: Process of finding problem solutions.
  • Purpose: Identify solutions that meet constraints and achieve goals.
  • Method: Systematically traverse the problem domain by applying operators to move through states.

Mapping Minds with State Space (Preview)

  • The next topic focuses on mapping cognitive processes to state-space representations in AI.

Types of Search in AI

  • Uninformed Search (no domain-specific knowledge)
  • Informed Search (uses domain knowledge/heuristics)
  • Common Uninformed Search methods:
    • Breadth-First Search (BFS)
    • Depth-First Search (DFS)
  • Common Informed Search methods:
    • Greedy Best-First Search (heuristic-driven)
    • Uniform Cost Search
    • A* Search (cost + heuristic)
  • Observations on operators and data structures:
    • BFS uses a Queue
    • DFS uses a Stack
  • A* Search is characterized as costing with a heuristic to optimize path selection.
  • Optimal path: A* is generally optimal when the heuristic is admissible.
  • Notation for A*: define f(n) as the evaluation function:
    • f(n)=g(n)+h(n)f(n) = g(n) + h(n)
      where:
    • g(n)g(n) is the cost from the start node to node nn,
    • h(n)h(n) is the heuristic estimate of the cost from nn to the goal.

Summary and Look Ahead

  • The material sets up the problem space formalism (states, operators, restrictions), and demonstrates how to formulate and solve problems via state-space search.
  • Next topic indicated: Mapping Minds with State Space – deeper exploration of representing cognitive processes as state spaces.