人工智能知識(shí)表示狀態(tài)空間

人工智能劉海波HarbinEngineeringUniversityReviewAnagentisanythingthatcanbeviewedasperceivingitsenvironmentthroughsensorsandactinguponthatenvironmentthrougheffectors.

Thepropertiesofanagent:AutonomyReactivitySocialabilityPro-activeness

ReviewMissionaryCannibalProblemLecture3:

KnowledgeRepresentation&StateSpace學(xué)習(xí)要求了解知識(shí)與知識(shí)表示的概念理解狀態(tài)與狀態(tài)空間的概念掌握狀態(tài)空間的圖描述方法掌握用狀態(tài)空間法表示與求解問(wèn)題KnowledgeBaconKnowledgeispowerFeigenbaumIntheknowledgeliesthepower如何讓知識(shí)爆發(fā)出力量呢？KnowledgeEnginneringKnowledgeEngineering(definedin1983byEdwardFeigenbaum)

isanengineeringdisciplinethatinvolvesintegratingknowledgeintocomputersystemsinordertosolvecomplexproblemsnormallyrequiringahighlevelofhumanexpertise。知識(shí)工程的研究課題知識(shí)表示問(wèn)題知識(shí)獲取問(wèn)題知識(shí)利用問(wèn)題Knowledge1997年版Webster詞典對(duì)知識(shí)的定義：知識(shí)是通過(guò)實(shí)踐、研究、聯(lián)系或調(diào)查獲得的關(guān)于事物的事實(shí)和狀態(tài)的認(rèn)識(shí)，是對(duì)科學(xué)、藝術(shù)或技術(shù)的理解，是人類(lèi)獲得的關(guān)于真理和原理的認(rèn)識(shí)的總和?？傊?，知識(shí)是人類(lèi)積累的關(guān)于自然和社會(huì)的認(rèn)識(shí)和經(jīng)驗(yàn)的總和。知識(shí)反映了客觀世界中事物之間的關(guān)系，不同事物或者相同事物間的不同關(guān)系形成了不同的知識(shí)。RelationsKnowledge知識(shí)的特性：相對(duì)正確性不確定性隨機(jī)性模糊性經(jīng)驗(yàn)性不完全性可表示性與可利用性協(xié)議性Knowledge知識(shí)的分類(lèi)按知識(shí)的作用范圍劃分為常識(shí)性知識(shí)和領(lǐng)域性知識(shí)按知識(shí)的作用及表示劃分為事實(shí)性知識(shí)、過(guò)程性知識(shí)和控制性知識(shí)

Knowledge知識(shí)的分分類(lèi)例：從哈哈爾濱到到北京是是乘飛機(jī)機(jī)還是坐坐火車(chē)的的問(wèn)題事實(shí)性知知識(shí)：哈哈爾濱、、北京、、飛機(jī)、、火車(chē)、、時(shí)間、、費(fèi)用過(guò)程性知知識(shí)：乘乘飛機(jī)、、坐火車(chē)車(chē)控制性知知識(shí)：乘乘飛機(jī)較較快、較較貴。坐坐火車(chē)較較慢、較較便宜。。Knowledge知識(shí)的分分類(lèi)按知識(shí)的的確定性性劃分為為確定性知知識(shí)和不確定性性知識(shí)按知識(shí)的的結(jié)構(gòu)及及表現(xiàn)形形式劃分分為邏輯性知知識(shí)和形象性知知識(shí)Knowledge知識(shí)的分分類(lèi)KnowledgeRepresentation表示是現(xiàn)實(shí)事事物的一一種替代代物，如如地圖。。KnowledgeRepresentation知識(shí)表示示就是將人人類(lèi)知識(shí)識(shí)形式化化或者模模型化。。實(shí)際上上就是一一種計(jì)算算機(jī)可以以接受的的用于描描述知識(shí)識(shí)的數(shù)據(jù)據(jù)結(jié)構(gòu)及及其處理理機(jī)制。。知識(shí)表示示=數(shù)據(jù)結(jié)構(gòu)構(gòu)+處理機(jī)制制KnowledgeRepresentation知識(shí)表示示的要求求正確有效效便于知識(shí)識(shí)的獲取取、組織織與維護(hù)護(hù)管理便于知識(shí)識(shí)的利用用（如搜搜索、推推理、計(jì)計(jì)算）便于知識(shí)識(shí)的理解解與機(jī)器器實(shí)現(xiàn)KnowledgeRepresentationStateSpaceRepresentation（狀態(tài)空空間法））ProblemReductionRepresentation（問(wèn)題歸歸約法））PredicateLogicRepresentation（謂詞邏邏輯法））SemanticNetworkRepresentations（語(yǔ)義網(wǎng)網(wǎng)絡(luò)法））FrameRepresentations（框架法法）ScriptRepresentations（腳本法法）ProcedureRepresentations（過(guò)程法法）PetriNetRepresentations（Petri網(wǎng)法）Object-OrientedRepresentations（面向?qū)?duì)象法））StateSpaceRepresentation狀態(tài)是用來(lái)表表示描述述系統(tǒng)狀狀態(tài)的事事實(shí)性知知識(shí)的一一組有序序變量集集合：Q=[q0,q1,……,qn]T式中每每個(gè)元元素qi(i=0,1，…,n)稱(chēng)為狀狀態(tài)變變量，，給定定每個(gè)個(gè)狀態(tài)態(tài)變量量的一一組值值就得得到一一個(gè)具具體的的狀態(tài)態(tài)。StateSpaceRepresentation操作是用來(lái)來(lái)表示示引起起狀態(tài)態(tài)變化化的過(guò)過(guò)程性性知識(shí)識(shí)的一一組關(guān)關(guān)系或或函數(shù)數(shù)：O={o1,o2,……,om}式中每每個(gè)元元素oj(j=0,1，…,m)稱(chēng)為操操作算算子。。StateSpaceRepresentation狀態(tài)空空間是利用用狀態(tài)態(tài)變量量和操操作算算子表表示系系統(tǒng)或或問(wèn)題題的有有關(guān)知知識(shí)的的符號(hào)號(hào)體系系，狀狀態(tài)空空間是是一個(gè)個(gè)四元元組：：(S,O,S0,G)其中：：S：狀態(tài)態(tài)集合合；O：操作作算子子的集集合；；S0：包含含問(wèn)題題的初初始狀狀態(tài)G：包含含問(wèn)題題的目目標(biāo)狀狀態(tài)StateSpaceRepresentation解是使初初始狀狀態(tài)轉(zhuǎn)轉(zhuǎn)換為為目標(biāo)標(biāo)狀態(tài)態(tài)的有有限操操作算算子序序列。。解往往往不惟惟一??！StateSpaceRepresentation任何類(lèi)類(lèi)型的的數(shù)據(jù)據(jù)結(jié)構(gòu)構(gòu)都可可以用用來(lái)描描述狀狀態(tài)，，如符符號(hào)、、字符符串、、向量量、多多維數(shù)數(shù)組、、樹(shù)和和表格格等。。所選用用的數(shù)數(shù)據(jù)結(jié)結(jié)構(gòu)形形式要要與狀狀態(tài)所所蘊(yùn)含含的某某些特特性具具有相相似性性。StateSpaceRepresentation例題：：八數(shù)數(shù)碼問(wèn)問(wèn)題（（重排排九宮宮問(wèn)題題）任何一一種擺擺法就就是一一個(gè)狀狀態(tài)，，所有有擺法法即為為狀態(tài)態(tài)集S，其大大小為為9!，S0和G分別為為上面面左右右兩圖圖所示示狀態(tài)態(tài)。操操作O如何表表示？？StateSpaceRepresentation例題：：八數(shù)數(shù)碼問(wèn)問(wèn)題（（重排排九宮宮問(wèn)題題）O={數(shù)碼移移動(dòng)操操作}O={,,,}，箭頭頭表示示移動(dòng)動(dòng)空格格如何求求解？？StateSpaceGraph狀態(tài)空空間可可用有有向圖圖來(lái)描描述圖的節(jié)節(jié)點(diǎn)表表示問(wèn)問(wèn)題的的狀態(tài)態(tài)圖的弧弧表示示狀態(tài)態(tài)之間間的關(guān)關(guān)系弧可用用一個(gè)個(gè)數(shù)字字表示示對(duì)應(yīng)應(yīng)操作作算子子的代代價(jià)問(wèn)題求求解等等價(jià)于于在圖圖中尋尋找從從起點(diǎn)點(diǎn)到目目標(biāo)點(diǎn)點(diǎn)的路路徑StateSpaceGraph八數(shù)碼碼問(wèn)題題狀態(tài)態(tài)空間間的圖圖描述述ExamplesTSP問(wèn)題（（TravelingSalemanProblem）有一個(gè)個(gè)推銷(xiāo)銷(xiāo)員，，要到到n個(gè)城市市推銷(xiāo)銷(xiāo)商品品，他他要找找出一一個(gè)包包含所所有n個(gè)城市市（每每個(gè)城城市只只能經(jīng)經(jīng)過(guò)一一次））的具具有最最短路路程的的環(huán)路路。ExamplesTSP問(wèn)題（（TravelingSalemanProblem）ExamplesCPP問(wèn)題（（ChinesePostmanProblem）一個(gè)郵郵遞員員從郵郵局出出發(fā)，，到所所轄街街道投投遞郵郵件，，最后后返回回郵局局，如如果他他必須須走遍遍所轄轄的每每條街街道至至少一一次，，那么么他應(yīng)應(yīng)如何何選擇擇投遞遞路線線，使使所走走的路路程最最短？？Extensions哥尼斯斯堡七七橋問(wèn)問(wèn)題PregelK?nigsbergPregelExtensions哥尼斯斯堡七七橋問(wèn)問(wèn)題ExtensionsEuler回路給定無(wú)無(wú)孤立立結(jié)點(diǎn)點(diǎn)圖G，若存存在一一條回回路，，經(jīng)過(guò)過(guò)圖中中每邊邊一次次且僅僅一次次，該該回路路稱(chēng)為為Euler回路。。ExtensionsHamilton回路給定圖圖G，若存存在一一條回回路，，經(jīng)過(guò)過(guò)圖中中每個(gè)個(gè)結(jié)點(diǎn)點(diǎn)恰好