Notes - Artificial Intelligence MT24, Problem solving and search

A function which takes a percept sequence and returns an action.

An agent outputting the best action for every percept sequence according to a given performance measure.

• Problem formulation: decide actions and states to consider.
• Search: find a sequence of actions.
• Execution: apply the sequence found.

An environment where sensors detect all aspects relevant to action choice.

The effects of all actions are known precisely; there are no errors or uncertainty.

Nothing changes while the agent is computing the response.

Time, environment state, and actions are discrete variables.

There is no interaction with other agents.

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.

A solution with the lowest cost among all paths.

• A state is a particular configuration of the problem
• A node is a data structure used to represent the search tree
  • Parent
  • Child
  • Depth
  • Path cost

function TreeSearch(problem, frontier) returns (a solution, or failure)
	Insert(RootNode(problem.InitialState), frontier)
	while the frontier is not empty:
		node = Remove(frontier)
		if problem.GoalTest(node.State):
			return node
		for each action in problem.Actions(node.State):
			Insert(ChildNode(problem, node, action), frontier)

where

function ChildNode(problem, parent, action) returns (a node):
	return a node with:
		State = problem.Result(parent.State, action)
		Parent = parent,
		Action = action,
		Depth = parent.Depth + 1,
		PathCost = parent.PathCost + problem.StepCost(parent.State, action)

• Breadth-first search: use a queue
• Depth-first search: use a stack

• $b$: maximum branching factor
• $d$: depth of least-cost goal node
• $m$: maximum depth of search tree (may be infinite)