物流無(wú)人機(jī)路徑規(guī)劃算法綜述

文/李丹

引言

近年來(lái)，隨著互聯(lián)網(wǎng)網(wǎng)購(gòu)的興起，物流配送需求增加，但在配送末端環(huán)節(jié)由于其采用的是人工配送，并且交通擁堵情況日益嚴(yán)重，末端環(huán)節(jié)的配送成本一直以來(lái)居高不下，給物流配送行業(yè)帶來(lái)很大壓力。無(wú)人機(jī)憑借其便捷、快速的特性在物流配送領(lǐng)域占據(jù)一席之地，國(guó)內(nèi)為大型的物流企業(yè)紛紛加入了無(wú)人機(jī)物流配送的競(jìng)爭(zhēng)。路徑規(guī)劃技術(shù)是無(wú)人機(jī)配送研發(fā)的關(guān)鍵技術(shù)之一，關(guān)于路徑優(yōu)化的重點(diǎn)在于研究算法問(wèn)題。經(jīng)典智能算法包括粒子群優(yōu)化算法[1]，螞蟻聚類算法[2]。還有一些新型仿生智能的算法，如烏賊算法，果蠅算法廣泛應(yīng)用于分布式無(wú)人機(jī)群合作控制。目前，國(guó)內(nèi)外學(xué)者針對(duì)算法問(wèn)題從開(kāi)展了大量研究，并且在基本算法上提出各種改進(jìn)算法或者提出新的算法理論，本文將對(duì)目前主流的智能算法進(jìn)行綜述，重點(diǎn)介紹算法的基本原理、最新成果以及優(yōu)缺點(diǎn)。在此基礎(chǔ)上，對(duì)無(wú)人機(jī)配送路徑規(guī)劃算法未來(lái)的發(fā)展方向進(jìn)行展望。本文根據(jù)物流無(wú)人機(jī)路徑規(guī)劃領(lǐng)域,選取了A*算法、粒子群算法、蟻群算法、遺傳算法、果蠅算法、和烏賊算法等四種經(jīng)典算法和兩種新型仿生智能算法進(jìn)行文獻(xiàn)綜述。主要介紹基本算法的概念和其存在的優(yōu)缺點(diǎn),并且列舉了上述優(yōu)化算法在無(wú)人機(jī)路徑規(guī)劃和其相關(guān)領(lǐng)域的最新研究成果，最后對(duì)無(wú)人機(jī)配送的路徑規(guī)劃算法的發(fā)展趨勢(shì)進(jìn)行了展望。

1.無(wú)人機(jī)路徑規(guī)劃

無(wú)人機(jī)路徑規(guī)劃是研究如何確定最可行的方法起點(diǎn)和終點(diǎn)之間的路徑。這個(gè)問(wèn)題是一個(gè)NP（Non-deterministic Polynomial）難題，因此可以根據(jù)相關(guān)約束條件將其建模并且采用算法求解轉(zhuǎn)化為優(yōu)化問(wèn)題。主流的路徑規(guī)劃智能算法，大概可以分為兩大類，一種是經(jīng)典的智能算法，例如蟻群算法[3]、遺傳算法[4]、A*算法[5]和粒子群算法[6]。另一種是新型仿生智能算法，例如烏賊算法，果蠅優(yōu)化算法等。本文列舉了在經(jīng)典算法和新型仿生智能算法有代表性的幾個(gè)算法來(lái)探討。

1.1 經(jīng)典算法。國(guó)內(nèi)外許多學(xué)者在研究無(wú)人機(jī)配送三維路徑規(guī)劃的時(shí)候?qū)⑵滢D(zhuǎn)換為二維問(wèn)題，這些都可以用經(jīng)典的智能算法來(lái)求解。在無(wú)人機(jī)配送路徑規(guī)劃的算法研究上使用較多的經(jīng)典算法有遺傳算法，蟻群算法和粒子群算法等。

1.1.1 遺傳算法。1975年，Holland首次提出了遺傳算法（genetic algorithm，GA）的概念。遺傳算法的思路是由生物界優(yōu)勝劣汰機(jī)制衍生出來(lái)的搜索算法。遺傳算法的優(yōu)點(diǎn)是它可以在搜索過(guò)程不斷自適應(yīng)調(diào)整方向以至于找到全局最優(yōu)解為止。但由于無(wú)人機(jī)路徑規(guī)劃有著時(shí)間短并且對(duì)計(jì)算機(jī)資源要求較高的特性，采用遺傳算法進(jìn)行求解時(shí)會(huì)有早熟的現(xiàn)象，往往很難得到全局的最優(yōu)解。一般用于參考路徑規(guī)劃，很難用于實(shí)時(shí)規(guī)劃。由于傳統(tǒng)的遺傳算法用于無(wú)人機(jī)路徑規(guī)劃存在以上缺陷，一般都是將改進(jìn)后的遺傳算法或者將遺傳算法與其他算法相結(jié)合用于無(wú)人機(jī)三維路徑規(guī)劃中。例如神經(jīng)網(wǎng)絡(luò)算法有著高效率和環(huán)境適應(yīng)性好的特點(diǎn)，將其與遺傳算法結(jié)合可以彌補(bǔ)其缺點(diǎn)。陳志軍等[7]提出一種基于模糊神經(jīng)網(wǎng)絡(luò)和遺傳算法，并建立了一種新的路徑規(guī)劃方法。

1.1.2 蟻群算法。蟻群算法（ant colony optimization,ACO）是意大利學(xué)者Dorigo由螞蟻找尋食物產(chǎn)生的想法，是一種路徑尋優(yōu)的概率型算法。但傳統(tǒng)的蟻群算法容易使路徑規(guī)劃求解陷入局部最優(yōu)解中，因此許多學(xué)者在研究無(wú)人機(jī)配送路徑規(guī)劃問(wèn)題時(shí)多數(shù)時(shí)候是將蟻群算法與其他算法相結(jié)合使用，目前比較常用的是將人工勢(shì)場(chǎng)法與蟻群算法結(jié)合、A*算法與蟻群算法結(jié)合、柵格法與蟻群算法結(jié)合等。王剛等[8]在研究機(jī)器人的三維避障路徑規(guī)劃問(wèn)題時(shí)，提出一種基于人工勢(shì)場(chǎng)法的改進(jìn)的蟻群算法，修改了蟻群算法的啟發(fā)值參數(shù)，改變了算法的更新規(guī)則，使得改進(jìn)后的蟻群算法能更快地收斂，找到最優(yōu)解。

1.1.3 粒子群算法。粒子群優(yōu)化算法（particle swarm optimization，PSO）最初由Kennedy和Eberhart提出，是一種基于鳥類種群捕食的啟發(fā)式算法。粒子群優(yōu)化算法有著容易陷入局部最優(yōu)解和實(shí)時(shí)避障能力不足的缺陷，對(duì)在動(dòng)態(tài)三維環(huán)境下，這些都是致命性的問(wèn)題。由于蟻群算法收斂速度慢，而粒子群算法初期收斂速度太快，許多學(xué)者提出在改進(jìn)的蟻群系統(tǒng)基礎(chǔ)上融合粒子群算法。王闖等[9]提出了一種新的隨機(jī)時(shí)滯粒子群優(yōu)化算法，很好地解決了傳統(tǒng)粒子群算法早期收斂速度快和局部尋優(yōu)的缺點(diǎn)。

1.2 新型仿生智能算法。三維多無(wú)人機(jī)路徑規(guī)劃非常困難，因?yàn)椴皇侵豢紤]二維平面問(wèn)題，還得考慮空中環(huán)境和安全因素，并且無(wú)人機(jī)配送路徑規(guī)劃是動(dòng)態(tài)的，傳統(tǒng)的二維算法將不再適用。新型仿生智能算法在無(wú)人機(jī)路徑規(guī)劃中也運(yùn)用較多。主要有烏賊算法，果蠅算法，鯨魚算法，鴿群算法等。

1.2.1 烏賊算法。烏賊優(yōu)化算法(Cuttlefish Optimization Algorithm，COA)由Adel Sabry Eesa等學(xué)者于2013年提出，靈感來(lái)源于海洋生物中烏賊，一種新型的仿生啟發(fā)式優(yōu)化算法，也是一種概率型算法。烏賊算法有著收斂速度快和時(shí)間短的優(yōu)點(diǎn)，但缺點(diǎn)是收斂精度不高。烏賊算法是一種新型的啟發(fā)式仿生智能優(yōu)化算法，非常適合用于動(dòng)態(tài)實(shí)時(shí)變化的路徑規(guī)劃問(wèn)題。舒緯偉等[10]針對(duì)無(wú)人機(jī)路徑規(guī)劃問(wèn)題，提出了一種基于烏賊算法求解問(wèn)題。烏賊算法與經(jīng)典的智能算法相比，其更收斂速度更快。

1.2.2 果蠅算法。果蠅優(yōu)化算法(Fruit Fly Optimization Algorith，F(xiàn)FOA)由潘文超[11]于2011年提出，該算法的設(shè)計(jì)思路來(lái)源于自然界中果蠅的覓食行為，通過(guò)模擬果蠅的嗅覺(jué)和味覺(jué)的捕食過(guò)程盡快地找到目標(biāo)點(diǎn)。果蠅算法是一種基于果蠅的覓食行為模擬出的尋找全局最優(yōu)解的迭代搜索方法，因?yàn)樵撍惴ㄓ兄菀讓?shí)現(xiàn)、設(shè)定參數(shù)少等特點(diǎn)受到了許多學(xué)者的青睞；然而基本的果蠅算法有著易于早熟、全局和局部尋優(yōu)不平衡、解決多元復(fù)雜問(wèn)題時(shí)會(huì)陷入局部最優(yōu)等問(wèn)題，許多學(xué)者將其用于三維路徑規(guī)劃時(shí)都會(huì)將其改進(jìn)。根據(jù)以上幾種算法的探討，表1把這幾種算法的優(yōu)缺點(diǎn)，更新機(jī)制，適用問(wèn)題等進(jìn)行了歸納整理。

表1 算法對(duì)比

2.結(jié)論

隨著對(duì)無(wú)人機(jī)路徑規(guī)劃算法研究的深入，需要明白在空中實(shí)時(shí)變化的動(dòng)態(tài)環(huán)境下，如何選擇合適的無(wú)人機(jī)路徑規(guī)劃智能算法及其實(shí)現(xiàn)，是完成無(wú)人機(jī)配送路徑問(wèn)題迫切需要解決的問(wèn)題。蟻群算法在其概念是立體的較為接近三維的路徑規(guī)劃問(wèn)題，但對(duì)存儲(chǔ)空間的要求較高；遺傳算法在路徑規(guī)劃方面的應(yīng)用非常廣泛，但由于無(wú)人機(jī)在飛行時(shí)的動(dòng)態(tài)路徑是不確定的，增加了算法的編碼難度。因此，為有效利用各種算法各自的優(yōu)勢(shì)，混合算法將成為航跡規(guī)劃的發(fā)展趨勢(shì)。上述的新型仿生智能算法目前研究的學(xué)者還不多，也可能是未來(lái)的發(fā)展趨勢(shì)。目前無(wú)人機(jī)三維航跡規(guī)劃能在單一約束下快速生成航跡，但在復(fù)雜環(huán)境約束下缺少對(duì)最優(yōu)路徑的考慮，且無(wú)法同時(shí)兼顧復(fù)雜環(huán)境約束與無(wú)人機(jī)自身性能約束。

引用出處

[1]王翼虎,王思明.基于改進(jìn)粒子群算法的無(wú)人機(jī)路徑規(guī)劃[J].計(jì)算機(jī)工程與科學(xué),2020,42(9):1690-1696.

[2]李佳盛.基于改進(jìn)蟻群算法的旅行商路徑優(yōu)化問(wèn)題研究[J].中國(guó)物流與采購(gòu),2020,606(17):47-48.

[3]王宇,王文浩,徐凡,等.基于改進(jìn)蟻群算法的植保無(wú)人機(jī)路徑規(guī)劃方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2020,51(11):92,103-112.

[4]李霞,魏瑞軒,周軍,等.基于改進(jìn)遺傳算法的無(wú)人飛行器三維路徑規(guī)劃[J].西北工業(yè)大學(xué)學(xué)報(bào),2010,28(3):343-348.

[5]李世國(guó),蘇衛(wèi)華,郭鵬飛,等.基于改進(jìn)A~★算法的無(wú)人搜救全局路徑規(guī)劃研究[J].醫(yī)療衛(wèi)生裝備,2020,41(12):16-20.

[6]楊超杰,裴以建,劉朋.改進(jìn)粒子群算法的三維空間路徑規(guī)劃研究[J].計(jì)算機(jī)工程與應(yīng)用,2019,55(11):117-122.

[7]陳志軍,曾蒸.基于模糊神經(jīng)網(wǎng)絡(luò)和遺傳算法的機(jī)器人三維路徑規(guī)劃[J].重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2018,35(1):93-99.

[8]王剛,張方,嚴(yán)大亮,等.基于改進(jìn)蟻群算法的機(jī)器人三維路徑規(guī)劃[J].國(guó)外電子測(cè)量技術(shù),2020,39(11):1-6.

[9]王闖,董宏麗,谷星澍,等.改進(jìn)粒子群算法及其在航跡規(guī)劃中的應(yīng)用[J].控制工程,2019,26(8):1466-1471.

[10]舒緯偉,敬忠良,董鵬.基于烏賊算法的無(wú)人機(jī)航跡規(guī)劃[J].科學(xué)技術(shù)與工程,2017,17(2):120-125.

[11]潘文超.應(yīng)用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)進(jìn)行企業(yè)經(jīng)營(yíng)績(jī)效評(píng)估[J].太原理工大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版),2011,29(4):1-5.