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