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

0 引 言

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

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

1 基于人工勢(shì)場(chǎng)的路徑規(guī)劃

1.1 傳統(tǒng)的人工勢(shì)場(chǎng)介紹

人工勢(shì)場(chǎng)將機(jī)器人視為質(zhì)點(diǎn)，存在于該勢(shì)場(chǎng)的機(jī)器人同時(shí)受到斥力和引力的作用[8]。當(dāng)機(jī)器人距離障礙物越近時(shí)，受到的斥力就越大；反之，如果機(jī)器人距離障礙物較遠(yuǎn)時(shí)，機(jī)器人與目標(biāo)之間的引力起主導(dǎo)作用，并且該引力大小與距離呈正相關(guān)。參考文獻(xiàn)[9]，將人工勢(shì)場(chǎng)表示為如下的形式：

Utotal=Urep+Uatt

(1)

式中:Utotal、Urep和Uatt分別為總勢(shì)場(chǎng)、引力場(chǎng)和斥力場(chǎng)。轉(zhuǎn)化為力的形式如下：

Ftotal=Frep+Fatt

(2)

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

(3)

(4)

根據(jù)人工勢(shì)場(chǎng)的理論，障礙物和目標(biāo)點(diǎn)對(duì)機(jī)器人分別表現(xiàn)出斥力與引力的作用。如果障礙物與機(jī)器人之間的距離大于ρ0，引力場(chǎng)的作用表現(xiàn)為零；如果障礙物與目標(biāo)點(diǎn)距離很小時(shí)，在機(jī)器人逐漸靠近目標(biāo)的過程中，表現(xiàn)出來的引力則會(huì)逐漸變小，斥力則會(huì)逐漸變大。這個(gè)時(shí)候，如果機(jī)器人可能出現(xiàn)在障礙物附近徘徊的情況，而無法到達(dá)目標(biāo)。根據(jù)勢(shì)場(chǎng)理論可知，隨著障礙物數(shù)目的增大，存在這種不可達(dá)的概率也越大。

1.2 改進(jìn)的人工勢(shì)場(chǎng)

經(jīng)過以上分析可知，傳統(tǒng)的勢(shì)場(chǎng)法具有對(duì)于處于障礙物附近的目標(biāo)，存在不可達(dá)的情況[10-11]，這是因?yàn)樵撜系K物附件的目標(biāo)點(diǎn)不能滿足式(1)的最小值。為了解決該問題，本文定義了如下函數(shù)表達(dá)式：

(5)

式中：ρ(Xr,Xgoal)表示目標(biāo)點(diǎn)和機(jī)器人兩者間的距離大小，ρ(Xr,Xobs)表示ρ(Xr,Xgoal)的最小值。如果出現(xiàn)機(jī)器人無法到達(dá)目標(biāo)時(shí)，通過式(5)可獲得改進(jìn)后斥力的表示形式，如公式所示：

(6)

式中：

(7)

(8)

單位向量a的方向?yàn)橛烧系K物指向機(jī)器人，單位向量b的方向與向量a相反。當(dāng)n=0時(shí)，由式(5)變化為如下函數(shù)：

(9)

改進(jìn)的人工勢(shì)場(chǎng)通過引入目標(biāo)點(diǎn)和機(jī)器人兩者間距離上的指數(shù)形式，對(duì)傳統(tǒng)的勢(shì)場(chǎng)函數(shù)表達(dá)式進(jìn)行改進(jìn)，從而對(duì)機(jī)器人無法達(dá)到目標(biāo)情況下的障礙物的斥力進(jìn)行描述，消除機(jī)器人在路徑規(guī)劃上的奇異點(diǎn)。改進(jìn)的人工勢(shì)場(chǎng)解決了機(jī)器人在路徑規(guī)劃上不可達(dá)的問題，但是通過該方法找到的路徑規(guī)劃有時(shí)候不只一條，那么應(yīng)該選擇哪條路徑進(jìn)行移動(dòng)，這時(shí)候需要對(duì)多條可達(dá)路徑進(jìn)行尋優(yōu)。

2 基于量子遺傳算法的路徑尋優(yōu)

針對(duì)改進(jìn)的人工勢(shì)場(chǎng)得到多條路徑規(guī)劃后，下面通過量子遺傳算法對(duì)多條可達(dá)的路徑進(jìn)行尋優(yōu)。這一節(jié)在傳統(tǒng)的量子遺傳算法的基礎(chǔ)上進(jìn)行了擴(kuò)展，建立了適合于本文場(chǎng)景下的尋優(yōu)方法。首先對(duì)量子遺傳算法中的量子比特編碼進(jìn)行介紹，然后提出了通過對(duì)量子門中的旋轉(zhuǎn)操作進(jìn)行調(diào)整來縮短算法收斂時(shí)間的方法，最后通過路徑代價(jià)和安全性作為評(píng)價(jià)標(biāo)準(zhǔn)，建立路徑規(guī)劃上的適應(yīng)度函數(shù)，從而進(jìn)行路徑的尋優(yōu)。

2.1 量子比特編碼介紹

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

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

(10)

式中：α、β代表相應(yīng)狀態(tài)出現(xiàn)概率的兩個(gè)復(fù)數(shù)，且：

(11)

2.2 對(duì)量子遺傳算法的改進(jìn)

根據(jù)量子計(jì)算可知，已知的量子態(tài)是由量子門進(jìn)行矩陣轉(zhuǎn)換的形式來完成轉(zhuǎn)換[12]。量子門的對(duì)應(yīng)旋轉(zhuǎn)角表示了染色體的變異處理，從而有效地縮短了運(yùn)算的收斂時(shí)間。下面對(duì)量子門中的旋轉(zhuǎn)操作進(jìn)行調(diào)整：

(12)

則

(13)

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

(14)

θi=s(αi,βi)與Δθi對(duì)應(yīng)表示旋轉(zhuǎn)操作的指向與角度數(shù)值，后者的值域?yàn)閇0.1π,0.005π]。

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

表1 旋轉(zhuǎn)角調(diào)整策略

2.3 構(gòu)建適應(yīng)度函數(shù)

對(duì)于改進(jìn)的人工勢(shì)場(chǎng)得到的多條路徑規(guī)劃來說，路徑代價(jià)與安全性是評(píng)價(jià)路徑優(yōu)劣的兩個(gè)重要標(biāo)準(zhǔn)。在路徑尋優(yōu)時(shí)，本文根據(jù)下述函數(shù)作為適應(yīng)度函數(shù)：

(15)

(16)

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

(17)

式中：L表示路徑點(diǎn)與目標(biāo)點(diǎn)之間的線段距離數(shù)值。由u值大小來確定對(duì)應(yīng)路徑選擇的合理與否。

(18)

式中：q表示路徑中存在的障礙物總數(shù)目。式(18)的數(shù)值表示了對(duì)應(yīng)路徑點(diǎn)上的安全性。

(19)

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

2.4 路徑規(guī)劃尋優(yōu)過程

根據(jù)以上提出的改進(jìn)的量子遺傳算法和適應(yīng)度函數(shù)，這一節(jié)介紹基于量子遺傳算法對(duì)改進(jìn)的人工勢(shì)場(chǎng)中得到的多個(gè)路徑規(guī)劃進(jìn)行尋優(yōu)的具體過程。具體步驟為：

步驟1利用改進(jìn)的人工勢(shì)場(chǎng)進(jìn)行初始化種群：

步驟3用上述的評(píng)價(jià)函數(shù)，準(zhǔn)確評(píng)價(jià)種群內(nèi)的全部個(gè)體。在獲取最優(yōu)解之后，取此時(shí)的目標(biāo)值與之對(duì)比。若出現(xiàn)目標(biāo)值小于最優(yōu)解的情況，取此時(shí)的最優(yōu)解當(dāng)做下次迭代操作時(shí)的目標(biāo)值大小，重復(fù)進(jìn)行上述操作；若出現(xiàn)目標(biāo)值大于最優(yōu)解的情況，進(jìn)行下次迭代時(shí)，目標(biāo)值依然恒定。

步驟4依據(jù)自適應(yīng)原則，使用旋轉(zhuǎn)門調(diào)整方法，對(duì)P(t)進(jìn)行下一輪的操作。

步驟5進(jìn)行停止條件判斷，如果條件實(shí)現(xiàn)，停止運(yùn)算，輸出結(jié)果，如果條件未滿足，繼續(xù)計(jì)算。

步驟6取t=t+1，繼續(xù)轉(zhuǎn)入步驟2，繼續(xù)計(jì)算。

3 仿真實(shí)驗(yàn)

針對(duì)本文提出的基于改進(jìn)的人工勢(shì)場(chǎng)進(jìn)行移動(dòng)機(jī)器人的路徑規(guī)劃方法，本節(jié)從兩個(gè)方面進(jìn)行實(shí)驗(yàn)驗(yàn)證分析：1) 對(duì)解決機(jī)器人在前往障礙物附近的目標(biāo)時(shí)的路徑不可達(dá)問題上的有效性；2) 通過與量子遺傳算法、遺傳算法進(jìn)行對(duì)比，驗(yàn)證本文改進(jìn)的算法在機(jī)器人路徑規(guī)劃尋優(yōu)上的優(yōu)勢(shì)。

實(shí)驗(yàn)一：當(dāng)目標(biāo)機(jī)器人在存在障礙物的區(qū)域內(nèi)行進(jìn)時(shí)，將會(huì)出現(xiàn)在附件徘徊的情況，無法達(dá)到目標(biāo)。這種狀況下，是由于傳統(tǒng)的人工勢(shì)場(chǎng)本身的局限性，致使機(jī)器人出現(xiàn)不能到達(dá)障礙物附件的目標(biāo)的問題，如圖1所示。

圖1 傳統(tǒng)人工勢(shì)場(chǎng)的不可達(dá)情況

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

圖2 勢(shì)場(chǎng)改進(jìn)后的效果圖

實(shí)驗(yàn)二：對(duì)于基于改進(jìn)的人工勢(shì)場(chǎng)得到的路徑規(guī)劃，將本文改進(jìn)的量子遺傳算法分別與量子遺傳算法、遺傳算法進(jìn)行對(duì)比。分別從算法性能和優(yōu)化能力兩個(gè)方面進(jìn)行實(shí)驗(yàn)。

其中，三種算法在解決移動(dòng)機(jī)器人的路徑規(guī)劃方案上的優(yōu)化問題上，具體表現(xiàn)出來的性能詳見表2。

表2 計(jì)算性能比較

另外，對(duì)于給定的規(guī)劃路徑，三種不同算法對(duì)于路徑的優(yōu)化能力見圖3，其中，虛線代表GA的適應(yīng)度，實(shí)線代表QGA的適應(yīng)度，點(diǎn)虛線代表本文算法的適應(yīng)度?？梢钥闯?，本文提出的改進(jìn)的算法具有較高的尋優(yōu)速度和能力，一般在20代左右收斂到最優(yōu)解附近。

圖3 三種算法的優(yōu)化能力比較

綜上所述，本文提出的改進(jìn)的量子遺傳算法一般的量子遺傳算法和遺傳算法比較可知，本文方法在尋找改進(jìn)人工勢(shì)場(chǎng)上的機(jī)器人路徑規(guī)劃時(shí)，具有較好的運(yùn)算性能和優(yōu)化能力。

4 結(jié) 語

對(duì)于移動(dòng)機(jī)器人的路徑規(guī)劃問題，本文在全面分析傳統(tǒng)的人工勢(shì)場(chǎng)法具備的缺點(diǎn)和劣勢(shì)的基礎(chǔ)上，提出了改進(jìn)的人工勢(shì)場(chǎng)來平衡障礙物的斥力、消除了奇異值點(diǎn)，使機(jī)器人可以到達(dá)障礙物附近的目標(biāo)點(diǎn)。然后針對(duì)改進(jìn)的人工勢(shì)場(chǎng)得到的多個(gè)路徑規(guī)劃，通過改進(jìn)的量子遺傳算法從路徑代價(jià)與安全性兩方面對(duì)路徑進(jìn)行尋優(yōu)。經(jīng)過實(shí)驗(yàn)可知，該方法具備有效性和可行性。

[1] 張浩杰, 龔建偉, 姜巖, 等. 基于變維度狀態(tài)空間的增量啟發(fā)式路徑規(guī)劃方法研究[J]. 自動(dòng)化學(xué)報(bào), 2013,39(10):1602- 1610.

[2] 陸萍, 董虎勝, 鐘寶江. 協(xié)同進(jìn)化粒子群滾動(dòng)優(yōu)化的機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)測(cè)量與控制, 2013, 21(11): 3128- 3130.

[3] 張殿富, 劉福. 基于人工勢(shì)場(chǎng)法的路徑規(guī)劃方法研究及展望[J]. 機(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] 歐陽鑫玉, 楊曙光. 基于勢(shì)場(chǎng)柵格法的移動(dòng)機(jī)器人避障路徑規(guī)劃[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] 高強(qiáng), 宋雨, 呂東澔, 等. 多移動(dòng)機(jī)器人路徑規(guī)劃仿真研究[J]. 計(jì)算機(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] 吳慧超, 羅元, 周前能, 等. 時(shí)效優(yōu)先的輪式機(jī)器人編隊(duì)避障策略[J]. 信息與控制, 2017, 46(2): 211- 217.

[11] 潘桂彬, 潘豐, 劉國(guó)棟. 基于改進(jìn)混合蛙跳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用, 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.