Agent Design

• Fully/partially observable => agent requires memory (internal state)
• Discrete/continuous => agent may not be able to enumerate all states
• Stochastic/deterministic => agent may have to prepare for contingencies
• Signle-agent/multi-agent => agent may need to behave randomly

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

Can a reflex agent be rational?

Planning Agents

• Planning agents:
  • Ask "What if"
  • Decisions based on (Hypothesizezd) 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 Problems

• A search problem consitsts 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.

Search Tree

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

Searching with a Search Tree

• Expand out potential plans (tree nodes)
• Maintain a fringe of partial palns under consideration
• Try to expand as few tree nodes as possible
• Might end up in a loop

General Tree Search

function TREE_SEARCH(problem, strategy) returns a solution or failure
	initialize the search tree using the intial state of problem
    loop do
    	if there are no candidates for expansion then return failure
        choose a leaf node for expansion according to strategy
        if the node contains a goal state then return the corresponding solution
        else expand the node and add the resulting nodes to the search tree
    end

Search Algorithm Properties

• Complete: Guaranteed to find a solution if one exists?

• Optimal: Guaranteed to find the least cost path?

• Time complexity?

• Space complexity?

• Cartoon of search tree:

  	- b is the branching factor

  • m is the maximum depth
  • solutions at various depths

• Number of nodes in entire tree?

  • 1 + b + b^2 + ... + b^m = O(b^m)

DFS Properties

• what nodes 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

BFS Properties

• 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)

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 ...
  • RUn a DFS with depth limit 3. ...
• Isn't that wastefully redundant?
  • Generally most work happens in the lowest level searched, so not so bad.

Cost-Sensitive search

BFS finds the shortest path in terms of number of actions.
It does not find the least-cost path. We will now cover a similar algorithm which does find the least-cost path.

Uniform Cost Search

• What nodes does UCS expand?

  • 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/e
  • Takes time O(b^(C*/e))

• How much space does the fringe take?

  • Has roughly the last tier, so O(B^(C*/e))

• Is it complete?

  • Assuming the best solution has a finite cost and minimum arc cost is postitive, yes!

• Is it optimal?

  • Yes! (Proof next lecture via A*)