Search Strategies
[AIMA 4G] Chapter 3
(Optional: 3.5.5-3.5.6; 3.6.3-3.6.6)
COSC1127/1125
Artificial Intelligence
Semester 2, 2021
Prof. Sebastian Sardiña
* Many slides are based on slides from James Harland, Kate Larson, and Pascal Poupart.
** All images gathered via Google image search
—
Wominjeka! Welcome!
I acknowledge, and invite you all to acknowledge, the Traditional Owners (Wurundjeri people of the Kulin Nations) of the land on which we will conduct this session for AI21. I recognise their continuing connection to land, waters and culture, as well as the challenges and injustices that continue up to our times, unfortunately.
IMPORTANT DISCLAIMER
These pack of slides are NOT core study
material. The core & main material is the book or any specific resources given for the week.
The slides in this presentations were only for supporting the instructor during the lectorial.
These pack of slides do not represent the complete material of the week, but only a few bits here and there around what was discussed in lectorials. Most of the week content will NOT show up in this pack of slides.
Please refer to the book (and any resources specifically given) for a comprehensive coverage of the week material.
Questions?
How did you spend the 6-8 self-study hours on this course last week?
Read the book?
Watched the videos?
Completed Tute 1?
*
Pacman Projects
Project 0: Python warm-up (no marks) – INDIVIDUAL
DONE!! Results to be emailed soon!
No certification = no marking.
Project 1: basic search – INDIVIDUAL
Specification available in EdStem Resources.
Due Sunday August 8th at 11:59pm
Project 2: search against an opponent – GROUP
Project 3 (bonus): learning to play! – INDIV
Capture the Flag Contest: GROUP
don’t speculate with teams: we will use our agents
details will come in assignment specification
Tell them that project 0 is already marked and results will come today afternoon! and also tell them Project 1 is available on the course web page and deadline is Sunday March 18 (pdf was wrong before!)
Project 1 – Search
Basis for the final Contest Project, don’t miss it!
You have 2 weeks to do it, don’t leave it to the end.
Q1-Q8 from UCB + Q9 on IDS.
Team formation, when?
Not yet, but you can get ready, of course!
You will build teams for Project 2 (in ~2 weeks).
Looking for partners? Check post #8!
Groups of 3 as default.
Groups of 4 for final
project if argued
well.
More will be asked.
Still, P2 in (two)
groups of 2..
Autograder
Autograder is a feedback for you, not the final mark of your solution.
We will:
Run more tests (you can make your own!).
Inspect code manually.
Inspect commit history:
Who committed, how often, how meaningful, message quality.
Poor commits: dummy, upload, few or none, poor message, huge changes in one commit, etc.
Call for interviews.
Run CodeQuiry for similarities
in and outside class.
Feedback branch
Keep an eye and reply if we contact you there…
AI’21 Honors Code
Your solutions must be your own work.
The code representing your actual solution to the problem should be your code – check here.
You may only reuse non-essential code, provided you understand it and acknowledge it clearly.
Do not Google solutions: do it yourself!
CODEQUIRY knows them all! Not worth the risk…
You may not share or show code with anyone.
You may not engage in any other activities that will dishonestly improve your results or dishonestly improve or damage the results of others.
*** DO NOT LET US DOWN ***
Tutorials: towards production-based
Let’s go back to Search!
*
Search is an exploration of possibilities.
Useful when a ‘direct’ method is not known.
Mathematically: graph reachability.
What is search?
Initial state
Goal states
Search for path planning
Searching for a ‘good’ route in a map
Search for solving puzzles
Search for aerospace missions
The Search Problem
A search problem is defined by:
Possible states
Initial state
Actions
Transition model
Goal test
Path “cost”
Initial State
Goal State
How to do this?
TRANSFORM VIA ACTIONS
*
Data Structures for Search
What is in each node of the tree?
Basic data structure: Search Node
Domain state
Parent node
Operator applied to parent to reach current node
Cost of the path so far
Depth of the node
This is an important slide. Differentiate the DOMAIN STATE from the SEARCH NODE. The domain state is just about the domain features, the search node contains information of the search process itself, like link to the parent and cost so far (and other data in advanced algorithms)
Search Types
Uninformed (blind search)
Depth-first
Breadth-first
Uniform cost
Depth-limited
Iterative Deepening
Informed search (heuristic)
Greedy Best-first search
A*
‹#›
*
Let’s play the search contest!!
Code 7014 4579 @ menti.com
‹#›
function SEARCH (problem, strategy) // outputs solution or failure
Initialize queue by inserting the node corresponding to the initial state
Repeat
1. If (queue is empty) then return failure
2. Dequeue a node as per strategy
3. If (node contains a goal state) then return solution
4. Else
Expand the node as per problem, by applying legal operators to the state within the node, and add new nodes to queue.
Implementation Details
‹#›
Need to keep track of nodes that need to be expanded (fringe):
– Use a (prioritized) queue
Search algorithms differ in their queuing function!
*
The beauty of search algorithms is that they are all “the same”, except for some plug-play aspects, mostly selecting the next node to “expand”
Un-informed (blind) search
Breadth-first search:
Frontier is a queue (FIFO): Shallowest node first
Complete, optimal, exponential.
Depth-first search:
Frontier is a stack (LIFO): Deepest node first
not complete or optimal, exp time, but poly space!
Uniform-cost search (variant of Dijkstra’s algo.)
Frontier is priority-queue on cost so far g(n)
Iterative deepening search
Combines breadth and depth first search
‹#›
*
This is a 1 slide summary; students should have seen BFS and DFS and Dijkstra in AA, so we would not go via them in detail but just a quick review. We want to go over A*, that is the important bit. So the slides next will go fast as a “review”
Search Performance
Completeness: Is it guaranteed to find a solution if one exists?
Optimality: Will it find an optimal solution?
Time complexity: How many nodes?
Space complexity: How much memory is needed?
b Branching factor
d Depth of shallowest goal node
m Maximum length of any path in the state space
*
Informed Search
[AIMA 4G] Sec. 3.5+
*
function SEARCH (problem, strategy) // outputs solution or failure
Initialize search tree with root being the initial state
Repeat
1. If (no leaf can be expanded) then return failure
2. Choose a leaf node as per strategy
3. If (chosen node contains a goal state) then return solution
4. Else
Expand the node as per problem, by applying legal operators to the state within the node, and add new nodes to the search tree.
Generic Search Procedure
‹#›
*
The beauty of search algorithms is that they are all “the same”, except for some plug-play aspects, mostly selecting the next node to “expand”
Tree vs Graph Search
‘Those who cannot remember the past are condemned to repeat it.’
— George Santayana (1905)
‘Search algorithms which cannot remember the past are condemned to repeat it’
— Russell & Norvig (2009)
Eight puzzle: can oscillate between states
Grids: many paths to same state
*
Implementation Details
‹#›
function SEARCH (problem, strategy) // outputs solution or failure
Initialize search tree with root being the initial state
Repeat
1. If (no leaf can be expanded) then return failure
2. Choose a leaf node as per strategy
3. If (chosen node contains a goal state) then return solution
4. Else
Add node to the explored (or visited) set of nodes
Expand the node as per problem, by applying legal operators to the state within the node, and add new nodes to the search tree only if not in the frontier or explored/visited set.
*
The beauty of search algorithms is that they are all “the same”, except for some plug-play aspects, mostly selecting the next node to “expand”
Tree Search vs Graph Search?
First, let’s separate graph describing the domain VS tree/graph search.
Graph search remembers nodes visited; tree search does not.
Recall….
Uninformed search methods expand nodes based on “distance” from start node.
Never look ahead to the goal.
E.g. in uniform cost search expand the cheapest path. We never consider the cost of getting to the goal.
Advantage is that we have this information.
But, we often have some additional knowledge about the problem.
E.g. in traveling around Romania we know the straight distances between cities.
Informed Search via Heuristics
How do we choose the ‘most promising’ move?
Use “informed” decision to guide moves.
Specified as h(n) or ‘how promising is node n’.
Lower values of h(n) are best.
Cost from here to solution.
Like uniform-cost search, but using evaluation.
function h(n) rather than path cost g(n).
KEY MESSAGE in CS: heuristic as “problem relaxation”.
*
Two heuristics for eight puzzle
1
4
2
6
8
5
7
3
6
3
2
1
4
5
7
8
1
3
6
4
8
7
2
5
h1: # tiles out of place
relaxed all move constraints
h2: (sum of) Manhattan distance to goal
relaxed tiles overlap constraint
h1: 1
h2: 1
h1: 5
h2: 7
h1: 0
h2: 0
‹#›
*
Is A* Optimal?
No. This example shows why not.
S
A
G
h=6
h=0
3
1
1
A* and revisiting states
If we allow states to be expanded again, we might get a better solution!
Try: tree-search, graph-search, graph-search + revisit
A
S
G
h=7
2
1
1
1
B
C
h=3
h=2
7
Optimality of A*
Optimal for tree-search with admissible heuristic.
Graph-search may not be optimal, unless:
We revisit nodes with lower g(n) than before
Use stronger condition than admissibility for h(n)
Consistency (monotonicity):
h(n) <= cost(n,n’) + h(n’), for all nodes n,n’
If h is consistent, once a node is expanded, the cost by which it was reached is the lowest possible!
Almost any admissible heuristic function will also be consistent.
If the heuristic is consistent, then A* graph-search is optimal
*
Properties of A*
Complete if the heuristic is consistent
Along any path, f always increases (if a solution exists somewhere, the f value will eventually get to its cost)
Exponential time complexity in worst case
A good heuristic will help a lot here
O(bm) if the heuristic is perfect
Exponential space complexity
*
Heuristic Functions: Relax problem!
A good heuristic function can make all the difference!
How do we get heuristics?
One approach is to think of an easier problem ("relaxed problem") and let h(n) be the cost of reaching the goal in the easier problem.
Use solution cost in relaxed problem as heuristic for the original problem.
*
8 Puzzle
Relax the game:
Can move tile from position A to position B if A is next to B (ignore whether or not position is blank)
Can move tile from position A to position B.
Misplaced tile heuristic
Manhattan distance heuristic
Which one is best?
*
Conclusion
We have seen:
Uninformed search
BFS, DFS, DL-DFS, IDS
Informed search
Greedy BFS, A*
Project 1 due end of Week 3
Al tutes this week on CU!
Drop-in lab on Friday!
*