 ##### Published

←Home

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^*)$$

Go Top