CS代考 FIT3080 – Artificial Intelligence

Solving Problems by Searching
www.monash.edu.au

Reading for this week:

– Russell and Norvig (4th edition), chapter 3, 3.1 – 3.4
This week’s activities:
– Labs / tutorials start this week
Other notes and reminders:
– Hurdle requirements (to pass)
– Academic integrity policies and consequences > Academic integrity practice quizzes
– Special consideration policies and process
Reading, this week’s activities, etc.
www.monash.edu.au

Last week: Agent Program
www.monash.edu.au

• Actions: Left, Right, Vacuum • Program:
Percepts: location and contents – e.g., [A, Dirty] or [B, Clean]
– if status = Dirty return Vacuum – else if Location = A return Right – else if Location = B return Left
Initial state (of the environment)
Last week: Vacuum-cleaner World and Agent
www.monash.edu.au
Desired state

Percepts: location and contents – e.g., [A, Dirty] or [B, Clean] e.g., [ Vacuum, Right, Vacuum ]
Search algorithms are general programs that compute such action sequences. We often call these sequences plans
Initial state (of the environment)
• Actions: Left, Right, Vacuum
• Program: Find a sequence of actions to achieve a desired state:
This week: Search
www.monash.edu.au
Desired state

Effective at solving sequential problems
Easily integrated with domain-specific insights
Some influential applications of search:
RTS, FPS and RPG all use search
Board games (Chess, Go, etc)
Robotics (e.g., planning for the Mars rover)
– Scheduling (e.g., in public transport, for manufacturing)
Why Search?
www.monash.edu.au

Basic framework of a problem-solving agent – Problem formulation
– Types of state spaces
– Tree-Search and Graph-Search frameworks
– Fundamental search strategies > Breadth-first search (BFS)
> Uniform-cost search (UCS)
> Depth-first search (DFS)
> Depth-limited search (DLS)
> Depth-First Iterative Deepening (DFID)
This week: Outline
www.monash.edu.au

Formulation
FIT3080 – Artificial Intelligence
www.monash.edu.au

Problem-solving Agent
www.monash.edu.au

Comprises decisions about:
– which properties of the world matter
– how to best represent those properties – which actions are possible
– how to best represent those actions
– cost model and objective function
Problem Formulation (I)
www.monash.edu.au

Basic constituents: States, Goals, Actions, Constraints
State space: the set of all states reachable from the initial state by any sequence of actions
Path in the state space: any sequence of actions leading from one state to another
Representing a problem
– Initial state
– Constraints
Operators (Actions) and transition model – Goal test
Path cost function
state to a goal state
A solution is a sequence of actions leading from the initial
Problem Formulation (II)
www.monash.edu.au

Example: Vacuum world
1. Initial–State:
2. Formulate–Goal: either of
3. Formulate-Problem:
(location, cleanliness, remaining dirty loc.) actions:
{Left, Right, Vacuum} transition model: effect of action in state path cost:
1 for every move
4. Solution sequence: [ Vacuum, Right, Vacuum ]
www.monash.edu.au

Example: Vacuum world
What about this state?!
Abstracting away from unnecessary detail can drastically reduce the size of the state space
www.monash.edu.au

Real world is complex
🡪 state space is usually abstracted for problem solving
(Abstract) state = set of real states
(Abstract) action = complex combination of real actions
For guaranteed realizability, any real state must get to some real state
(Abstract) solution = a solution that can be expanded into a set of real paths in the real world
solving the original problem
Each abstract action should be “easier” to perform than
Selecting a State Space
www.monash.edu.au

Assumptions about the Environment
In our vacuum cleaner problem we assumed:
• Observable
• Single -agent • Deterministic • Sequential
• Discrete
The formulation needs to reflect our assumptions!
www.monash.edu.au

On holiday in Romania; currently in Arad. Flight leaves tomorrow from Bucharest.
• Formulategoal:
– be in Bucharest
• Formulateproblem:
– states: various cities
– actions: drive between cities
• Find solution:
– sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
Example: Romania
www.monash.edu.au

Example: Romania
www.monash.edu.au

1. initial state – e.g., “at Arad”
2. actions
– e.g., {Go(Sibiu),Go(Timisoara), … }
transition model
– e.g.,Result(In(Arad),Go(Zerind))🡪In(Zerind)
3. constraints – there are roads between cities
4. goal test can be
– explicit,e.g.,In(Bucharest) – implicit,e.g.,Checkmate(x)
5. path cost (additive)
e.g., sum of distances, number of actions executed
c(s,a,s’) is the step cost of taking action a at state s to reach
state s’, assumed to be
Problem Formulation – Romania
www.monash.edu.au

Problem Formulation – 8 Puzzle (I)
www.monash.edu.au

– Location of each of the 8 tiles in one of the 9 squares
– Possible moves of blank tile
Constraints
– A tile cannot move out of bounds
– Have we reached the goal configuration?
– If we want to minimize the number of steps, then cost of 1 per step
Problem Formulation – 8 Puzzle (II)
www.monash.edu.au

Problem Formulation: Robotic Assembly
www.monash.edu.au

states?: real-valued coordinates of robot joint angles; parts of the object to be assembled
actions?: continuous motions of robot joints constraints?: arm cannot fully rotate up and down goal test?: complete assembly
path cost?: time to execute
Problem Formulation: Robotic Assembly
www.monash.edu.au

Algorithms
FIT3080 – Artificial Intelligence
www.monash.edu.au

Tree – each node has at most one parent Root of search tree is the initial state
Leaves are states without successors (the “fringe” or “frontier”)
At each step, choose one leaf node to expand
Search Tree
www.monash.edu.au

function TREE-SEARCH(problem) returns a solution or failure
Initialize the frontier using the initial state of problem Loop
1. ifthefrontierisemptythenreturnfailure
2. choosealeafnodeandremoveitfromthefrontier 3. ifthenodecontainsagoalstatethenreturnthe
corresponding solution
4. expandthechosennode,addingtheresultingnodesto
the frontier
Basic Tree Search Algorithm
www.monash.edu.au

Example: Romania
www.monash.edu.au

Example: Tree Search (Romania)
www.monash.edu.au

Implementation: States vs Nodes
state – a (representation of a) physical configuration
node – a data structure that is part of a search tree
– includes state, parent node, action, children, path cost g(x), depth
– creates new nodes, fills in the various fields
– uses SuccessorFn(Operators) to create the corresponding states State space: set of all reachable states
Search space: set of all reachable nodes
The Expand function
www.monash.edu.au

Repeated States
www.monash.edu.au

3 ways to deal with repeated states (ordered by
cost and effectiveness):
– Do not return to the state you just came from
🡪 don’t generate successors with same state as a node’s parent
– Do not create paths with cycles in them
– 🡪 don’t generate successors with same state as any ancestor
Do not generate any state that was ever generated before
🡪 Use hashset – or some way of remembering – to check whether state has been visited
Dealing with Repeated States
www.monash.edu.au

Graph Search Algorithm
www.monash.edu.au

CLOSED list
Graph Search Algorithm
www.monash.edu.au

OPEN CLOSED EXPAND
Graph Search Algorithm
www.monash.edu.au

Basic Search Algorithm: Key Issues
• Tree- or Graph- search?
Trees may be unbounded (search space is infinite) + suffer from repeated states
Graph may be prohibitively large (search space is huge)
• Return a path or a node?
• Repeated states
– Failure to detect repeated states can increase the complexity of a problem
• How are the nodes ordered? 🡺Search strategy
– Is the graph weighted or unweighted?
– How much is known about the “quality” of intermediate states?
– Is the aim to find a minimal cost path or any path
www.monash.edu.au
a.s.a.p. (as soon as possible)?

Strategies
FIT3080 – Artificial Intelligence
www.monash.edu.au

Search Strategies
A search strategy is defined by picking the order of node expansion
• Can be categorised into two distinct types
Uninformed – decide based only on problem definition
Informed – use guidance on where to look for solutions
• Evaluated along several dimensions:
– completeness: does it always find a solution if one exists?
– time complexity: maximum number of nodes generated
– space complexity: maximum number of nodes in memory
– optimality: does it always find a least-cost solution?
• Some important metrics for comparing strategies:
– b: maximum branching factor of the search tree
– d: depth of the least-cost solution
– m: maximum depth of any path in the state space (may be ∞)
www.monash.edu.au

Uninformed Search Strategies
FIT3080 – Artificial Intelligence
www.monash.edu.au

Uninformed Search Strategies
Uninformed search strategies use only the information available in the problem definition
action costs node depth etc
Some well known approaches:
Breadth-first search (BFS) Uniform-cost search (UCS) Depth-first search (DFS) Depth-limited search (DLS) Iterative deepening search (IDS)
www.monash.edu.au

Expand shallowest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: FIFO – put successors at end of queue
Breadth-first Search (I)
www.monash.edu.au

Expand shallowest unexpanded node Implementation: managing the frontier
– QUEUEING-FN: FIFO – put successors at end of queue
Breadth-first Search (II)
www.monash.edu.au

Expand shallowest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: FIFO – put successors at end of queue
Breadth-first Search (III)
www.monash.edu.au

Expand shallowest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: FIFO – put successors at end of queue
Breadth-first Search (IV)
www.monash.edu.au

BFS – Example
www.monash.edu.au

Properties of Breadth-First Search
www.monash.edu.au

Assume: Branching factor b=10, 1 million nodes/second, 1000 bytes per node
Complexity of BFS
www.monash.edu.au

Assume: Branching factor b=10, 1 million nodes/second, 1000 bytes per node
Memory is the bigger problem
Complexity of BFS
www.monash.edu.au

Expand node n with the smallest path cost (g-value)
g(n) = sum of action costs from the start node
frontier node.
Update g-values when we find a smallest cost path to a QUEUEING-FN: Priority Queue (e.g., Binary Heap)
Uniform-Cost Strategy
www.monash.edu.au

function UNIFORM-COST-SEARCH(problem) returns a solution or failure
Initialize the frontier (OPEN list) using the initial state of problem • Loop
1. if OPEN is empty then return failure
2. remove the lowest-cost node from OPEN
3. if the node is a goal then return corresponding solution.
4. add the chosen node to the CLOSED list.
5. expand the chosen node
a. if the resulting nodes are in CLOSED then discard them
b. if the resulting nodes are not in OPEN then add them
c. else if the resulting nodes are in OPEN with higher path cost
then update them and their re-compute their priority
Uniform-Cost Search (Tree or Graph)
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
OPEN = { } CLOSED = { }
Uniform-cost (Graph-) Search
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
OPEN = { (Sibiu, 0) } CLOSED = { }
Uniform-cost (Graph-) Search
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
OPEN = { ( , 80), (Fag CLOSED = { }
Uniform-cost (Graph-) Search
www.monash.edu.au
aras, 99) }

Fagaras 211
OPEN CLOSED EXPAND
OPEN = { ( , 80), (Fag CLOSED = { (Sibiu, 0) }
Uniform-cost (Graph-) Search
www.monash.edu.au
aras, 99) }

Fagaras 211
OPEN CLOSED EXPAND
Uniform-cost (Graph-) Search
OPEN = { (Fagaras, 99), (Pitesti, 177) } CLOSED = { (Sibiu, 0) }
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
Uniform-cost (Graph-) Search
OPEN = { (Fagaras, 99), (Pitesti, 177) } CLOSED = { (Sibiu, 0), ( , 80) }
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
Uniform-cost (Graph-) Search
OPEN = { (Pitesti, 177), (Bucharest, 310) } CLOSED = { (Sibiu, 0), ( , 80) }
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
Uniform-cost (Graph-) Search
OPEN = { (Pitesti, 177), (Bucharest, 310) }
CLOSED = { (Sibiu, 0), ( , 80), (Fagaras, 99) }
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
Uniform-cost (Graph-) Search
OPEN = { (Bucharest, 278) }
CLOSED = { (Sibiu, 0), ( , 80), (Fagaras, 99) }
www.monash.edu.au

Fagaras 211
OPEN CLOSED EXPAND
Uniform-cost (Graph-) Search
OPEN = { (Bucharest, 278) }
CLOSED = { (Sibiu, 0), ( , 80), (Fagaras, 99), (Pitesti, 177) }
www.monash.edu.au

Very similar, with some small changes:
Selection strategy (minimum g-value) unchanged Cost updates are unchanged
There is no CLOSED list!
We can try some other simpler duplicate detection
Never generate parent Never generate any ancestor
Uniform Cost (Tree-) Search
www.monash.edu.au

Almost equivalent to BFS if step costs all equal!
Complete? Yes, if step cost ≥ ε Time? O(b1+floor(C*/ε))
where C* is the cost of the optimal solution Space? O(b1+floor(C*/ε))
Optimal? Yes – nodes expanded in increasing order of g(n) = cost of path to node n
Properties of Uniform-cost Search
www.monash.edu.au

UCS may expand more nodes than BFS in practice. Why?
Properties of Uniform-cost Search
www.monash.edu.au

When UCS selects a node for expansion, the optimal path to that node has been found. Why?
Properties of Uniform-cost Search
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (I)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (II)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (III)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (IV)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (V)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (VI)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (VII)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (VIII)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (IX)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (X)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (XI)
www.monash.edu.au

Expand the deepest unexpanded node
Implementation: managing the frontier
– QUEUEING-FN: LIFO – insert successors in front of
Depth-first Search (XII)
www.monash.edu.au

– Infinite-state spaces: No
– Finite-state spaces: Yes, if we check for ancestors
Time? O(bm) (terrible if m is much larger than d!) Space? O(bm) (i.e., linear space)
Optimal? No
When all step c DFS find t
osts are the same, will
he optimal path?
Properties of Depth-first Search
www.monash.edu.au

When all step costs are the same, will DLS find the optimal path?
Depth-limited Search
www.monash.edu.au

function DFID-SEARCH(problem) returns a solution or failure
Initialize the frontier using the initial state of problem
For depth 🡨 0 to ∞
result 🡨 DEPTH-LIMITED-SEARCH(problem,depth)
if result ≠ cut-off then return result end
indicates failure
Depth First Iterative Deepening
www.monash.edu.au

Example: DFID
www.monash.edu.au

DFID Generated Nodes
www.monash.edu.au

Properties of DFID
www.monash.edu.au

Which algorithm is faster in practice?
BFS, DFS or DFID? Let’s race them!
https://www.movingai.com/SAS/EXP/
www.monash.edu.au

We have considered:
– Basic framework of a problem-solving agent – Problem formulation
– Basic tree search over state spaces
– Graph search and pruning
– Uninformed search algorithms > Breadth-first search (BFS)
> Uniform-cost search (UCS)
> Depth-first search (DFS)
> Depth-limited search (DLS)
> Depth-First Iterative Deepening (DFID)
Re-cap: Problem Solving with

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts