Transcript CS 175 Artificial Intelligence

CS 170 Artificial Intelligence
Prof. Rao Vemuri
Search #1:
Problem Solving by Searching
Searching
•
Search is needed when a solution requires a sequence of choices
•
The history of the choices considered forms a tree.
•
Each node represents a choice.
•
Each path represents a set of choices that build on each other.
•
Note: Search tree nodes may be different from problem nodes.
Example Problems
• The Monkeys & Bananas
• The Missionaries &
Cannibals
• Wolf, Goat and Cabbage
• The Towers of Hanoi
• Route Finding
• Water Jugs Problem
• Time Table Problem
•
•
•
•
•
•
The 8-Puzzle
The 8 Queens Problem
Tic-Tac-Toe Game
Checkers
Chess
Bridge
Canonical Problem Formulation
•
•
•
•
•
State: What the world is doing at this time?
State Space: A collection of possible states
Initial State: Where the search starts
Goal State: Where the search ends
Path: A sequence of operators leading from one
state to another
• Path Cost: Sum of the costs of operators along the
path
Example1: Route Finding
• Find Route From Here to There
– State = Current location on a map
• Initial State = Starting City, say City A
• Goal State = Destination City, say City Z
– Operators: Move along a road to another city
– Path Costs = Sum of lengths from here to there
– Solution = Path from here to there
• Issues
– What is the Cost of Finding the Route?
– What is the Cost of Traversing the Route?
Example2: Timetable
• Find Lecture Timetable by Incrementally
Modifying a Draft to Eliminate Conflicts
– State: A version of a time table
• Initial state: A draft version of a timetable
• Goal State: A timetable with no conflicts
– Operators: exchange a pair of assigned time slots
– Costs: Time taken to make the exchange and verify
conflicts
– Solution: A timetable with no time conflicts (Here the
path is irrelevant)
Search Trees: Terminology
• Search is equivalent to building a search tree
– Node, Branch, Path, Root node, Leaf node
– Parent, Ancestor; Child, Descendent
• Expanding: Determining the children
• Open: Node is open until expanded, then it becomes
closed
• Nodes are data structures: Nodes have parents, children,
depth (d), etc.
• Fringe: is a collection of nodes waiting to be expanded
– A Queue is one way to organize the fringe.
Search Trees: Terminology
• Branching Factor “b” of a Node: The number of children
of a node.
• Branching Factor of a Tree: If every node has the same
branching factor, then it has a branching factor b.
– The total number of paths in a tree of depth d with a branching
factor b is = bd.
– Number of paths explode exponentially with d.
• State: Where am I now? What choices do I have?
• Strategy: The choice of which state to expand next.
Search Space
•
Three kinds of nodes in search space
– Visited nodes: seen, processed, and expanded
• May be remembered
– Fringe nodes: seen but not processed or expanded. Waiting to be
expanded
• Must be remembered
– Unvisited nodes: not seen yet (implicit)
Basic Search Algorithm
•
Repeat
• Take some nodes off the fringe
• Expand them (find their neighbors)
• Add neighbors to the fringe
• Until solution is found
General Search Algorithm
•
•
Repeat
Initialize parameters of search.
–
–
–
–
–
–
–
–
–
•
•
Repeat
Take some nodes off the fringe
Decide whether to stop (1)
Expand them (find their neighbors)
Add neighbors to the fringe
Evaluate neighbors
Add to fringe and reorder fringe
Prune fringe
Decide whether to stop (2)
Until done
Until done
Expanding Nodes
•
(constructing neighbors):
•
Lots of flexibility:
– add step onto end of plan.
– add step onto beginning of plan
– add step into middle of plan
Even more flexibility:
– combine parts of two poor solutions to make a new candidate
• e. g. timetables.
• (Genetic Algorithms)
•
Adding to the Fringe
•
(Queue discipline of Fringe)
– LIFO = ``Depth First''
– FIFO = ``Breadth first''
– BIFO = ``Best/priority First''
•
What counts as best?
•
Heuristics to guide the search
•
Constructing good heuristics are an important part of many AI systems.
Managing the Fringe
•
Queue Discipline of fringe
– LIFO, Depth First
– FIFO, Breadth First
– BIFO, Best/Priority First
•
Keeping the entire fringe is too expensive
–
–
–
–
–
–
•
Keep just the best node (``Hill Climbing'')
Keep just the best nodes (``Beam Search'')
Keep a random subset of the fringe
Prune all but first duplicate
Prune all but best duplicate (``Dynamic Programming'')
Prune whenever partial solution is already worse than the best solution found
so far. (``Branch and Bound'')
What is best?
– Heuristics (The heart of AI)
Radical Pruning
• Keeping the entire fringe is too expensive
– Keep just the best node (``Hill Climbing'')
– Keep just the best nodes (``Beam Search'')
– Keep a random subset of the fringe.
Three Varieties of Search
•
Blind Search
– Depth-first search
– Breadth first search
– Random search
•
Heuristic Search
– Hill climbing = DFS + Quality measurements
– Beam search, expands severalpartial paths and purges the rest
– Best-first search, Expands the best partial path
•
Optimal Search
– Branch and Bound, Expands least cost partial path
– Branch and Bound augmented by under-estimates
– A* - B&B plus under estimates plus dynamic programming