Xiaohong Deng

四 22 八月 2019


CS188: Search

CS188: Artificial Intelligence, Fall 2018, UC Berkeley by Pieter Abbeel and Dan Klein.

Lectures 1 - 3

Definition of Search Problems

  • A state space, all possible states in the world. Could be cells with coordinates in a grid. Could be nodes in a graph.
  • A successor function, f: (current_state, action) -> (action_cost, next_state)
  • A start state
  • A goal state

State Space and Search Tree

State space can be represented as a graph. Starting from the start state, traversing different sequences results in a search tree that branches. Considering the possibility of cycles in the graph, a search tree can be infinitely large.

Uninformed Search

  • Fringe, the nodes on the frontier of explored area of the graph, adjacent to unexplored nodes. Once a node is no longer adjacent to any unexplored nodes, we call it expanded.
  • In implementation, when you pop up (expand) a goal state from the fringe you declare a success, not when you add it to the fringe.
  • Depth-first search, breath-first search, uniform cost search. Uniform cost search expands nodes which have the lowest accumulated edge weight along the path (backward-cost). UCS often maintains nodes in a priority queue.

Informed Search

If we have an idea of where we are relative to the goal state, we are informed.

  • Heuristics. Optimality/admissibility, that is \(0\le h(n)\le h(n^*)\) where \(h(n^*)\) is the true cost (e.g., distance from current state to the goal state) and \(h(n)\) is the heuristic function estimated cost, and consistency, that is sum of forward-cost and backward-cost is always nondecreasing.
  • Greedy search, lowest edge weight to the next node first (forward-cost); A* search, lowest sum of forward-cost and backward-cost first.
  • Graph search. Once we expanded a node in one path, we never expand it again in another path. This could lead to suboptimal solution. Consistent heuristic function can fix it.
  • Dominance. Heuristic a is dominant over b if \(\forall{n}, 0 \le h_b(n) \le h_a(n) \le h(n^*)\)

Project: Search

Go Top
comments powered by Disqus