ArtificialIntelligenceFall2008FrankHadlockDefinitionsofAIThestudyofrepresentationandsearchthroughwhichintelligentactivitycanbeenactedonamechanicaldevice.Thestudyofproblemsatwhichhumanbeingsarecurrentlymoreadeptthancomputersatsolvingandthetranslationandimprovementofhumansolutionsintoformswhichcanbeimplementedonacomputer.PhysicalsymbolsystemhypothesisThephysicalsymbolsystemhypothesis(PSSH),firstformulatedbyNewellandSimonintheirTuringAwardpaper,1statesthat“aphysicalsymbolsystem[suchasadigitalcomputer,forexample]hasthenecessaryandsufficientmeansforintelligentaction.”Thehypothesisimpliesthatcomputers,whenweprovidethemwiththeappropriatesymbol-processingprograms,willbecapableofintelligentaction.Italsoimplies,asNewellandSimonwrote,that“thesymbolicbehaviorofmanarisesbecausehehasthecharacteristicsofaphysicalsymbolsystem.”HistoryGraphtheory&statespacerepresentation(Euler)Booleanalgebra–propositionalcalculus(Boole)Predicatecalculus–(Frege)DescartesDiscourseTuring’sTestPhysicalSymbolSystemHypothesisConnectionism

Discourse-DescartesIfthereweremachineswhichborearesemblancetoourbodiesandimitatedouractionsascloselyaspossibleforallpracticalpurposes,weshouldstillhavetwoverycertainmeansofrecognizingthattheywerenotrealmen.Thefirstisthattheycouldneverusewords,orputtogethersigns,aswedoinordertodeclareourthoughtstoothers.Forwecancertainlyconceiveofamachinesoconstructedthatitutterswords,andevenutterswordsthatcorrespondtobodilyactionscausingachangeinitsorgans.…Butitisnotconceivablethatsuchamachineshouldproducedifferentarrangementsofwordssoastogiveanappropriatelymeaningfulanswertowhateverissaidinitspresence,asthedullestofmencando.Secondly,eventhoughsomemachinesmightdosomethingsaswellaswedothem,orperhapsevenbetter,theywouldinevitablyfailinothers,whichwouldrevealthattheyareactingnotfromunderstanding,butonlyfromthedispositionoftheirorgans.Forwhereasreasonisauniversalinstrument,whichcanbeusedinallkindsofsituations,theseorgansneedsomeparticularaction;henceitisforallpracticalpurposesimpossibleforamachinetohaveenoughdifferentorganstomakeitactinallthecontingenciesoflifeinthewayinwhichourreasonmakesusact.(TranslationbyRobertStoothoff)TuringTestTheTuringtestisaproposalforatestofamachine'sabilitytodemonstrateintelligence.DescribedbyAlanTuringinthe1950paper"ComputingMachineryandIntelligence,"itproceedsasfollows:ahumanjudgeengagesinanaturallanguageconversationwithonehumanandonemachine,eachofwhichtrytoappearhuman;ifthejudgecannotreliablytellwhichiswhich,thenthemachineissaidtopassthetest.Inordertotestthemachine'sintelligenceratherthanitsabilitytorenderwordsintoaudio,theconversationislimitedtoatext-onlychannelsuchasacomputerkeyboardandscreen(Turingoriginallysuggestedateletypemachine,oneofthefewtext-onlycommunicationsystemsavailablein1950).AIApplicationAreasGamePlayingAutomatedReasoningExpertSystemsNaturalLanguageUnderstandingModelingHumanPerformancePlanningandRoboticsLanguagesforAI(Clips,LispandProlog)MachineLearningNeuralnetsandGeneticAlgorithmsIntelligentAgentsBoardgamescanberepresentedbyausuallylargebutfinitesetofboardconfigurationsorstates.ThesquaresofTicTacToecanbenumbered1..9andeachconfigurationasasequenceover{H,C,B}wheremanyofthe39cannotoccurbecauseoforderofplay.AstateBCBBBBBBBmaybefollowedbyanyofeightstatesobtainedbyreplacinganyoftheeightBsbyanH.BBBBBBBBBistheinitialstateandanystatewitharoworcolumnordiagonalconsistingofallCsisawinningstatefortheComputer.Ifthecomputercanfindapathfromstarttowinningstate,thepathcorrespondstoawinforthecomputerandfindingsuchapathconstitutesanexampleofartificialintelligence.GamePlayingandStateSpaceSearchGraphtheory:ThecityofK?nigsberg

Thecityisdividedbyariver.Therearetwoislandsattheriver.Thefirstislandisconnectedbytwobridgestobothriverbanksandisalsoconnectedbyabridgetotheotherisland.Thesecondislandtwobridgeseachconnectingtooneriverbank.Question:Isthereawalkaroundthecitythatcrosseseachbridgeexactlyonce?SwissmathematicianLeonhardEulerinventedgraphtheorytosolvethisproblem.ThecityofK?nigsbergGraphoftheK?nigsbergbridgesystemEulerCircuitsAgraphhasanEulercircuitiffitisconnectedandeveryvertexisofevendegree.Necessity–Eulercircuitentersavertexeachtimeonanewedgeandleavesthevertexonanewedge.Sovertexhasdegree2*numberoftimesoncircuitSufficiency–Pickstartingvertexandtraversegraph,eachtimepickingnewedge.Canonlybeblockedatstart.EitherhaveEulercircuitorcanpickvertexwithunusededgeoncircuitandbuildsubtourstartingwithit.Splicesubtourin.Eventuallywillhaveusedalledgesonce.StatespacesearchRepresentedbyafour-tuple[N,A,S,GD],where:Nistheproblemspace

Aisthesetofarcs(orlinks)betweennodes.Thesecorrespondtotheoperators.

SisanonemptysubsetofN.Itrepresentsthestartstate(s)oftheproblem.

StateSpaceSearchcontinuedGDisanonemptysubsetofN.Itrepresentsthegoalstate(s)oftheproblem.ThestatesinGDaredescribedusingeither:

ameasurablepropertyofthestates

apropertyofthepathdevelopedinthe

search(asolutionpathisapathfrom

nodeStoanodeinGD)The8-puzzleproblemasstatespacesearchstates:possibleboardpositionsoperators:oneforslidingeachsquareineachoffourdirections,

or,better,oneformovingtheblanksquareineachoffourdirectionsinitialstate:somegivenboardpositiongoalstate:somegivenboardpositionNote:the“solution”isnotinterestinghere,weneedthepath.EightPuzzle1437658214376258Statespaceofthe8-puzzlegeneratedby“moveblank”operationsTravelingsalespersonproblemasstatespacesearchThesalespersonhasncitiestovisitandmustthenreturnhome.Findtheshortestpathtotravel.statespace:operators:initialstate:goalstate:AutomatedReasoningandTheoremProvingLogicsystemsbeganwithPropositionalCalculusinwhichdeclarativestatementswithatruthvalueoftrueorfalsearerepresentedbyP,Q,R,etcandcombinedwithlogicoperatorsOr,And,Not,If.Asentencesuchas“BillmusttakeCSC2020”isrepresentedbyletterPandistrueorfalse.PropositionalCalculuswasextendedtoPredicateCalculusbyaddingPredicates(relations),variables,andquantifiers(ForAllandThereExists).Asentencesuchas“EveryCSmajormusttakeCSC2020”isrepresentedby“(ForAllX)(CSMajor(X)MustTake(CSC2020))”GivensomefactsexpressedineitherPropositionalorPredicateCalculus,newfactsorknowledgeisinferredbyinferencerulessuchasmodusponensorresolution.Ifthecomputercanfindapathfromgivenfactstoanewtheorem,thepathcorrespondstoaproofandfindingsuchapathconstitutesanexampleofartificialintelligencePropositionalLogicAdeclarativestatementsuchas“BillisaCSstudent”hasatruthvalueofTorFandisdenotedbyP(atruthvariable)Propositionsmaybecombinedwithlogicaloperatorsandthecompositestatementhasvalueasshownbelow.PQistrueifeitherPorQaretrueandfalseifbotharefalsePQistrueifbothPandQaretrueandfalseifeitherisfalse.?PistrueifPisfalseandfalseifPistruePQistrueifPandQhavethesametruthvalueandfalseiftheirvaluesdifferPQisfalseifPistrueandQisfalseandtrueotherwise.Atautologyisalwaystrue.PQ?PQisatautology.P(QR)

(PQ)(PR)isatautology.RulesofInferenceP,PQthenQ-modusponens?Q,PQthen?P-modustollensExpertSystemsGeneralproblemsolvinghasbeenattemptedinAIbutwithoutsuccess.Instead,systemshavebeendevelopedwhichspecializeindomain-specificknowledgesuchasmedicine.Peoplewhoworkintheseareasarecalleddomainexpertsandsolveproblemsbyusingdomain-specificruleswhichareappliedtofactsorknowledgeintheknowledgebase.Generalproblemclassessolvablebyexpertsystems(whichreplacethedomainexperts)arediagnosticproblems(backwardchaining)anddesignorconfigurationproblems(forwardchaining).Whenapathisfoundfromaconditionbackwardtoasetoffactscausingthecondition(orviseversa),thepathcorrespondstoadiagnosis(ordesign)andfindingsuchapathconstitutesanexampleofartificialintelligenceNaturalLanguageUnderstanding&SemanticsTranslationfromtextinonenaturallanguagetoanotherrequiresmorethanvocabularysubstitutionbecauseoftheinherentambiguityofnaturallanguages.Toresolvethisambiguityrequirescontextualknowledgeintheformofaworldmodel.Asanexample,apunctuationsymbol“,”canhavethemeaningofalistseparator,orbeusedinplaceof“then”,orbeusedtodelimitadanglingmodifier.Anotherexampleisthetransaltionof“hydraulicram”inEnglishintotheRussianequivalentof“watergoat”.Inthislastexample,aworldmodelwouldsaythatthereissuchananimalasa“waterbuffalo”butnota“watergoat”.TranslationusuallyinvolvessyntacticanalysisfollowedbysemanticanalysisandatranslationpathfromsourcetotargetconstitutesanexampleofartificialintelligenceModelingHumanPerformanceMuchofartificialintelligenceisconcernedwithduplicatingorsurpassinghumaningenuityonthecomputerwithnoconcernwithhowhumansperform.Cognitivemodelingisconcernedwithusingcomputerstodeterminehumanperformance.Computerbasedtutoringisanexamplewhichhasbeenappliedtotutoringalgebrastudentstosolvewordproblems.CognitivemodelingsystemssuchasACTmodelhumanperformancewithrulesorproductions.Thetutorinteractswiththestudentbyposingaproblemandthenposingquestions,attemptingtoguidethestudenttoacorrectsolution.Byexaminingtheresponses,thetutoreitherposesanotherquestioncorrespondingtoacorrectstepinthesolution,ordiagnosesanincorrect“buggy”rulebeingusedbythestudent.Inthiscase,thetutorrevertsbacktoapreviousconceptneededinthecorrectsolution.ApathfromproblemstatementtoanyintermediatestateconstitutesanexampleofartificialintelligencePlanningandRoboticsDiscussionofplanningandroboticshereisconfinedtomotionplanningintwodimensions.AbasicassumptioninthisdiscussionisthattheEuclideancoordinatesareavailableforthepositionoftherobot,ofobstacles,andofgoals.Motionplanningisaccomplishedbyworkingwiththestatespaceofpositionswherepositionsareconnectedbyanedgeifthereisnointerveningobstacle.Apathfrominitialpositiontoagoalpositionisasolutiontotheproblemofmotionplanningthatconstitutesanexampleofartificialintelligence.CognitiveAlgebraTutorsAlgebraclassmaybelessdifficultandabitmorefunthesedays,thankstoresearchonhowhumancognitionworks.DevelopedovertwodecadesbypsychologistJohnAnderson,theAdaptiveCharacterofThought(ACT-R)theoryisaframeworkforunderstandinghowwethinkaboutandattackproblems,includingmathequations.Thetheoryreflectsourunderstandingohumancognitionbasedonnumerousfactsderivedfrompsychologicalexperiments.ACT-Rsuggeststhatcomplexcognitionarisesfromaninteractionofproceduralanddeclarativeknowledge.Declarativeknowledgeisafairlydirectencodingoffacts(suchasWashington,DCisthecapitaloftheUnitedStates,5+3=8);proceduralknowledgeisafairlydirectencodingofhowwedothings(suchhowtodriveorhowtoperformaddition).AccordingtotheACT-Rtheory,thepowerofhumancognitiondependsonhowpeoplecombinethesetwotypesofknowledge.SignificanceTheACT-Rtheoryprovidesinsightsintohowstudentslearnnewskillsandconcepts,and,indoingsoallowsteacherstoseewherestudentsmayneedextrapracticetomasterthenewwork.PracticalApplicationDr.AndersonandcolleaguesatCarnegieMellonUniversityhaveusedthisresearchtodevelopcognitivetutors,computer-tutoringprogramsthatincorporatetheACT-Rtheoryintheteachingofalgebra,geometryandintegratedmath.Thetutorsarebasedoncognitivemodelsthattaketheformofcomputersimulationsthatarecapableofsolvingthetypesofproblemsthatstudentsareaskedtosolve.Thetutorsincorporatethedeclarativeandproceduralknowledgeimbeddedintheinstructionandmonitorstudents’problemsolvingtodeterminewhatthestudentsknowanddon’tknow.Thisallowsinstructiontobedirectedatwhatstillneedstobemasteredandhelpsinsurethatstudents’learningtimeisspentinamoreefficientmanner.Studentsworkonaconceptuntilitisfullyunderstood.Studentswhoarehavingconceptualproblemswillbedrilledoninthatarea,whilethosewhohavemasteredtheconceptmoveontootherareas.Themostwidelyusedcognitivetutorprogram–nowknownasCarnegieLearning’sCognitiveTutor-combinessoftware-based,individualizedcomputerlessonswithcollaborative,real-worldproblem-solvingactivities.Theprogramnowservesmorethan150,000studentsinmostofthenation’slargestschooldistricts.Fieldstudieshaveshowndramaticstudentachievementgainswheretheprogramisinuse.In2003,theU.S.DepartmentofDefenseSchoolsawardedacontractthatwilluseCognitiveTutormathematicscurriculainits224publicschoolsin21districtslocatedin14foreigncountries,sevenstates,GuamandPuertoRico.Theseschoolshaveapproximately8,800teachersserving106,000students.CitedResearchAnderson,J.R.(1983).Thearchitectureofcognition.Cambridge:MA:HarvardUniversityPress.Anderson,J.R.(1993).RulesoftheMind.Hillsdale,NJ:Erlbaum.LispLispisthefirstlanguageusedinArtificialIntelligenceandisstructuredsothatalistiseitherdataorafunctioncall.Inthecaseofafunctioncall,Lispusesprefixnotationwhichmeansthatthefirstlistitemisthenameofthefunctionandtheremainingitemsarethearguments.Lispindicatesvariablesbyaquestionmark.Toillustrate(forall?x(implies(cs_student?x)(must_take?xdata_structures)))(cs_studentbill)Wouldyield(must_takebilldata_structures)PrologPrologisalogicprogramminglanguagebasedonpredicatelogic.Prologusescapitallettersforvariablesandlowercaselettersforpredicatesandconstantsandreversestheorderforimplication.InsteadofwritingPQ,PrologordersimplicationasQ:-P.Acommaisusedtoseparateargumentsandforconjunctionwithaperiodmarkingtheendofasentence.Toillustrate,cs_student(bill).must_take(data_structures,X):-cs_student(X)Thefirstsentenceassertsafactthat“bill”isacs_studentwhilethesecondsentenceassertsthatanycs_studentmusttakedatastructures.Prologislaunchedbyagoalsuchas:-must_take(data_structures,Y)whichwouldreturnmust_take(data_structures,bill)CLIPS

Clipsorganizesknowledgebyusingnamedfacttemplatesconsistingofnamedslots.AnexampleisthePAYtemplatewithslotsforhoursandpayrate.Thedeffactsstatementcreatesinitialfactsaccolrdingtoselectedtemplates.Anexampleisthepayrollstatementwhichassignsaninitialfactof44hoursandofarateof$8/hour.

FactList(deftemplatepay(slothours)(slotrate))(deffactspayroll(pay(hours44)(rate8))(statusincomplete))CLIPS

Clipsinfersnewknowledgebyusingnamedruletemplatesconsistingofanantecedentwhichmustmatchfactsinthefactlistandaconsequentwhichaddsormodifiesfacts.FactListRuleList(defrulecalculate_basic?p<-(pay(hours?h)(rate?r))(test(<=?h40))=>(assert(basic_pay(*?h?r)))(retract?p))CLIPSRuleListRuleList(defrulecalculate_basic?p<-(pay(hours?h)(rate?r))(test(<=?h40))=>(assert(basic_pay(*?h?r)))(retract?p))(defrulecalculate_overtime(pay(hours?h)(rate?r))(test(>?h40))(statusincomplete)=>(assert(overtime(*(-?h40)(*?r1.5)))))(defrulecalculate_regular(pay(hours?h)(rate?r))(statusincomplete)(test(>?h40))=>(assert(regular(*40?r))))(defrulecalculate_adjustedgross(regular?r)(overtime?o)(statusincomplete)=>(assert(adjusted_gross(+?r?o)))(assert(statusdone)))(deftemplatepay(slothours)(slotrate))(deffactspayroll(pay(hours44)(rate8))(statusincomplete))NeuralNetsAnartificialneuronconsistsofinputsxi,I=1..n,whichhaveavalueof0or1.Eachinputxicancollectavaluefromtheenvironmentorfromtheoutputofanotherneuronandanassociatedweightwi.Aneuronisactivatedifthesumoftheweightedinputswixiexceedsathresholdfunctionf.Theneuronoutputsa1ifactivatedandotherwiseoutputsa0.Twosetsofpointsin2dimensionalspacearelinearlyseparableiftheycanbeseparatedbyastraightline.Inthiscase,thepointscanbeclassifiedbyasingleneuronwhichoutputsa0forpointsononesideofthelineanda1forpointsontheotherside.Thisclassificationisanexampleofartificialintelligence.ThepointsetsclassifiedbyalogicalOrgateandthoseclassifiedbyalogicalAndgatearelinearlyseparablebutnotthoseclassifiedbyanExclusiveOr.GeneticAlgorithmsGeneticalgorithmsarebasedonabiologicalmetaphorofevolvingsolutionstoaproblem.Thesolutionsarestringsoversomealphabetandarereferredtoasgenes.GivenaninitialpopulationP0,eachmembergeneisevaluatedbyafitnessfunctionspecifictotheproblemForexample,fortheknapsackfunction,thegenemightbealistofobjectindicestobeincludedandthefitnessmightbethewastedspaceintheknapsack.Membersareselectedbasedonfitnessandoffspringarecreatedusingcrossoverandmutationoperatorstoformthenextpopulation.TheprocesshaltsaftersomanypopulationsandthemostfitmemberofthefinalpopulationisselectedasthesolutiontotheproblemRepresentationandSearchRepresentationofProblemInformationPropositional&PredicateLogicSemanticnetworksStateSpacesetofproblemstatesalongwithtransitionsbetweenstatesandasetofstartstatesandgoalstates.apathfromstarttogoalisasolution

SearchTechniquesforfindingasolution

EightPuzzleRepresentation–Thesquaresoftheeightpuzzlecanberepresentedbyintegers1..8and9representsemptysquare.Astateofthepuzzleisapermutationof1..9where1stthreerepresenttoprow,2ndthreerepresentmiddlerow,and3rdthreerepresentbottomrow.EightpuzzletransitionsAneightpuzzletransitionconsistsofmovingasquarenumbered1..8intotheadjacentvacantsquarewhichcanonlybedoneifitisadjacenttothenumberedsquare.Representationofaboardconfigurationisapermutationof1..9where9representsvacantsquare.Example–132496758represents1strow132,2ndrow4blnk6,3rdrow748.Sincetheblankisinthemiddleposition,3canbemoveddown,or4totheright,or6totheleft,or5movedup.Thesetransitionsmake132496758haveneighbors192436758,132946758,132469758,and132456798.KnowledgeRepresentationEssentialtoartificialintelligencearemethodsofrepresentingknowledge.Besidespropositionalandpredicatelogic,anumberofothermethodshavebeendeveloped,including:SemanticNetworksConceptualDependenciesScriptsFramesSemanticNetworksModelsmeaningoflanguage:NodescorrespondtowordconceptsArcsarelabeledwithapropertyname

orrelationshipandlinkanode(wordconcept)withanother(valueofproperty).Quillian(1967)introducedsemanticnetworkswhileothers(Simmons-1973,Brachman-1979,Schank-1979)haveextendedthemodel.SemanticNetworks

StandardizationofRelationshipsStandardizationofrelationshipsforrepresentingknowledgeexpressedinlanguagefocusesoncaserelationsbetweenverbsandnounsinsentence(Fillmore’68,Simmons’73)Prepositionsorarticlesindicaterelationshipbetweenverbandnoun:Agent:entityperformingtheactionObject:entityacteduponInstrument:entityusedinperformingtheactionEtc.ConceptualDependencies

SetofPrimitiveActionsStandardizationofrelationsledtoaxiomaticapproachtobuildsemanticmodelforrepresentingmeaningoflanguageFourPrimitiveConceptClassesACTS-ActionsPPs–Objects(Pictureproducers)AAs–Modifiersofactions(ActionAiders)PAs–Modifiersofobjects(pictureaiders)EachActionisassumedtoreducetooneormoreoftheprimitiveACTsATRANS–transferrelationship(give)PTRANS–transferphysicallocation(go)PROPELMOVEGRASPINGESTEXPELMTRANSMBUILDCONCSPEAKATTENDBuildingComplexConceptualDependencies