Lec 3
Lec 3
Lec 3
Search
Search
• Search permeates all of AI
• What choices are we searching through?
– Problem solving
Action combinations (move 1, then move 3, then move 2...)
– Natural language
Ways to map words to parts of speech
– Computer vision
Ways to map features to object model
– Machine learning
Possible concepts that fit examples seen so far
– Motion planning
Sequence of moves to reach goal destination
• An intelligent agent is trying to find a set or sequence of actions to
achieve a goal
• This is a goal-based agent
Problem-solving Agent
SimpleProblemSolvingAgent(percept)
state = UpdateState(state, percept)
if sequence is empty then
goal = FormulateGoal(state)
problem = FormulateProblem(state, g)
sequence = Search(problem)
action = First(sequence)
sequence = Rest(sequence)
Return action
Assumptions
• Static or dynamic?
Environment is static
Assumptions
• Static or dynamic?
• Fully or partially observable?
Environment is discrete
Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
Environment is deterministic
Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
• Episodic or sequential?
Environment is sequential
Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
• Episodic or sequential?
• Single agent or multiple agent?
Assumptions
• Static or dynamic?
• Fully or partially observable?
• Discrete or continuous?
• Deterministic or stochastic?
• Episodic or sequential?
• Single agent or multiple agent?
Search Example
Formulate goal: Be in
Bucharest.
b=2
Example trees
• Features
Simple to implement
Complete
Finds shortest solution (not necessarily least-cost unless all operators have equal cost)
Analysis
• See what happens with b=10
– expand 10,000 nodes/second
– 1,000 bytes/node
Depth Nodes Time Memory
2 1110 .11 seconds 1 megabyte
4 111,100 11 seconds 106 megabytes
6 107 19 minutes 10 gigabytes
8 109 31 hours 1 terabyte
10 1011 129 days 101 terabytes
12 1013 35 years 10 petabytes
15 1015 3,523 years 1 exabyte
Depth-First Search
• QueueingFn adds the children to the
front of the open list
• BFS emulates FIFO queue
• DFS emulates LIFO stack
• Net effect
– Follow leftmost path to bottom, then
backtrack
– Expand deepest node first
DFS Examples
Example trees
Analysis
• Time complexity
In the worst case, search entire space
Goal may be at level d but tree may continue to level m, m>=d
O(bm)
Particularly bad if tree is infinitely deep
• Space complexity
Only need to save one set of children at each level
1 + b + b + … + b (m levels total) = O(bm)
For previous example, DFS requires 118kb instead of 10 petabytes for d=12 (10 billion times less)
• Benefits
May not always find solution
Solution is not necessarily shortest or least cost
If many solutions, may find one quickly (quickly moves to depth d)
Simple to implement
Space often bigger constraint, so more usable than BFS for large problems
Comparison of Search Techniques
DFS BFS
Complete N Y
Optimal N N
Heuristic N N
Time bm bd+1
Space bm bd+1
Avoiding Repeated States
Can we do it?
E) 0 | 0 1 1 0 0 Score: 4 G) 0 1 1 | 1 0 0 Score: 3
F) 1 | 1 1 0 1 1 Score: 3 H) 0 0 1 | 0 1 0 Score: 6
G) 0 1 1 0 1 | 0 Score: 4 I) 0 0 | 1 0 1 0 Score: 6
H) 1 0 1 1 0 | 1 Score: 2 J) 0 1 | 1 1 0 0 Score: 3