# Informed search

# Uninformed Search

- Search problems where nothing is known about the environment beforehand (or about the goal).
- BFS, DFS, and UCS are all uninformed search algorithms, knowing nothing about the goal or the environment but just blindly exploring action paths (and UCS using path costs).

# Informed Search

- Search problems where specific problem knowledge is known and can be used by an algorithm
- This information is encoded in a
**heuristic**, which effectively estimates how close a state is to the goal in some way- Examples include a measure of distance to goal (manhattan, euclidean)

## Greedy Search

- Greedy search implements the strategy where nodes estimated to be nearest to the goal are expanded first
- Greedily prioritizes the best estimates first

## A* search

- A* search incorporates both
*uniform-cost search and greedy search*, expanding nodes according to the priority determined by the sum $f(n) = g(n) + h(n)$, where $g(n)$ is the current path cost (or backward cost, since cost is not toward the goal but backward toward the starting node), and $h(n)$ is the goal proximity (or forward cost). - Algorithm only terminates when a goal state is
*dequeued*rather than enqueued. That particular goal state may be reachable by a different path not yet explored with lower overall cost, but was enqueued according to on particular with the intermediate distance to goal estimate wrong. - Most of the work is coming up good
*admissible*heuristics

## Admissible Heuristics

- Admissable (optimistic)
*heuristics*slow bad plans but don’t outweigh true costs. More formally, a heuristic is admissible if $0 \le h(n) \le h^*(n)$ where $h*(n)$ is the true cost to the nearest goal state.

## Creating Admissible Heuristics

- Generally constitutes most of the work in solving hard search problems
- Admissible heuristics are often solutions to a relaxed version of the search problem
- Quality and work tradeoff: as heuristic gets closer to the true cost, fewer nodes will be expanded but will usually have to do more work per node to get the estimated value