Uninformed Search

Reflex agents:

  • agents that have a current percept and maybe memory.

  • they do not consider the future consequences of their actions.

Planning agents:

  • ask “what if”

  • decisions based on consequences of actions

  • must formulate a goal (test)

Planning vs. Replanning:

  • planning looks at all options first

  • replanning only looks at the next option

  • ex. pacman

A search problem consists of:

  • a state space

  • a successor function (with actions, costs)

  • start state

  • goal test

  • a solution is a sequence of actions (a plan) which transforms the start state to a goal state

Ex. Travelling in Romania

  • State space: cities

  • Successor function: roads (go to adjacent city with cost = distance)

  • start state: given city

  • goal test: Is State == given city?

Another Example:

State Space Graphs:

  • mathematical representation of a search problem

  • nodes are world configurations

  • each state only occurs once

  • arcs represent successors

  • WAY too big!

Search Trees:

  • starts with start state then expand out potential plans (tree nodes)

    • maintain a fringe of partial parts under consideration

      • fringe: set of leaf nodes waiting to be expanded

    • try to expand as few tree nodes as possible

  • a “what if” tree of plans and their outcomes

  • start state is the root node

  • children correspond to successors

Depth-First Search:

  • expand a deepest node first

  • fringe is a LIFO

  • b is the branching factor

  • m is the maximum depth

  • solutions could be at various depths

  • number of nodes in a tree: O(bm)

  • if m is finite, takes time O(bm)

  • Is it complete?

    • m could be infinite, so only if we prvent cycles

  • Is it optimal?

    • no, it finds the leftmost solution

Breadth-First Search:

  • expand shallowest node first

  • fringe is FIFO

  • search takes time O(bs) where s is the depth of shallowest solution

  • Is it complete?

    • s must be finite if a solution exists, so yes

  • Is it optimal?

    • only if costs are all 1

When will BFS outperform DFS?

  • when finding the shortest path

When will DFS outperform BFS?

  • If all solutions are quite deep, this will be faster

Iterative Deepening:

  • idea: get DFS’s space advantage with BFS’s time/shallow-solution advantages

  • Run a DFS with depth limit 1. If no solution…

  • Run a DFS with depth limit 2. If no solution…

  • Etc.

Cost-Sensitive Search:

  • Uniform-Cost Search:

    • expand the cheapest node first

    • fringe is a priority queue

    • Is it complete?

      • assuming best solution has a finite cost and minimum cost arc is positive, yes

    • Is it optimal?

      • yes