2知识表示.

状态空间（StateSpace）问题归约（ProblemReduction）逻辑（Logic）产生式规则（ProductionRules）语义网络（SemanticNetworks）框架（Frame）…中南大学刘丽珏知识和知识表示状态空间表示法问题归约表示法一阶谓词逻辑表示法产生式表示法语义网络表示法框架表示法其他表示法数据、信息知识知识层次数据噪声信息组织分析知识解释评价智慧理解归纳数据：一些无关联的事实(fact)例：下雨了信息：建立了事实间的联系后形成信息，提供对what,who,when,where等问题的回答例：温度下降了15度后就下雨了知识：当能建立模式之间的联系后便涌现了知识，提供对how的回答例：如果湿度非常大并且温度下降显著，大气无法保留湿气便下雨了智慧：能描述模式之间关系的规律，提供对why的回答例：理解下雨、蒸发、空气状况、温度等级及它们的变化之间的相互作用真伪性相对性不完全性不确定性可表示性可存储性、可传递性和可处理性相容性知识表示是问题求解的基础◦问题求解是人工智能的核心问题之一◦问题求解的目的机器自动找出某问题的正确解决策略更进一步，能够举一反三，具有解决同类问题的能力智能系统中◦知识是对世界的描述决定系统的能力◦表示是知识的编码方式决定系统的性能不同类型的知识需要不同的表示方式不同的表示方法需要不同的求解技术知识表示的过程◦非形式化的自然语言描述形式化的易于被计算机理解问题解求解表示输出计算表示解释非形式化形式化GOFAI(GoodOld-FashionedArtificialIntelligence)philosophy:◦ProblemSolving=KnowledgeRepresentation◦+SearchStateSpace(状态空间)RepresentationProblemReduction(问题归约)RepresentationPredicateLogic（谓词逻辑）ProductionRules（产生式规则）SemanticNetwork（语义网络）RepresentationFrame,Script,Procedure（框架，剧本，过程）八数码难题在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。12384567初始状态81324567目标状态如何将棋盘从某一初始状态变成最后的目标状态？问题示例10怎样找到两点之间的最短路径呢？问题有了，可怎么让计算机知道这些问题呢？例：真空吸尘器的世界◦假设：吸尘器的世界只有两块地毯大小，地毯或者是脏的，或者是干净的◦吸尘器能做的动作只有三个{向左(Left)，向右(Right)，吸尘(Suck)}◦一共有多少种可能的情况？状态状态之间可以互相转换状态空间图传教士野人问题（Missionaries&Cannibals，MC问题）有三个传教士M和三个野人C过河，只有一条能装下两个人的船，在河的一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险，你能不能提出一种安全的渡河方法呢？状态(State)：问题在某一时刻所处的“位置”，“情况”等根据问题所关心的因素，一般用向量形式表示，一位表示一个因素0：右岸1：左岸初始状态：(0,0,0)目标状态：(3,3,1)哪些操作能导致状态变化？状态可有多种表示方法：(左岸传教士数,右岸传教士数,左岸野人数,右岸野人数,船的位置)或(左岸传教士数,左岸野人数,船的位置)算子（Operator,算符，操作符）——使状态发生改变的操作MC问题中的算子◦将传教士或野人运到河对岸◦Move-1m1c-lr：将一个传教士(m)一个野人(c)从左岸(l)运到右岸(r)◦所有可能操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rlMove-2m-lrMove-2m-rlMove-1c-lrMove-1c-rlMove-1m-lrMove-1m-rlMC求解过程转化为在状态空间图中搜索一条从初始节点到目标节点的路径问题状态问题描述StateSpaceMethod:一种基于解空间的问题表示和问题求解方法ItisbasedontheStateandOperator.◦State(状态):somevariables,describingthedifferenceamongdifferentthingsoreventsofsomeclassQ=[q0，q1，…，qn]T◦Operator(算符):Ameansthatisusedtotransformaproblemfromonestatetoanother.StateSpace(状态空间):一个包括问题所有可能状态及它们之间关系的图◦通常表示为三元组：{S,F,G}S:setofallpossibleinitialstatesofproblemF:setofoperatorsG:setofgoalstatesOriginalStateMiddleStateGoalState123845671238456712384567MoveBlanksquareLeftMoveBlanksquareUpMoveBlanksquareRight8PuzzleProblem(8数码难题)12384567OriginalState12384567GoalStateInitialstateUpLeftDown12384567Up1238456712384567123845678132456712384675RightGoalSolution:Atransition/operatorsequence1:MoveBlanksquareUp2:MoveBlanksquareLeft3:MoveBlanksquareDown4:MoveBlanksquareRightIsitoptimal?Howtofindit?8PuzzleProblemInsummary,Inordertocompleteastatedescription,weneeddefine:◦initialstatedescription◦setofoperators&theiractions◦goalstatedescription119415171331214102865（InitialState）（GoalState）11941517133121410286512345678910111214131512345678910111214131512345678910111214131512345678910111214131512345678910111214131512345678910111214131512345678910111214131512345678910111214131515PuzzleProblemstates?:real-valuedcoordinatesofrobotjointanglespartsoftheobjecttobeassembledactions?:continuousmotionsofrobotjointsgoaltest?:completeassemblypathcost?:timetoexecuteDirectedGraph=Nodes+ArcsSequenceofnodes(ni1，ni2，…，nik)◦Ifexistapathfromnitonj,thennjissaidtobeaccessiblefromni;••ninjnj:Asuccessor(后继)ofni;ni:Anancestor(前驱)ofnjC(ni,nj):thecostofanarcdirectedfromnjtoni.ExplicitandImplicitGraph（显示图与隐式图）Implicit,隐式(362866states)=9*8!-14Explicit,显式(14states)571238456712384567123845671238456712384567123845671238456712384567123845671238456712384567813245671238456712384675InitialStateGoalMonkeyandBananaproblemQuestionStatesSet:（W，x，Y，z）WThemonkey’shorizontalpositionxWhenmonkeyisabovetheboxx=1,elsex=0YThebox’shorizontalpositionzWhenmonkeygetthebananaz=1,elsez=0Operator:goto（U）meansmonkeygotopositionU（W，0，Y，z）goto（U）（U，0，Y，z）pushbox（V）monkeypushestheboxtopositionV:（W，0，W，z）pushbox（V）（V，0，V，z）Example–Monkey&BananaExample–Monkey&Bananaclimbbox:monkeyclimbsthetopofthebox（W，0，W，z）climbbox（W，1，W，z）Attention:whenusedthesetwooperators,themonkeyandtheboxshouldbeonthesamehorizontalpositionandthemonkeyisnotonthetopofthebox.grasp:monkeygetthebanana（c，1，c，0）grasp（c，1，c，1）c:thepositionthatrightbelowthebanana初始状态：(a，0，b，0)从初始状态到目标状态的操作序列：｛goto(b),pushbox(c),climbbox,grasp｝isasolutionoftheproblem.（a，0，b，0）（b，1，b，0）（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）GoalStategoto（U）goto（U）goto（U）U=b，climbboxU=Vgoto（U）U=bpushbox（V）V=c，climbboxgraspInitialState•猴子香蕉箱子•猴子香蕉箱子••••••••••Ha!Ha!Example–Monkey&BananaThesolvingprocess（动画）：GeneticsProfessor◦Wantingtonamehernewbabyboy◦UsingonlythelettersD,N&ASearchbywritingdownpossibilities(states)◦D,DN,DNNA,NA,AND,DNAN,etc.◦Operators:addlettersontotheendofalreadyknownstates(i)adda'D'toanexistingstring(ii)addan'N'toanexistingstringand(iii)addan'A'toanexistingstring◦InitialstateisanemptystringGoaltest◦Lookupstateinabookofboysnames◦Goodsolution:DANQuestion◦Howmanystringsof3orfewerlettersaretherewherethelettersareD,NorA?◦AreyouguaranteedtofindallboysnameswithlettersD,NandAinthismanner?Answer◦Forstringsoflength3,therearethreechoicesfort