Informed search

created: 2020-01-15 · modified: 2020-09-08

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).

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 implements the strategy where nodes estimated to be nearest to the goal are expanded first
Greedily prioritizes the best estimates first

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

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.

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