the vault

Informed Search

create frontier

insert Node(initial_state) to frontier:

while frontier is not empty:
	node = frontier.pop()
	if node.state is goal:
		return solution

	for action in actions(node.state):
		next_state = transition(node.state, action)
		frontier.add(Node(next_state))

return failure

Motivations

These algorithms are used when there are extra information - such as a heuristic function describing the cost.

Heuristics

Heuristic

An estimate of the optimal path cost from any state to the goal state.

Straight-line distance h_{SLD}, Manhattan distance h_{MD}.

Admissibility

Admissible

An admissible heuristic is one that never overestimates the cost to reach a goal (therefore an optimistic heuristic)

A heuristic is admissible if for every node , where is the optimal path cost to reach the goal state from .

Given heuristics which are all admissible,

is also admissible by definition. This can be seen by the proof:

Inventing Admissible Heuristics

A problem with fewer restrictions on the actions is called a relaxed problem. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.

Relaxing a navigation problem

Original problem: Agent can only move on roqads Relaxations: Agents can move off road - use , or can teleport - use

Consistency

A heuristic is consistent, if for every node , every successor of generated by any action ,

and

Triangle inequality

This is a form of the triangle inequality, stipulating that a side of a triangle cannot be longer than the sum of other two sides.

Stronger property of admissibility

Every consistent heuristic is admissible, but not vice versa.

Given heuristics which are all consistent,

is also consistent by definition. Proof is trivial and similar to proving that average of all admissible heuristics is also admissible.

SGnh*(n)cost(S, n)h*(S)h(S)h(n, G) ## Dominance

If for all , then dominates ,

  • is better for search if admissible.

Note

If a heuristic is dominant over the other, and admissible, it means that the heuristic function returns results closer to the actual cost since it does not overestimate the cost at all time.

Best-first Search

create frontier: PriorityQueue(f(n))

insert Node(initial_state) to frontier:

while frontier is not empty:
	node = frontier.pop()
	if node.state is goal:
		return solution

	for action in actions(node.state):
		next_state = transition(node.state, action)
		frontier.add(Node(next_state))

return failure

where refers to the cost to reach , and is the estimated cost from .

Analysis

Time complexity (number of nodes generated): Exponential Space complexity (size of frontier): Exponential with regards to the depth of the optimal solution Completeness: Complete, if edge cost is the same Optimality: Optimal, if step cost is the same.

If h(n) is admissable, A* search using search (with visited memory) is optimal.

If h(n) is consistent, A* search using search (with/without visited memory) is optimal.

Note that consistency implies admissability, so the first property holds.

However, inadmissibility of a heuristic does not automatically disqualify A* from being cost-optimal. There are two cases in which this does not hold:

  • If there is a cost-optimal path on which is admissible on all nodes , regardless of whether is admissible on all the other states off the path, that path will be found regardless.
  • If the optimal solution has cost and second best has cost , if overestimates costs, but never by more than , is still guaranteed to return cost-optimal solutions (without visited memory)

Graph View

Backlinks