ࡱ> DC( / 00DTimes New RomanRv 0( 0DWingdingsRomanRv 0( 0 DScript MT BoldRv 0( 0B0DSymbolMT BoldRv 0( 0 ` .  @n?" dd@  @@`` LP     c $@{uʚ;2Nʚ; g42d2dv 0ppp@ <4!d!d` 0LlR<4dddd` 0LlR<4BdBd` 0LlR?&+ Dr. RiggsO =AI Overview Jackson C2Dr Riggs Spring 2004AI is AI is : computer systems the replicate intelligent activity eg: language understanding Learning Reasoning problem solving & FA< < < <@State Space Search hStates Start state Goal state(s)  termination test Operations Move from one state to next Generate & test From a state, generate possible next states Problem Space Solution spaceZ-Z ZZ=ZZ      -     Search Orders Depth-first Children are considered in stack order Quickest, if it takes the right path! Breadth-first Children are considered in queue order Will find shortest solution path  NI   N   H    6Example P. 17  State Space Example p 17 : SearchStacks (DFS) {A} A {AC CA} AC {ACT ATC TAC CA} ACT {ATC TAC CA} ATC {TAC CA} TAC {CA} CA {CAT CTA TCA} CAT {CTA TCA} CTA {TCA} TCA {}V  0N( Queues (BFS) {A} A {AC CA} AC {CA ACT ATC TAC} CA {ACT ATC TAC CAT CTA TCA} ACT {ATC TAC CAT CTA TCA} ATC {TAC CAT CTA TCA} TAC {CAT CTA TCA} CAT {CTA TCA} CTA {TCA} TCA {}V  MB : Exponential Explosion# states often grows as 2levels or faster! The letters problem: Level # letters #states 1 1 letter 1 2 2 letters 1+2 3 3 3 letters 1+2+2*3 9 4 4 letters 1+2*1+3*2+4*3 21 >2N 1,2,4,8,16n+t v Heuristic Search Need a measure of the  goodness of a state Evaluation function hv(s) R (+/-) Approximates distance to the goal Hill-Climbing Rule Take the step the moves closest to a goal Never take a step that moves farther from goal Problem Local highs (lows),/"Y , "    Y  A  A* SearchdFind best value of each node Keep pairs: (node,cost) Cost(n) = cost_of_path + (1-hv(n)) OPEN list : nodes to expand CLOSED list : nodes expanded Algorithm Sketch Pick best OPEN node and expand For each expansion node n If (n is new) put n in OPEN If ( n is already in OPEN or CLOSED & new cost(n) is better) Delete the old record & place the new in OPEN#:9Z.#:9  Z.R Knowledge Representation ORepresent the facts and methods that a person uses to think Some possibilities:PP  The Modern Period (70-95) Knowledge is power (CYC) Knowledge  chunks ( declarative) are (box 2.5 p 29) More similar to human Fast prototyping and incremental development Can solve some problems and give what it does know Complex interactions make chunk system difficult Current best ES practice: Knowledge base // inference engine Uniform (single) knowledge representation Present explanations Z6ZwZMZcZ""" """w"" 1"""a "    Homework  due Monday (1/25/04) in class Solve the missionaries and cannibals problem (C2, #6) by drawing the complete state space graph. Then answer these questions at the bottom of the page with your drawing, or on a separate sheet: 1How many unique states are there? 2How many are solutions? 3How many distinct paths to a solution are there? 4What is the minimum number of nodes that breadth first search could look at to find a solution? 5What is the maximum number of nodes that depth first search could look at to find a solution?<Z""3""  ` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> jb(    6`R "` R T Click to edit Master title style! !$  0R " R RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0tR "`` R X*  0 "`  R Z*  0 "`   Z*H  0޽h ? ̙33 Classes0 zr@ (    0T P    P*    0     R*  d  c $ ?    0  @  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6R `P   P*    6(M `   R*  H  0޽h ? ̙33@ PH(  H H 0+ P    X*  H 00     Z*  H 63 `P   X*  H 67 `   Z* H H 0޽h ? ̙33 0 $(   r  S Hp  r  S  `    H  0޽h ? ̙33  `$(  r  S `A`   r  S B  H  0޽h ? ̙33  p$(  r  S PF`   r  S  G  H  0޽h ? ̙33  $(  r  S N`   r  S XO  H  0޽h ? ̙33     (Q (  (r ( S Q`    ( 0SP p  1a 2 ( 0  F 2ca 2 ( 0I0@ 2ac 2 ( 0(p @  3cat 2 ( 0(p    Mcta 2 ( 0+p   Mtca 2  ( 0)j 0  3act 2  ( 0pp 0  Matc 2  ( 0|tp `  Mtac 2RB  (@ s *D RB  ( s *D  RB (@ s *D@`p RB ( s *D@``p RB ( s *D@`` p RB (@ s *D@ p RB ( s *D@p RB ( s *D@ p H ( 0޽h ? ̙33v  &$(  $r $ S {`   ~ $ s *t|  0   ~ $ s *0}  P 0   H $ 0޽h ? ̙33  0$(  0r 0 S @`   r 0 S   H 0 0޽h ? ̙33  ,$(  ,r , S `   r , S ؛  H , 0޽h ? ̙33  4$(  4r 4 S 0`   r 4 S   H 4 0޽h ? ̙33  ia8(  8r 8 S `   r 8 S Լ  l 8 0Hp`   @Rules & facts (see CLIPS programs) Logic Prolog Theorem provers0 Z0Z0 Z0Z "" "9Y 8 <,n@P  aNetworks Semantic network (box 2.4 p 26) Frame hierarchy Records Frames Scripts (box 2.3, p. 24)p   1 0 Z 0Z 1"  "H 8 0޽h ? ̙33  <$(  <r < S ``   r < S   H < 0޽h ? ̙33   @$(  @r @ S <   r @ S   H @ 0޽h ? ̙33rHp'1357 C9!H5F JKPR- TQOh+'0\ hp ( H T `ltAI Overview Jackson C2 Ken Riggsw YC:\Documents and Settings\administrator\Application Data\Microsoft\Templates\Classes.poto Ken Riggsts3n Microsoft PowerPointing@ѥ!@p569@p"-Gg  & &&#TNPP2OMi & TNPP &&TNPP    --- !-----iyH--w@ [wdw0- @Times New Roman[wdw0- 33.2 @ AI Overview+.+.33--'A'-33- 33+$@ 33'.2 dP Jackson C2!*.--mQmp-- 33qrjP--Q1-- 33mp@Times New Roman[wdw0- mp.2 Dr Riggs  . mp.2 a Spring 2004!   .--"System 0-&TNPP &՜.+,0    rOn-screen ShowoFAMUreeU  Times New Roman WingdingsScript MT BoldSymbolClassesAI Overview Jackson C2AI isState Space SearchSearch OrdersExample P. 17 State SpaceExample p 17 : SearchExponential ExplosionHeuristic Search A* SearchKnowledge RepresentationThe Modern Period (70-95) Homework  Fonts UsedDesign Template Slide Titles !_T Ken RiggsKen Riggs  !"#$%&'()*,-./012456789:<=>?@ABERoot EntrydO)Current User;SummaryInformation(+PowerPoint Document(UDocumentSummaryInformation83