Search 4

Problem Solving Rational agents need to perform sequences of actions in
order to achieve goals.
Intelligent behavior can be generated by having a look-up

table or reactive policy that tells the agent what to do in every circumstance, but:
Problem Solving and Search
-Such a table or policy is difcult to build -All contingencies must be anticipated A more general approach is for the agent to have
knowledge of the world and how its actions affect it and be able to simulate execution of actions in an internal model of the world in order to determine a sequence of actions that will accomplish its goals.
This is the general task of problem solving and is typically

performed by searching through an internally modelled space of world states.
Problem Solving Task Given: -An initial state of the world -A set of possible possible actions or operators that can
be performed.
Measuring Performance
Path cost: a function that assigns a cost to a path, typically

by summing the cost of the individual operators in the path. May want to nd minimum cost solution.
-A goal test that can be applied to a single state of the

world to determine if it is a goal state.
Search cost: The computational time and space (memory)

required to nd the solution.
Find: -A solution stated as a path of states and operators that

shows how to transform the initial state into one that satises the goal test.
Generally there is a trade-off between path cost and search

cost and one must satisce and nd the best solution in the time that is available.
The initial state and set of operators implicitly dene a state

space of states of the world and operator transitions between them. May be innite.
Sample Route Finding Problem

Oradea Neamt Zerind Iasi Arad Sibiu Fagaras Vaslui Timisoara Rimnicu Vilcea
Sample Toy Problems 8-puzzle (sliding tile puzzle)

5 6 7
Hirsova
4 1 3
Start State
5 1 8 8 2 2 6 8 7
4 2
3 8 4
Lugoj
Pitesti
6
Goal State
2 5
Mehadia
Urziceni Bucharest
Dobreta Craiova Giurgiu Eforie
Peg Puzzle (Hi-Q) Cryptarithmetic

+ + FORTY TEN TEN ---------SIXTY 29786 + 850 + 850 --------31486 F=2, O=9, R=7, T=8,...
Initial state: Arad Goal state: Bucharest Path cost: Number of intermediate cities, distance traveled, expected travel time
Toy Problems (cont) 8-queens problem (N-queens problem)
More Realistic Problems Route nding Travelling salesman problem VLSI layout Robot navigation Web searching
Missionaries and cannibals

Identity of individuals irrelevant,best to represent state as (M,C,B) M = number of missionaries on left bank C = number of cannibals on left bank B = number of boats on left bank (0 or 1) Operators to move: 1M, 1C, 2M, 2C, 1M1C Goal state: (0,0,0)
Searching Concepts A state can be expanded by generating all states that can
be reached by applying a legal operator to the state.
Expanding Nodes and Search

(a) The initial state Arad
(b) After expanding Arad
Arad
State space can also be dened by a successor function

that returns all states produced by applying a single legal operator.
(c) After expanding Sibiu Sibiu Timisoara Zerind
A search tree is generated by generating search nodes by

successively expanding states starting from the initial state as the root.
Sibiu
Arad
Timisoara
Zerind
A search node in the tree can contain -Corresponding state -Parent node -Operator applied to reach this node -Length of path from root to node (depth) -Path cost of path from initial state to node
Arad
Fagaras
Oradea
Rimnicu Vilcea
function GENERAL-SEARCH( problem,strategy) returns a solution, or failure initialize the search tree using the initial state of problem loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according to strategy if the node contains a goal state then return the corresponding solution else expand the node and add the resulting nodes to the search tree end
10
Search Algorithm Easiest way to implement various search strategies is to

maintain a queue of unexpanded search nodes.
Search Strategies Properties of search strategies -Completeness -Time Complexity -Space Complexity -Optimality Uniformed search strategies (blind, exhaustive, bruteforce) do not guide the search with any additional information about the problem.
Different strategies result from different methods for

inserting new nodes in the queue.
function GENERAL-SEARCH( problem,QUEUING-FN) returns a solution, or failure nodes MAKE-QUEUE(MAKE-NODE(INITIAL-STATE[problem])) loop do if nodes is empty then return failure node REMOVE-FRONT(nodes) if GOAL-TEST[problem] applied to STATE(node) succeeds then return node nodes QUEUING-FN(nodes,EXPAND(node,OPERATORS[problem])) end
Informed search strategies (heuristic, intelligent) use

information about the problem (estimated distance from a state to the goal) to guide the search.
11
12
Breadth-First Search Expands search nodes level by level, all nodes at level d
are expanded before expanding nodes at level d+1
Breadth-First Complexity Assume there are an average of b successors to each

node, called the branching factor.
Therefore, to nd a solution path of length d must explore

1+b+b +b ++b
2 3 d
nodes.
Plus need bd Implemented by adding new nodes to the end of the queue
(FIFO queue): GENERAL-SEARCH(problem, ENQUEUE-AT-END)
nodes in memory to store leaves in queue.
Assuming can expand and check 1000 nodes/sec and need

100 bytes/node storage , b=10
Depth 0 2 4 6 8 10 12 14 Nodes 1 111 11,111 106 108 1010 1012 1014 1 .1 11 18 31 128 35 3500 Time millisecond seconds seconds minutes hours days years years Memory 100 11 1 111 11 1 111 11,111 bytes kilobytes megabyte megabytes gigabytes terabyte terabytes terabytes
Since eventually visits every node to a given depth,

guaranteed to be complete.
Also optimal provided path cost is a nondecreasing function

of the depth of the node (e.g. all operators of equal cost) since nodes explored in depth order.
Note memory is a bigger problem than time.
13
14
Uniform Cost Search Like breadth-rst except always expand node of least cost
instead of of least depth (i.e. sort new queue by path cost).
S 0 S
Depth-First Search Always expand node at deepest level of the tree, i.e. one of
the most recently generated nodes. When hit a dead-end, backtrack to last choice.
A 1
B 5
C 15 S
A A 1 S 15 C G 11 (a) (b) G 10 5 B 5 5 A B C 15 10 G G 11 B 5 C 15 S
Do not recognize goal until it is the least cost node on the

queue and removed for goal testing.
Therefore, guarantees optimality as long as path cost never

decreases as a path increases (non-negative operator costs).
Implemented by adding new nodes to front of the queue:

GENERAL-SEARCH(problem, ENQUEUE-AT-FRONT)
15
16
Depth-First Properties Not guaranteed to be complete since might get lost

following innite path.
Iterative Deepening Conduct a series of depth-limited searches, increasing

depth-limit each time.
function ITERATIVE-DEEPENING-SEARCH( problem) returns a solution sequence inputs: problem, a problem for depth 0 to do if DEPTH-LIMITED-SEARCH(problem,depth) succeeds then return its result end return failure
Not guaranteed optimal since can nd deeper solution

before shallower ones explored.
Time complexity in worst case is still O(bd) since need to

explore entire tree. But if many solutions exist may nd one quickly before exploring all of the space.
Space complexity is only O(bm) where m is maximum

depth of the tree since queue just contains a single path from the root to a leaf node along with remaining sibling nodes for each node along the path.
Seems wasteful since work is repeated, but most work is at

the leaves at each iteration and is not repeated. Depth-rst:
1+b+b ++b
2
d2
+b
d1
+b
Can impose a depth limit, l, to prevent exploring nodes

beyond a given depth. Prevents innite regress, but incomplete if no solution within depth limit.
Iterative deepening:
( d + 1 )1 + db + ( d 1 )b + + 3b
2
d2
+ 2b
d1
+ 1b
Time complexity is still O(bd) Space complexity O(bm)
17
18
Avoiding Repeated States Basic search methods may repeatedly search the same
state if it can be reached via multiple paths.
A B C D C A
B C C
B C
Three methods for reducing repeated work in order of

effectiveness and computational overhead:
-Do not follow self-loops (remove successors back to the

same state).
-Do no create paths with cycles (remove successors

already on the path back to the root). O(d) overhead.
-Do not generate any state that was already generated.
Requires storing all generated states (O(bd) space) and searching them (usually using a hash-table for efciency).
19

Search 4

Uploaded by

Copyright:

Available Formats

Search 4

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Search 4

Uploaded by

Copyright:

Available Formats

Problem Solving Rational agents need to perform sequences of actions in

order to achieve goals.

Intelligent behavior can be generated by having a look-up

Problem Solving and Search

This is the general task of problem solving and is typically

Path cost: a function that assigns a cost to a path, typically

-A goal test that can be applied to a single state of the

Search cost: The computational time and space (memory)

Find: -A solution stated as a path of states and operators that

Generally there is a trade-off between path cost and search

The initial state and set of operators implicitly dene a state

Sample Route Finding Problem

Sample Toy Problems 8-puzzle (sliding tile puzzle)

Dobreta Craiova Giurgiu Eforie

Peg Puzzle (Hi-Q) Cryptarithmetic

Toy Problems (cont) 8-queens problem (N-queens problem)

Missionaries and cannibals

Expanding Nodes and Search

(b) After expanding Arad

State space can also be dened by a successor function

A search tree is generated by generating search nodes by

Search Algorithm Easiest way to implement various search strategies is to

Different strategies result from different methods for

Informed search strategies (heuristic, intelligent) use

Breadth-First Complexity Assume there are an average of b successors to each

Therefore, to nd a solution path of length d must explore

nodes in memory to store leaves in queue.

Assuming can expand and check 1000 nodes/sec and need

Since eventually visits every node to a given depth,

Also optimal provided path cost is a nondecreasing function

Note memory is a bigger problem than time.

Do not recognize goal until it is the least cost node on the

Therefore, guarantees optimality as long as path cost never

Implemented by adding new nodes to front of the queue:

Depth-First Properties Not guaranteed to be complete since might get lost

Iterative Deepening Conduct a series of depth-limited searches, increasing

Not guaranteed optimal since can nd deeper solution

Time complexity in worst case is still O(bd) since need to

Space complexity is only O(bm) where m is maximum

Seems wasteful since work is repeated, but most work is at

Can impose a depth limit, l, to prevent exploring nodes

Time complexity is still O(bd) Space complexity O(bm)

Three methods for reducing repeated work in order of

-Do not follow self-loops (remove successors back to the

-Do no create paths with cycles (remove successors

-Do not generate any state that was already generated.

You might also like