Artificial Intelligence 15-381Today’s TopicsWhat is AI: Some Quick AnswersWhat is AI: Some Quick Answers (cont.)Operationally Speaking, AI is:Slide 6Slide 7AI “Application” AreasAI “Application” Areas (cont.)AI-Based Problem SolvingAI-Based Problem Solving (cont.)More on the State SpaceMore on the State Space (cont.)Zero-Knowledge SearchDepth First SearchDFS (cont.)Slide 17Zero Knowledge Search (cont.)Breadth-First SearchSimple BFS cont.Slide 21Backwards Breadth-First SearchBackward-BFS (cont.)Bi-Directional SearchBi-Directional Breadth-First SearchBi-Directional Search (cont.)Island-Driven BFSIsland-Driven SearchArtificial Intelligence 15-38115-381: Artificial IntelligenceToday: Introduction to AI & Search Methods Jaime [email protected]’s TopicsAre we in the right class?What exactly is AI, anyway?AI = search+knowledge+learningAI application areasCourse OutlineAdministration and grading Basic search methodsWhat 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 eitherOperationally Speaking, AI is:Applied Cognitive ScienceComputational models of human reasoning•Problem solving•Scientific thinkingModels of non-introspective mental processes•Language comprehension, language learning•Human memory organization (STM, LTM)Operationally Speaking, AI is:Knowledge EngineeringCodify human knowledge for specific tasksE.g.: Medical diagnosis, Machine TranslationCentral in 1970s & 80s just one lecture hereProblem-Solving MethodsHow to encode and use knowledge to find answerE.g. HS, MEA, A*, Logic resolutionAlways at the very core of AI many lecturesOperationally Speaking, AI is:Machine LearningLearning as the hallmark of intelligence…but it is already practical in multiple applicationsE.g.: D-trees, rule-induction, reinforcement, NNetsDiscredited in 1960s Vibrant core in 1990sApplications: data & text mining, speech, roboticsMost active research area in AI many lecturesAI “Application” AreasRule-Based Expert SystemsMedical Diagnosis: MYCIN, INTERNIST, PUFFCSP Scheduling: ISIS, Airline schedulingData MiningFinancial: Fraud detection, credit scoringSales: Customer preferences, inventoryScience: NASA galaxy DB, genome analysisAI “Application” Areas (cont.)Language ProcessingSpeech: dictation, HCILanguage: Machine TranslationML & NLP: Fact ExtractionML & words: Information RetrievalRoboticsMachine VisionMobile Robots & “agents”ManipulationAI-Based Problem SolvingState-Space <{S}, S0, {SGj}, {Oi}>S0: Initial StateSG: Goal State (to achieve)Oi: Operators O: {S} => {S}AI-Based Problem Solving (cont.)State-Space NavigationForward 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 SpaceUseful 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+1o-Path(sa0, san) = (oj0, oj1,…, ojn-1) …such that for all sa1 exists oj(sai) = sai+1More on the State Space (cont.)Useful Concepts:Solution = o-Path(s0, sG) [or s-Path]Cost(Solution) = cost(oj) … often cost(oj) = 1P is solvable if at least one o-Path(s0, sG) existsSolutions may be constructed forward, backward or any which wayState spaces may be finite, infinite, implicit or explicitZero-Knowledge SearchSimple Depth-First SearchDFS(Scurr, Sgoal, S-queue)IF Scurr = Sgoal, SUCCESSELSE Append(Succ(Scurr), S-queue)IF Null(S-queue), FAILUREELSE DFS(First(S-queue), Sgoal, Trail(S-queue))Depth First Search17865234…SGSIDFS (cont.)Problems with DFSDeep (possibly infinite) rat holes depth-bounded DFS, D = max depthLoops: Succ(Succ(..Succ(S))) = S Keep s-Path and always check ScurrNon-Optimality: Other paths may be less costly No fix here for DFSWorst-case time complexity (O(bmax(D,d))DFS (cont.)When is DFS useful?Very-high solution densitySatisficing vs. optimizingMemory-limited search: O(d) spaceSolution at Known-depth (then D=d)Zero Knowledge Search (cont.)Simple Breadth-First SearchBFS(Scurr, Sgoal, S-queue)IF Scurr = Sgoal, SUCCESSELSE Append(Succ(Scurr), S-queue)IF Null(S-queue), FAILUREELSE BFS(Last(S-queue), Sgoal, All-But-Last(S-queue))Breadth-First Search112111098765432SG…Simple BFS cont.Problems with BFS:Loops: Succ(Succ(…Succ(S)))=SPseudo-loops: Revisiting old states off-path Keep full visited prefix treeWorst case time complexity O(bd)Worst case space complexity O(bd)When is BFS Useful?Guarantee shortest pathVery sparse solution space (better if some solution is close to SI)Zero Knowledge Search (cont.)Backwards Breadth-First SearchBFS(Scurr, Sinit, S-queue)IF Scurr = Sinit, SUCCESSELSE Append(Succ-1(Scurr), S-queue)IF Null(S-queue), FAILUREELSE BFS(Last(S-queue), Sinit, All-But-Last(S-queue))Backwards Breadth-First Search987654321…SISGBackward-BFS (cont.)Problems with Backward-BFSAll the ones for BFSSucc(Scurr) must be invertible: Succ-1(Scurr)When is Backward-BFS useful?In general, same as BFSIf backward branching < forward branchingBi-Directional SearchAlgorithm:1. Initialize Fboundary:= {Sinit}2. Initialize Bboundary:= {Sgoal}3. Initialize treef:= Sinit4. Initialize treeb:= Sgoal5. 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) 6. For every Sb in Bboundary IF Succ(Sb) intersects Fboundary THEN return
View Full Document
Unlocking...