基于人工勢場和量子遺傳算法的移動機器人路徑規劃方法

侯 翔(四川文理學院智能制造學院 四川 達州 635000)

0 引 言

移動機器人是一種在特定空間內自行組織、運行與路徑規劃的智能機器人，其中路徑規劃是機器人學和智能技術中重要的部分[1]。目前，移動機器人路徑規劃的主要方法包括：滾動路徑規劃法[2]、人工勢場法[3-4]、遺傳算法[5]等。Khatib最先提出人工勢場(Artificial Potential Field)理論，通過把機器人所處的環境看作是理想化的人造力場，來解決機器人在環境中的路徑規劃問題。另外，有學者提出通過柵格方法[6]來代表地圖中的不同地形，從而實現了在對全局區域上的機器人路徑規劃，并取得較好的效果。隨著遺傳算法理論的提出，這種通過模擬自然界中物種進化的方式來搜索最優解的方法被引入到機器人路徑規劃的問題上，但是該理論存在收斂效率低下的弊端。隨著量子力學理論[7]的不斷發展，利用量子的重疊與牽連原理使得量子計算具有很強的功能，但它具有容易陷入局部最優的缺點。目前的研究無法解決移動機器人在前往障礙物附近的目標時的路徑規劃的問題。

本文在現有人工勢場的基礎上進行改進，提出一種用于解決機器人在前往障礙物附近的目標時的路徑不可達的問題。本文方法包括兩個方面：首先，在設定的環境內通過引入指數因子的形式來優化勢場函數表達式，從而平衡障礙物的斥力、消除了奇異值點，使機器人可以正確地到達目標點。針對得到的路徑軌跡，利用量子遺傳算法對最優或次優的路徑規劃進行選擇。通過仿真實驗表明，該方法解決了障礙物附近目標不可達問題，有效地提高了路徑規劃的性能。

1 基于人工勢場的路徑規劃

1.1 傳統的人工勢場介紹

人工勢場將機器人視為質點，存在于該勢場的機器人同時受到斥力和引力的作用[8]。當機器人距離障礙物越近時，受到的斥力就越大；反之，如果機器人距離障礙物較遠時，機器人與目標之間的引力起主導作用，并且該引力大小與距離呈正相關。參考文獻[9]，將人工勢場表示為如下的形式：

Utotal=Urep+Uatt

(1)

式中:Utotal、Urep和Uatt分別為總勢場、引力場和斥力場。轉化為力的形式如下：

Ftotal=Frep+Fatt

(2)

式中：Ftotal是合力；Frep是斥力；Fatt是引力，式(2)中：

(3)

(4)

根據人工勢場的理論，障礙物和目標點對機器人分別表現出斥力與引力的作用。如果障礙物與機器人之間的距離大于ρ0，引力場的作用表現為零；如果障礙物與目標點距離很小時，在機器人逐漸靠近目標的過程中，表現出來的引力則會逐漸變小，斥力則會逐漸變大。這個時候，如果機器人可能出現在障礙物附近徘徊的情況，而無法到達目標。根據勢場理論可知，隨著障礙物數目的增大，存在這種不可達的概率也越大。

1.2 改進的人工勢場

經過以上分析可知，傳統的勢場法具有對于處于障礙物附近的目標，存在不可達的情況[10-11]，這是因為該障礙物附件的目標點不能滿足式(1)的最小值。為了解決該問題，本文定義了如下函數表達式：

(5)

式中：ρ(Xr,Xgoal)表示目標點和機器人兩者間的距離大小，ρ(Xr,Xobs)表示ρ(Xr,Xgoal)的最小值。如果出現機器人無法到達目標時，通過式(5)可獲得改進后斥力的表示形式，如公式所示：

(6)

式中：

(7)

(8)

單位向量a的方向為由障礙物指向機器人，單位向量b的方向與向量a相反。當n=0時，由式(5)變化為如下函數：

(9)

改進的人工勢場通過引入目標點和機器人兩者間距離上的指數形式，對傳統的勢場函數表達式進行改進，從而對機器人無法達到目標情況下的障礙物的斥力進行描述，消除機器人在路徑規劃上的奇異點。改進的人工勢場解決了機器人在路徑規劃上不可達的問題，但是通過該方法找到的路徑規劃有時候不只一條，那么應該選擇哪條路徑進行移動，這時候需要對多條可達路徑進行尋優。

2 基于量子遺傳算法的路徑尋優

針對改進的人工勢場得到多條路徑規劃后，下面通過量子遺傳算法對多條可達的路徑進行尋優。這一節在傳統的量子遺傳算法的基礎上進行了擴展，建立了適合于本文場景下的尋優方法。首先對量子遺傳算法中的量子比特編碼進行介紹，然后提出了通過對量子門中的旋轉操作進行調整來縮短算法收斂時間的方法，最后通過路徑代價和安全性作為評價標準，建立路徑規劃上的適應度函數，從而進行路徑的尋優。

2.1 量子比特編碼介紹

根據量子遺傳算法理論，基本的信息元素以量子位的形式表示，量子位是進行量子化處理的基本單元。該單位的所處形態用0或1來代表，形式如公式所示：

|φ〉=α|0〉+β|1〉

(10)

式中：α、β代表相應狀態出現概率的兩個復數，且：

(11)

2.2 對量子遺傳算法的改進

根據量子計算可知，已知的量子態是由量子門進行矩陣轉換的形式來完成轉換[12]。量子門的對應旋轉角表示了染色體的變異處理，從而有效地縮短了運算的收斂時間。下面對量子門中的旋轉操作進行調整：

(12)

則

(13)

θi=s(αi,βi)Δθi

(14)

θi=s(αi,βi)與Δθi對應表示旋轉操作的指向與角度數值，后者的值域為[0.1π,0.005π]。

本文通過調整旋轉角度，從自適應的角度對傳統的量子遺傳算法進行了改進，見表1。此策略方法依據個體此時對應的測量值和目標值的適應度，查看滿足的條件來確定下一步的操作，測量值和目標值分別用f(xi)與f(bi)來表示。若滿足關系式(f(xi)-f(bi))/f(bi)小于給定的閾值時，采取降低δ值的方法來提高收斂速度，縮短運算時間；否則，就應采用增大δ值的方法，避免局部尋優現象的出現。

表1 旋轉角調整策略

2.3 構建適應度函數

對于改進的人工勢場得到的多條路徑規劃來說，路徑代價與安全性是評價路徑優劣的兩個重要標準。在路徑尋優時，本文根據下述函數作為適應度函數：

(15)

(16)

式中：i與j分別為染色體與路徑點的次序數，β、γ表示調整系數值大小，其中β+γ=1，兩者之間數值的選取表示了路徑正確性與安全性之間的權衡，一般情況下將β的值設置為大于γ，并根據系統對安全性的需求來提高對γ的賦值。

(17)

式中：L表示路徑點與目標點之間的線段距離數值。由u值大小來確定對應路徑選擇的合理與否。

(18)

式中：q表示路徑中存在的障礙物總數目。式(18)的數值表示了對應路徑點上的安全性。

(19)

式(19)的數值表示障礙影響參數，數值越大說明障礙對機器人的路徑的阻礙越大。

2.4 路徑規劃尋優過程

根據以上提出的改進的量子遺傳算法和適應度函數，這一節介紹基于量子遺傳算法對改進的人工勢場中得到的多個路徑規劃進行尋優的具體過程。具體步驟為：

步驟1利用改進的人工勢場進行初始化種群：

步驟3用上述的評價函數，準確評價種群內的全部個體。在獲取最優解之后，取此時的目標值與之對比。若出現目標值小于最優解的情況，取此時的最優解當做下次迭代操作時的目標值大小，重復進行上述操作；若出現目標值大于最優解的情況，進行下次迭代時，目標值依然恒定。

步驟4依據自適應原則，使用旋轉門調整方法，對P(t)進行下一輪的操作。

步驟5進行停止條件判斷，如果條件實現，停止運算，輸出結果，如果條件未滿足，繼續計算。

步驟6取t=t+1，繼續轉入步驟2，繼續計算。

3 仿真實驗

針對本文提出的基于改進的人工勢場進行移動機器人的路徑規劃方法，本節從兩個方面進行實驗驗證分析：1) 對解決機器人在前往障礙物附近的目標時的路徑不可達問題上的有效性；2) 通過與量子遺傳算法、遺傳算法進行對比，驗證本文改進的算法在機器人路徑規劃尋優上的優勢。

實驗一：當目標機器人在存在障礙物的區域內行進時，將會出現在附件徘徊的情況，無法達到目標。這種狀況下，是由于傳統的人工勢場本身的局限性，致使機器人出現不能到達障礙物附件的目標的問題，如圖1所示。

圖1 傳統人工勢場的不可達情況

當人工勢場經過改進之后，區域計算時引入了ρ(Xr,Xgoal)因子參數，并且設定n=2。圖2表示通過改進后人工勢場進行路徑規劃的效果圖。從圖中可以看出，移動機器人能夠順利到達目標區域，從而說明改進的人工勢場可以有效解決移動機器人對于障礙物附件目標的不可達的問題。

圖2 勢場改進后的效果圖

實驗二：對于基于改進的人工勢場得到的路徑規劃，將本文改進的量子遺傳算法分別與量子遺傳算法、遺傳算法進行對比。分別從算法性能和優化能力兩個方面進行實驗。

其中，三種算法在解決移動機器人的路徑規劃方案上的優化問題上，具體表現出來的性能詳見表2。

表2 計算性能比較

另外，對于給定的規劃路徑，三種不同算法對于路徑的優化能力見圖3，其中，虛線代表GA的適應度，實線代表QGA的適應度，點虛線代表本文算法的適應度。可以看出，本文提出的改進的算法具有較高的尋優速度和能力，一般在20代左右收斂到最優解附近。

圖3 三種算法的優化能力比較

綜上所述，本文提出的改進的量子遺傳算法一般的量子遺傳算法和遺傳算法比較可知，本文方法在尋找改進人工勢場上的機器人路徑規劃時，具有較好的運算性能和優化能力。

4 結 語

對于移動機器人的路徑規劃問題，本文在全面分析傳統的人工勢場法具備的缺點和劣勢的基礎上，提出了改進的人工勢場來平衡障礙物的斥力、消除了奇異值點，使機器人可以到達障礙物附近的目標點。然后針對改進的人工勢場得到的多個路徑規劃，通過改進的量子遺傳算法從路徑代價與安全性兩方面對路徑進行尋優。經過實驗可知，該方法具備有效性和可行性。

[1] 張浩杰, 龔建偉, 姜巖, 等. 基于變維度狀態空間的增量啟發式路徑規劃方法研究[J]. 自動化學報, 2013,39(10):1602- 1610.

[2] 陸萍, 董虎勝, 鐘寶江. 協同進化粒子群滾動優化的機器人路徑規劃[J]. 計算機測量與控制, 2013, 21(11): 3128- 3130.

[3] 張殿富, 劉福. 基于人工勢場法的路徑規劃方法研究及展望[J]. 機器人, 2013, 35(6): 88- 95.

[4] Han D, Nie H, Chen J, et al. Dynamic obstacle avoidance for manipulators using distance calculation and discrete detection[J]. Robotics and Computer-Integrated Manufacturing, 2018, 49: 98- 104.

[5] Roberge V, Tarbouchi M, Labonté G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. Industrial Informatics, IEEE Transactions on, 2013, 9(1): 132- 141.

[6] 歐陽鑫玉, 楊曙光. 基于勢場柵格法的移動機器人避障路徑規劃[J]. 控制工程, 2014, 21(1): 134- 137.

[7] He B, Liu G, Yan J, et al. A UAV Route Planning Method Based on Voronoi Diagram and Quantum Genetic Algorithm[J]. Electronics Optics & Control, 2013, 11(2): 194- 203.

[8] 高強, 宋雨, 呂東澔, 等. 多移動機器人路徑規劃仿真研究[J]. 計算機仿真, 2014, 31(7): 325- 329.

[9] Li G, Tamura Y, Yamashita A, et al. Effective improved artificial potential field-based regression search method for autonomous mobile robot path planning[J]. International Journal of Mechatronics and Automation, 2013, 3(3): 141- 170.

[10] 吳慧超, 羅元, 周前能, 等. 時效優先的輪式機器人編隊避障策略[J]. 信息與控制, 2017, 46(2): 211- 217.

[11] 潘桂彬, 潘豐, 劉國棟. 基于改進混合蛙跳算法的移動機器人路徑規劃[J]. 計算機應用, 2014, 34(10): 2850- 2853.

[12] Du K L, Swamy M N S. Bacterial Foraging Algorithm[M]//Search and Optimization by Metaheuristics. Springer International Publishing, 2016: 217- 225.