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

1、.人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)2016.12.20目錄人工智能導(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)康?二、方法（對(duì)每個(gè)問題的分析及解決問題的方法）4Q1: Depth First Search4Q2: Breadth First Search4Q3: Uniform Cost Search5Q4: A* Search6Q5: Corners Problem: Representation6Q6: Corners Problem: Heuristic6Q7: Eating All The Dot

2、s: Heuristic7Q8: Suboptimal Search7三、實(shí)驗(yàn)結(jié)果（解決每個(gè)問題的結(jié)果）7Q1: Depth First Search7Q2: Breadth First Search9Q3: Uniform Cost Search10Q4: A* Search12Q5: Corners Problem: Representation13Q6: Corners Problem: Heuristic14Q7: Eating All The Dots: Heuristic14Q8: Suboptimal Search15自動(dòng)評(píng)分15四、總結(jié)及討論（對(duì)該實(shí)驗(yàn)的總結(jié)以及任何該實(shí)驗(yàn)的啟發(fā)

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

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

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

6、點(diǎn)v；2) 依次從v的未被訪問的鄰接點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問；3) 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則從一個(gè)未被訪問的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問過(guò)為止。深度優(yōu)先搜索的順序如下圖所示：在depthFirstSearch中，由于搜索過(guò)程中火重復(fù)訪問到部分節(jié)點(diǎn)，所以需要對(duì)于每個(gè)節(jié)點(diǎn)設(shè)置標(biāo)記，以指示該節(jié)點(diǎn)是否被訪問過(guò)。 先將每個(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è)特定的位置的豆，我們通過(guò)bread

7、thFirstSearch函數(shù)實(shí)現(xiàn)深度優(yōu)先搜索的功能。廣度優(yōu)先搜索算法的思想是：從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未曾被訪問過(guò)的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問到為止。如下圖：在breadthFirstSearch中，大體的搜索思路與深度優(yōu)先算法一致，只是搜索的次序發(fā)生了變化。在這里注意，在深度優(yōu)先搜索和廣度優(yōu)先搜索方法中，我們使用的圖

8、搜索算法是一樣的，但是涉及到具體的數(shù)據(jù)結(jié)構(gòu)卻是不同的。在深度優(yōu)先搜索算法中，我們使用棧進(jìn)行操作，在深度優(yōu)先搜索算法中，我們使用隊(duì)列進(jìn)行操作，如下圖所示。這兩種數(shù)據(jù)結(jié)構(gòu)的不同之處就在于其中元素的輸出次序，在深度優(yōu)先搜索中需要按照壓棧順序的逆序進(jìn)行搜索，咋子廣度優(yōu)先搜索中需要按照入隊(duì)順序的順序進(jìn)行搜索。Q3: Uniform Cost Search很多情況下，路徑中的代價(jià)是可以改變的，在這個(gè)問題中，我們完成代價(jià)一致搜索方法。代價(jià)一致搜索，其實(shí)就是一個(gè)貪心搜索，取代擴(kuò)展深度最淺的節(jié)點(diǎn)，代價(jià)一致搜索擴(kuò)展的是路徑消耗最低的節(jié)點(diǎn)n。如果所有單步耗散都相等的話，這種算法就和廣度優(yōu)先搜索算法是一樣的。不過(guò)，這

9、樣在擴(kuò)展到一個(gè)具有能返回到同一狀態(tài)的零耗散行動(dòng)的節(jié)點(diǎn)時(shí)就會(huì)陷入無(wú)限循環(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)中求解最短路最有效的直接搜索方法，也是許多其他問題的常用啟發(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到目

10、標(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é)果集，在搜索的過(guò)程中，還需要標(biāo)記節(jié)點(diǎn)是否已經(jīng)被訪問過(guò)。Q5: Corners Problem: Representation找到所有的角落，在角落迷宮的四個(gè)角上面有四個(gè)豆，通過(guò)這個(gè)函數(shù)找到一條訪問所有四個(gè)角落的最短的路徑。在CornersPr

11、oblem類中，我們使用_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í)，在四個(gè)方向一次遍歷，使用directionToVector移動(dòng)位置，如果沒有墻，則把下一個(gè)的狀態(tài)，動(dòng)作，花費(fèi)的步數(shù)加入下一節(jié)點(diǎn)Q6: Corners Problem: Heuristic構(gòu)建合適的啟發(fā)函數(shù)，完成問題5中的角落搜索問題。在問題五使用的CornersPr

12、oblem類中定義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ù)吃掉所有的豆子。這個(gè)問題利用之前A*算法可以很容易找到解，此種方法在這里不再詳述。下面在FoodSearchProblem類中定義函數(shù)foodHeuristic，構(gòu)建合適的啟發(fā)函數(shù)完成豆子搜索（啟發(fā)式）問題。Q8: Suboptimal Search次最優(yōu)搜索，定義一個(gè)優(yōu)先吃最近的豆子的函數(shù)，以此來(lái)提高搜索速度。

13、補(bǔ)充AnyFoodSearchProblem目標(biāo)測(cè)試函數(shù)，并在ClosestDotSearchAgent當(dāng)中添加findPathToClosestDot函數(shù)，用于尋找最近的豆子。三、 實(shí)驗(yàn)結(jié)果（解決每個(gè)問題的結(jié)果）Q1: Depth First Search python pacman.py -l tinyMaze -p SearchAgent python pacman.py -l mediumMaze -p SearchAgentpython pacman.py -l bigMaze -z .5 -p SearchAgentQ2: Breadth First Search python p

14、acman.py -l mediumMaze -p SearchAgent -a fn=bfspython pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5Q3: Uniform Cost Search python pacman.py -l mediumMaze -p SearchAgent -a fn=ucspython pacman.py -l mediumDottedMaze -p StayEastSearchAgentpython pacman.py -l mediumScaryMaze -p StayWestSearchAgen

15、tQ4: A* Search python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristicQ5: Corners Problem: Representation python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblempython pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblemQ6: Co

16、rners Problem: Heuristic python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5Q7: Eating All The Dots: Heuristic python pacman.py -l trickySearch -p AStarFoodSearchAgentQ8: Suboptimal Searchpython pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5自動(dòng)評(píng)分四、 總結(jié)及討論（對(duì)該實(shí)驗(yàn)的總結(jié)以及任何該實(shí)驗(yàn)的啟發(fā)）1. 在這個(gè)實(shí)驗(yàn)中，我們對(duì)深度優(yōu)先搜索、廣度優(yōu)先搜索、代價(jià)一致搜索和A*算法四種搜索方法進(jìn)行了python代碼實(shí)現(xiàn)，對(duì)這四種