CS代写 COMP 424 - Artificial Intelligence Uninformed Search

COMP 424 – Artificial Intelligence Uninformed Search
Readings: R&N Ch. 3, up to 3.4 (3rd or 4th ed)

Search in AI

• 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 (cont’d)
• 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 sgG
• 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 o’clock): {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 o’clock): {Start, d, b, a, c, e, r, f, Goal}
What if we expand nodes counter-clockwise, from 9 o’clock?

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 o’clock): {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?
• 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!

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.
• 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.]

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.
• 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代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts