Skip to content

2 Uninformed Search

Search Problems

Why do we even care about search??? - ubiqitous problem in evrday life - how did you even get to this lecture hall? How will you get home? - WHich classes should you take in which order, to achineve your liife goals?

A rational Agent will find the most optimal way to achieve this foal?

Quotations from "Lost and Found" by katherine Shulz: perhaps worth a read

  • Pathing and routing problems (both for people and robots)
  • chip design
  • resource planning problems
  • robot motion lanning
  • proten desing
  • language analysis
  • etc...

TODAY - agents that plan ahead - search problems, - uninformed search - dfs - bfs - uniform cost

Agents and Environments - An agent perceives its enviornment through sensors and acts upon it through actuators (effectors) - The agent function maps percept sequences to actions - It is generated by an agent program running on a machine

TYPES OF AGENTS

  • reflex agent

    • Choose an action based on its current percept
    • may have memory or a model of the world's current state
    • does not consider the future of their actions
    • consider how the world IS (Does not simulate)
    • Can a reflex agent be rational?
      • No, it cannot be rational
      • It cannot achieve the right consequences
      • Imagine Pac-Man just goes for the pellets and doesn't care if they leave dots, doesnt care if its getting closer to a ghost

  • Agents that plan

    • Planning agents
      • ask "what if?>"'
      • makes decisions based on the hypothesized consequences of the agent
      • must have a model of how the world evolces in response to actions
      • must formulate a goal
      • considers how the world WOULD BE
    • Optimal vs Complete planning
    • Planning vs Replanning

A search problem consists of: - a state space - a successor function (With actions, costs) - North(1), East(1), etc for pac man - a start state and a goal test - Goal test may not be a location (are all the pellets eaten?) A solution is a sequence of actions that transforms the start state to a goal state

Search problems are MODELS - lowk not good to write out all the states - So let's only expand out as many states as we need to - I only want to roll out as many options as tractibly possible

Example: traveling in Romania

We want to get from ARAD to BUCHAREST Distinct costs are traveling from one city to the next until we can travel in Romania

  • State Space
    • Cities
  • Successor Function
    • A function that takes the current city
    • Go to the adjacent city with cost c
    • Roads
  • Start State
    • ARAD
  • Goal State
    • Bucharest
  • Solution
    • least cost
    • Optimal path through the space

WHATS A STATE???

The world state includes every last detail of the environment:

A search state keeps only the details needed for planning (Abstraction)

  • Problem: Pathing
    • States: (x, y) location
    • ACTIONS: North, South, East, West
    • Successor: update location only
    • Goal Test is (x, y) = END
  • FOR PAC MAN -> Problem: Eat all the dots
    • States ((x, y) with dot booleans)
    • Actions: North, South, East, West
    • Successor: Update Location and dot booleans possibly
    • Goal Test: All dots eaten (False)

State space sizes? - world state: - Agent positions: 120 - food count: 30 - ghost positions: 12 - Agent facing: NSEW - How many: - World States? \(120 * 2^{30} * 12^{2} * 4\) - states for pathing? \(120\) - States for eats all dots? \(120 * 2^{30}\)

ws = 120 * 2^30 * 12^2 *4
p  = 12
e = 120 * 2^30

QUIZ - problem: eat all the dots while keeping the ghosts perma-scared - what does the state space have to specify? - Agent Position, Dot Booleans, Power Pellet Booleans, Remaining Scared time

State space graphs and search tree - State space graph: A mathematical reperesentation of a search problem. - nodes are abstracted world configurations - arcs represent successors - the goal test is a set of goal nodes: maybe the only one - in a state space graph each state occurs only once! - we can rarely build this full graph in memory 9its too big) but its a useful idea

Search Tree

() <- start state
| \
|  \
()  () <- child nodes are from the parents
.
.
.
and so on
  • asks a "what if plan of plans and their outcomes"
  • follows the state space graph to achieve the goal state
  • Each terminal node is a goal state
  • Plan out the possible futures you have in the tree because you can't track it in the state space graph

State space graph vs search trees - Each node in the search tree is an entire path of the state space graph - We construct only what we need on demand - If you start out with a graph - You can follow all of the successors and branch out in your search tree - the depth d of the states you can be in after d actions

QUIZ!!!

Let's create the search tree for this graph

Tree search, let's go back to our example from Romania!

Start at ARAD

searching with the search tree: - expand out potential plans (tree nodes) - maintain a fringe of partial plans under construction - try to expand as few tree nodes as possible

General Tree Search

Function TREE-SEARCH(Problem, Strategy) returns a solution or failure
    initialize the tree using the initial 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 correspinding solution
        else expand the node and add the resulting nores to the search tree
    end
  • important ideas
    • fringe
    • expansion
    • exporation strategy
  • MAIN QUESTION: Which fringe nodes to explore?

Example: Tree Search S

S->D S->E S->P S->D->B S->D->C S->D->E S->D->E->H S->D->E->R S->D->E->R->F S->D->E->R->F->G Yay We made it!

This is a reflex agent that always goes left somehow found the goal!

Lets cover DFS - as it sounds - expand as deep as possible - dont care about anything other than making the tree as long as possible - DFS Strategy: Expand the deepest node first - Implementation: Fringe is a LIFO Stack - Now how will it go?

so then S S-D S-D-B S-D-B-A Dead End Go Back S-D-C S-D-C-A Dead End S-D-E S-D-E-H S-D-E-H-P S-D-E-H-P-Q Dead End S-D-E-H-Q Dead End S-D-E-R S-D-E-R-F S-D-E-R-F-G made it! Finally!

Lets look at the proterties

  • Complete: Guaranteed to find a soln if one exists? YES
  • Optimal: Guaranteed to find least cost path? NO
  • Time Complexity: Branching Factor and etc
  • Space Complexity: depends on how we expand and our stack
  • Cartoon of search tree
    • b is the branching factor
    • m is the max depth
    • solns at vairous depths
  • number of nodes in the entire tree
  • 1 + b + b^2 + ... + b^m = O(b^m)
    • thats how long it could take depending on these consts

For DFS - 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) to traverse the tree - How much space does the fringe take - only siblings are on the path to the root so O(bm) - is it complete? m could be infinite, so only if we prevent cycles - is it optimal? - no it finds the leftmost soln regardless of depth or cost

Define BFS - strategy: expand a shallowest node first - Implementation: fringe is a FIFO queue - traverses entire layer before moving on - add all children to queue after popping

BFS properties: - bfs expands - process all nodes abouve the shallowest soln - let depth of shallowest be s - search takes time O(b^s) - how much space does

QUIZ when will bfs outperform dfs? - if the goal is close to the root/on the right side - will not hit infinite loops/will handle much better when will dfs outperform bfs? - dont have much memory - solutions are deep and far away from root - solns more on the left

Iterative deepening: - run dfs with depth lim of 1 if no soln, - run dfs with depth lim of 2 if no soln,

Cost-sensitive search?? - bfs finds the shortest path, but does not find the least-cost path - with romaina and different edges having different cost - so bfs wont help us with no cost analysis

Uniform cost search: - expand the cheapest node first - fringe is now a priority queue - only expand the node that gives you the cumulatively lowest cost next (Djikstras algo)

next time A search etc. heuristics informed search greedy and A