Repository navigation
Module 2a ‐ Search Problem Fundamentals
In Artificial Intelligence, search is the systematic process of exploring possible sequences of choices to navigate from an initial state to a desired goal state. Rather than acting blindly or attempting haphazard trial-and-error, an intelligent agent formulates its task as a search problem to identify the most efficient sequence of actions before executing them.
Key real-world applications of search problems introduced in the course include:
- Grocery Shopping: Identifying the shortest, most efficient walking path through store aisles to collect required items while avoiding unnecessary aisles.
- Route Planning: Computing optimal navigational routes in apps like Google Maps based on distance, travel time, or fuel consumption.
- Game Playing: Determining legal tactical moves in games like chess to reach a winning board configuration.
- Maze Solving: Navigating an agent from a starting entry point through passages to an exit.
A search problem is formally specified by five foundational components:
-
Initial State (
$s_0$ ): The starting condition or position where the agent begins its search.- Example (Maze): The entry location of the agent.
- Example (Chess): The standard opening board configuration.
- Example (Route Planning): The agent's current geographical location.
-
Actions / Successor Function (
$Actions(s) $ ): The set of all legal moves or decisions available to the agent when in a given state$s$ .- Example (Maze): Legal directional steps such as
$Actions(s) \in {\text{Up}, \text{Down}, \text{Left}, \text{Right}}$ . - Example (Chess): Moving a pawn, capturing a piece, or castling according to rules.
- Example (Route Planning): Choosing which road to take or which direction to turn at an intersection.
- Example (Maze): Legal directional steps such as
-
Transition Model (
$Result(s, a) $ ): A deterministic function that maps state$s$ and action$a$ to the resulting state$s'$ .- Example (Maze): If the agent is at coordinates
$(x, y)$ and takes action$\text{Right}$ , the transition model yields state$(x+1, y)$ . - Example (Chess): Board layout resulting from executing a selected legal move.
- Example (Maze): If the agent is at coordinates
-
Goal Test Function (
$IsGoal(s) $ ): A boolean function that evaluates whether a given state$s$ satisfies the problem's objective, indicating when the search process should terminate.- Example (Maze): Checking whether the current position equals the exit coordinates.
- Example (Puzzle): Evaluating whether the current tile configuration matches the target solved pattern.
- Example (Route Planning): Checking whether all required destination towns have been visited.
-
Path Cost Function (
$C(p) $ ): A numeric scoring function that assigns a cumulative cost to a sequence of actions or state transitions along path$p$ , allowing the agent to evaluate and compare alternative solutions to find the optimal route.- Example (Maze): Total physical distance or step count to reach the exit.
- Example (Chess): Total number of moves required to achieve checkmate.
- Example (Route Planning): Distance traveled, time spent, or energy/fuel consumed.
The Initial State, Actions, and Transition Model together implicitly define the state space of a search problem.
The state space represents the complete universe of all valid states or configurations that an agent can potentially occupy during search. The precise features included in a state definition depend strictly on the problem formulation:
- Maze: Set of all valid physical coordinates
$(x, y)$ inside the maze grid. - Chess: Set of all legal, reachable piece configurations on the
$8 \times 8$ board. - Route Planning: The agent's position on the road network, target destinations, and history of route segments traveled.
To illustrate how a real-world scenario is formulated as a formal search problem, consider planning a road trip to visit a specific set of towns efficiently without wasting fuel or sitting in traffic.
The road trip search problem is structured as follows:
- Initial State (
$s_0$ ): The starting location of the vehicle. - Actions (
$Actions(s) $ ): The choice of road segments available at the current intersection. - Transition Model (
$Result(s, a) $ ): The updated geographical position and travel state after driving down the chosen road. - Goal Test (
$IsGoal(s) $ ): Evaluating whether the vehicle has successfully visited all target towns on the itinerary. - Path Cost Function (
$C(p) $ ): Total cumulative distance traveled, driving time, or fuel consumed.
Let path
where
The multi-step derivation for the total path cost
Depending on user or domain requirements, the step cost function
- Distance-based cost:
$c(s_{i-1}, a_i, s_i) = \text{miles or kilometers driven}$ . - Time-based cost:
$c(s_{i-1}, a_i, s_i) = \text{travel duration accounting for traffic delays}$ . - Energy-based cost:
$c(s_{i-1}, a_i, s_i) = \text{gallons of gasoline or kWh of electricity consumed}$ .
In Artificial Intelligence, a toy problem is a simplified, abstract problem designed specifically for research, teaching, and algorithm testing. Rather than capturing all the messy, unpredictable details of real-world environments, toy problems strip a domain down to its core mathematical essence.
Key benefits of toy problems include:
- Safe and Controlled Environment: Allows developers to test, debug, and understand search strategies on a small scale.
- Standardized Benchmarking: Provides common, universally understood problem setups to compare algorithm performance fairly.
- Problem Formulation Practice: Offers clear practice in defining states, actions, transition models, goal tests, and path costs.
- Scalability Foundation: Builds foundational insights that directly transfer to complex real-world domains such as robotics, industrial scheduling, and route navigation.
The Vacuum World consists of a minimal
The state representation is defined by three state variables:
- Agent Location: The vacuum cleaner position
$\text{Loc} \in {\text{Square A}, \text{Square B}}$ . - Status of Square A: Dirt state
$\text{Status}_A \in {\text{Clean}, \text{Dirty}}$ . - Status of Square B: Dirt state
$\text{Status}_B \in {\text{Clean}, \text{Dirty}}$ .
The total discrete state space size
The Vacuum World search problem is defined as:
- Initial State (
$s_0$ ): Any valid configuration of agent location and dirt status (e.g., Vacuum in Square A, Square A dirty, Square B dirty). - Actions (
$Actions(s) $ ):$Actions(s) \in {\text{Left}, \text{Right}, \text{Suck}}$ . - Transition Model (
$Result(s, a) $ ):- Action
$\text{Left}$ : Moves agent to Square A (no effect if already in Square A). - Action
$\text{Right}$ : Moves agent to Square B (no effect if already in Square B). - Action
$\text{Suck}$ : Changes status of the agent's current square to Clean (no effect if already clean).
- Action
- Goal Test (
$IsGoal(s) $ ): Evaluates to True when both Square A and Square B are Clean ($\text{Status}_A = \text{Clean} \land \text{Status}_B = \text{Clean}$ ). The final position of the vacuum agent is irrelevant. - Path Cost (
$C(p) $ ): Total number of actions executed in the solution sequence (each action has a step cost of$1$ ).
The Vacuum World can be extended to demonstrate key advanced AI paradigms:
- Fully Observable Model: The agent possesses complete state information. Algorithms like
$A^*$ search compute the optimal action sequence to clean all squares. - Partially Observable Model: The agent only senses the dirt status of its current square. This hides global state features and introduces concepts of uncertainty, internal memory, reward optimization, and active sensing.
- Stochastic / Non-Deterministic Dynamics: Introduces environmental randomness where actions may fail or dirt may spontaneously reappear, serving as a testbed for stochastic search and Reinforcement Learning (RL) policies.
The Sliding Eight Tile Puzzle (8-Puzzle) consists of a
The problem components are formulated as follows:
- State Representation: Grid position of each numbered tile (
$1$ to$8$ ) and the blank square. - Initial State (
$s_0$ ): Any valid starting tile arrangement. - Actions (
$Actions(s) $ ): Sliding an adjacent neighboring tile into the empty square (equivalently, moving the blank space Up, Down, Left, or Right). - Transition Model (
$Result(s, a) $ ): The resulting$3 \times 3$ board layout after a tile slide. - Goal Test (
$IsGoal(s) $ ): Checking whether the board matches the target ordered configuration (e.g., tiles in sequence$1$ through$8$ with the blank square in the designated corner). - Path Cost (
$C(p) $ ): Total number of moves or tile slides executed.
While simple to describe, the state space of the 8-Puzzle is significantly large.
The mathematical derivation for the reachable state space size
The complexity of the 8-Puzzle yields key theoretical insights:
- Intractability of Brute-Force: With over 180,000 reachable states, uninformed brute-force search is inefficient, highlighting the necessity of heuristic-driven search strategies.
- Heuristic Evaluation: Serves as a standard domain to measure heuristic accuracy and evaluate effective branching factors (number of expanded nodes).
- Cross-Domain Transfer: Techniques developed for sliding tile puzzles apply directly to real-world planning, scheduling, and route navigation problems.
An algorithm is a precise, step-by-step computational procedure for solving a problem or processing input data into a desired output. In Artificial Intelligence, a search algorithm defines how an agent systematically explores available state transitions, evaluates solution progress, and selects an optimal or feasible sequence of actions from an initial state to a goal state.
Different search strategies introduce distinct operational trade-offs:
- Uninformed (blind) search strategies evaluate nodes based solely on path structure or path cost without domain-specific estimates.
- Informed (heuristic) search strategies incorporate heuristic evaluation functions to guide exploration efficiently toward the goal.
Search algorithms explore state spaces by dynamically building a search tree:
- Root Node: Represents the initial state
$s_0$ where exploration begins. - Branches: Represent legal actions
$a \in Actions(s)$ taken from a state. - Child Nodes: Represent resulting successor states
$s' = \text{Result}(s, a)$ . - Node Expansion: The process of retrieving a node
$n$ from the frontier, identifying all valid actions$a \in Actions(n.\text{STATE})$ , and instantiating child nodes for each generated successor state$s'$ .
The critical distinction between the State Space Graph and the Search Tree is structural:
- State Space Graph: A static representation of the problem domain
$G = (V, E)$ , where vertices$V$ represent unique environment states and edges$E$ represent action transitions. - Search Tree: A dynamic execution tree constructed during search. A single environment state
$s \in V$ may correspond to multiple distinct search nodes in the search tree if reached via different action paths.
All classical search algorithms share a common algorithmic pipeline.
The Frontier (also termed the Open List) is the active data structure containing all generated search nodes that are pending expansion. The policy used to pop nodes from the frontier defines the specific search algorithm strategy.
The Expanded Set (also termed the Closed List or Explored Set) maintains a collection of all states that have already been expanded. Storing visited states prevents duplicate expansion, eliminates redundant paths, and guarantees loop suppression in state space graphs containing cycles.
The general search algorithm loop proceeds as follows:
- Initialize the Frontier using the root node instantiated at initial state
$s_0$ . Initialize the Expanded Set as empty. - If the Frontier is empty, terminate and return failure (no path to goal exists).
- Remove a node
$n$ from the Frontier according to the node selection strategy of the algorithm. - Goal Test: Check if
$n.\text{STATE}$ satisfies the goal condition ($\text{IsGoal}(n.\text{STATE}) == \text{True}$ ). If satisfied, return the solution path by back-tracking parent pointers from$n$ to the root node. - Add
$n.\text{STATE}$ to the Expanded Set. - Expand Node
$n$ : For each legal action$a \in Actions(n.\text{STATE})$ :- Generate successor state
$s' = \text{Result}(n.\text{STATE}, a)$ . - Calculate step cost
$c(n.\text{STATE}, a, s')$ and cumulative path cost$g(s')$ . - Instantiate successor node
$n'$ . - If
$s'$ is neither in the Frontier nor in the Expanded Set, add$n'$ to the Frontier.
- Generate successor state
Programmatically, a search node
-
n.STATE: The specific state space configuration$s$ represented by the node. -
n.PARENT: A reference/pointer to the parent node that generated node$n$ (enables solution path reconstruction). -
n.ACTION: The specific action$a$ applied to the parent node to generate$n$ . -
n.PATH-COST($g(n) $ ): The total cumulative cost of the path from initial state$s_0$ to node$n$ . - Priority Value (
$f(n) $ ): An evaluation function value used by priority queues to order node expansion.
The cumulative path cost
For grid-based robotic navigation (e.g., warehouse automated guided vehicles), the environment model requires three structural representations:
- Grid Dimensions: Defined by total rows
$R$ and columns$C$ , where coordinates are discrete integer tuples$(r, c)$ with$0 \le r < R$ and$0 \le c < C$ . - Obstacle Map: A matrix
$M_{obs} \in {0, 1}^{R \times C}$ , where$M_{obs}[r, c] = 1$ indicates an unpassable barrier and$0$ indicates a passable cell. - Cell Traversal Cost Map: A matrix
$W \in \mathbb{R}^{R \times C}$ where$W[r, c] > 0$ defines the movement cost associated with entering or traversing cell$(r, c)$ .
During node expansion, each candidate move to coordinate
- In-Bounds Condition:
$0 \le r' < R \quad \text{and} \quad 0 \le c' < C$ . - Passability Condition:
$M_{obs}[r', c'] == 0$ .
Candidate moves failing either condition are discarded without instantiation into the Frontier.
The operational behavior of a search algorithm depends on the concrete data structure implementing its Frontier:
- Data Structure: First-In, First-Out (FIFO) Queue.
- Selection Policy: Pops the oldest node in the queue (shallowest node in the search tree).
- Search Traversal: Explores the search space level-by-level.
- Data Structure: Last-In, First-Out (LIFO) Stack or call-stack recursion.
- Selection Policy: Pops the most recently added node (deepest node in the search tree).
- Search Traversal: Pursues a single search branch to its maximum depth before backtracking.
- Data Structure: Min-Priority Queue (Min-Heap).
- Selection Policy: Pops the node with the minimum priority key
$f(n)$ . - Key Specifications:
- Uniform Cost Search (UCS): Priority key
$f(n) = g(n)$ (expands nodes in order of increasing path cost). - A* Search: Priority key
$f(n) = g(n) + h(n)$ , combining actual path cost$g(n)$ with heuristic estimate$h(n)$ .
- Uniform Cost Search (UCS): Priority key
Search algorithms present fundamental trade-offs between solution quality, execution time, and memory footprint. In AI applications, evaluating an algorithm determines its suitability for specific domain requirements, such as prioritizing execution speed in real-time gaming versus guaranteeing path optimality in automated navigation.
Completeness evaluates whether a search algorithm is guaranteed to return a valid solution path whenever at least one solution exists in the search space.
-
Definition: An algorithm is complete if
$IsGoal(s) = \text{True}$ is guaranteed to be reached in finite steps whenever a goal state exists. -
Algorithm Dependencies:
- Breadth-First Search (BFS): Complete in finite state spaces because it systematically expands all nodes level-by-level.
- Depth-First Search (DFS): Incomplete in infinite search spaces or state spaces with unhandled cycles, as it can traverse endlessly down an infinite branch without backtracking.
- Graph Search Modification: Implementing an Explored Set (Closed List) guarantees completeness for finite state spaces by preventing infinite loops caused by cyclic redundant paths.
Optimality assesses whether the algorithm guarantees discovering the path
- Definition: Path optimality is satisfied if:
-
Guarantees Across Search Strategies:
-
Breadth-First Search (BFS): Optimal if and only if all step costs
$c(s, a, s')$ are uniform and equal to a constant$k > 0$ . -
Uniform Cost Search (UCS): Optimal for arbitrary positive step costs (
$c(s, a, s') \ge \epsilon > 0$ ) because it expands frontier nodes strictly in increasing order of path cost$g(n)$ . -
A* Search: Optimal provided its heuristic function
$h(n)$ is admissible (never overestimates true remaining cost) and consistent (monotonic).
-
Breadth-First Search (BFS): Optimal if and only if all step costs
To quantify algorithmic complexity, the search tree geometry is parameterized using three fundamental structural variables:
-
Branching Factor (
$b$ ): The average or maximum number of successor nodes generated by expanding any single state:
-
Shallowest Goal Depth (
$d$ ): The minimum depth level in the search tree containing a valid goal node. -
Maximum Search Tree Depth (
$m$ ): The maximum length or path depth of any branch in the state space tree, which may be infinite ($m = \infty$ ) if loops exist.
Time complexity measures the computational effort of an algorithm as a function of search space dimensions, traditionally evaluated by the total number of node expansions and generated edges.
-
Uninformed Search Time Complexities:
-
BFS:
$O(b^d)$ — Must generate all nodes up to depth level$d$ . -
DFS:
$O(b^m)$ — May explore to the maximum tree depth$m$ before encountering a solution.
-
BFS:
-
Informed Search Time Complexities:
-
A* Search:
$O(|E| \log |V|)$ on finite graphs using a min-priority queue (where$|V|$ denotes the number of vertices/states and$|E|$ denotes the number of edges/transitions), bounded worst-case by$O(b^d)$ depending on heuristic precision.
-
A* Search:
Space complexity evaluates the maximum memory consumption required by the algorithm during execution, governed by the maximum number of stored nodes across the Frontier and Explored Set.
-
Memory Bounds:
-
BFS & A* Search:
$O(b^d)$ — Retains all generated nodes in memory to maintain level order or path history, leading to memory exhaustion in massive search spaces. -
DFS:
$O(b \cdot m)$ — Requires linear memory space relative to maximum depth$m$ , storing only nodes along the current active path and unexpanded siblings.
-
BFS & A* Search:
- Derivation of Total Stored Nodes in BFS Tree:
-
Memory Optimization Strategies:
-
Iterative Deepening A* (IDA*): Combines DFS linear space efficiency
$O(b \cdot m)$ with A* heuristic guidance. - Dynamic A* (D*): Reuses previous path search trees during local map modifications to avoid full recalculation.
-
Iterative Deepening A* (IDA*): Combines DFS linear space efficiency
In industrial deployments and robotics, theoretical Big-O metrics are insufficient. Additional operational criteria determine real-world system feasibility.
- Definition: Scalability measures performance stability as state space size expands by orders of magnitude.
- Sublinear Growth Requirement: Industrial algorithms require sublinear or logarithmic execution time/memory growth relative to problem size.
-
High-Dimensional Motion Planning: Classical grid search (
$A^*$ ) fails in high-dimensional continuous configuration spaces (e.g., multi-joint robotic arms). Randomized sampling algorithms solve high-dimensional spaces:- Rapidly-exploring Random Trees (RRT): Randomly samples configuration space to build search trees efficiently.
- Probabilistic Roadmaps (PRM): Constructs roadmap graphs over continuous spaces via random sampling.
- Definition: Robustness measures an algorithm's ability to handle environmental uncertainty, dynamic obstacles, or unexpected state perturbation.
- Graceful Degradation: Robust algorithms maintain sub-optimal or functional operations rather than experiencing total system failure when conditions change.
-
Dynamic Replanning (Dynamic A* / D*):
- Classical search algorithms (BFS, A*) must discard search trees and restart from scratch when environmental obstacles change.
- Dynamic A* (D*) updates affected path cost values incrementally by repairing existing search trees, reducing replanning latency.
-
Impact of Heuristic Precision: An admissible heuristic guides search toward the goal state. Heuristic accuracy dictates the total number of expanded nodes
$N$ . -
Effective Branching Factor (
$b^*$ ): The parameter$b^*$ represents the branching factor of a uniform tree of depth$d$ containing$N$ expanded nodes:
- Approximation:
-
Evaluation Standard: An ideal heuristic yields
$b^* \to 1$ , reducing search complexity from exponential expansion down to linear progression toward the goal state.
- Parallelizability: The capacity to distribute Frontier node expansions across multi-core CPUs, GPUs, or distributed computing clusters.
- Learnability: The capacity of an agent to improve search heuristic quality or transition models over repeated search episodes using experience.
- Resource & Energy Efficiency: In mobile robotics and edge computing, battery power and thermal energy consumption supersede CPU execution time as the critical limiting operational resource.