Please enable JavaScript.

Coggle requires JavaScript to display documents.

Intro to AI (Search Problem (State space (State space size (W: Needed to…

- - - - W: Needed to solve for a search problem (using fundamental counting principle)
    - - W: States representing nodes with edges representing actions
- - - - W: If solution exists to the search problem, is the strategy guaranteed to find it given infinite computational resources
        
        is there a solution?
    - - W: Strategy guaranteed to find the lowest cost path to a goal state
        
        guaranteed to find the least cost path?
    - - W: Increase in the number of nodes on the fringe node is dequed and replaced with its children O(b)
    - - W: m
    - - W: Depth of the shallowest solution s
  - - - Complete & optimal
      - Strategy: expand lowest cost
      - Worst case: 1) explores options in every 'direction', 2) no info about goal location
    - - D: Always selects the deepest fringe node from the start node for expression
      - Fringe representation: 1) Remove deepest node, 2) Replace it on the fringe with its children (children = deepest nodes); last-in, first-out (LIFO) stack represents a fringe when implementing DFS
        
        left to right
      - Completeness: DFS is not complete (will get "stuck" if cycles exist in a state space graph)
      - Optimality: DFS finds the "leftmost" solution without regard for path costs == not optimal
      - Time Complexity: DFS may end up exploring the entire search tree (worst-case scenario); runtime for maximum depth = O(b^m)
        
        how much time for compute?
      - Space Complexity: DFS maintains b nodes at each m depth levels on the fringe; space complexity = O(bm)
        
        how much memory for compute?
  - - - function that estimates how close a state is to a goal (through cost)
      - Manhattan distance, Euclidean distance
      - Creating admissible heuristics
        
        Ask: 1) What are the states?, 2) How many states?, 3) What are the actions?, 4) How many successors from the start state?, 5) What should the costs be?
        
        solutions to relaxed problems
        
        Trade-off: As heuristics get closer to the true cost, you will expand fewer nodes but usually do more work per node to compute the heuristic itself
      - Semi-lattice
        
        To check b/w 2 heuristics: take the max
      - Consistency
        
        1) estimated heuristic costs <= actual costs; 2) heuristic arc cost <= actual cost for each arc
        
        IF CONSISTENT: f cost will continue to go up so when goal is expanded, nothing else can go higher
    - - Pick the closest to the goal in the fringe
      - What can go wrong: Ignoring cost
      - Heuristic: estimates distance to nearest goal for e/a state (greatly depends on the heuristic
      - Worst case: badly-guided DFS
    - - Not optimal: actual cost < heuristic
      - Admissibility
        
        Inadmissible: heuristic breaks optimality
        
        Admissible: heuristic slows down bad plans but never outweigh true costs; heuristic <= cheapest cost node to the goal
        
        0 <= h(n) <= hstar(n); hstar(n) is the true cost to a nearest goal
        
        EX: manhattan, pancake flipping
      - Properties
        
        Favors the direction towards the goal; stops when we deque a goal
        
        brings together UCS + Greedy Search
        
        Orders by the sum: g + h
        
        Uses both backward costs and (estimates of) forward costs
        
        optimal with admissible/consistent heuristics
      - Applications: Video games, resource planning problems, robot motion planning, language analysis, machine translation
  - - - consistency implies admissibility
- - - - W: Doesn't think about consequences of actions
      - Considers how the world IS
    - - W: 1) has goals; 2) performs actions to yield goals
      - Optimizes expected utility
    - - W: Outperforms reflex agents