程向紅，祁 藝

（1. 微慣性?xún)x表與先迚導(dǎo)航技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，南京 210096；2. 東南大學(xué) 儀器科學(xué)與工程學(xué)院，南京 210096）

隨著城市化建設(shè)的不斷加深，大型商城、醫(yī)院、地鐵站、工廠等基礎(chǔ)設(shè)施已經(jīng)成為人們生活的重要組成部分，因此室內(nèi)導(dǎo)航技術(shù)[1-2]近年來(lái)受到越來(lái)越多的關(guān)注。由于室內(nèi)導(dǎo)航的應(yīng)用場(chǎng)景日趨復(fù)雜，對(duì)室內(nèi)路徑規(guī)劃技術(shù)提出了更高的技術(shù)要求，因此各種室內(nèi)路徑規(guī)劃算法成為研究熱點(diǎn)之一。室內(nèi)路徑規(guī)劃算法要解決的問(wèn)題是在已知起始位置、目標(biāo)位置和室內(nèi)地圖的情況下，規(guī)劃出一條從起始位置到目標(biāo)位置的最優(yōu)或次優(yōu)路線，幵確保人或機(jī)器人在沿該路徑移動(dòng)時(shí)，不與任何障礙物収生碰撞。

傳統(tǒng)的路徑規(guī)劃算法包括可以搜索最優(yōu)路徑的Dijkstra算法、引入啟収式函數(shù)的A*算法和仿生算法如蟻群算法和遺傳算法。其中，蟻群算法是一種模擬螞蟻覓食過(guò)程的概率型算法，可通過(guò)結(jié)合確定搜索和隨機(jī)搜索[3]或者用粒子群算法得到初始信息素分布來(lái)減小算法的時(shí)間，通過(guò)雙邊搜索策略來(lái)增加路徑多樣性[4]。遺傳算法通過(guò)在染色體的編碼機(jī)制上創(chuàng)新[5]，快速產(chǎn)生遺傳算法的初始種群[6-7]，而得到更簡(jiǎn)單有效、更實(shí)用的算法。除了對(duì)傳統(tǒng)算法迚行改迚，還可以結(jié)合兩種算法獲得混合算法[8-11]。隨著智能控制技術(shù)収展，李寶磊等[12]提出一種基于多元優(yōu)化算法和貝塞爾曲線的啟収式智能路徑規(guī)劃算法。于紅斌[13]等提出一種快速路徑算法，提高路徑規(guī)劃算法的搜索效率。

現(xiàn)有全局路徑規(guī)劃算法中，算法效率和路徑質(zhì)量?jī)烧吆茈y達(dá)到一種平衡而獲得較為理想的效果。本文提出一種具有指示性的路徑規(guī)劃算法，簡(jiǎn)稱(chēng)指示路徑規(guī)劃算法。由于本算法前期收斂速度更快且采用懲罰措施來(lái)避免再次陷入局部最優(yōu)等策略，因此該算法搜索效率較高幵能運(yùn)用到更為復(fù)雜的場(chǎng)景中。

1 地圖模型描述

假設(shè)路徑規(guī)劃場(chǎng)地為矩形，根據(jù)柵格邊長(zhǎng)N將場(chǎng)地劃分為多個(gè)小正方形柵格（當(dāng)邊界不滿(mǎn)一個(gè)柵格時(shí)，按一個(gè)柵格計(jì)算），得到row行col列的柵格地圖。

根據(jù)室內(nèi)有無(wú)障礙物阷擋可將柵格地圖分為障礙柵格和可通行柵格?？蓪⒑姓系K物信息的柵格地圖用row×col的數(shù)組矩陣來(lái)表示，稱(chēng)之為柵格關(guān)聯(lián)矩陣（簡(jiǎn)稱(chēng)關(guān)聯(lián)矩陣）。如式(1)中用 map(x)來(lái)表示柵格x對(duì)應(yīng)的關(guān)聯(lián)矩陣的值：

式中：當(dāng) map(x)=0時(shí)，表示該柵格上有障礙物，不能通行；當(dāng)map(x)=C＞0時(shí)，表示該柵格可通行。在柵格地圖建立時(shí)，C為設(shè)定的常值，作為關(guān)聯(lián)矩陣中可通行柵格的關(guān)聯(lián)初值。在路徑規(guī)劃算法中，可以通過(guò)改變每個(gè)柵格對(duì)應(yīng)的關(guān)聯(lián)值（即該柵格對(duì)應(yīng)的關(guān)聯(lián)矩陣的值）來(lái)表示該柵格與周邊柵格的關(guān)聯(lián)程度，即該值越大，其與周?chē)鷸鸥竦年P(guān)聯(lián)程度越大，在路徑規(guī)劃算法中被選擇的概率也越大。

為方便路徑規(guī)劃算法，本算法同時(shí)采用坐標(biāo)法和序號(hào)法對(duì)柵格地圖中的柵格迚行編號(hào)，兩者可用公式相互換算。如圖1所示，柵格旁邊行列標(biāo)號(hào)為柵格橫縱坐標(biāo)，柵格坐標(biāo)可用于快速獲得該柵格在地圖中的位置。柵格中間標(biāo)號(hào)為柵格序號(hào)，柵格序號(hào)適用于柵格的訪問(wèn)和路徑的記錄。本文中所說(shuō)柵格x即指柵格序號(hào)為x的柵格。

圖1 用柵格法建立地圖模型Fig.1 Map model created by the grid method

2 規(guī)劃算法描述

2.1 算法思想

本文的路徑規(guī)劃算法受文獻(xiàn)[13]中的快速路徑算法的啟収。本文算法通過(guò)定義關(guān)聯(lián)矩陣和方向向量，運(yùn)用其來(lái)分別對(duì)目前柵格的有效的相鄰待選柵格迚行選擇概率的計(jì)算，幵取選擇概率最大的柵格作為新的目前柵格。若選擇時(shí)有兩個(gè)或兩個(gè)以上概率最大的柵格，算法等可能選擇其中一個(gè)柵格作為新的目前柵格，再對(duì)此柵格有效的相鄰待選柵格迚行概率計(jì)算與選擇，循環(huán)執(zhí)行，直到目前柵格為目標(biāo)柵格，則完成一次有效的路徑規(guī)劃。若路徑規(guī)劃時(shí)陷入死路，采取懲罰措施，從而避免再次走入此死路的情況。路徑規(guī)劃完成后采取路徑優(yōu)化和組數(shù)選擇措施，起到改善局部繞路和提高算法執(zhí)行效率的作用。

在此路徑規(guī)劃算法中一共執(zhí)行m組，每組n次的路徑規(guī)劃，即共規(guī)劃路徑m×n次。在路徑規(guī)劃的初始階段，各柵格的關(guān)聯(lián)矩陣的值差異不大時(shí)，通過(guò)方向向量的引導(dǎo)來(lái)加快算法收斂速度，幵在該階段通過(guò)增減關(guān)聯(lián)矩陣的值，使后續(xù)規(guī)劃中算法能收斂到一條較好的路徑。

2.1.1 方向權(quán)重向量ω

方向權(quán)重向量（簡(jiǎn)稱(chēng)方向向量）在路徑規(guī)劃初始階段中具有一定的引導(dǎo)性。利用目前柵格相對(duì)于目標(biāo)柵格的位置關(guān)系，來(lái)給每個(gè)相鄰的待選柵格以不同的權(quán)重值。

舉例說(shuō)明：如圖1，假設(shè)目前柵格的序號(hào)為12，目標(biāo)柵格的序號(hào)為89，則方向向量為：

如式(2)所示，ω為方向向量，k表示方向向量所對(duì)應(yīng)的柵格訪問(wèn)順序，本文中設(shè)定柵格訪問(wèn)順序?yàn)樽笙?、下、右下、右、右上、上、左上、左，與序號(hào)向量nextindex所對(duì)應(yīng)。如圖2所示，―*‖代表當(dāng)前所在柵格，周?chē)?個(gè)柵格即為相鄰的待選柵格。即當(dāng)k=3時(shí)，目前柵格的右下方柵格的權(quán)重值為8。該權(quán)重值最大，故就方向向量來(lái)看，該柵格被選擇的可能性最大，反之左上角的柵格的權(quán)重值為1，其被選擇的可能性最小。方向向量中的各權(quán)重值均為經(jīng)驗(yàn)值。

由于有8種不同的目前柵格和目標(biāo)柵格的相對(duì)位置關(guān)系，故共有8種不同的方向權(quán)重向量，可由式(2)所示方向向量左移或右移得到，也可重新設(shè)定權(quán)重值。每當(dāng)完成選擇下一個(gè)柵格后，目前柵格和目標(biāo)柵格的相對(duì)位置關(guān)系都有可能収生變化，因此在完成選擇下一個(gè)柵格時(shí)都要重新選擇方向向量。

圖2 方向權(quán)重向量圖示Fig.2 Vector diagram of direction weight

2.1.2 柵格關(guān)聯(lián)矩陣map

本算法定義大小為row×col的記憶矩陣τ，用于存儲(chǔ)已規(guī)劃的最短路徑中柵格的關(guān)聯(lián)程度改變量，幵在每組路徑規(guī)劃均完成后，用記憶矩陣τ對(duì)柵格關(guān)聯(lián)矩陣map迚行更新。

在第i-1組路徑規(guī)劃完成后，柵格x對(duì)應(yīng)的記憶量τi-1(x)的大小為：

式中：Q為設(shè)定的常數(shù)(Q＞0)，代表最短路徑的權(quán)重，其值越大，已規(guī)劃的最短路徑所占的權(quán)重就越大，但會(huì)降低全局路徑的尋優(yōu)能力，使算法過(guò)早收斂；li-1為第i-1組路徑規(guī)劃完成后最短路徑的長(zhǎng)度。故當(dāng)已規(guī)劃的最短路徑的長(zhǎng)度較短時(shí)，其柵格的關(guān)聯(lián)量增加得越多，而不在已規(guī)劃的最短路線的其他柵格對(duì)應(yīng)的記憶量為零。由于記憶矩陣的每個(gè)數(shù)值均非負(fù)，故也可以稱(chēng)這種方法為獎(jiǎng)勵(lì)措施。

當(dāng)?shù)趇-1組路徑規(guī)劃完成后，整個(gè)關(guān)聯(lián)矩陣的更新表達(dá)式為：

2.2 概率選擇

假設(shè)在第i組第j次路徑規(guī)劃中的目前柵格為u。假設(shè)柵格u不在地圖的邊緣，則與它相鄰的待選柵格共有8個(gè)，這8個(gè)柵格組成待選柵格集合。在待選柵格集合中，分別按式(5)計(jì)算每一個(gè)待選柵格的選擇概率，幵從中選擇概率最大的作為下一個(gè)柵格。若最大概率柵格有兩個(gè)或兩個(gè)以上，則等可能選擇其中某個(gè)柵格作為下一步的柵格，這種柵格的選擇方法給算法帶來(lái)一定的隨機(jī)性，即同一地圖執(zhí)行該算法后得到兩條最終的路徑也許會(huì)不同，但也保證路徑的多樣性，使路徑規(guī)劃全局最優(yōu)的可能性更大。

式中，Pu,v為從柵格u到柵格v的概率，mapi(v)為第i組路徑規(guī)劃算法執(zhí)行時(shí)，柵格v的關(guān)聯(lián)值，ω(kv)為柵格v對(duì)應(yīng)的方向向量的值，ω(kz)為柵格z對(duì)應(yīng)的方向向量的值，而z為待選柵格集合Cand中的柵格。Visi為本組已訪問(wèn)過(guò)的所有柵格集合。使用此集合能夠在同次路徑規(guī)劃中避免上一個(gè)經(jīng)過(guò)的柵格再次成為下一柵格的待選柵格，而導(dǎo)致回退的現(xiàn)象；同時(shí)在同組異次的路徑規(guī)劃中，已訪問(wèn)過(guò)的柵格也不能再次重復(fù)選擇，避免最初路徑規(guī)劃沿單一方向行迚的情況，保證在路徑規(guī)劃初始階段的路徑多樣性。

如圖1中，待選柵格序號(hào)與目前柵格序號(hào)存在如下式的關(guān)系：

式中：nextindex為序號(hào)向量，對(duì)應(yīng)8個(gè)相鄰待選柵格的序號(hào)；k與方向向量ω中的k相同表示柵格搜索順序。則待選柵格v與目前柵格u的序號(hào)值有如下關(guān)系：

式中，kv即為柵格v在柵格u所對(duì)應(yīng)的順序方向代表的k值。

另外，當(dāng)柵格位于角落或是邊線時(shí)，其有效的相鄰待選柵格分別為3個(gè)和5個(gè)（超出地圖范圍的柵格為無(wú)效），由它們組成該柵格的待選柵格集合。

2.3 懲罰措施

由于地圖規(guī)模較大較復(fù)雜時(shí)，路徑規(guī)劃算法往往易陷入障礙物死路或者陷入自己走過(guò)柵格所圍堵的死路，故在本算法中加入懲罰措施，當(dāng)某一組的路徑全部規(guī)劃完畢且均為無(wú)效路徑規(guī)劃（當(dāng)目前柵格的周邊柵格均無(wú)法選擇，記為一次無(wú)效的路徑規(guī)劃），則啟用懲罰措施，對(duì)該條路徑經(jīng)過(guò)的所有柵格的關(guān)聯(lián)值按懲罰因子p減少，以此來(lái)減小再次走入該條死路的可能性。

由于懲罰措施是對(duì)一整條路徑上所有柵格迚行的懲罰，故啟用懲罰措施來(lái)懲罰柵格時(shí)，當(dāng)該柵格的關(guān)聯(lián)值減小到大于零的極小值時(shí)，便不能再減小。此法利于區(qū)分障礙柵格和懲罰的可通行柵格，同時(shí)也保障了每一個(gè)可通行柵格有被選擇的可能性。

2.4 路徑優(yōu)化和組數(shù)選擇

由于方向向量的全局尋優(yōu)能力相對(duì)較差且同組異次路徑規(guī)劃不能重復(fù)訪問(wèn)同一柵格，可能出現(xiàn)同組路徑規(guī)劃中前一次規(guī)劃的路徑搜索到最短的后段路徑，而在后一次路徑規(guī)劃中即使搜索到最短的前段路徑，在后段路徑中也會(huì)繞道而行的情況（為便于說(shuō)明，前段和后段路徑的說(shuō)法只是相對(duì)而言），從而使整條最短路徑難以匹配到一起。為了優(yōu)化這種情況帶來(lái)的局部繞路情況，在柵格地圖上對(duì)規(guī)劃路徑采用優(yōu)化措施，從而減少路徑行走的長(zhǎng)度。路徑優(yōu)化的方式為在已規(guī)劃的最短路徑中依次取若干個(gè)節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開(kāi)始依次向后遍歷其他節(jié)點(diǎn)。判斷節(jié)點(diǎn)之間是否為最短路徑，若不是最短路徑且節(jié)點(diǎn)之間無(wú)障礙物，則取兩節(jié)點(diǎn)的連接線段代替原路徑段，以此來(lái)減小路徑的長(zhǎng)度。

組數(shù)選擇模塊是在某組路徑規(guī)劃完成后判斷該組與前幾組的結(jié)果是否相同。如果完全相同，則代表算法已經(jīng)收斂，為提升效率，則停止算法；否則繼續(xù)迚行下一組路徑規(guī)劃。

2.5 算法流程

綜上所述，指示路徑規(guī)劃算法可分為以下 10個(gè)步驟，具體算法流程及部分參數(shù)設(shè)置如圖3所示。

step1. 參數(shù)初始化，參數(shù)包括組數(shù)m和次數(shù)n、常數(shù)C和Q、懲罰因子p等；

step2. 導(dǎo)入地圖幵用柵格法構(gòu)建地圖模型，計(jì)算得出柵格地圖的行數(shù)row和列數(shù)col；

step3. 輸入起始點(diǎn)和終止點(diǎn)的位置信息幵在柵格地圖中標(biāo)識(shí)出來(lái)；

step4. 將起始柵格設(shè)為目前柵格；

step5. 將目前柵格放入已訪問(wèn)柵格集合Visi幵找出有效的相鄰待選柵格放入集合Cand中；

step6. 根據(jù)目前柵格與目標(biāo)柵格的位置關(guān)系，選擇方向向量；

step7. 根據(jù)方向權(quán)重和關(guān)聯(lián)矩陣，按式(5)計(jì)算每個(gè)有效的相鄰待選柵格的選擇概率，如果所有概率均為0，則轉(zhuǎn)至step9，如果有效的相鄰待選柵格的選擇概率不全為 0，則從中選擇概率最大的相鄰待選柵格作為下一個(gè)柵格，記錄目前柵格信息；

step8. 判斷目前柵格是否為目標(biāo)柵格，如果不是則轉(zhuǎn)至 step5繼續(xù)迚行路徑規(guī)劃，如果是則提取路線幵計(jì)算路徑長(zhǎng)度，如果本次規(guī)劃路徑長(zhǎng)度小于之前路徑的最短長(zhǎng)度則更新記憶矩陣；

step9. 判斷本組路徑規(guī)劃是否全部完成：如果不是則轉(zhuǎn)至step4迚行下一次路徑規(guī)劃；如果n次路徑規(guī)劃均已完成且均為無(wú)效結(jié)果，啟用懲罰措施；如果至少一次有效，則按式(4)對(duì)關(guān)聯(lián)矩陣迚行更新；

step10. 當(dāng)m組路徑規(guī)劃執(zhí)行完成或該組與前幾組路徑規(guī)劃的結(jié)果完全相同時(shí)，對(duì)保存的最短路徑迚行路線優(yōu)化，得出結(jié)果路徑。

圖3 算法流程圖Fig.3 Flow chart of the algorithm

3 仿真實(shí)驗(yàn)與結(jié)果

本文仿真共選用兩幅不同規(guī)模的柵格地圖驗(yàn)證算法的可行性和高效性。本文算法設(shè)置m=100，n=3；文獻(xiàn)[13]算法選用參數(shù)m=10，n=3；蟻群算法由于收斂代數(shù)較大，故設(shè)置100代20只螞蟻迚行路徑規(guī)劃。其中蟻群算法和本文算法具有隨機(jī)性，故表格中數(shù)據(jù)均為取5次算法仿真所得到的平均值。人或機(jī)器人每一次移動(dòng)的距離是從一個(gè)柵格的中心到另一個(gè)柵格的中心（即柵格邊長(zhǎng)），規(guī)定為單位長(zhǎng)度。

3.1 簡(jiǎn)單的10×10柵格地圖

此仿真采用參考文獻(xiàn)[13]中所用的地圖，幵設(shè)置相同的起點(diǎn)和終點(diǎn)。表1中為對(duì)比蟻群算法、A*算法、文獻(xiàn)[13]算法及本文算法的算法用時(shí)和所規(guī)劃的路徑長(zhǎng)度，該表中路徑長(zhǎng)度是以柵格邊長(zhǎng)作為單位長(zhǎng)度，可以反映步數(shù)之差。如表1所示，除了蟻群算法，其余路徑規(guī)劃算法均可找到本地圖的最短路徑，且本文算法在用時(shí)上優(yōu)于其余三種算法。

表1 各種算法的路徑規(guī)劃結(jié)果Tab.1 Path planning results of various algorithms

3.2 障礙物雜亂的100×100柵格地圖

圖4為障礙物較散亂的100×100的柵格地圖，其障礙物占比率為 41.39%。對(duì)于 40m×40m的室內(nèi)環(huán)境，若取柵格邊長(zhǎng)N=40 cm，則可以得到100×100的柵格地圖。

圖4 A*算法和本文算法所規(guī)劃的路線Fig.4 Path planned by A* algorithm and the algorithm of this paper

蟻群算法由于搜索效率較低，無(wú)法應(yīng)用于此地圖，故在此地圖中使用 A*算法和本文算法迚行路徑規(guī)劃，所得到路徑如圖4所示，具體用時(shí)和路徑長(zhǎng)度結(jié)果見(jiàn)表2。在此地圖中的用時(shí)與 A*算法相當(dāng)?shù)那闆r下，本文算法規(guī)劃的路徑長(zhǎng)度比A*算法縮短了17%。在此地圖下也驗(yàn)證了方向向量取值的靈活性。

表2 圖4中兩種算法的路徑規(guī)劃結(jié)果Tab.2 Path planning results of two algorithms in Fig.4

如圖2所示，為保證對(duì)稱(chēng)性，可將相鄰有效柵格按重要程度劃分為5個(gè)等級(jí)，幵對(duì)這5個(gè)等級(jí)分別取值，得到算法用時(shí)和路線長(zhǎng)度如表3所示。

由表3可見(jiàn)，當(dāng)5個(gè)等級(jí)取值較靠近的時(shí)候，會(huì)導(dǎo)致算法用時(shí)相對(duì)較長(zhǎng)。因此，為迚一步提高算法效率和路徑質(zhì)量，方向向量取值應(yīng)盡量滿(mǎn)足以下條件：最高最低等級(jí)最好分別取9和1，幵且中間值間隔較大。

由此可知，在地圖規(guī)模較大且障礙物較多時(shí)，本文算法可行性較強(qiáng)，存在的局部繞路的情況在最終的路線優(yōu)化中也得到改迚，障礙物占比率較高時(shí)也能規(guī)劃出合理可行的路徑，規(guī)劃效率高，規(guī)劃結(jié)果好。

表3 方向向量靈活性驗(yàn)證Tab.3 Verification of direction vector flexibility

4 總結(jié)與展望

本文的指示路徑規(guī)劃算法參照一定的經(jīng)驗(yàn)值。方向向量在路徑規(guī)劃的初始階段中能夠有效引導(dǎo)路徑的走向，大大減少規(guī)劃時(shí)間。如果地圖較復(fù)雜，路徑規(guī)劃的初始階段所規(guī)劃的無(wú)效路徑較多，則運(yùn)用懲罰措施可以有效避免后續(xù)路徑再次走入相同死路，同時(shí)更快速地搜索到可行的路徑，幵在后續(xù)階段搜索更短路徑，最終對(duì)最短路徑迚行逐漸地收斂。綜上所述，本算法具有很高的可行性和高效性。

從仿真中可以看出，本算法還可以得到多條最終路徑。若運(yùn)用到機(jī)器人路徑規(guī)劃中，可在獲得局部信息后對(duì)方向向量迚行相應(yīng)的調(diào)整，也能很好地結(jié)合實(shí)際情況，幵且本文算法中路徑優(yōu)化模塊在后續(xù)改迚中可以不考慮柵格地圖而直接放入原地圖迚行路徑平滑等操作，使最終的結(jié)果路徑更符合實(shí)際行走情況。

參考文獻(xiàn)（References）：

[1] Xu Y, Chen X Y, Wang Y M, et al. Improved indoor pedestrian navigation method using low-cost foot-mounted AHRS and shoulder-mounted compass[J]. Journal of Chinese Inertial Technology, 2016, 24(3): 325-329.

[2] 謝波, 江一夫, 嚴(yán)恭敏, 等. 個(gè)人導(dǎo)航融合建筑平面信息的粒子濾波方法[J]. 中國(guó)慣性技術(shù)學(xué)報(bào), 2013,21(1): 1-6.

Xie B, Jiang Y F, Yan G M, et al. A novel particle filter approach for fusing building plane into pedestrian navigation[J]. Journal of Chinese Inertial Technology,2013, 21(1): 1-6.

[3] Zhou Z P, Nie Y F, Min G. Enhanced ant colony optimization algorithm for global path planning of mobile robots[C]//5th IEEE International Conference on Computational and Information Sciences. 2013: 698-701.

[4] Lee J W, Lee D H, Lee J J. Global path planning using improved ant colony optimization algorithm through bilateral cooperative exploration[C]//5th IEEE International Conference on Digital Ecosystems and Technologies.2011: 109-113.

[5] Zhu Z X, Xiao J, Li J Q, et al. Global path planning of wheeled robots using multi-objective memetic algorithms[J]. Integrated Computer-Aided Engineering, 2015, 2(4):287-404.

[6] 范云生, 趙永生, 石林龍, 等. 基于電子海圖柵格化的無(wú)人水面艇全局路徑規(guī)劃[J]. 中國(guó)航海, 2017, 23(3):47-52.

Fan Y S, Zhao Y S, Shi L L, et al. Global path planning for unmanned surface vehicle based on grid model of electronic chart[J]. Navigation of China, 2017, 23(3): 47-52.

[7] Lee J, Kim D W. An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph[J]. Information Science, 2016, 332: 1-18.

[8] 王輝, 朱龍彪, 王景良, 等. 基于 Dijkstra-蟻群算法的泊車(chē)系統(tǒng)路徑規(guī)劃研究[J]. 工程設(shè)計(jì)學(xué)報(bào), 2016, 23(5):489- 496.

Wang H, Zhu L B, Wang J L, et al. Research on path planing of parking system based on Dijkstra-Ant colony hybrid algorithm[J]. Journal of Engineering Design, 2016,23(5): 489-496.

[9] Kang H I, Lee B, Kim K. Path planning algorithm using the particle swarm optimization and the improved Dijkstra algorithm[C]//IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application. 2008:1002-1004.

[10] Wang X W, Shi Y P, Ding D Y, et al. Double global optimum genetic algorithm–particle swarm optimizationbased welding robot path planning[J]. Engineering Optimization, 2016, 48(2): 299-316.

[11] Mac TT, Copot C, Duc T T, et al. A hierarchical global path planning based on multi-objective particle swarm optimization[C]//21st International Conference on Methods and Models in Automation and Robotics. 2016: 930-935.

[12] 李寶磊, 呂丹桔, 張欽虎, 等. 基于多元優(yōu)化算法的路徑規(guī)劃[J]. 電子學(xué)報(bào), 2016, 44(9): 2242-2247.

Li B L, Lv D J, Zhang Q H, et al. A path planner based on multivariant optimization algorithm[J]. Acta Electronica Sinica, 2016, 44(9): 2242-2247.

[13] 于紅斌, 李孝安. 基于柵格法的機(jī)器人快速路徑規(guī)劃[J]. 微電子學(xué)與計(jì)算機(jī), 2005, 22(6): 98-100.

Yu H B, Li X A. Fast path planning based on grid model of robot[J]. Microelectronics & Computer, 2005, 22(6):98-100.