2021-11-18 22:09:25 索煒達電子 1762
項目編號：B405
文件大?。?8M
操作系統(tǒng)：Windows10旗艦版
源碼說明：帶中文注釋
開發(fā)工具：Python
開發(fā)語言：.py
機器人路徑規(guī)劃問題：左上角為坐標原點，水平向右為 x 軸方向，豎直向下為 y 軸方向。白色為自由柵格，黑色為障礙柵格，機器人只能在自由柵格中運動，并躲避障礙。每個柵格由唯一的坐標（x, y）表示。機器人一般有八個可移動方向。給出由初始位置（3，3）到目標位置（9，9）的最佳路線。
實驗結(jié)果
根據(jù)上述代碼流程圖可以知道，算法會根據(jù)當前的狀態(tài)選擇最優(yōu)的節(jié)點進行拓展。根據(jù)啟發(fā)函數(shù)的定義，拓展的方向總是一開始沿著從起始節(jié)點指向終止節(jié)點的。首先給出搜過過程的動態(tài)變化圖。
圖中，灰色的區(qū)域為機器人可以移動的范圍；黑色的區(qū)域為地圖上的障礙；淺綠色的點為機器人出發(fā)的位置；藍色的點為目標位置；紅色的區(qū)域為open表涵蓋的區(qū)域；橙色的區(qū)域為close表涵蓋的區(qū)域；最后出現(xiàn)的紫色區(qū)域是機器人的最優(yōu)路徑。
可以給出搜索圖如下：
程序每次從當前所在的位置出發(fā)，尋找周圍可以移動的區(qū)域，加入拓展表中，若新的位置已經(jīng)存在于open表或者close表中，則重新計算代價進行評估；若不在，則直接加入open表。從open表中尋找到下一個最優(yōu)的節(jié)點，并將其移入close表開始拓展。動態(tài)過程圖展示的情況和算法一致。
從搜索圖中可以看出，一共進行了6次拓展，每次按照最優(yōu)的啟發(fā)函數(shù)尋找節(jié)點進行拓展，過程為(3,3)→(4,4)→(5,5)→(6,6)→(7,7)→(8,8)→(9,9)。從搜索過程的動態(tài)變化圖和搜索樹中可以發(fā)現(xiàn)，程序找到的確實是最優(yōu)路徑，每次的啟發(fā)函數(shù)估計值最小。由于地圖中有障礙的存在，因此始終滿足h(n)≤h^* (n)。
目錄│文件列表:
└ robot_path_planning_by_Astar
│ 2021人工智能大作業(yè).pdf
│ Astar總.jpg
│ Astar搜索圖.jpg
│ Astar搜索過程.jpg
│ calculate.py
│ main.py
│ test.py
│ 人工智能大作業(yè).docx
│ 人工智能部分大作業(yè).pdf
├ .idea
│ │ deployment.xml
│ │ misc.xml
│ │ modules.xml
│ │ Robots_path_planning.iml
│ │ vcs.xml
│ └ inspectionProfiles
│ │ profiles_settings.xml
│ └ Project_Default.xml
├ fig
│ │ 0.jpg
│ │ 1.jpg
│ │ 10.jpg
│ │ 11.jpg
│ │ 12.jpg
│ │ 13.jpg
│ │ 14.jpg
│ │ 15.jpg
│ │ 16.jpg
│ │ 17.jpg
│ │ 18.jpg
│ │ 19.jpg
│ │ 2.jpg
│ │ 20.jpg
│ │ 21.jpg
│ │ 22.jpg
│ │ 23.jpg
│ │ 24.jpg
│ │ 25.jpg
│ │ 26.jpg
│ │ 27.jpg
│ │ 28.jpg
│ │ 29.jpg
│ │ 3.jpg
│ │ 30.jpg
│ │ 31.jpg
│ │ 32.jpg
│ │ 33.jpg
│ │ 34.jpg
│ │ 35.jpg
│ │ 36.jpg
│ │ 37.jpg
│ │ 4.jpg
│ │ 5.jpg
│ │ 6.jpg
│ │ 7.jpg
│ │ 8.jpg
│ └ 9.jpg
├ random
│ │ 0.jpg
│ │ 1.jpg
│ │ 10.jpg
│ │ 11.jpg
│ │ 12.jpg
│ │ 13.jpg
│ │ 14.jpg
│ │ 15.jpg
│ │ 16.jpg
│ │ 17.jpg
│ │ 18.jpg
│ │ 19.jpg
│ │ 2.jpg
│ │ 20.jpg
