Uninformed Search and Exploration

Problem Solving Agent

Type of goal-based agent that finds sequences of actions that lead to desirable states.

Goal Formulation: Based on current situation and agent’s performance measure

Problem Formulation: Deciding what actions and states to consider, given a goal11. This is where problem abstraction comes in—ignoring irrelevant features like the color of the car or the weather.

Example: Romania Touring

Situation: In Arad, have a ticket out of Bucharest tomorrow.

Goal Formulation: Be in Bucharest before the flight.

Problem Formulation: States = Various cities; Actions = Drive between cities.

Search: Sequence of cities (e.g., Arad \to Sibiu \to Fagaras \to Bucharest)

Well-Defined Problems

Defined formally by 5 components:

  1. Initial state
  2. Actions
  3. Transition model: description of what each action does (successor)22. The transition model together with the initial state define the entire state space of the problem.
  4. Goal test
  5. Path cost

Problem Abstraction: Remove detail while retaining validity and usefulness.

General Search Algorithms

General Graph Search Algorithm

An augmented version of General Tree Search Algorithm that remembers an explored set to avoid repeated states/loopy paths.33. Graph search is strictly necessary on grids and maps, where practically every path has a redundant alternative.

function GRAPH-SEARCH(problem) returns solution \lor failure
    initialize frontier using initial state of problem
    initialize explored set to be empty
    loop do
        if frontier is empty then return failure
        choose leaf node and remove it from the frontier // Search Strategy!
        if node contains goal state then return solution
        add the node to the explored set
        expand chosen node, add resulting nodes to frontier only if not in the frontier or explored set

Search Strategies

Strategies are evaluated by:

Dimensions:

Uninformed Search Strategies (USS)

Strategies that only use information available in the problem definition (blind search).

Breadth-First Search (BFS)

Expand shallowest unexpanded node. Frontier is a FIFO queue.

function BREADTH-FIRST-SEARCH(problem) returns solution \lor failure
    node \leftarrow MAKE-NODE(problem.INITIAL-STATE)
    if problem.GOAL-TEST(node.STATE) then return node
    frontier \leftarrow FIFO queue with node
    explored \leftarrow empty set
    // ... loop expands, adds to explored, checks children against goal before queuing

Note — Space is a larger problem than time for BFS. At d=8 with b=10, memory hits ~103GiB.55. Exponential space complexity means BFS is totally useless for deep problems, regardless of how fast your processor is.

Uniform-Cost Search (UCS / Dijkstra’s)

Expand least-cost unexpanded node. Frontier is a Priority Queue ordered by path cost g(n).66. Uniform-Cost Search is equivalent to Dijkstra’s algorithm from standard data structures, applied to AI state spaces.

function UNIFORM-COST-SEARCH(problem) returns solution \lor failure
    node \leftarrow MAKE-NODE(problem.INITIAL-STATE)
    frontier \leftarrow priority queue ordered by PATH-COST, with node as only element
    explored \leftarrow empty set
    // ... loop expands lowest cost node, updates costs if better path found

Depth-First Search (DFS)

Expand deepest unexpanded node. Frontier is a LIFO queue (stack). Memory efficient but can get stuck in loops (if tree search) or infinite depths.

Depth-Limited Search (DLS)

Variant of DFS with a depth-limit (l). Nodes at depth l have no successors.

function DEPTH-LIMITED-SEARCH(problem, limit) returns solution \lor failure/cutoff
    return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE), problem, limit)

Iterative Deepening Search (IDS)

Gradually increase the depth-limit until a goal is found. Combines benefits of DFS space and BFS completeness/optimality.77. Generating the upper levels of the tree multiple times seems wasteful, but because tree size grows exponentially, the repeated work is dwarfed by the work at the deepest level.

function ITERATIVE-DEEPENING-SEARCH(problem) returns solution \lor failure
    for depth = 0 to infinity do
        result \leftarrow DEPTH-LIMITED-SEARCH(problem, depth)
        if result \ne cutoff then return result

Summary of Uninformed Search Strategies (Tree Search)

Criterion BFS UCS DFS DLS IDS
Complete? Yes Yes No No Yes
Time O(b^d) O(b^{\lceil C^*/\epsilon \rceil}) O(b^m) O(b^l) O(b^d)
Space O(b^d) O(b^{\lceil C^*/\epsilon \rceil}) O(bm) O(bl) O(bd)
Optimal? Yes Yes No No Yes

  1. This is where problem abstraction comes in—ignoring irrelevant features like the color of the car or the weather.↩︎

  2. The transition model together with the initial state define the entire state space of the problem.↩︎

  3. Graph search is strictly necessary on grids and maps, where practically every path has a redundant alternative.↩︎

  4. The branching factor is the average number of legal moves from any given state. For chess, b is approximately 35.↩︎

  5. Exponential space complexity means BFS is totally useless for deep problems, regardless of how fast your processor is.↩︎

  6. Uniform-Cost Search is equivalent to Dijkstra’s algorithm from standard data structures, applied to AI state spaces.↩︎

  7. Generating the upper levels of the tree multiple times seems wasteful, but because tree size grows exponentially, the repeated work is dwarfed by the work at the deepest level.↩︎