Transcript Introduction to AI, Basic Search Methods

Artificial Intelligence 15-381
Introduction to AI & Search Methods I
Jaime Carbonell
[email protected]
28 August 2001
Today’s Topics
Are we in the right class?
What exactly is AI, anyway?
AI = search+knowledge+learning
AI application areas
Course Outline
Administration and grading 
Basic search methods
What is AI: Some Quick Answers
From the Media: AI is…





…What socially-inept superhackers do
…The opposite of natural stupidity
…Building useful idiot-savant programs
…Deep Blue (IBM’s chess program)
…Robots with feelings (Spielberg)
What is AI:
Some Quick Answers (cont.)
From Academia: AI is…





…modeling aspects of human cognition by
computer
…the study of solving ill-formed problems
…"nothing more" than advanced algorithms
research
…cool stuff! Machine learning, data mining,
speech, language, vision, web agents…and you can
actually get paid a lot for having fun!
…what other CS folks don’t yet know how to do,
and we AIers aren’t always too sure either
Operationally Speaking, AI is:
Applied Cognitive Science

Computational models of human reasoning
•
•

Problem solving
Scientific thinking
Models of non-introspective mental processes
• Language comprehension, language learning
• Human memory organization (STM, LTM)
Operationally Speaking, AI is:
Knowledge Engineering



Codify human knowledge for specific tasks
E.g.: Medical diagnosis, Machine Translation
Central in 1970s & 80sjust one lecture here
Problem-Solving Methods



How to encode and use knowledge to find answer
E.g. HS, MEA, A*, Logic resolution
Always at the very core of AImany lectures
Operationally Speaking, AI is:
Machine Learning





Learning as the hallmark of intelligence…but it is
already practical in multiple applications
E.g.: D-trees, rule-induction, reinforcement, NNets
Discredited in 1960s Vibrant core in 1990s
Applications: data & text mining, speech, robotics
Most active research area in AI many lectures
AI “Application” Areas
Rule-Based Expert Systems


Medical Diagnosis: MYCIN, INTERNIST,
PUFF
CSP Scheduling: ISIS, Airline scheduling
Data Mining



Financial: Fraud detection, credit scoring
Sales: Customer preferences, inventory
Science: NASA galaxy DB, genome analysis
AI “Application” Areas (cont.)
Language Processing




Speech: dictation, HCI
Language: Machine Translation
ML & NLP: Fact Extraction
ML & words: Information Retrieval
Robotics



Machine Vision
Mobile Robots & “agents”
Manipulation
AI-Based Problem Solving
State-Space <{S}, S0, {SGj}, {Oi}>
S0:
SG:
Oi:
Initial State
Goal State (to achieve)
Operators O: {S} => {S}
AI-Based Problem Solving (cont.)
State-Space Navigation








Forward Search: BFS, DFS, HS,…
Backward Search: BFS-1, Backchaining,…
Bi-Directional Search: BFS2,…
Goal Reduction: Island-S, MEA…
Transformation: {S}  {S’}
Abstraction: {S}  {SA} + MEA ({SA})…
Analogy: If Sim(P,P’) then Sol(P) Sol’(P’)
…
More on the State Space
Useful Functions:






Succ(si) = {sk | oj(si) = sk}
Reachable(si) = {U{sk} | Succ *(si)}
Succ-1(si) = {sk | oj(sk) = si)
Reachable-1(si) = {U{sk} | (Succ-1)*(si)}
s-Path(sa0, san) = (sa0, sa1,…, san)
…such that for all sa1 exists oj(sai) = sai+1
o-Path(sa0, san) = (oj0, oj1,…, ojn-1)
…such that for all sa1 exists oj(sai) = sai+1
More on the State Space (cont.)
Useful Concepts:





Solution = o-Path(s0, sG) [or s-Path]
Cost(Solution) = cost(oj) … (often cost(oj) = 1)
P is solvable if at least one o-Path(s0, sG) exists
Solutions may be constructed forward, backward
or any which way
State spaces may be finite, infinite, implicit or
explicit
Zero-Knowledge Search
Simple Depth-First Search
DFS(Scurr, Sgoal, S-queue)
IF Scurr = Sgoal, SUCCESS
ELSE Append(Succ(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE DFS(First(S-queue), Sgoal, Trail(S-queue))
Depth First Search
1
SI
2
7
3
5
4
6
8
…
SG
DFS (cont.)
Problems with DFS




Deep (possibly infinite) rat holes
 depth-bounded DFS, D = max depth
Loops: Succ(Succ(..Succ(S))) = S
 Keep s-Path and always check Scurr
Non-Optimality: Other paths may be less costly
 No fix here for DFS
Worst-case time complexity (O(bmax(D,d))
DFS (cont.)
When is DFS useful?




Very-high solution density
Satisficing vs. optimizing
Memory-limited search: O(d) space
Solution at Known-depth (then D=d)
Zero Knowledge Search (cont.)
Simple Breadth-First Search
BFS(Scurr, Sgoal, S-queue)
IF Scurr = Sgoal, SUCCESS
ELSE Append(Succ(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE BFS(Last(S-queue), Sgoal, All-ButLast(S-queue))
Breadth-First Search
1
2
5
12
6
3
7
4
8
9
10
…
SG
11
Simple BFS cont.
Problems with BFS:



Loops: Succ(Succ(…Succ(S)))=S
Pseudo-loops: Revisiting old states off-path
 Keep full visited prefix tree
Worst case time complexity O(bd)
Worst case space complexity O(bd)
When is BFS Useful?


Guarantee shortest path
Very sparse solution space (better if some solution is
close to SI)
Zero Knowledge Search (cont.)
Backwards Breadth-First Search
BFS(Scurr, Sinit, S-queue)
IF Scurr = Sinit, SUCCESS
ELSE Append(Succ-1(Scurr), S-queue)
IF Null(S-queue), FAILURE
ELSE BFS(Last(S-queue), Sinit, All-But-Last(Squeue))
Backwards Breadth-First Search
9
SI
…
4
5
6
7
2
8
3
1
SG
Backward-BFS (cont.)
Problems with Backward-BFS


All the ones for BFS
Succ(Scurr) must be invertible: Succ-1(Scurr)
When is Backward-BFS useful?


In general, same as BFS
If backward branching<forward branching
Bi-Directional Search
Algorithm:
1.
2.
3.
4.
5.
6.
7.
Initialize Fboundary:= {Sinit}
Initialize Bboundary:= {Sgoal}
Initialize treef:= Sinit
Initialize treeb:= Sgoal
For every Sf in Fboundary
IF Succ(Sf) intersects Bboundary
THEN return APPEND(Path(treef), Path-1(treeb))
ELSE Replace Sf by Succ(Sf) & UPDATE (treef)
For every Sb in Bboundary
IF Succ(Sb) intersects Fboundary
THEN return APPEND(Path(treef), Path-1(treeb))
ELSE Replace Sb by Succ-1(Sb) & UPDATE (treeb)
o to 5.
Note: where’s the bug?
Bi-Directional
Breadth-First Search
1 SI
3
4
8
9
10
13 …
5
6
2 S
G
7
11
12
Bi-Directional Search (cont.)
Problems with Bi-BFS
Loops: Succ(Succ(…Succ(S))) = S
Loops: Succ-1(Succ-1(… Succ-1(S)))) = S
Pseudo-loops: Revisiting old states off-path
 Keep full visited prefix treef, trees
-1
 Succ(Scurr)must be invertible: Succ (Scurr)

When is Bi-BFS useful?

Space and time complexity:
O(bfd/2) + O(bbd/2) = O(bd/2) if bf = bb
Island-Driven BFS
Definition:
An island is a state known a-priori to be on the solution
path between Sinit and Sgoal.

If there are k sequential islands:
BFS(Sinit, S-(goal)=
APPEND(BFS(Sinit, Sk1), BFS(Sk1, Sk2),…BFS(SIk, Sgoal))

Upper bound complexity: O(k*maxi=0:k[bdki,ki+1])

Complexity if islands are evenly spaced:
O((k+1)*bd/(k+1))
Island-Driven Search
1
SI
…
SIsland
SG