State Space

A state is a complete snapshot or configuration of the problem at a given point in time. It encodes all relevant information necessary to make a decision.

• Examples: In chess, a state is the board position of all pieces. In pathfinding, it's the (x, y) coordinates of an agent.
• Key Property: States must be discrete and enumerable for algorithmic search, though the set can be infinite.
• Representation: Typically implemented as a data structure (e.g., tuple, object, hash) that uniquely identifies the configuration.

The initial state is the starting point of the search problem, representing the configuration from which the agent or algorithm begins its exploration.

• Formal Role: Denoted as s₀ in problem definitions. All valid solution paths must originate from this state.
• Practical Impact: The complexity of finding a solution is often measured relative to the distance from the initial state to a goal state.
• Example: In the 8-puzzle, the initial state is the specific, scrambled arrangement of tiles.

A goal state is any state that satisfies the problem's termination conditions. The search algorithm's objective is to find a sequence of actions leading from the initial state to any goal state.

• Types: Can be a single explicit state (e.g., checkmate in chess) or a set of states defined by a goal test (e.g., any city named 'Bucharest' in route planning).
• Goal Test: A function isGoal(s) that returns True if state s meets the solution criteria.
• Example: In propositional logic, a goal state is any assignment of variables that makes the entire formula true.

Actions (or operators) define the set of legal moves or transformations that can be applied to a state to transition to a new state. They encapsulate the problem's dynamics.

• Formalism: For a given state s, Actions(s) returns the finite set of applicable actions.
• Determinism: In classic search, applying action a in state s leads to a single, deterministic successor state s'.
• Example: In the vacuum cleaner world, actions are {Move_Left, Move_Right, Suck}. In Rubik's Cube, an action is a 90-degree turn of a face.

The transition model (implemented by the successor function) defines the outcome of applying an action to a state. It is the engine that generates the state space graph.

• Function: Result(s, a) → s'. Given a state s and an applicable action a, it returns the successor state s'.
• Core of Search: This function is called during node expansion to generate child nodes. Its efficiency is critical for algorithm performance.
• Graph Representation: Collectively, the transition model defines the edges of the state space graph, connecting states.

The path cost function assigns a numeric cost to a sequence of actions (a path). Search algorithms like A* and Uniform-Cost Search use this to find optimal (lowest-cost) solutions.

• Additivity: The cost of a path is typically the sum of the step costs: c(s, a, s') for each action taken.
• Step Cost: The cost c(s, a, s') of moving from state s to s' via action a. Often assumed to be non-negative.
• Optimality: An algorithm is optimal if it finds a solution path with the minimum possible total cost. If all step costs are identical, minimizing cost is equivalent to minimizing the number of steps.

The search space is the specific subset of the total state space that an algorithm actually explores while looking for a solution. It is defined by the search strategy's frontier and explored set.

• A state space represents all possibilities; the search space is the explored portion.
• Efficient algorithms like A* use heuristics to prune the search space, avoiding exponential growth.
• In chess, the state space is ~10^120 possible board sequences, but a competitive engine's search space during a move might be limited to a few billion positions evaluated via alpha-beta pruning.

A successor function (or transition function) is a formal operator that defines the legal moves from any given state, generating its neighboring states. It is the engine that maps the current state to the next possible states in the graph.

• For a navigation agent, the successor function returns adjacent locations reachable by moving north, south, east, or west.
• In automated planning, it applies actions defined in a Planning Domain Definition Language (PDDL) to produce new world states.
• The complexity of the successor function directly impacts the branching factor of the search tree.

State representation is the data structure used to encode a problem's configuration. An effective representation is both sufficient (contains all necessary information) and efficient for the successor and heuristic functions to compute.

• Common representations include vectors, matrices, graphs, or symbolic logic expressions.
• For a sliding tile puzzle (e.g., 8-puzzle), a compact representation is a 3x3 matrix of numbers.
• Poor representation can make a problem intractable; good representation is a key step in problem formulation for search.

These are two fundamental paradigms for exploring a state space, differing in how they handle revisited states.

• Tree Search algorithms (like basic DFS) can revisit states, potentially getting stuck in infinite loops in cyclic graphs. They only track the frontier.
• Graph Search algorithms maintain an explored set (or closed list) to avoid re-expanding any state, guaranteeing termination in finite spaces. Uniform-Cost Search and A* are typically implemented as graph searches.
• The choice impacts completeness, optimality, and memory usage.

The branching factor is a critical metric describing the average number of successors generated by applying the successor function to a state. It determines the exponential growth of the search tree.

• A high branching factor (e.g., in Go, ~250) creates a vast state space, necessitating strong heuristics and pruning.
• A low branching factor makes exhaustive search more feasible.
• The effective branching factor is often used to analyze an algorithm's performance in practice, measuring how well heuristics control expansion.

Problem formulation is the process of defining a real-world task as a formal search problem within a state space. It requires specifying:

1. The initial state.
2. The goal state or goal test.
3. The actions (operators) and the successor function.
4. A path cost function.

• Poor formulation leads to inefficient or incorrect searches. For example, formulating a logistics problem at the individual package level versus the truckload level creates vastly different state spaces.
• It is the essential first step before applying any heuristic search algorithm.