COMP 424 Artificial Intelligence Uninformed Search
Readings: R&N Ch. 3, up to 3.4 (3rd or 4th ed)
Search in AI
Copyright By Assignmentchef assignmentchef
Search is at the heart of all AI systems!
Typical setup of an AI task:
Formal representation of the problem to be solved
Includes definitions of state, goal, available actions
Other factual or probabilistic knowledge about the problem Search
Process of finding a solution (or possibly, the best solution)
Eight-Puzzle
How would you build an AI agent to solve this problem?
Dialogue systems
Decide what do say next:
Hi, [Cortana / Google / Bixby / Siri]. Tell me a joke!
Suppose we have a measure of goodness for every possible sequence of words, and a list of words the system knows about.
Outline of Rest of Lecture
Definition of problem
Uninformed search algorithms
Breadth-first search
Depth-first search
Analyzing search algorithms
More uninformed search algorithms
Uniform-cost search
Depth-limited and iterative deepening search
Defining a search problem
State space S: all possible configurations of the domain.
Initial state s0 S: the start state
Goal states G S: the set of end states
Operators A: the actions available
Often defined in terms of mapping from state to successor state.
Defining a search problem (contd)
Path: a sequence of states and operators.
Path cost, c: a number associated with any path.
Solution of search problem: a path from s0 to sgG
Optimal solution: a path with minimum cost.
Example: Eight-Puzzle
Operators? Path cost?
Example: Eight-Puzzle
States? Configurations of the puzzle. Goals? Target configuration.
Operators? Swap the blank with an adjacent tile.
Path cost? Number of moves.
Example: Robot path planning
Get from red square to yellow dot.
Operators? Path cost?
Example: Robot path planning
Get from red square to yellow dot.
States? Position, velocity, map, obstacles.
Goals? Get to target position without crashing.
Operators? Small steps in several directions.
Path cost? Length of path, energy consumption, time to goal,
Basic assumptions (for next few lectures)
Observable
Discrete
Deterministic
(c.f. dynamic) environment
(c.f. unobservable) environment (c.f. continuous) states
(c.f. stochastic) environment
Simplifying assumptions for now. Later, we will consider search in other settings.
State Space Graph
Can visualize the state space search in terms of a graph.
Graph defined by a set of vertices and a set of edges connecting the vertices.
Nodes correspond to states in S.
Edges correspond to operators.
e.g., pathfinding in a grid
Search Tree
Represents the exploration paths in a search procedure
Nodes represent partial solutions, including a state in S.
Edges correspond to operators.
e.g., first two levels of search tree for previous problem
Example with edge costs
Search tree nodes are NOT the same as the state space graph nodes!
Data structures for search tree
Defining a search tree node:
Each node contains a state id (from the states in the graph)
Node also contain additional information:
The parent state and the operator used to generate it
Cost of the path so far
Depth of the node
Expanding a search tree node:
Applying all legal operators to the state
Generating nodes for all the corresponding successor states
Generic search algorithm
Initialize the search tree using the initial state of the problem
1. If no candidate nodes can be expanded, return failure.
2. Choose a node for expansion, according to some search strategy.
3. If the node contains a goal state, then
return the corresponding path.
4. Otherwise expand the node, by:
applying each applicable operator
generating the successor state, and
adding the resulting nodes to the tree.
Now expand a little further
Problem: Search trees can get very big!
Implementation details
Need to keep track of the nodes to be expanded: the frontier.
Implement this using a queue:
1. Initialize queue by inserting a node for the initial state.
a) If the queue is empty, return failure
b) Dequeue a node.
c) If the node contains a goal state, return path.
d) Otherwise expand the node by applying all legal operators to the state.
e) Insert the resulting nodes in the queue.
Search algorithms differ in their queuing function.
Uninformed (blind) search
If a state is not a goal, you cannot tell how close to the goal it might be.
Hence, all you can do is move systematically between states until you stumble on a goal.
In contrast, informed (heuristic) search uses a guess on how close to the goal a state might be.
(More on this next class.)
Uniformed Search Algorithms
Basic algorithms
Breadth-first search
Depth-first search
Dealing with general-cost graphs
Uniform-cost search
Search with limited resources
Depth-limited search
Iterative deepening search
Breadth-First Search (BFS)
Enqueue nodes at the end of queue.
All nodes at level i get expanded before all nodes at level i+1.
=expand next =terminal node
In what order are nodes expanded using Breadth-first search?
Label all start states as V0.
Label all successors of states in V0 that have not been labeled as V1.
Label all successors of states in V1 that have not been labeled as V2.
Label all successors of states in V2 that have not been labeled as V3.
Label all successors of states in V3 that have not been labeled as V4.
To recover the path, follow pointers back to the parent node.
Revisiting states
What if we revisit a state that was already expanded?
What if we visit a state that was already in the queue? Example:
Revisiting states
Maintain a closed list to store every expanded node.
More efficient on problems with many repeated states.
Worst-case time and space requirements are O(|S|) (|S| = #states)
In some cases, allowing states to be re-expanded could produce a better solution.
When repeated state is detected, compare old and new path to find lowest cost path.
In large domains, may not be able to store all states.
Depth-First Search (DFS)
Enqueue nodes at the front of queue
In other words, use a stack in stead of a queue.
Nodes at deepest level expanded before shallower ones.
=expand next =terminal node
In what order are nodes expanded using Depth-first search?
In what order are nodes expanded using Depth-first search?
Order of operators matter!
Solution (if you expand nodes in clockwise order, staring at 9 oclock): {Start, d, b, a, c, e, r, f, Goal}
In what order are nodes expanded using Depth-first search?
Order of operators matter!
Solution (if you expand nodes in clockwise order, staring at 9 oclock): {Start, d, b, a, c, e, r, f, Goal}
What if we expand nodes counter-clockwise, from 9 oclock?
In what order are nodes expanded using Depth-first search?
Order of operators matter!
Solution (if you expand nodes in clockwise order, staring at 9 oclock): {Start, d, b, a, c, e, r, f, Goal}
Solution (if we expand nodes counter-clockwise): {Start, p, q, r, f, Goal}
Key properties of search algorithms
Completeness: Are we assured to find a solution, if one exists?
Optimality: How good is the solution?
Space complexity: How much storage is needed?
Time complexity: How many operations are needed?
Key properties of search algorithms
Completeness: Are we assured to find a solution, if one exists?
Optimality: How good is the solution?
Space complexity: How much storage is needed?
Time complexity: How many operations are needed?
Other desirable properties:
Can the algorithm provide an intermediate solution?
Can an inadequate solution be refined or improved?
Can the work done on one search be reused for a different set of start/goal states?
Search complexity
Evaluated in terms of two characteristics:
Branching factor of the state space (b): how many operators
(upper limit) can be applied at any time?
E.g. for the eight-puzzle problem: branching factor is 4, although most of the time we can apply only 2 or 3 operators.
Solution depth (d): how long is the path to the closest (shallowest) goal state?
Good news:
Complete.
Analyzing BFS
Paths to different goals can be explored at the same time.
Guaranteed to find shallowest path to the goal if unit cost per step.
Will not necessarily find optimal path if graph is weighted. Bad news:
Exponential time complexity: O(bd)
Exponential space complexity: O(bd) [This is not good!]
Good news:
Analyzing DFS
Linear space complexity: O(bm)
m is the maximum depth of the tree
Why? Need to remember where we are at each level of the tree
Easy to implement recursively (do not even need queue data structure).
More efficient than BFS if there are many paths leading to solution.
Analyzing DFS
Good news:
Linear space complexity: O(bm)
Easy to implement recursively (do not even need queue data structure).
More efficient than BFS if there are many paths leading to solution.
Exponential time complexity: O(bm)
Not optimal.
DFS may not complete!
NEVER use DFS if you suspect a big tree depth!
Uniformed Search Algorithms
Basic algorithms
Breadth-first search
Depth-first search
Dealing with general-cost graphs
Uniform-cost search
Search with limited resources
Depth-limited search
Iterative deepening search
General Step Cost
Actions often have different costs
e.g., I can buy a burger for $5 or fries for $3
e.g., I can walk to the classroom outside at a cost of 500 units of warmth, or I can walk through the underground tunnels at a cost of 5 units of warmth
Uniform Cost Search
Goal: Fix BFS to ensure an optimal path with general step costs (i.e., in a weighted graph).
Important distinction:
Unit cost = Problem where each action has the same cost.
General cost = Actions can have different costs.
Uniform Cost Search
Goal: Fix BFS to ensure an optimal path with general step costs (i.e., in a weighted graph).
Important distinction:
Unit cost = Problem where each action has the same cost.
General cost = Actions can have different costs.
Approach:
Use a priority queue instead of a simple queue.
Insert nodes in the increasing order of the cost of the path so far.
Properties:
Guaranteed to find optimal solution for with general step costs (same as BFS when all operators have the same cost).
In what order are nodes expanded using Uniform cost search?
Example solved
Priority queue = {(Start, 0)}
= {(Start, 0), (p,1), (d,3), (e,9)}
= {(Start, 0), (p,1), (d,3), (e,9), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (c,11), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (c,11), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (c,11), (r,14), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (c,11), (r,14), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,14)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13), (f,18)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13), (f,18)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13), (f,18), (goal,23)}
[Find faster path to e.]
Uniformed Search Algorithms
Basic algorithms
Breadth-first search
Depth-first search
Dealing with general-cost graphs
Uniform-cost search
Search with limited resources
Depth-limited search
Iterative deepening search
Depth-limited search
Algorithm: search depth-first, but terminate a path either if a goal state is found, or if the maximum depth allowed is reached.
Always terminates:
Avoids the problem of search never terminating by imposing a
hard limit on the depth of any search path.
However, it is still not complete (the goal depth may be greater than the limit allowed.)
Iterative Deepening Search (IDS)
Algorithm: do depth-limited search, but with increasing depth.
Expands nodes multiple times, but computation time has same complexity.
Analysis of IDS
Complete (like BFS).
Has linear memory requirements (like DFS).
Classical time-space tradeoff.
Recall from last lecture: achieving rationality subject to resource
constraints
Will see similar trade-off often in this course.
Analysis of IDS
Complete (like BFS).
Has linear memory requirements (like DFS).
Classical time-space tradeoff.
Recall from last lecture: achieving rationality subject to resource
constraints
Will see similar trade-off often in this course.
Optimal for problems with unit step costs.
This is the preferred method for large state spaces, where the solution path length is unknown.
Summary of uninformed search
Main difference between methods is order in which they consider states
Uniform cost search
Fixed-depth DFS
Iterative deepening
Assumes no knowledge about the problem:
Very general, can be applied to any problem
Very expensive, since no knowledge about the problem
Some algorithms are complete
All uninformed search methods have exponential worst-case complexity.
CS: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.