版權聲明(míng)：本文爲CSDN博主「曼陀羅彼岸花」的(de)原創文章(zhāng)，遵循 CC 4.0 BY-SA 版權協議(yì)，轉載請附上原文出處鏈接及本聲明(míng)。

        原文鏈接：

        https://blog.csdn.net/tiandijun/article/details/62226163

        下(xià)面是路徑規劃最常用(yòng)的(de)A*算(suàn)法的(de)介紹。

        1、路徑規劃定義

        路徑規劃是指的(de)是機器人(rén)的(de)最優路徑規劃問題，即依據某個(gè)或某些優化(huà)準則（如工作代價最小、行走路徑最短、行走時(shí)間最短等），在工作空間中找到一個(gè)從起始狀态到目标狀态能避開障礙物(wù)的(de)最優路徑。

        也(yě)就是說，應注意以下(xià)三點：

        ❖   明(míng)确起始位置及終點

        ❖   避開障礙物(wù)

        ❖   盡可(kě)能做(zuò)到路徑上的(de)優化(huà)

        機器人(rén)的(de)路徑規劃應用(yòng)場(chǎng)景極豐富，最常見如遊戲中NPC及控制角色的(de)位置移動，百度地圖等導航問題，小到家庭掃地機器人(rén)、無人(rén)機，大(dà)到各公司正争相開拓的(de)無人(rén)駕駛汽車等。

        這(zhè)裏介紹一下(xià)在遊戲以及無人(rén)機航線規劃上最常見的(de)A*算(suàn)法。

        2、A*算(suàn)法詳解

        在計算(suàn)機科學中，A*算(suàn)法作爲Dijkstra算(suàn)法的(de)擴展，因其高(gāo)效性而被廣泛應用(yòng)于尋路及圖的(de)遍曆，如星際争霸等遊戲中就大(dà)量使用(yòng)。

        在理(lǐ)解算(suàn)法前，我們需要知道幾個(gè)概念：

        搜索區(qū)域（The Search Area）：圖中的(de)搜索區(qū)域被劃分(fēn)爲了(le)簡單的(de)二維數組，數組每個(gè)元素對(duì)應一個(gè)小方格，當然我們也(yě)可(kě)以将區(qū)域等分(fēn)成是五角星、矩形等，通(tōng)常将一個(gè)單位的(de)中心點稱之爲搜索區(qū)域節點（Node），而非方格（Squares）。

        開放列表(Open List)：我們将路徑規劃過程中待檢測的(de)節點存放于Open List中，而已檢測過的(de)格子則存放于Close List中。

        父節點（parent）：在路徑規劃中用(yòng)于回溯的(de)節點，開發時(shí)可(kě)考慮爲雙向鏈表結構中的(de)父節點指針。

        路徑排序（Path Sorting）：具體往哪個(gè)節點移動由以下(xià)公式确定：F(n) = G(n) + H(n)。G代表的(de)是從初始位置A沿著(zhe)已生成的(de)路徑到指定待檢測格子的(de)移動開銷。H指定待測格子到目标節點B的(de)估計移動開銷。

        啓發函數（Heuristics Function）：H爲啓發函數，也(yě)被認爲是一種試探，由于在找到唯一路徑前，我們不确定在前面會出現什(shén)麽障礙物(wù)，因此用(yòng)了(le)一種計算(suàn)H的(de)算(suàn)法，具體根據實際場(chǎng)景決定。在我們簡化(huà)的(de)模型中，H采用(yòng)的(de)是傳統的(de)曼哈頓距離（Manhattan Distance），也(yě)就是橫縱向走的(de)距離之和(hé)。

        如圖中所示，綠色方塊爲機器人(rén)起始位置A，紅色方塊爲目标位置B，藍色爲障礙物(wù)。

        現用(yòng)A*算(suàn)法尋找出一條自綠色A到紅色B的(de)最短路徑，經簡化(huà)，每個(gè)方格的(de)邊長(cháng)爲10，即垂直水(shuǐ)平方向移動開銷爲10。節點對(duì)角線爲10，因此斜對(duì)角移動開銷約等于14。因此具體步驟如下(xià)：

        （1）将A點加入到Open List中，圖中所示，上下(xià)左右移動一格距離爲10，斜對(duì)角移動距離爲14。環繞綠色方塊的(de)就是待檢測格子，左下(xià)角的(de)值就是G值，右下(xià)角爲H值，左上角對(duì)應的(de)就是F值，找到F值最小的(de)節點作爲新的(de)起始位置。

        （2）綠色格子右側的(de)節點F爲40，選作當前處理(lǐ)節點，并将這(zhè)個(gè)點從Open List删除，增加到Close List中，對(duì)這(zhè)個(gè)節點周圍的(de)8個(gè)格子進行判斷，若是不可(kě)通(tōng)過或已經在Close List中，則忽略之。否則執行以下(xià)步驟：

        若當前處理(lǐ)格子的(de)相鄰格子已經在Open List中，那就計算(suàn)臨近節點經當前處理(lǐ)節點到起點的(de)距離G是否比原G值小，若小，則把相鄰節點的(de)父節點（parent）設置爲當前處理(lǐ)節點。

        若當前處理(lǐ)格子的(de)相鄰格子不在Open List中，那麽把它加入，并将它的(de)父節點設置爲該節點。

        （3）重複1、2步驟，直到終點B加入到了(le)Open List中，再沿著(zhe)各節點的(de)父節點回溯遍曆，将遍曆得(de)到的(de)節點坐(zuò)标保存下(xià)來(lái)，所得(de)的(de)節點就是最短路徑。

        最終效果如圖所示：

        在Github上找到了(le)一個(gè)A-star的(de)c++源碼：https://github.com/booirror/data-structures-and-algorithm-in-c供參考。

        但也(yě)發現，在整個(gè)計算(suàn)過程中，A*算(suàn)法結合了(le)啓發式方法，利用(yòng)估值函數F(H)來(lái)估計途中當前點與終點距離，并由此決定搜索方向，當這(zhè)條路失敗會重新嘗試其他(tā)路徑，但不理(lǐ)想的(de)估值函數會導緻整個(gè)算(suàn)法運行很慢(màn)，而且這(zhè)種算(suàn)法雖說在時(shí)間上最優，但也(yě)存在空間增長(cháng)是指數級别的(de)缺點。因此在往高(gāo)維狀态空間進行運算(suàn)時(shí)，速度會受到影(yǐng)響，基于A*算(suàn)法叠代加深的(de)IDA*算(suàn)法則有效解決了(le)空間增長(cháng)帶來(lái)的(de)問題。

        3、自動駕駛對(duì)路徑規劃的(de)需求

        目前業内對(duì)自動駕駛的(de)技術方案觀點較爲一緻，主要可(kě)分(fēn)爲四個(gè)部分(fēn)：

        因此首先要做(zuò)的(de)就是對(duì)外部環境的(de)實時(shí)獲取及車輛的(de)動态路徑規劃。 傳統機器人(rén)路徑規劃大(dà)緻可(kě)分(fēn)三種：

        ❖   靜态結構化(huà)環境下(xià)的(de)路徑規劃

        ❖   動态已知環境下(xià)的(de)路徑規劃

        ❖   動态不确定環境下(xià)的(de)路徑規劃

        将其與自動駕駛對(duì)應起來(lái)，靜态的(de)規劃就是根據地理(lǐ)信息以及交通(tōng)規則在已知的(de)全局地圖上進行道路循迹，但這(zhè)個(gè)技術對(duì)于目前自動駕駛實現來(lái)說并沒有什(shén)麽實際應用(yòng)價值。

        自動駕駛需要的(de)是對(duì)預先已選擇好的(de)最優路徑，甚至在未知的(de)環境下(xià)，基于實時(shí)不确定的(de)場(chǎng)景，進行動态調整的(de)路徑規劃技術，而這(zhè)對(duì)地圖的(de)需求、外部信息采集等就還(hái)是要依賴上一篇提及的(de)如攝像頭、激光(guāng)雷達、傳感器等硬件的(de)支持。

        之前網上有在轉載的(de)一篇《從算(suàn)法上解讀自動駕駛是如何實現的(de)》也(yě)有所總結，提到目前自動駕駛上應用(yòng)較廣的(de)有Dijkstra、Lee、Floyd、雙向搜索算(suàn)法以及蟻群算(suàn)法，大(dà)家如果感興趣可(kě)以自行搜索學習(xí)，這(zhè)裏不再贅述。

        現有傳統機器人(rén)路徑規劃技術已經發展得(de)較爲成熟，而将該技術如何更爲符合場(chǎng)景地應用(yòng)到自動駕駛技術上還(hái)有很長(cháng)的(de)探索階段，但現已存在的(de)包括A*算(suàn)法在内的(de)一系列最優路徑算(suàn)法将會越來(lái)越由于圖論、人(rén)工智能、機器人(rén)技術、自動駕駛等多(duō)學科的(de)融合下(xià)得(de)到更大(dà)的(de)發展。