賓海茵 吳超龍 趙琳

摘? 要：結(jié)合移動(dòng)機(jī)器人的實(shí)際應(yīng)用場(chǎng)景，針對(duì)常規(guī)算法規(guī)劃出的路徑存在折點(diǎn)多、轉(zhuǎn)彎角度過(guò)大、與障礙物距離較小、搜索的路徑較長(zhǎng)等問(wèn)題，對(duì)在柵格地圖下混合全局路徑規(guī)劃與局部路徑規(guī)劃算法進(jìn)行了研究，采用人工勢(shì)場(chǎng)算法與蟻群算法混合，為移動(dòng)機(jī)器人規(guī)劃出全局最優(yōu)路徑，同時(shí)實(shí)時(shí)躲避局部障礙物。經(jīng)過(guò)仿真測(cè)試，移動(dòng)機(jī)器人可以根據(jù)全局路徑規(guī)劃的路徑得到最優(yōu)的整體路徑，通過(guò)局部路徑規(guī)劃算法避開(kāi)局部區(qū)域的障礙物，使移動(dòng)機(jī)器人能夠從起點(diǎn)平穩(wěn)無(wú)碰撞地行駛至目標(biāo)點(diǎn)。

關(guān)鍵詞：智能算法；機(jī)器人路徑規(guī)劃；移動(dòng)機(jī)器人；避障機(jī)器人

中圖分類(lèi)號(hào)：TP242? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2023）07-0157-04

Abstract： Aiming at the problems of many inflection points， too large turning angle， small distance from obstacles， and long search path in the path planned by conventional algorithms， this paper combines with the practical application scenario of mobile robots， studies the hybrid global path planning and local path planning algorithms under grid maps， uses the hybrid artificial potential field algorithm and ant colony algorithm to plan the global optimal path for mobile robots， and avoids local obstacles at the same time. Through the simulation test， the mobile robot can obtain the optimal overall path according to the path planned by the global path planning， and avoid the obstacles in the local area through the local path planning algorithm， so that the mobile robot can travel without collision from the starting point to the target point smoothly.

Keywords： intelligent algorithm; robot path planning; mobile robot; obstacle avoidance robot

0? 引? 言

移動(dòng)機(jī)器人的路徑規(guī)劃是機(jī)器人學(xué)的重要研究領(lǐng)域，也是人工智能和機(jī)器人學(xué)的一個(gè)非常重要的結(jié)合。不管移動(dòng)機(jī)器人的應(yīng)用如何，在工作過(guò)程中往往需要沿著工作區(qū)域的最佳路徑或非最佳路徑進(jìn)行（如最小路徑長(zhǎng)度、最合適路徑等）。路徑規(guī)劃問(wèn)題可以看作是一種受制約的優(yōu)化問(wèn)題，它需要完成路徑規(guī)劃，自我定位和避障操作，路徑算法的改進(jìn)實(shí)質(zhì)上也是滿(mǎn)足一定約束條件下的改進(jìn)問(wèn)題。路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航中最重要的任務(wù)之一，通過(guò)路徑規(guī)劃移動(dòng)機(jī)器人在無(wú)人控制的情況下，可以對(duì)環(huán)境已“清楚”會(huì)出現(xiàn)的障礙物以及可能出現(xiàn)的障礙物進(jìn)行分析和避讓?zhuān)丛谟姓系K物的環(huán)境中尋找從開(kāi)始狀態(tài)到目標(biāo)狀態(tài)不發(fā)生碰撞的路徑，從而進(jìn)行自主行駛完成相應(yīng)任務(wù)。機(jī)器人面對(duì)復(fù)雜多變的室外環(huán)境，通過(guò)對(duì)算法的優(yōu)化改進(jìn)來(lái)提高機(jī)器人的性能，路徑規(guī)劃的實(shí)時(shí)避障性、路徑平滑性、規(guī)劃有效性就成為了路徑規(guī)劃算法的核心研究?jī)?nèi)容。

因此將對(duì)移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)進(jìn)行分析和研究，結(jié)合機(jī)器人的實(shí)際應(yīng)用，考慮機(jī)器人在跟隨路徑時(shí)的適應(yīng)性，為移動(dòng)機(jī)器人規(guī)劃最優(yōu)路徑，探討了人工勢(shì)場(chǎng)算法和蟻群算法的融合算法，利用蟻群算法進(jìn)行全局路徑規(guī)劃，再利用人工勢(shì)場(chǎng)算法進(jìn)行局部路徑規(guī)劃，并針對(duì)人工勢(shì)場(chǎng)算法和蟻群算法可能會(huì)出現(xiàn)的問(wèn)題，進(jìn)行改進(jìn)和優(yōu)化，使移動(dòng)機(jī)器人獲得一條可以在實(shí)際應(yīng)用中繞過(guò)障礙物安全平穩(wěn)到達(dá)目標(biāo)點(diǎn)的最優(yōu)平滑路徑。

1? 國(guó)內(nèi)外發(fā)展現(xiàn)狀

隨著科技的發(fā)展，在移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域，國(guó)內(nèi)外許多研究學(xué)者進(jìn)行了深入研究和改進(jìn)，取得了許多成果。根據(jù)機(jī)器人對(duì)環(huán)境信息的理解程度，路徑規(guī)劃問(wèn)題可分為環(huán)境信息完全已知的全局路徑規(guī)劃和環(huán)境信息不完全了解或部分不了解的局部路徑規(guī)劃兩類(lèi)[1]。其中，全局路徑規(guī)劃主要有拓?fù)浞?、柵格法、可視圖法等。局部路徑規(guī)劃方法主要有人工勢(shì)場(chǎng)法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法等。目前，路徑規(guī)劃技術(shù)雖然取得了相當(dāng)大的成果，但方法之間有優(yōu)缺點(diǎn)[2]，任何一種方法都不能適用于任何環(huán)境。雖然我國(guó)對(duì)移動(dòng)機(jī)器人的起步較晚，但是在國(guó)家的大力支持下，我國(guó)對(duì)移動(dòng)機(jī)器人技術(shù)日漸成熟[3]。

根據(jù)路徑算法原理特點(diǎn)進(jìn)行劃分，目前常用的路徑規(guī)劃方法可以分為傳統(tǒng)算法和智能仿生算法兩類(lèi)。傳統(tǒng)的人工勢(shì)場(chǎng)算法常有局部最小值不易脫離和無(wú)法到達(dá)目標(biāo)點(diǎn)的問(wèn)題，為解決這些問(wèn)題，張琪等[4]針對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法在避障路徑規(guī)劃存在的缺陷，增加逃逸子因數(shù)，在Krogh算法的基礎(chǔ)上對(duì)人工勢(shì)場(chǎng)進(jìn)行改進(jìn)并提出了新的人工勢(shì)場(chǎng)函數(shù)，修復(fù)了無(wú)法到達(dá)障礙物附件上的目標(biāo)點(diǎn)的問(wèn)題，并驗(yàn)證了改進(jìn)人工勢(shì)場(chǎng)算法的有效性。

隨著環(huán)境的復(fù)雜性和空間性的增加，對(duì)移動(dòng)機(jī)器人的需求越來(lái)越大，傳統(tǒng)的算法結(jié)合已經(jīng)沒(méi)辦法滿(mǎn)足需求，它的實(shí)用性下降，計(jì)算量增大，由此，機(jī)器人領(lǐng)域的學(xué)者提出了一系列智能優(yōu)化算法。例如，神經(jīng)網(wǎng)絡(luò)與遺傳算法的結(jié)合、粒子群與遺傳算法的結(jié)合、粒子群與灰狼算法結(jié)合。李真等[5]針對(duì)粒子群算法易陷入局部最優(yōu)的缺點(diǎn)，提出了最差改進(jìn)策略和最優(yōu)粒子擾動(dòng)策略，并將灰狼算法的優(yōu)勢(shì)引入粒子群算法進(jìn)一步提高算法的搜索能力，由此提高了粒子群的多樣性以及最優(yōu)粒子進(jìn)行擾動(dòng)使粒子群跳出局部最優(yōu)。

隨著近年來(lái)人工智能技術(shù)的興起。傳統(tǒng)與智能路徑規(guī)劃算法的日益成熟推動(dòng)了兩者的結(jié)合，例如柵格法與遺傳算法、粒子群算法等的融合、人工勢(shì)場(chǎng)法與人工神經(jīng)網(wǎng)絡(luò)（ANN）、蟻群算法以及遺傳算法等的融合。例如，段建民等[6]通過(guò)引入填平勢(shì)場(chǎng)使勢(shì)場(chǎng)函數(shù)跳出局部極小值，并利用人工勢(shì)場(chǎng)算法對(duì)遺傳算法規(guī)劃路徑進(jìn)行優(yōu)化，在改進(jìn)的基礎(chǔ)上尋求全局最優(yōu)解的策略。李航宇等[7]采用了柵格法環(huán)境建模，對(duì)遺傳算法上引入刪減及增添算子，采用了動(dòng)態(tài)自適應(yīng)策略，對(duì)算法的運(yùn)算效率有了很大的提高。

2? 機(jī)器人路徑規(guī)劃

在機(jī)器人領(lǐng)域的研究，移動(dòng)機(jī)器人路徑規(guī)劃已經(jīng)取得了大量的成果，但是對(duì)于某些實(shí)際場(chǎng)景仍然有局限性。移動(dòng)機(jī)器人在不同的應(yīng)用領(lǐng)域有不同的要求和問(wèn)題[8]，因此，在關(guān)注具體需求和實(shí)際應(yīng)用場(chǎng)景的同時(shí)，可以保證全局路徑規(guī)劃的有效性和及時(shí)性，優(yōu)化拐角的路徑、提高平滑性、確保移動(dòng)機(jī)器人安全繞過(guò)障礙到達(dá)終點(diǎn)，能夠得到對(duì)工作環(huán)境更合適的最佳路徑規(guī)劃路線。

2.1? 柵格法繪制地圖

移動(dòng)機(jī)器一般使用柵格法構(gòu)建空間環(huán)境，實(shí)質(zhì)上就是對(duì)機(jī)器人工作空間進(jìn)行單元分割?？臻g環(huán)境通常使用四叉樹(shù)或八叉樹(shù)來(lái)表示，并通過(guò)規(guī)劃算法進(jìn)行路徑搜索。柵格數(shù)據(jù)就是將分割后的各單元網(wǎng)格賦予相應(yīng)的屬性值來(lái)象征實(shí)體，使場(chǎng)景所有物進(jìn)行二值化，矩陣中的1代表障礙物，對(duì)應(yīng)黑色柵格，0代表可移動(dòng)空間，對(duì)應(yīng)白色柵格。如圖1所示。

2.2? 蟻群算法規(guī)劃路徑

2.2.1? 蟻群算法原理

蟻群算法由Marco Dorigo等提出的一種用于尋找優(yōu)化路徑的概率型算法，他們?cè)谘芯坑^察螞蟻覓食過(guò)程中，發(fā)現(xiàn)蟻群的協(xié)作上表現(xiàn)出一些智能的行為[2]。從圖2可以看出，假設(shè)螞蟻從蟻巢即起點(diǎn)A向食物源B行走，第一波螞蟻行走方向是隨機(jī)的，蟻群的選擇有三條路徑，剛開(kāi)始三條路徑上的螞蟻數(shù)量差不多。螞蟻尋到食物立即將部分食物立即返回運(yùn)輸，由于路徑C距離較短，螞蟻很快能在起終點(diǎn)往返，重復(fù)頻率快，螞蟻在單位時(shí)間內(nèi)來(lái)回移動(dòng)的次數(shù)越多，它們留下的信息素就越多，更是吸引更多的螞蟻選擇C路徑，因此越來(lái)越多的螞蟻聚集到最短路徑上，得到一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。

2.2.2? 蟻群算法的仿真

通過(guò)圖3中的蟻群算法仿真可以看出，可以在柵格地圖中尋到一條最優(yōu)路徑，并且可以避讓障礙物，因此將引用蟻群算法為機(jī)器人規(guī)劃全局路徑。但是應(yīng)用到實(shí)際生活中，仍存在一些拐角過(guò)多、路線不夠平滑的缺點(diǎn)。

2.3? 人工勢(shì)場(chǎng)法規(guī)劃路徑

人工勢(shì)場(chǎng)法由Khatib提出的一種虛擬力法，其基本內(nèi)容是將移動(dòng)機(jī)器人所在環(huán)境抽象化，即周?chē)h(huán)境下的機(jī)器人運(yùn)動(dòng)抽象為一種人造的引力勢(shì)場(chǎng)運(yùn)動(dòng)，重力電位場(chǎng)在環(huán)境中的目標(biāo)點(diǎn)周?chē)纬?，斥力電位?chǎng)在障礙物上形成。目標(biāo)點(diǎn)對(duì)機(jī)器人產(chǎn)生引力，障礙物對(duì)機(jī)器人產(chǎn)生斥力，兩者合力控制機(jī)器人的動(dòng)作[9]。多用于局部路徑規(guī)劃。其優(yōu)點(diǎn)是計(jì)算速度快，能在環(huán)境中實(shí)時(shí)避障，路徑平滑且有一定的魯棒性。從圖4可以看到就相較于蟻群算法圖3規(guī)劃出的路徑，人工勢(shì)場(chǎng)規(guī)劃的路徑更平滑，使實(shí)際應(yīng)用中機(jī)器人的行駛更安全。從圖4人工勢(shì)場(chǎng)算法規(guī)劃的仿真可以觀察到，所規(guī)劃的路徑平滑無(wú)碰撞到達(dá)終點(diǎn)，這符合最初在實(shí)際情況下機(jī)器人需要考慮的問(wèn)題，為改善算法問(wèn)題，這里引入人工勢(shì)場(chǎng)算法，結(jié)合人工勢(shì)場(chǎng)的作用機(jī)理，融合算法的特點(diǎn)來(lái)為機(jī)器人進(jìn)行局部路徑規(guī)劃。

2.4? 人工勢(shì)場(chǎng)-蟻群融合算法規(guī)劃路徑

通過(guò)對(duì)蟻群和人工勢(shì)場(chǎng)算法的仿真，可以觀察到，蟻群算法的路徑在經(jīng)過(guò)拐角的時(shí)候緊貼障礙物，所規(guī)劃的路徑出現(xiàn)多處折點(diǎn)，在機(jī)器人的實(shí)際應(yīng)用中，需考慮機(jī)器人的尺寸和運(yùn)動(dòng)學(xué)以及動(dòng)力學(xué)的約束，否則容易與障礙物發(fā)生碰撞，且路徑的不平滑性，對(duì)于機(jī)器人而言，可能存在不易轉(zhuǎn)彎的困難，而多余的折點(diǎn)也是不必要出現(xiàn)的。通過(guò)人工勢(shì)場(chǎng)算法的仿真，雖然其路徑是一條平滑的路徑，但是由于機(jī)器人行進(jìn)的過(guò)程中只考慮最近的障礙物，面對(duì)復(fù)雜道路，可能使得規(guī)劃出的路徑不是最優(yōu)解。傳統(tǒng)人工勢(shì)場(chǎng)算法并不適用作全局路徑規(guī)劃，一般用作局部路徑規(guī)劃。

因此從機(jī)器人實(shí)際應(yīng)用的角度出發(fā)，結(jié)合實(shí)際考慮問(wèn)題，利用單一算法其特點(diǎn)，將人工勢(shì)場(chǎng)算法與蟻群算法混合，使用蟻群算法進(jìn)行全局路徑規(guī)劃，根據(jù)全局規(guī)劃路徑再使用人工勢(shì)場(chǎng)方法進(jìn)行局部路徑規(guī)劃。為在工作空間活動(dòng)的機(jī)器人設(shè)計(jì)最佳且平滑的路徑，使移動(dòng)機(jī)器人能平穩(wěn)從起始點(diǎn)到終點(diǎn)無(wú)碰撞且平滑的到達(dá)終點(diǎn)。

3? 融合算法路徑規(guī)劃仿真

3.1? 地圖構(gòu)建

仿真實(shí)驗(yàn)將利用MATLAB進(jìn)行路徑規(guī)劃算法仿真。其仿真環(huán)境為25×25的柵格地圖?？紤]到機(jī)器人的尺寸，為了更方便分析不同算法的不同路徑和最終混合的效果，更直接地觀察移動(dòng)機(jī)器人無(wú)碰撞行駛的過(guò)程，將人工勢(shì)場(chǎng)地圖的方格大小設(shè)為5，蟻群柵格地圖方格大小設(shè)為1，通過(guò)地圖的比例縮小，減少蟻群算法的計(jì)算量和收斂速度的同時(shí)兼顧解決全局路徑規(guī)劃與局部路徑規(guī)劃的主要問(wèn)題，此外，兩者地圖坐標(biāo)是可以相互對(duì)應(yīng)的，所規(guī)劃的路線可以通過(guò)坐標(biāo)的轉(zhuǎn)換在相同的空間地圖內(nèi)行駛。如圖5所示。

3.2? 單一算法規(guī)劃路徑仿真

使用蟻群算法規(guī)劃，得出如圖6中的規(guī)劃路徑，但其中機(jī)器人被看作一個(gè)質(zhì)點(diǎn)，路線緊貼障礙物，沒(méi)有考慮到機(jī)器人的尺寸。如果應(yīng)用到機(jī)器人上則會(huì)發(fā)生碰撞，且所規(guī)劃的路徑不平滑，這對(duì)機(jī)器人的移動(dòng)產(chǎn)生阻礙。

使用人工勢(shì)場(chǎng)算法規(guī)劃仿真，規(guī)劃出了一條平滑的路徑，但由于算法的每次檢測(cè)周期只考慮距離最近的障礙物，面對(duì)復(fù)雜的環(huán)境無(wú)法做出最佳策略，可能規(guī)劃出的對(duì)于全局路徑規(guī)劃不是最優(yōu)解的線路。

將勢(shì)場(chǎng)蟻群結(jié)合，可以解決上述問(wèn)題。使用蟻群算法進(jìn)行全局路徑規(guī)劃，將規(guī)劃的全局獲得的路徑傳送到人工勢(shì)場(chǎng)算法中，人工勢(shì)場(chǎng)算法就會(huì)沿著全局運(yùn)行移動(dòng)，分段式的行駛，逐漸靠近目標(biāo)點(diǎn)。

3.3? 兩種算法結(jié)合的仿真

圖7開(kāi)始對(duì)機(jī)器人移動(dòng)路徑進(jìn)行仿真實(shí)驗(yàn)，觀察全局路徑規(guī)劃的蟻群算法與對(duì)局部路徑規(guī)劃的人工勢(shì)場(chǎng)算法的結(jié)合效果。

相較于算法結(jié)合之前規(guī)劃出來(lái)的路徑，該仿真可以觀察到機(jī)器人更加安全的通過(guò)拐點(diǎn)并與障礙物保持安全的距離，避免移動(dòng)機(jī)器人和障礙物發(fā)生碰撞，增強(qiáng)了其平滑性，使機(jī)器人更平滑到達(dá)終點(diǎn)，規(guī)劃出工作空間的最優(yōu)路徑，使用更少的時(shí)間完成從起點(diǎn)到終點(diǎn)的移動(dòng)。在實(shí)際應(yīng)用中，機(jī)器人可以更安全平穩(wěn)的從起點(diǎn)向終點(diǎn)移動(dòng)，解決了算法出現(xiàn)多折角和不是最優(yōu)解的問(wèn)題。

4? 結(jié)? 論

移動(dòng)機(jī)器人在實(shí)際應(yīng)用中受很多復(fù)雜因素的影響，因此機(jī)器人在自主移動(dòng)中需要考慮的問(wèn)題有很多。為機(jī)器人更適應(yīng)環(huán)境，考慮到實(shí)際的應(yīng)用場(chǎng)景，以是否能安全通過(guò)拐角、路徑平滑性和最優(yōu)路徑的問(wèn)題展開(kāi)對(duì)路徑算法的研究，通過(guò)蟻群算法的全局與人工勢(shì)場(chǎng)法的局部路徑規(guī)劃結(jié)合，為機(jī)器人規(guī)劃出一條安全平穩(wěn)的路徑。通過(guò)仿真證明，經(jīng)過(guò)兩者的結(jié)合，所規(guī)劃的路徑可以更好讓機(jī)器人適應(yīng)工作環(huán)境并安全平穩(wěn)的從起點(diǎn)移動(dòng)到終點(diǎn)。

參考文獻(xiàn)：

[1] 劉自強(qiáng).無(wú)人駕駛低速電動(dòng)車(chē)的路徑規(guī)劃和控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) [D].成都：電子科技大學(xué)，2020.

[2] 吳保勝，郭宇，王發(fā)麟，等.基于改進(jìn)蟻群算法的線纜路徑規(guī)劃技術(shù)研究 [J].計(jì)算機(jī)工程與應(yīng)用，2018，54（10）：236-241.

[3] 孫凌宇，冷明，朱平，等.移動(dòng)機(jī)器人路徑規(guī)劃算法的研究 [J].井岡山大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，31（2）：56-59+64.

[4] 張琪，田甜，欒天宇，等.基于改進(jìn)人工勢(shì)場(chǎng)算法的無(wú)人船路徑規(guī)劃 [J].艦船科學(xué)技術(shù)，2022，44（9）：63-68+78.

[5] 李真，王帆，王冉珺.一種結(jié)合灰狼算法的粒子群優(yōu)化算法 [J].計(jì)算機(jī)測(cè)量與控制，2021，29（10）：217-222.

[6] 段建民，陳強(qiáng)龍.基于改進(jìn)人工勢(shì)場(chǎng)-遺傳算法的路徑規(guī)劃算法研究 [J].國(guó)外電子測(cè)量技術(shù)，2019，38（3）：19-24.

[7] 李航宇，郭曉利.考慮多因素的自適應(yīng)遺傳算法機(jī)器人路徑規(guī)劃 [J].制造業(yè)自動(dòng)化，2022，44（10）：76-78+95.

[8] 王梓強(qiáng)，胡曉光，李曉筱，等.移動(dòng)機(jī)器人全局路徑規(guī)劃算法綜述 [J].計(jì)算機(jī)科學(xué)，2021，48（10）：19-29.

[9] 郭銀景，劉琦，鮑建康，等.基于人工勢(shì)場(chǎng)法的AUV避障算法研究綜述 [J].計(jì)算機(jī)工程與應(yīng)用，2020，56（4）：16-23.

作者簡(jiǎn)介：賓海茵（2000—），女，漢族，廣西貴港人，本科在讀，研究方向：智能控制系統(tǒng)的設(shè)計(jì)；吳超龍（2000—），男，漢族，廣西貴港人，本科在讀，研究方向：智能控制系統(tǒng)的設(shè)計(jì)；趙琳（1981—），女，漢族，河北定州人，講師，碩士研究生，研究方向：通信技術(shù)、智能控制技術(shù)。