Lecture 1:

Lecture 2:

1. What’s Agent?
2. PEAS

Lecture 3:

1. Difference between tree search and graph search:
   Graph search will record the explored nodes, and won’t explore them again.

Lecture 4:

1. DFS, BFS, uniform-cost search, interative deepening search, evaluating search performance about completeness, optimality, time and space complexity
2. BFS:
   Completeness: Yes(When b is finite)
   Optimality: Yes(If path is nondecreasing)
   Time: O(b^d)
   Space: O(b^d)
3. DFS:
   Completeness: Yes(If graph search version)
   Optimality: No
   Time: O(b^m)
   Space: O(b*m)
4. Uniform-cost search:
   Completeness: Yes
   Optimality: Yes(If path is nondecreasing)
   Uniform-cost search not optimal if it is terminated when some node in the queue has goal state.
5. Iterative deepening search:
   Completeness: Yes
   Optimality: Yes
   Time: O(b^d)
   Space: O(bd)

Lecture 5:

1. Uniformed search, bi-directional search, informed search, greedy best first search, A*, interative deepening A*, recursive best first search, simplified memory-bounded A*
2. Bidirectional search:
   Search forward from initial state, and backward from goal.
   Completeness: Yes
   Optimality: Yes
   Time: O(b^(d/2)
   Space: O(b^(d/2)
3. Greedy best first search:
   Greedy BFS keeps all the nodes generated in the
   Frontier, which is sorted based on h(n).
   Completeness: No
   Optimality: No
   Time: O(b^m)
   Space: O(b^m)
4. A* Search:
   Use (approximate) total path cost to guide search
   Admissible Heurisitic: A heuristic is admissible if it never overestimates the cost to reach the goal
   e.g. hSLD(n) is admissible because it never overestimates the actual road distance
   Admissible heuristics does not guarantee that the chosen path is optimal
   A heuristic is consistent if for every node n and every successor n’ of n generated by any action a
   h(n) ≤ c(n,a,n’) + h(n’)
   That is, f(n) is nondecreasing along every path.
   Completeness: Yes
   Optimality: Yes(if admissible in tree search or consistent in graph search)
5. Recursive Best-Frist Search:
   Keep track of f value (f-limit) of best sibling of path currently exploring
   Space: O(bd)
6. Memory-Bounded A*:
   I.e., expand best leaves until available memory is full;When full, SMA* drops worst leaf node (highest f-value);Like RBFS, backup forgotten node value to its parent