Search

Reflex Agents

• Reflex Agents
  • Choose action based on current percept (and maybe memory)
  • May have memory or a model of the world’s current state
  • Do not consider the future consequences of their actions
  • Consider how the world IS

Planning agents:

• Planning agents
  • Ask “what if”
  • Decisions based on (hypothesized) consequences of actions
  • Must have a model of how the world evolves in response to actions
  • Must formulate a goal (test)
  • Consider how the world WOULD BE
• Optimal vs. complete planning
• Planning vs. replanning

Search problem

• A search problem consists of:
  • A state space
  • A successor function(with actions, costs)
  • A start state and a goal test
• A solution is a sequence of actions (a plan) which transforms the start state to a goal state

State Space Graphs

• State space graph: A mathematical representation of a search problem
  • Nodes are (abstracted) world configurations
  • Arcs represent successors (action results)
  • The goal test is a set of goal nodes (maybe only one)
• In a state space graph, each state occurs only once!
• We can rarely build this full graph in memory(it’s too big), but it’s a useful idea

Search Trees

• A search tree: A”what if” tree of plans and their outcomes
  • The start state is the root node
  • Children correspond to successors
  • Nodes show states, but correspond to PLANS that achieve those states
  • For most problems, we can never actually build the whole tree

Each NODE in the search tree is an entire PATH in the state space graph.
We construct both on demand一and we construct as little as possible.
Depth-First Search

• What nodes does DFS expand？
  • Some left prefix of the tree.
  • Could process the whole tree！
  • If m is finite，takes time $O(b^m)$
• How much space does the fringe take？
  • Only has siblings on path to root，so $O(bm)$
• Is it complete？
  • m could be infinite，so only if we prevent cycles（more later）
• Is it optimal？
  • No，it finds the “leftmost” solution，regardless of depth or cost

Breadth-First Search

• What nodes does BFS expand?
  • Processes all nodes above shallowest solution
  • Let depth of shallowest solution be s
  • Search takes time $O(b^s)$
• How much space does the fringe take?
  • Has roughly the last tier, so $O(b^s)$
• Is it complete?
  • S must be finite if a solution exists, so yes!
• Is it optimal?
  • Only if costs are all 1 (more on costs later)

Uniform Cost Search

• What nodes does USC expend?
  • Processes all nodes with cost less than cheapest solution!
  • If that solution costs C and arcs cost at least e, then the “effective depth” is roughly $$C^/\varepsilon$$
  • Takes time $O(b^{C^*/\varepsilon})$ (exponential in effective depth)
• How much space does the fringe take?
  • Has roughly the last tier, so $O(b^{C^*/\varepsilon})$
• Is it complete?
  • Assuming best solution has a finite cost and minimum arc cost is positive, yes!
• Is it optimal?
  • Yes! (Proof next lecture via A*)

Search and Models

• Search operates over models of the world
  • The agent doesn’t actually try all the plans out in the real world!
  • Planning is all “in simulation”
  • Your search is only as good as your models…