哈工大人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告

1、人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告學(xué)院：電腦科學(xué)與技術(shù)學(xué)院專業(yè)：電腦科學(xué)與技術(shù)目錄人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告 1一、簡(jiǎn)介 對(duì)該實(shí)驗(yàn)背景，方法以及目的的理解 31. 實(shí)驗(yàn)背景 32. 實(shí)驗(yàn)方法 33. 實(shí)驗(yàn)?zāi)康?3二、方法對(duì)每個(gè)問題的分析及解決問題的方法 4Q1: Depth First Search 4Q2: Breadth First Search 4Q3: Uniform Cost Search 5Q4: A* Search 6Q5: Corners Problem: Representation 6Q6: Corners Problem: Heuristic 6Q7: Eating All The Dots

2、: Heuristic7Q8: Suboptimal Search 7三、實(shí)驗(yàn)結(jié)果解決每個(gè)問題的結(jié)果 7Q1: Depth First Search 7Q2: Breadth First Search 9Q3: Uniform Cost Search 1.0Q4: A* Search 1.2Q5: Corners Problem: Representation 1.3 Q6: Corners Problem: Heuristic 1.4Q7: Eating All The Dots: Heuristic1.4 Q8: Suboptimal Search 1.5自動(dòng)評(píng)分 1.6四、總結(jié)及討論對(duì)該

3、實(shí)驗(yàn)的總結(jié)以及任何該實(shí)驗(yàn)的啟發(fā) 1.6.簡(jiǎn)介對(duì)該實(shí)驗(yàn)背景，方法以及目的的理解1. 實(shí)驗(yàn)背景1自人工智能概念被提出，人工智能的開展就受到了很大的關(guān)注，取得了長(zhǎng)足的開展，成為一門廣泛的交叉和前沿科學(xué)。到目前，弱人工智能取得了長(zhǎng)足的開展，而強(qiáng)人工智能那么暫時(shí)處于瓶頸。2吃豆人Pacman居住在亮藍(lán)色的世界里，在這個(gè)世界有彎曲的走廊和美味佳肴。游戲的目的就是控制游戲的主角小精靈吃掉藏在迷宮內(nèi)所有的豆子，并且不能被幽靈抓到。高效地瀏覽世界將是吃豆人掌握世界的第一步。3通過本學(xué)期的學(xué)習(xí)我們已經(jīng)初步掌握了人工智能的根本知識(shí)，在實(shí)驗(yàn)中那么應(yīng)用這些知識(shí)使用人工智能操縱吃豆人游戲。2. 實(shí)驗(yàn)方法1在本實(shí)驗(yàn)中，Pa

4、cman智能體將找到通過迷宮世界的路徑，既包括到達(dá)一個(gè)指定的位置，也包括高效地搜集食物。我們編輯文件，編寫一系列吃豆人程序，包括到達(dá)指定位置以 及有效的吃豆，并將其應(yīng)用到Pacman場(chǎng)景，完成對(duì)相關(guān)人工智能功能的完善。2在本實(shí)驗(yàn)中，我們對(duì)下面8個(gè)問題進(jìn)行研究，針對(duì)每個(gè)問題提出解決方法，逐步完成吃 豆人游戲：Q1: Depth First SearchQ2: Breadth First SearchQ3: Un iform Cost SearchQ4: A* SearchQ5: Corners Problem: Represe ntati onQ6: Corners Problem: Heuri

5、sticQ7: Eat ing All The Dots: HeuristicQ8: Suboptimal Search3. 實(shí)驗(yàn)?zāi)康?完成實(shí)驗(yàn)報(bào)告中的問題，編寫一系列吃豆人程序，包括到達(dá)指定位置以及有效的吃豆;2通過分析吃豆人游戲穩(wěn)固課堂上所學(xué)內(nèi)容；3復(fù)習(xí)python語言的使用。方法對(duì)每個(gè)問題的分析及解決問題的方法Q1: Depth First Search應(yīng)用深度優(yōu)先算法找到一個(gè)特定的位置的豆，我們通過depthFirstSearch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜索的功能。深度優(yōu)先遍歷的方法是，從圖中某頂點(diǎn)v出發(fā)：1)訪問頂點(diǎn)V；2)依次從v的未被訪問的鄰接點(diǎn)出發(fā)， 的頂點(diǎn)都被訪問；對(duì)圖進(jìn)行深度優(yōu)先遍

6、歷； 直至圖中和v有路徑相通3)假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么從一個(gè)未被訪冋的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問過為止。深度優(yōu)先搜索的順序如以下圖所示:在depthFirstSearch中，由于搜索過程中火重復(fù)訪問到局部節(jié)點(diǎn)，所以需要對(duì)于每個(gè)節(jié)點(diǎn)設(shè) 置標(biāo)記，以指示該節(jié)點(diǎn)是否被訪問過。先將每個(gè)后繼節(jié)點(diǎn)壓入搜索棧中，然后以深度優(yōu)先的順序進(jìn)行搜索，判定是否符合目標(biāo)狀態(tài)，并將符合結(jié)果的節(jié)點(diǎn)放入結(jié)果集。Q2: Breadth First Search應(yīng)用寬度優(yōu)先算法找到一個(gè)特定的位置的豆，我們通過breadthFirstSearch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜索的功能。廣度優(yōu)先搜索算法的

7、思想是：從圖中某頂點(diǎn)v出發(fā)，在訪問了 v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的 頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，那么需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新化。在這里注意，在深度優(yōu)先搜索和廣度優(yōu)先搜索方法中，我們使用的圖搜索算法是一樣的，但是涉及到具體的數(shù)據(jù)結(jié)構(gòu)卻是不同的。在深度優(yōu)先搜索算法中， 我們使用棧進(jìn)行操作， 在深度優(yōu)先搜索算法中，我們使用隊(duì)列進(jìn)行操作，如以下圖所示。這兩種數(shù)據(jù)結(jié)構(gòu)的不同之處就在于其中元素的輸出次序，在深度優(yōu)先搜索中需要

8、按照壓棧順序的逆序進(jìn)行搜索，咋子廣度優(yōu)先搜索中需要按照入隊(duì)順序的順序進(jìn)行搜索。147 d&f depthFirstSearch(probtejjj):148 井深應(yīng)優(yōu)先搜索149search_stack - uti匚k()It5 t def breadthfirstSear'chtpro/jtejn): 16L哎.優(yōu)先搜索187 "* YOUR CODE HERE *1881E9searchOueue util.Queue()Q3: Uniform Cost Search很多情況下，路徑中的代價(jià)是可以改變的，在這個(gè)問題中，我們完成代價(jià)一致搜索方法。 代價(jià)一致搜索， 其

9、實(shí)就是一個(gè)貪心搜索， 取代擴(kuò)展深度最淺的節(jié)點(diǎn)， 代價(jià)一致搜索擴(kuò)展的是 路徑消耗最低的節(jié)點(diǎn) n 。如果所有單步耗散都相等的話， 這種算法就和廣度優(yōu)先搜索算法是 一樣的。 不過， 這樣在擴(kuò)展到一個(gè)具有能返回到同一狀態(tài)的零耗散行動(dòng)的節(jié)點(diǎn)時(shí)就會(huì)陷入無 限循環(huán)。在 uniformCostSearch 函數(shù)中，我們計(jì)算每條路徑的總代價(jià)， 將總代價(jià)作為優(yōu)先級(jí)進(jìn)行搜索， 待搜索序列存儲(chǔ)于隊(duì)列中。 對(duì)于每個(gè)節(jié)點(diǎn)， 使用代價(jià)函數(shù) getCostOfActions 計(jì)算其所產(chǎn)生的 代價(jià)，并依次作為搜索的優(yōu)先級(jí)進(jìn)行搜索。同樣的，對(duì)于每個(gè)節(jié)點(diǎn)添加是否被訪問的標(biāo)記。Q4: A* SearchA*算法是一種靜態(tài)路網(wǎng)中求解最

10、短路最有效的直接搜索方法，也是許多其他問題的常用啟 發(fā)式算法，對(duì)代價(jià)一致搜索算法進(jìn)行了改進(jìn)，參加了一個(gè)估計(jì)代價(jià)h 。公式表示為：f(n)=g(n)+h(n), 其中 f(n) 是從初始狀態(tài)經(jīng)由狀態(tài) n 到目標(biāo)狀態(tài)的代價(jià)估計(jì)， g(n) 是在狀態(tài) 空間中從初始狀態(tài)到狀態(tài) n的實(shí)際代價(jià)，h(n)是從狀態(tài)n到目標(biāo)狀態(tài)的最正確路徑的估計(jì) 代價(jià)對(duì)于路徑搜索問題，狀態(tài)就是圖中的節(jié)點(diǎn)，代價(jià)就是距離 。在本實(shí)驗(yàn)中，我們使用曼哈頓距離作為啟發(fā)函數(shù)。在 aStarSearch 函數(shù)中，我們首先搜索具 有最低組合本錢和啟發(fā)式的節(jié)點(diǎn)。 類似于問題三， 我們計(jì)算每個(gè)節(jié)點(diǎn)的代價(jià)， 并以此為依據(jù) 搜索產(chǎn)生結(jié)果集，在搜索的過

11、程中，還需要標(biāo)記節(jié)點(diǎn)是否已經(jīng)被訪問過。Q5: Corners Problem: Representation找到所有的角落， 在角落迷宮的四個(gè)角上面有四個(gè)豆， 通過這個(gè)函數(shù)找到一條訪問所有四個(gè) 角落的最短的路徑。在 CornersProblem 類中，我們使用 _init_函數(shù)存儲(chǔ)墻壁的位置， 吃豆人的起點(diǎn)和角落位置， 定義新的函數(shù) getStartState 用于獲得節(jié)點(diǎn)起始狀態(tài)， isGoalState 函數(shù)判斷當(dāng)前節(jié)點(diǎn)是否為 目標(biāo)節(jié)點(diǎn)， getSuccessors 函數(shù)返回后繼狀態(tài)， 所需的操作以及代價(jià)， getCostOfActions 函數(shù) 計(jì)算動(dòng)作序列所需的代價(jià)。查找后繼節(jié)點(diǎn)時(shí)，

12、在四個(gè)方向一次遍歷， 使用 directionToVector 移動(dòng)位置， 如果沒有墻， 那么 把下一個(gè)的狀態(tài)，動(dòng)作，花費(fèi)的步數(shù)參加下一節(jié)點(diǎn)Q6: Corners Problem: Heuristic構(gòu)建適宜的啟發(fā)函數(shù)，完成問題 5 中的角落搜索問題。在問題五使用的 CornersProblem 類中定義 cornersHeuristic 函數(shù)，為角落問題構(gòu)造啟發(fā)函 數(shù)。在 cornersHeuristic 函數(shù)中使用了 GetNextNodes 函數(shù)獲取下一個(gè)節(jié)點(diǎn)， isGoal 函數(shù)判斷 是否為目標(biāo)。Q7: Eating All The Dots: Heuristic用盡可能少的步數(shù)吃掉所

13、有的豆子。這個(gè)問題利用之前A*算法可以很容易找到解，此種方法在這里不再詳述。下面在FoodSearchProblem 類中定義函數(shù) foodHeuristic，構(gòu)建適宜的啟發(fā)函數(shù)完成豆子搜 索啟發(fā)式問題。Q8: Suboptimal Search次最優(yōu)搜索，定義一個(gè)優(yōu)先吃最近的豆子的函數(shù)，以此來提高搜索速度。補(bǔ) 充 An yFoodSearchProblem目標(biāo)測(cè)試函數(shù)，并在 ClosestDotSearchAge nt 當(dāng) 中添加fin dPathToClosestDot函數(shù)，用于尋找最近的豆子。三、 實(shí)驗(yàn)結(jié)果解決每個(gè)問題的結(jié)果Q1: Depth First Searchpyth on pa

14、cma n.py -l tiny Maze -p SearchAge ntEsearch_Code5e=irch>r'ython padnan. py _1 tinyMaze -p SearcTiAeentESearchAerit us ins func tianst SearchSearchAgent using r>rablem tvpetlcinEg自rchPrcblriPa.th found with total cost of 10 in 0. 0 secondsSearch nodes expanded： 20Pacnan emerges victorious!

15、 Score: 50CAverage Score: 500.0Scores:500.0I in Rate：1/1(L 00)Record:Tin|總 Ciiaa 知 cm.SCORE: 500pyth on pacma n.py -l mediumMaze -p SearchAge ntE： 入工智能導(dǎo)論實(shí)臉 ar ch_Co de s e ar chp/thon paman. py -1 rnediuirMaEe -p EearelrAerLt SearchAant usirg i me tian dap thFirsiSe arch.EearchAg&ntJ using prcbl

16、an type Posi t i cnSsar chPr obi errath found with tutai cost of 130 in 0.C secondsSearch nDles eiparded:氐2PiciTAn ejnrga? victoricns? Score: 5E0Aeragt! jk,urt!: 380, 0Scores'38Q. 0VLn Rito：1/ (1.00)Record;pyth on pacma n.py -l bigMaze -z .5 -p SearchAge ntE:A 二智 s a Arch _Cu lie ear y thai l t-

17、'atiiiaij. py -1. 5 p Sea-i'chAeurit=StciicliAgHiit jsltig £luiuLluii dtjp lliflrs t-Sudixl.LctdJ. ullAgKllt iJolhg pl'ublhiiu"uwi ; i oiiu e di cl iTr l LI eiLPath found witti total tost cf 210 in 0. 0 second*Gear ch mdes eKpandei： 569Pacrnari cncrcoa victorious! Score: 300Avc

18、rocScore： 200,Scarce：300+DWin Rato：1/1(1.00)Roccxd：WinQ2: Breadth First Searchpyth on pacma n.py -l mediumMaze -p SearchAge nt -a fn=bfsE: 人工彗能導(dǎo)尬 l實(shí)?鈣then tiaciua.n_ py 三 1 vniadLLurNz 三p S&archAgent fn-bfslut-areJiAgwijilfun亡目門 bf trCearchAgADl using problemi iyr'e Posi t ianSearcHProbl bhP

19、ath found total co&t of 6? in 0. 0 secondsSerdh node-s espanded； 269Pacrnan eirerfies victoriauF! Ecnre； 442AverageScore： 442. 0Scoros：442. 0Vin Ra«：L/L (1.00)Raard:Vinpyth on pacma n.py -l bigMaze -p SearchAge nt -a fn=bfs -z .5E:工暫±earch_C DdB sear eh>py thon pdLjmn- p>' 1

20、tdS e 1' _ hAg ei it a £ti-l'fs "i . bfUactiDti bfa.ScarhAscnt ucinjc; pre bl zm tvpo Pc i xi znSo arcPr obi z mFath feun vidi totL cost of 210 in Q* 0 secondsSatc! nnrJfis ftp indpri：斤2Pacman eniiT&ms viciorious! Seers; 300AvsraES:or3： 300iDScores：300.DJin Rate：J/l(1.00)Rffcnr

21、d:Wincsiaap»nSCORE: 45Q3: Uniform Cost Searchpyth on pacma n.py -l mediumMaze -p SearchAge nt -a fn=ucsI. ： VvIeiSt XfeXEearchCcicteVsearchythjin pcicminP7 -1 rodiunflaz -p EearchAgent -a tn"u.:s SEQrchAsontJ uine function ucsSE-archAscntuNm prableira tms PDsitionSearcIn-ProbLexPath found

22、with total tosrt of 6S in 1 secondsFerch nades expard-Fd: 269Facran emerges virtirrioiis! Score: 442Average Scare： 44A.DSccires：44.0Win RaLe：1/1(1. 00)Record:linSCO£tE: 39pyth on pacma n.py -l mediumDottedMaze -p StayEastSearchAge nt1: A-L 哲 直屯異 I £ ktrar - h_C l du=di J . py tliuri pacjan

23、u, py -1 mu 11 luiDt. ；u 山遼匕 -p i ta vH 皿 l S e u陶3 it- aniins： This do?s not look like a rtsular search bamfound witL toLal eosl ot I in 0.0 secDikUSearch nodes CKpijdcd； 1S&Jn*_niin =rer vi ctnri 1 Sccte2 -4hriver£gaScor: 646. 0Scares'&46. 0in Rats：VI ：. 00Record:VinSCORE: 72pyth

24、on pacma n.py -l mediumScaryMaze -p StayWestSearchAge nt(» 1)in0 'OOE0!0OE:pjnay :日冋uIfl：=i_£n 咄:SIDSrQQE ;ajam£ jsnoijci|i saEiaja hikii? j6fg :戸口credit serpcru qzxed 砂42柚 Ft Ul卻 *sa> E疋* MIXA 吟心丄 >4IMiqaqojnam TTSa J a4Ai maTqDHd 9trim: Iisrnstrem"jLi'aai I'Ti

25、sii-TLar put 工&口電 uDiixm:月口號(hào)sn iua'3：xsa-as:t!T.O1E1U4 iria&rj? irag tf- j' j- 苗冋q卜 初 丸科叩叫1皿 啪玄陽珂碑。門丹破叭哦壬、撫皆第聯(lián)工*：卻orsu nHUEl 冋 UEiuaqs!noi|'EiSE=uje- ;ua6vi|0Jeas d- g- z-aze|/|6!q|-Adueiuoeduo屮人dMOJees N :K)uPUPq魂丼了盡uN:卩蜩(oti) in:旳明町習(xí)u 'STt：EajEnD30 'Sih血j:制git ：3M5S ET&

26、#187;TJO45tA SczIMO UBB：M got Topurdito cop du ho j?FPEMY 0 0 鞏 f9®6Aol2.89 J£Pld xjiy. piraj1 LT冃 yT_- jph§工阪sXp-).g d- exp評(píng)jnip 冃u訊hw討 W叩njFH?he珥彈迫電占泄岳工¥':團(tuán)SCORE： 261Il |SPI1 1MlQ5: Corners Problem: Representationpyth on pacma n.py -l tinyCorners -p SearchAge nt -a fn=bfs,p

27、rob=Cor nersProblem1二皆匸 3實(shí)臉、BEHFfhjZod&l匪ylhe pbcuuil -1 tlnyCl賞 15*0 -p SearcbiAgerjt -h. tn- bfs, j>Tob=C uTir P丄 ibl"SercliAKenti usi-iur fimction bis| _ g&aGhA 鼻日nt us i ns probLear typ曰 CccTLersF robl Ial±L rciD'id. wlth latjl erat at 2S in 0* 0 直色亡血白血expanded.： 22Qcina

28、n sTTErgBs pictorinuE! Scure： 512£亡arm: E12.0畸 or 語：512.0in Rateij/1 (1- 00)e&Qrd:Vin霏亡問血-xSCORE: 7pyth on pacma n.py -l mediumCor ners -p SearchAge nt -a fn=bfs,prob=Cor nersProbleml:.3Lt.a.ar-rCDdeediFch ：,j>yth jh pui.riurL. py -1 肥ii： liflCsmiEi l； -p Se-ir chA«rLi 由prat Ciirrit

29、rPi dblemrSBrch?,wntJ ueifl=: fu:tian bfsISsirch.sent using :prctjieE tyre ComsrEPtab 1 ent邛 th f ound with Lcital cost ot 1.06 Ln 0. 1 抽芒血於淪dull n>d#« s-XT'iiKisd 1 篝$ererg.es vitoricus1 畧c：口re: 434'.V&lft Sco-9： 4M4.0丸OTEi：4M< 0riti Rate:l/l (1. 00)Ftacd:HnSCORE: -17Q6: Corn

30、ers Problem: HeuristicE：A工首'龍異0 arch_C dcXsaar cti>pythan pieman, py -1 mcdlunCorrifirs -r> AStarC omarffAB ant -a 0. 5Tsdi lu'jijd yflth tuidLl gt'H；t a£ 106 111 Q. j 詛呂emiL血rejirch nodes Bpandrj：Facman iwrgss vitoriow! Score： 434Aver stgScare: 434. 0Scores:434 0VLn te:1/1 <1.00)RwcordlVLn定 LSlfc PaznwnSCORE: 17Q7: Eating All The Dots: Heuristicpyth on pacma n.py -l trickySearch -p AStarFoodSearchAge ntF- - AHIts總冬ula Kr ch_g dt s. ma r chythm g總戸tsy 丄 tri. CJCyr.:盅 rchh.A £ 曲氏 3?;mAQ.1Agerdlu-h foundvir*h