楊凱 龍佳 馬雪燕 余中政

摘 ?要： 針對傳統(tǒng)人工勢場法進(jìn)行移動機(jī)器人路徑規(guī)劃過程中常出現(xiàn)目標(biāo)不可達(dá)、局部極小值等問題，提出一種改進(jìn)人工勢場的移動機(jī)器人路徑規(guī)劃新方法。將移動機(jī)器人和目標(biāo)點(diǎn)之間的歐氏距離融入到斥力函數(shù)中，并將障礙物產(chǎn)生的斥力分解為兩個不同方向的斥力分量，引導(dǎo)移動機(jī)器人到達(dá)目標(biāo)點(diǎn);根據(jù)移動機(jī)器人的位置、障礙物的最大影響距離以及移動機(jī)器人與目標(biāo)點(diǎn)之間的歐氏距離建立數(shù)學(xué)關(guān)系，尋找虛擬目標(biāo)點(diǎn)，以解決移動機(jī)器人在移動過程中受到的合力為零時出現(xiàn)的局部極小值問題。仿真及實(shí)驗(yàn)結(jié)果表明，改進(jìn)人工勢場算法能夠使移動機(jī)器人順利繞過障礙物到達(dá)目標(biāo)點(diǎn)。

關(guān)鍵詞： 移動機(jī)器人; 路徑規(guī)劃; 改進(jìn)人工勢場算法; 斥力函數(shù); 局部極小值; 虛擬目標(biāo)點(diǎn)

中圖分類號： TN99?34; TP242 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）07?0141?05

Research on mobile robot path planning method

based on improved artificial potential field

YANG Kai1， 2， LONG Jia1， MA Xueyan1， YU Zhongzheng1

（1. Post?doctoral Scientific Research Station， General Hospital of Eastern War Zone， Nanjing 210000， China;

2. Department of Aviation Machinery， Chinese people′s Liberation Army Aviation School， Beijing 101123， China）

Abstract： Since the destination unreachable and local minimum value occurs in the process of mobile robot path planning based on traditional artificial potential field， a new path planning method for mobile robot with improved artificial potential field is proposed in this paper. The Euclidean distance between the mobile robot and the target point is introduced into the repulsion function， and the repulsion generated by the obstacle is decomposed into two repulsion components in different directions to guide the mobile robot arriving at the target point. According to the position of the mobile robot， the maximum influence distance of the obstacle and the Euclidean distance between the mobile robot and the target point， the mathematical relationship is established to find the virtual target point to solve the problem of local minimum value when the resultant force received by the mobile robot is zero during the movement to target point. The simulation and experimental results show that， with the improved artificial potential field method， the mobile robot can successfully bypass the obstacles and arrive at the target point.

Keywords： mobile robot; path planning; improved artificial potential field method; repulsive function; local minimum value; virtual target point

0 ?引 ?言

隨著無人駕駛技術(shù)的不斷發(fā)展，移動機(jī)器人的路徑規(guī)劃和自主避障已廣泛應(yīng)用在危險任務(wù)的執(zhí)行、爆破、巡航等方面，成為國內(nèi)外學(xué)者研究的熱點(diǎn)[1?3]。移動機(jī)器人路徑規(guī)劃是指通過在移動機(jī)器人上安裝多種傳感器探測周圍的環(huán)境信息，規(guī)劃出一條滿足動力學(xué)要求、穩(wěn)定性以及舒適性等評價標(biāo)準(zhǔn)的優(yōu)化路線，方便對移動機(jī)器人進(jìn)行跟蹤。目前路徑規(guī)劃的主要方法包括神經(jīng)網(wǎng)絡(luò)算法[4]、向量直方圖算法[5]、遺傳算法[6]、人工勢場法（Artificial Potential Field Algorithm，APFA）[7]等。人工勢場法具有計(jì)算量小、規(guī)劃時間短、便于實(shí)現(xiàn)底層控制等特點(diǎn)，在移動機(jī)器人的路徑規(guī)劃中廣泛應(yīng)用[8]。然而，當(dāng)機(jī)器人所處環(huán)境復(fù)雜多變時，傳統(tǒng)的人工勢場法容易出現(xiàn)局部極小值問題，導(dǎo)致移動機(jī)器人無法正常移動至目標(biāo)點(diǎn)。因此，科研人員提出許多改進(jìn)的人工勢場法。文獻(xiàn)[9]根據(jù)障礙物的距離遠(yuǎn)近，采用不同的引力和斥力方向計(jì)算方法，并縮小障礙物的范圍以解決局部極小值問題。文獻(xiàn)[10]利用概率論建立了一個勢場模型，根據(jù)累積分布函數(shù)的特征和障礙物的邊界條件推導(dǎo)出勢場模型的解析式，并利用概率密度函數(shù)求出勢場的表達(dá)式，以解決目標(biāo)不可達(dá)問題。文獻(xiàn)[11]在斥力函數(shù)中引入逃逸力，以解決局部極小值問題，并利用遺傳算法得到更加平滑的規(guī)劃路徑。文獻(xiàn)[12]將滾動窗口理論和人工勢場相結(jié)合，提高機(jī)器人躲避障礙物的能力，使機(jī)器人能夠精準(zhǔn)移動至目標(biāo)點(diǎn)。本文提出一種新的改進(jìn)人工勢場的移動機(jī)器人路徑規(guī)劃方法，以期實(shí)現(xiàn)移動機(jī)器人靈活地避開障礙物，精準(zhǔn)到達(dá)目標(biāo)點(diǎn)。

1 ?基于虛擬目標(biāo)點(diǎn)的改進(jìn)人工勢場路徑規(guī)劃算法

1.1 ?人工勢場法及其問題分析

人工勢場法（APFA）是由Khatib于1986年提出[13]，它是解決路徑規(guī)劃問題最有效的方法之一。人工勢場法將移動機(jī)器人所在的環(huán)境模擬成物理學(xué)中的“場”，稱為虛擬勢場。該虛擬勢場包含引力場和斥力場，引力場由目標(biāo)點(diǎn)生成，斥力場由環(huán)境中的障礙物生成。移動機(jī)器人借助于引力場的作用，逐漸向目標(biāo)點(diǎn)靠近;與此同時，斥力場作用于移動機(jī)器人上，使其巧妙地繞過障礙物。移動機(jī)器人的人工勢場受力分析如圖1所示。

在人工勢場法中，用[X]表示移動機(jī)器人當(dāng)前所處的位置，[Xg]表示目標(biāo)點(diǎn)所處的位置，[Xb]表示障礙物所的處位置。

引力勢函數(shù)可表示為：

[Ua=12?ka?d2g] （1）

式中：[ka]表示引力勢場常數(shù);[dg]表示移動機(jī)器人當(dāng)前所處位置[X]和目標(biāo)點(diǎn)所處位置[Xg]之間的歐氏距離。

引力可以表示為引力勢函數(shù)的負(fù)梯度：

[Fa=-grad（Ua）=-ka?dg] （2）

斥力勢函數(shù)可表示為：

[Ur=12?kr?1db-1dm2， ? ?db≤dm0， ? ?db>dm] （3）

式中：[kr]表示斥力勢場常數(shù);[db]表示移動機(jī)器人當(dāng)前所處位置[X]和障礙物所處位置[Xb]之間的歐氏距離;[dm]表示障礙物能夠影響的最大距離。當(dāng)移動機(jī)器人和障礙物之間的距離[db<][dm]時，障礙物產(chǎn)生的斥力場才能作用于移動機(jī)器人。

斥力可以表示為斥力勢函數(shù)的負(fù)梯度：

[Fr=kr?1db-1dm?1d2b， ? ?db≤dm0， ? ?db>dm] （4）

移動機(jī)器人受到的合力為：

[F=Fa+Fr] （5）

利用人工勢場法進(jìn)行移動機(jī)器人路徑規(guī)劃時通常存在如下問題：

1） 目標(biāo)點(diǎn)和障礙物之間的距離較近，且目標(biāo)點(diǎn)處在障礙物的影響距離內(nèi)，當(dāng)移動機(jī)器人快要移動到目標(biāo)點(diǎn)時，其所受的斥力可能大于引力，此時移動機(jī)器人會不斷在目標(biāo)點(diǎn)周圍徘徊，陷入局部極小值的陷阱中，無法抵達(dá)目標(biāo)點(diǎn)。

2） 目標(biāo)點(diǎn)、障礙物和移動機(jī)器人處于一條直線上，移動機(jī)器人在向目標(biāo)點(diǎn)移動的過程中所受的引力和斥力也在一條直線上并且方向相反，如果此時引力和斥力的合力為零，那么移動機(jī)器人就無法判斷接下來的前進(jìn)方向，它就會誤認(rèn)為已經(jīng)到達(dá)目標(biāo)點(diǎn)，進(jìn)而停止移動。

1.2 ?斥力函數(shù)的改進(jìn)

為了解決人工勢場法中的目標(biāo)不可達(dá)問題，將移動機(jī)器人當(dāng)前所處位置[X]和目標(biāo)點(diǎn)所處位置[Xg]之間的歐氏距離[dg]融入到斥力函數(shù)中，如式（6）所示：

[Ur=12?kr?（1db-d0-1dm-d0）2dtg， ? ?db≤dm0， ? ?db>dm] （6）

式中：[t]表示移動機(jī)器人當(dāng)前所處位置和目標(biāo)點(diǎn)所處位置之間的歐氏距離對斥力的影響系數(shù);[d0]表示障礙物的安全距離。當(dāng)移動機(jī)器人越靠近目標(biāo)點(diǎn)時，斥力函數(shù)值越接近0。

將由障礙物產(chǎn)生的作用于移動機(jī)器人的斥力分解為兩個分量，分別是由障礙物指向移動機(jī)器人方向的斥力分量[Fr1]，以及由移動機(jī)器人指向目標(biāo)點(diǎn)方向的斥力分量[Fr2]。移動機(jī)器人的改進(jìn)人工勢場受力分析如圖2所示。

引力[Fa]和斥力[Fr]可以分別表示為引力勢函數(shù)和斥力勢函數(shù)的負(fù)梯度：

[Fa=-kadg] （7）

[Fr=Fr1+Fr2， ? ?db≤dm0， ? ?db>dm] （8）

斥力[Fr]的分量[Fr1]和[Fr2]分別表示如下：

[Fr1=kr?1db-d0-1dm-d0?1（db-d0）2?dtg] （9）

[Fr2=12?t?kr?1db-d0-1dm-d02?dt-1g] （10）

當(dāng)移動機(jī)器人逐漸靠近障礙物并受其斥力影響時，斥力分量[Fr1]會給移動機(jī)器人施加一定的阻力，使其向遠(yuǎn)離障礙物的方向移動，斥力分量[Fr2]和引力[Fa]則引導(dǎo)移動機(jī)器人向目標(biāo)點(diǎn)的方向移動。

1.3 ?虛擬目標(biāo)點(diǎn)設(shè)置

如果目標(biāo)點(diǎn)、障礙物和移動機(jī)器人處于一條直線上，則移動機(jī)器人所受的引力和斥力也處于一條直線上，當(dāng)移動機(jī)器人在向目標(biāo)點(diǎn)移動的過程中受到的合力為零時，它就會誤認(rèn)為此時已經(jīng)到達(dá)目標(biāo)點(diǎn)，進(jìn)而停止移動。

1.3.1 ?局部極小值問題檢測

由于移動機(jī)器人的移動環(huán)境是未知的，移動機(jī)器人在向目標(biāo)點(diǎn)移動的過程中受到的合力為零時的情況出現(xiàn)的概率很小，最常見的是移動機(jī)器人在某一點(diǎn)附近震蕩走動，即移動機(jī)器人在以該點(diǎn)為圓心的圓內(nèi)徘徊，陷入局部極小值陷阱。因此，根據(jù)距離檢測的方式來判斷移動機(jī)器人是否陷入局部極小值陷阱。在圖3中，假設(shè)以局部極小值點(diǎn)為圓心的圓半徑是[R]，在[t]時刻，移動機(jī)器人所處的位置為[Xt（xt，yt）]。經(jīng)過[Δt]時間后，移動機(jī)器人移動到新的位置[Xt+Δt（xt+Δt，yt+Δt）]，則[Xt]與[Xt+Δt]之間的距離為：

[d=（xt-xt+Δt）2+（yt-yt+Δt）2] （11）

如果[d

1.3.2 ?虛擬目標(biāo)點(diǎn)的設(shè)置

[2] 張嘉琦.基于移動子目標(biāo)的復(fù)合式路徑規(guī)劃算法[J].中國公路學(xué)報，2017，30（11）：138?146.

[3] 王美玲，潘允輝.基于GIS與約束條件下的最優(yōu)路徑規(guī)劃研究[J].北京理工大學(xué)學(xué)報，2016，36（8）：851?856.

[4] ZENG Nianyin， ZHANG Hong， CHEN Yanping， et al. Path planning for intelligent robot based on switching local evolutionary PSO algorithm [J]. Assembly automation， 2016， 36（2）： 120?126.

[5] 陳志軍，曾蒸.基于模糊神經(jīng)網(wǎng)絡(luò)和遺傳算法的機(jī)器人三維路徑規(guī)劃[J].重慶師范大學(xué)學(xué)報（自然科學(xué)版），2018（1）：99?105.

[6] SONG B， WANG Z， SHENG L. A new genetic algorithm approach to smooth path planning for mobile robots [J]. Assembly automation， 2016， 36（2）： 138?145.

[7] 劉志強(qiáng)，朱偉達(dá)，倪婕，等.基于新型人工勢場法的車輛避障路徑規(guī)劃研究方法[J].科學(xué)技術(shù)與工程，2017，17（16）：310?315.

[8] 徐飛.基于改進(jìn)人工勢場法的機(jī)器人避障及路徑規(guī)劃研究[J].計(jì)算機(jī)科學(xué)，2016，43（12）：293?296.

[9] 溫素芳，郭光耀.基于改進(jìn)人工勢場法的移動機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（10）：2818?2822.

[10] ZHANG Yewei， LI Hui， HAN Xuezheng. A heuristic path planning method based on the potential field using probability theory [J]. Journal of computational & theoretical nanoscience， 2016， 13（11）： 8088?8100.

[11] 趙東輝，李偉莉.改進(jìn)人工勢場的機(jī)器人路徑規(guī)劃[J].機(jī)械設(shè)計(jì)與制造，2017（7）：252?255.

[12] 史進(jìn)，董瑤，白振東，等.移動機(jī)器人動態(tài)路徑規(guī)劃方法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2017，37（11）：3119?3123.

[13] SUN J， TANG J， LAO S. Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm [J]. IEEE access， 2017， 5： 18382?18390.