Transcript ppt - IIT Bombay

CS621 : Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept.,
IIT Bombay
Lecture 3 - Search
Common Dimensions in Search Methods
• How does a solution correspond to a search tree?
– Solutions can be any nodes
– Solutions must be terminal nodes
– Solutions are paths through the tree
• When does a search method stop?
–
–
–
–
Satisficing: when its finds one solution
Exhaustive: when it has considered all possible solutions
Optimizing: when it has found the best solution
Resource limited: when it has exhausted its computational
resources
– Due process: when it has searched with a method that has
proven adequate for most cases
Common Dimensions in Search Methods (contd.)
• How is the search directed?
– Blind: systematic search through possibilities
– Directed: heuristics used to guide the search
– Hierarchical: abstract solutions used to organize
the search
• How thorough is the search
– Complete: If there is a solution in the search space,
the system will find it
– Incomplete: the system may miss some solutions
AI search is always backed up by
knowledge
Ontological knowledge: a hierarchy
of concepts
The Hierarchical Assembly in an automobile system
Motor System
Breaking System
Engine System
Electrical System
Charging
System
Voltage
Regulator
Generator
Cooling System
Starter System
Battery
Transmission System
Solenoid
Starter Motor
Ignition System
Spark Plugs
Motor System
Cooling hose
Coil
Radiator
Informed Search
• Avoid useless subtrees
• Important for Web
Intelligent Search on Web
Root of the
Web
Literature
Poetry
Drama
Economics
Novel
Macro
Sports
Micro
•Give “Shakespeare's Hamlet”.
•No point going to Economics subtree.
•Document clustering and classification needed.
Racket
Stick
Two Cardinal Theorems for A*
• Admissibility
– A* always terminates finding the optimal path.
• Informedness
– More informed heuristic is “better”, i.e., a less
informed heuristic will expand at least as many
times as a more informed one.
Proof of Admissibility
S
Start Node
N1
N2
N is the node on optimal path on open
list, All its ancestors are in closed list
Ni = N
G
Goal Node
Proof of Admissibility (contd.)
• If A* does not terminate f values of nodes on
open list become unbounded.
f(N) = g(N) + h(N)
and g(N)>= e .Σarcs
e=least cost on the arcs (+ve).
Proof of Admissibility (cont.)
N is on optimal path.
N’s ancestors are all in CL
g(N) = g*(N) ; optimal path to N found
h(N) <= h*(N), by defn of A*
Hence,
f(N) <= f*(N) = f*(S)
Since for each N on optimal path f* values are
equal and equal to the cost of the optimal path
from S to G.
Proof of Admissibility (cont.)
Fact 1: If A* does not terminate f values of
nodes on OL become unbounded.
Fact 2: Any time before A* terminates there
exists on OL a node N with f(N) < f*(S)
These two can be reconciled iff A* terminates
Intuition of Termination
A* keeps wavering and straying. But is brought
back to the correct path.