Notes - Artificial Intelligence MT24, Uninformed search

Search strategies that use no external domain knowledge, just the definition of the problem. For reference, this is:

1. A set of states $S$
2. An initial state $s$, where the agent starts
3. Possible actions, described by a function $\mathbf{Actions}(s)$ which returns the set of actions applicable to state $s$
4. A transition model, given by a successor function $\mathbf{Result}(s, a)$ which returns the state obtained by applying action $a$ to state $s$
5. Goal test: A function for checking whether a state is a goal
6. Path cost: A function assigning a value $\mathbf{pc}(p)$ to each path $p = s _ 0, a _ 1, s _ 1, a _ 2, \ldots$ and so on.

Expand the oldest unexpanded node.

• Complete? Yes, if $b$ finite
• Time? $O(b^{d+1})$ (consider $1 + b + b^2 + \cdots$ worst case)
• Space? $O(b^{d+1})$
• Optimal? Not in general, but yes if cost is $1$ for every step.

Expand the least-cost unexpanded node in the frontier.

• Complete? Yes, if all step costs are $\ge \varepsilon$ where $\varepsilon$ is a positive constant (otherwise you could go into an infinite loop with zero-cost actions)
• Time? $O(b^{\lceil C^\star / \varepsilon\rceil})$ where $C^\star$ is the cost of the optimal path (this is equivalent to the number of nodes with path cost $\le C^\star$).
• Space? $O(b^{\lceil C^\star / \varepsilon\rceil})$ where $C^\star$ is the cost of the optimal path.
• Optimal? Yes.

Expand the deepest unexpanded node.

• Complete? Not in general, but yes if the search space is finite.
• Time? $O(b^m)$
• Space? $O(bm)$
• Optimal? No.

Call depth-limited search with increasing depth limit until a solution is found.

• Complete? Yes.
• Time? $O(b^d)$
  • $(d+1) b^0 + db^1 + (d-1)b^2 + \cdots + b^d$
• Space? $O(bd)$
• Optimal? Not in general, but yes if the step cost is one.

Failing to remember already explored states can turn a linear problem into an exponential one.

function GraphSearch(problem, frontier) returns (solution or failure):
	explored = {}
	Insert(RootNode(problem.InitialState), frontier)
	while the frontier is not empty:
		node = Remove(frontier)
		add node.State to explored
		if problem.GoalTest(problem.node.State):
			return node
		for each action in problem.Actions(node.State):
			if child.State is not in explored: (*)
				Insert(ChildNode(problem, node, action), frontier)
	return failure

• Need to be able to compare states for equality
• Can also check in $(\star)$ that we haven’t already added child.State to the frontier

It requires memory linear in the size of the state space, since you need to remember almost all states in the worst case. One way to get around this is only to check for repeated states on the current path.