Content
Definition
Formalising a search problem
Search state graph
Search tree
Generic tree search
What is Search
Agents may need to be able to plan ahead, i.e. to reason so as to find a sequence of actions needed to solve a task.
In AI, search techniques are universal problem‐solving methods. Agents use these search methods to solve a specific problem and provide solutions.
Search is the process of navigating from a start state to a goal state by transitioning through intermediate states.
Search Problems
A search problem consists of
State space: all possible states.
Start state: where agent begins the
search.
Goal test: whether the goal state is
achieved or not.
A successor function (also called transition function): what each action does and the effects on states, associated with cost.
Cities Start state: Arad
A solution is a sequence of actions which transforms the start state to a goal state.
Successor function: Road to adjacent city with cost =
State space:
Goal test: Is state == Bucharest
Solution:
any path from Arad to Bucharest
distance
State Space Graph
State space graph: A mathematical representation of a search problem
Nodes represent states
Arcs represent successors (action results) Goaltestisagoalnodeorasetofgoal
A
CG
nodes
S
B
In real world problems, we usually cannot build state space graph in memory as it is too big
Search Tree
A
CG
A search tree
S
B
The start state is the root node
Children correspond to successors
Nodes show state, but correspond to
S
B
plans that achieve those states
A BCC
CGG G
Search Tree
A
CG
A search tree
S
B
The start state is the root node
Children correspond to successors
Nodes show state, but correspond to
S
B
plans that achieve those states
A BCC
CGG G
Search Tree
A
CG
A search tree
S
B
The start state is the root node
Children correspond to successors
Nodes show state, but correspond to
plans that achieve those states
For most problems, we can never
build the whole tree
IfaddinganarcfromBtoA,thenit
ends up an infinite tree
Example: Romania
Search with a search tree
Sibiu
Timisoara Zerind
Arad
Arad Fagaras Oradea R.V. Arad Lugoj Arad Oradea
Search with a search tree
Sibiu
Timisoara Zerind
Arad
Arad Fagaras Oradea R.V. Arad Lugoj Arad Oradea
Search with a search tree
Sibiu
Timisoara Zerind
Search
Arad
Arad Fagaras Oradea R.V. Arad Lugoj Arad Oradea
Expand out potential plans (tree nodes) Maintain a frontier (also called fringe) of
partial plans under consideration
Try to expand as few nodes as possible
Generic tree search
function Tree-Search (problem, strategy) return a solution, or failure initialise the search tree via setting Frontier to be the start state of problem loop do
end
if there are no nodes in Frontier for expansion then return failure
choose a node in Frontier for expansion according to strategy and remove it from Frontier
if the node contains a goal state then return the corresponding solution
else expand the node based on problem and add the resulting nodes to Frontier
Important ideas:
Frontier
Expansion
Exploration strategy
Main question: which node in Frontier to explore?
Example: Tree Search and Priority Queue
Search tree
SS
Priority queue
B BC
S‐B
A
S‐A‐B S‐A‐C
S
B
A
CG
State space graph
S‐A
Example: Tree Search and Priority Queue
Search tree
SS
Priority queue
B BCC
S‐B
A
S‐A‐B S‐A‐C
G
S‐A‐C‐G S‐B‐C
S
B
A
CG
State space graph
S‐A