Please enable JavaScript.

Coggle requires JavaScript to display documents.

AI (Search algorithms ~ the order of expand search nodes ~ the way use…

- - - - Completeness: No, infinitely long unless acyclic, thus cycle check
        Optimality: no, hope to get lucky :
      - Time: O(b^d )
        Space: O(bd )
    - - Completeness: Yes
        Optimality: for Uniform Cost is yes, find the shallowest goal state
      - Time: O(b^d )
        Space: O(b^d ) worse
    - - Completeness: Yes for acyclic path, thus cycle check
        Optimality: for Uniform Cost is yes, find the shallowest goal state
      - Time: O(b^d )
        Space: O(bd)
      - suits for large state spaces with unknown solution depth
  - - - Greedy Best-First search: satisfying planning
        
        Completeness:Yes for safe heuristic and duplicate detection to avoid cycles.
        Optimality: No, the first one might not be the best.
        
        implementation: priority queue(h(state(σ)) & check duplicates
        
        tie-breaking: same h value, then choose the smaller g value
      - Weighted A*: satisfying planning
        
        For W = 0, weighted A∗ behaves like: Uniform-Cost
        
        For W = 1, weighted A∗ behaves like: A*
        
        For W→∞, weighted A∗ behaves like: Greedy Best-First
        
        bounded suboptimal
      - A*: optimal planning
        
        Completeness:Yes for safe heuristic(even without duplicate detection).
        Optimality: Yes,for admissible heuristics(even without duplicate detection).
        
        Implementation:
        
        priority queue f(s) = g(state(σ)) + h(state(σ)
        
        re-opening: not required for admissible and consistent h
        
        hard to spot bug
        
        tie-breaking: the same f value then choose the smaller h value
    - - Hill Climbing:
        only if h(s) > 0 for s 不属于 SG
        
        It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.
        
        Completeness:No, will be trapped in loops. -> tie breaking strategy, restart
        Optimality: No, easily get stuck in local minima
      - Enforced Hill Climbing:
        satisfying planning/ Local + systematic;
        only if h(s) > 0 for s 不属于 SG
        
        FIFO queue,
        when h(s) -> 0, 该算法越趋向于BFS
        Completeness: In general No, Yes under some special circumstance.
        
        if goal state with strictly small h-value is not reachable from the current state. But this would not happen for undirected state space（有进有出）.
        Optimal: No, similar to BFS
    - - safe if h∗(s) = ∞ for all s ∈ S with h(s) = ∞;
        h*: optimal heuristic value
        h: heuristic value
      - goal-aware if h(s) = 0 for all goal states s ∈ SG;
      - admissible if h(s) ≤ h∗(s) for all s ∈ s ;
      - consistent if h(s) ≤ h(s') + c(a) for all transitions s --a-->s'
      - admissible => safe:
      - Goal-aware & consistent -> admissible
        admissible -> Goal-aware & safe
- - - - IW(k) breadth-first search that prunes newly generated states whose novelty(s) > k.
        IW is a sequence of calls IW(k) for i = 0, 1, 2, . . . over problem P until problem
        solved or i exceeds number of variables in problem
      - IW(k) expands at most O(n^k) states, where n is the number of atoms.
      - width(Π) = k:
        
        IW(k) solves Π in time O(n^k)
        
        IW(k) solves Π optimally
        
        IW(k) is complete for Π
      - works excellent for atomic goals
    - - achieve atomic goals one at a time
      - blind search; better than GBFS + hadd
  - - - planners needs to work without complete declarative representations/languages
- - - - Fully observable, probabilities state models
        唯一的不同是 transition probabilities:
        Pa(s'|s) for s ∈ S and a ∈ A(s)
  - - - Problem: a tuple P = <F, O, I, G>
        
        F: boolean facts
        
        O: operators/actions
        
        I: initial situation
        
        G: goal situation
        
        Operators:
        
        Add: Add
        
        Delete: Del
        
        Precondition： Prec
      - state model:
        S=2^F
        G ⊆ s
- - - - native ifP' ⊆ P and h'* = h∗; same heuristic method rather than value
      - efficiently constructible if there exists a polynomial-time algorithm that, given Π ∈ P, computes r(Π); not exponential
      - efficiently computable if there exists a polynomial-time algorithm that, given Π' ∈ P', computes h'*(Π').
      - relaxation heuristic hR(Π) := h'(r(Π)) satisfies hR(Π) ≤ h∗(Π).
        *Admissibility of h^R strict requirement
    - - Dominance:
        s'+ dominates s+ if s'+ ⊇ s+
        
        If s+ is a goal state, then s'+ is a goal state as well.
        
        If vector a+ is applicable in s+, then vector a+ is applicable in s'+ as well, and appl(s'+,vector a+) dominates appl(s+,vector a+).
        
        appl(s'+,vector a+) -> pre(a0) ⊆ s+
        
        appl(s, a+) dominates both (i) s and (ii) appl(s, a)
        没有del，结果集只会增不会减
      - delete relaxation is admissible when have the optimal relaxed plan
        
        vector a is the optimal plan of the problem, then the relaxed plan vector a+ ⊇ vector a, then the relaxed plan is admissible
        only when vector a+ is the optimal relaxation plan
        
        Greedy Relaxed Planning
        
        satisfying planning
        
        sound
        
        completeness
        
        terminates in time polynomial in the size of Π
        the number of possible actions that the problem can accept/execute (each action can play once)
        
        safe: Yes
        goal-aware: Yes
        admissible: No, because the relaxed plan is not optimal, just randomly choose an action
        consistent -> no.
        
        for optimal delete relaxation plan,
        
        native: Yes
        
        efficiently constructible: Yes
        
        efficiently computetional: No, still NP-hard
      - Approximate h+: Additive and Max Heuristics
        
        reduce the computational cost of delete relaxation(quick)
        
        approximate h+
        
        assumption: all sub-goal facts are achieved independently
        
        h^max is optimistic-> optimal
        h^max ≤ h+, and thus hmax ≤ h∗
        因此 h^max is admissible
        
        h^add is pessimistic
        h^add ≥ h+, and thus h^add > h*(s)
        因此 not admissible but more informed
        
        better informed for the wrong reason: overcounts[cause dramatic over-estimate of h*] <- ignore positive interactions
        ie: sub-plans shared between sub-goals
        
        (hmax and hadd Agree with h+ on ∞)
        h+(s) = ∞ if and only if hmax(s) = ∞ if and only if hadd(s) = ∞.
        
        relaxed plan extraction to reduce the overcounts
        
        computer best-supporter function: bs
        closed and well-founded function
        
        for each fact p属于F returns the cheapest achiever action(within relaxation)
        
        can based on hmax or hadd
        
        The support graph of bs is the directed graph with vertices F ∪ A and arcs {(p, a) | p ∈ prea} ∪ {(a, p) | a = bs(p)}.
        
        We say that bs is closed if bs(p) is defined for every p ∈ (F \ s) that has a path to a goal g ∈ G in the support graph.
        
        We say that bs is well-founded if the support graph is acyclic.
        
        If a relaxed plan exists, then there also exists a closed well-founded best-supporter function
      - hFF Relaxed Plan Heuristic
        
        not overcount, may be inadmissible like hadd, not/not too much over-estimate h*
        
        hFF is Pessimistic and Agrees with h∗ on ∞