基于改進(jìn)人工勢場法的無人船路徑規(guī)劃算法

劉　琨，張永輝，任　佳

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

?

基于改進(jìn)人工勢場法的無人船路徑規(guī)劃算法

劉琨，張永輝，任佳

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

摘要：提出了一種改進(jìn)的人工勢場法，用指數(shù)函數(shù)代替二次函數(shù)構(gòu)造勢場函數(shù)，降低了勢場強(qiáng)度的變化幅度，并在斥力勢場函數(shù)中增加無人船與目標(biāo)點(diǎn)的相對位置的一個因子，解決目標(biāo)不可達(dá)問題；同時設(shè)置勢場系數(shù)調(diào)整因子，引入2個判斷條件確定無人船是否陷入局部最小值，在此基礎(chǔ)上選擇相應(yīng)的勢場系數(shù)，從而跳出局部極小值點(diǎn).仿真結(jié)果證明了該方法的有效性.

關(guān)鍵詞：水面無人船； 人工勢場； 局部極小值點(diǎn)； 路徑規(guī)劃

水面無人船(Unmanned Surface Vehicle, USV)是一種能夠在海洋環(huán)境下自主航行，并完成各種任務(wù)的水面運(yùn)動平臺[1]，集船舶設(shè)計(jì)、人工智能、信息處理和運(yùn)動控制等專業(yè)技術(shù)為一體，研究內(nèi)容涉及自動駕駛、自主避障、規(guī)劃與導(dǎo)航和模式識別等多方面[2].水面無人船由于其靈活機(jī)動、造價低、環(huán)境適應(yīng)能力強(qiáng)等優(yōu)點(diǎn)，廣泛應(yīng)用于港口監(jiān)控、水質(zhì)采樣、水文勘察和海事搜救，為海洋發(fā)展和航運(yùn)發(fā)展提供了一種在危險情況下代替人工進(jìn)行作業(yè)的安全途徑[3].

無人船在復(fù)雜環(huán)境下具備自主航行的能力，首先需要解決路徑規(guī)劃問題，即找出一條從出發(fā)點(diǎn)到目標(biāo)點(diǎn)無人船安全航行路線.目前適用于無人船自主路徑規(guī)劃的方法有模擬退火算法[4]、人工勢場法[5]和模擬邏輯算法等[6].其中，人工勢場法相對于其他算法具有反應(yīng)快速、計(jì)算簡單以及實(shí)時性強(qiáng)等優(yōu)點(diǎn)，對算法加以改進(jìn)能在智能體路徑規(guī)劃任務(wù)中得到很好的應(yīng)用，但是傳統(tǒng)的人工勢場法存在局部極小值問題，易造成無人船無法及時躲避障礙.因此，文獻(xiàn)[7]提出一種帶記憶功能的“沿邊法”，通過沿著障礙物邊緣行走來逃離局部最小值點(diǎn)，但會造成路徑變長，不能實(shí)現(xiàn)最優(yōu)路徑；文獻(xiàn)[8]采用沿等勢線逃離和隨機(jī)逃離結(jié)合的方法跳出局部最小值點(diǎn)，但隨機(jī)性較高，缺乏全局指導(dǎo)性；文獻(xiàn)[9]采用入侵雜草法產(chǎn)生最優(yōu)子目的地，根據(jù)子目的地重新分配空間內(nèi)的引力勢，從而指引機(jī)器人擺脫局部最小值點(diǎn)，但過程較為繁瑣；文獻(xiàn)[10]利用人工勢場法的規(guī)劃結(jié)果作為先驗(yàn)知識，可提高算法的收斂速度，但容易出現(xiàn)早熟現(xiàn)象，且計(jì)算開銷較大，導(dǎo)致解決局部最小值問題的效率降低.

針對上述問題，筆者采用新的勢場函數(shù)模型，通過動態(tài)調(diào)整勢場函數(shù)系數(shù)，解決傳統(tǒng)人工勢場法中目標(biāo)不可達(dá)和局部最小值問題.

1場景描述

港口是水陸交通的集結(jié)點(diǎn)和樞紐，由于停靠的船舶以及來往船只較多，港口擁擠而復(fù)雜的環(huán)境使得無人船路徑規(guī)劃的難度加大.如圖1所示，以中國南海某一港口為例，設(shè)定A處為起點(diǎn)，B處為終點(diǎn)，要完成從A點(diǎn)到B點(diǎn)的路徑規(guī)劃，采用傳統(tǒng)人工勢場法的算法過程以及遇到的問題如下.

圖1　中國南海某港口

1) 無人船在A點(diǎn)受到的目標(biāo)點(diǎn)的引力勢場為Ua，通常引力勢場的一般形式如下

(1)

其中，X是無人船的當(dāng)前位置，Xg是目標(biāo)點(diǎn)的位置，k是引力勢場的增益系數(shù).

無人船在該點(diǎn)受到的引力Fa為引力勢場的梯度，方向指向目標(biāo)點(diǎn)，公式如下所示

Fa(X)=-▽Ua(X)=k(X-Xg)，

(2)

當(dāng)無人船離目標(biāo)點(diǎn)越近，受到的引力越小，反之越大，當(dāng)無人船到達(dá)目標(biāo)點(diǎn)時，引力為零.

無人船在A點(diǎn)受到障礙物的斥力勢場為Ur，公式如下

(3)

其中，Xo是障礙物的位置，m是斥力勢場的增益系數(shù)，ρ為障礙物的影響半徑.

相應(yīng)的，無人船受到的斥力為斥力勢場的負(fù)梯度，公式如下

(4)

當(dāng)無人船離障礙物越近，受到的斥力越大，反之越小.

無人船受到的合力為F，公式如下

F=Fr+Fa.

(5)

2)無人船在合力的作用下，躲避障礙，朝著目標(biāo)點(diǎn)移動，途徑A點(diǎn)、B點(diǎn)、C點(diǎn)，行動路徑如圖1所示，當(dāng)無人船進(jìn)入D區(qū)域時，無人船、目標(biāo)點(diǎn)和障礙物三者處于同一條直線上，且障礙物位于無人船與目標(biāo)點(diǎn)之間，目標(biāo)點(diǎn)對無人船的引力和障礙物對無人船的斥力的合力為零，無人船則陷入局部最小值點(diǎn)，在該局部小范圍內(nèi)反復(fù)移動而無法到達(dá)目的點(diǎn).

3)若在目標(biāo)E點(diǎn)附近存在較大的障礙物，同時無人船也處于障礙物的影響范圍內(nèi)，當(dāng)無人船向E點(diǎn)靠近時，受到的引力減小，同時也向障礙物靠近，則受到的斥力增大，引力相當(dāng)于斥力來說很小，最終也導(dǎo)致無人船無法到達(dá)目標(biāo)點(diǎn).

2改進(jìn)的人工勢場法

2.1改進(jìn)的勢場函數(shù)從以下幾個方面對傳統(tǒng)人工勢場法進(jìn)行改進(jìn)

1) 將對無人船的受力分析改為受勢場強(qiáng)度分析，使計(jì)算的復(fù)雜度降低，促進(jìn)時效性；

2) 大多數(shù)人工勢場的斥力勢場函數(shù)都是以無人船與障礙物的相對位置的倒數(shù)為自變量的二次函數(shù)，無人船小幅度地移動就能引起勢場強(qiáng)度大幅度的變化，即斥力場強(qiáng)度變化較快.而在實(shí)際應(yīng)用中，斥力場強(qiáng)度的數(shù)值變化過快會影響對運(yùn)動路徑的判斷，因此對斥力常量m的選擇要求較為苛刻，因此采用指數(shù)函數(shù)作為斥力勢場函數(shù)，其表達(dá)式如下

(6)

3)為了解決目標(biāo)不可達(dá)的問題，引入目標(biāo)點(diǎn)與無人船的相對位置，將原來的斥力場函數(shù)乘以一個因子(X-Xg)n，使得目標(biāo)點(diǎn)位置的斥力為零.改進(jìn)的斥力場函數(shù)為

(7)

4)為了防止無人船陷入局部最小值的困境，動態(tài)調(diào)整斥力場系數(shù).在計(jì)算下一步位置之前增加2個判斷條件：①無人船未到達(dá)目標(biāo)點(diǎn)(無人船與目標(biāo)點(diǎn)的距離不為零)；②無人船連續(xù)3步移動的距離小于步長).滿足以上2個條件則判斷無人船陷入局部最小值點(diǎn)，然后增大引力勢場系數(shù)或減小斥力勢場系數(shù)，變化值為3n(0.1

2.2改進(jìn)的路徑規(guī)劃無人船船身均勻安裝16個超聲波探頭，通過檢測無人船與障礙的相對位置來確定合力勢場，從而對無人船進(jìn)行路徑規(guī)劃，即利用合力勢場來確定無人船的運(yùn)動方向.

1) 超聲波探頭的角度

(8)

其中，N為超聲波探頭的個數(shù)，i為超聲波探頭的序號.

2)超聲波探頭的位置

(9)

其中，(x, y)是無人船的中心坐標(biāo)，r為無人船中心到超聲波探頭的距離，θi為第i個超聲波探頭的角度.

3)超聲波探頭的引力場

(10)

4)超聲波探頭的斥力場

(11)

5)超聲波探頭的合力勢場

U(XSi)=Uo(XSi)+Ug(XSi)，

(12)

Umin=min(U(XSi))i=0，1，…，N-1，

(13)

找出受最小合力勢的超聲波探頭序號I，求得該超聲波探頭的角度β，

(14)

(6)無人船下一時刻的位置為

(15)

其中，(xk，yk)為無人船當(dāng)前時刻的位置，λ為無人船移動的步長.

3仿真實(shí)驗(yàn)與結(jié)果分析

設(shè)定無人船的航行范圍為一大小為30 m×30 m的區(qū)域，在該區(qū)域隨機(jī)布置多個障礙物并測得其位置坐標(biāo)分別為(8,10)，(10,10)，(12,10)，(18,20)，(20,15)，(22,25)，(25,20)，設(shè)定無人船的初始位置X為(5,5)，目標(biāo)點(diǎn)的位置Xg為(25,25)，引力場系數(shù)k=10-4，斥力勢場系數(shù)m=1，步長為0.1 m，用Matlab進(jìn)行仿真.在簡單的環(huán)境中，當(dāng)障礙物與目標(biāo)點(diǎn)相鄰時，使用傳統(tǒng)人工勢場法的無人船的行動路徑如圖2所示，無人船無法到達(dá)目標(biāo)點(diǎn)；使用本文提出的改進(jìn)的人工勢場法，無人船的行動路徑如圖3所示，無人船能夠躲避障礙物，并且也能準(zhǔn)確地到達(dá)目的地.

當(dāng)無人船處于復(fù)雜環(huán)境中，即障礙物的數(shù)量增多，且位置改變時，障礙物的位置分別為(8,10)，(10,10)，(12,10)，(18,10)，(18,15)，(20,15)，(18,20)，(18,22)，(24,20)，(23,22)，采用傳統(tǒng)人工勢場法，仿真結(jié)果的無人船行動路徑如圖4所示.從圖5顯示的無人船的行動步數(shù)看出，無人船到達(dá)(16,18)坐標(biāo)點(diǎn)后，開始停滯不前，在小范圍內(nèi)往復(fù)移動，此時無人船陷入了局部最小值點(diǎn)的困境.

采用文獻(xiàn)[7]提出的算法，仿真結(jié)果的無人船行動路徑如圖6所示，無人船沿著障礙物的邊緣移動，跳出局部最小值點(diǎn)，圖7的行動步數(shù)顯示，經(jīng)過372步，無人船最終達(dá)到目標(biāo)點(diǎn).

采用本文提出的改進(jìn)的人工勢場法，通過合理布局超聲波探頭對無人船進(jìn)行路徑規(guī)劃，并在無人船陷入局部最小值時及時對斥力勢場系數(shù)進(jìn)行調(diào)整，將原系數(shù)修改為0.5，使此刻障礙物對無人船的斥力減小，仿真結(jié)果的無人船行動路徑如圖8所示，無人船的移動步數(shù)如圖9所示，經(jīng)過337步，無人船到達(dá)目標(biāo)點(diǎn).

通過實(shí)驗(yàn)可以看出，在復(fù)雜環(huán)境中，本文提出的改進(jìn)的人工勢場算法對障礙物有一定的規(guī)避能力.從規(guī)劃的路徑來看，無人船避開了所有障礙物，并且跳出了所遇到的局部最小值點(diǎn)，準(zhǔn)確地到達(dá)目標(biāo)點(diǎn).通過比較圖8與圖6，圖9與圖7，本文算法的規(guī)劃速度明顯快于文獻(xiàn)[7]的算法規(guī)劃速度，且路徑長度更短，更滿足路徑規(guī)劃的實(shí)時性要求.

4小結(jié)

針對傳統(tǒng)的人工勢場法存在的主要缺陷，即目標(biāo)不可達(dá)和局部極小值點(diǎn)問題提出了一種改進(jìn)算法，由于傳統(tǒng)勢場函數(shù)數(shù)值變化過快容易導(dǎo)致錯誤的路徑規(guī)劃，采用指數(shù)形式的勢力場函數(shù)，并且增加無人船與目標(biāo)點(diǎn)的相對位置的因子解決目標(biāo)不可達(dá)的問題；采用合理布局超聲波探頭進(jìn)行路徑規(guī)劃的方法，動態(tài)調(diào)整勢力場系數(shù)，從而快速跳出局部最小值.仿真實(shí)驗(yàn)結(jié)果顯示，采用本文算法在復(fù)雜環(huán)境中，無人船能躲避障礙，逃離局部最小值點(diǎn)，準(zhǔn)確到達(dá)目標(biāo)點(diǎn)，且路徑平滑，滿足USV實(shí)時路徑規(guī)劃的要求.

參考文獻(xiàn)：

[1] 李家良. 水面無人艇發(fā)展與應(yīng)用[J]. 火力與指揮控制,2012,37(6):203-207.

[2] 張樹凱. 無人船艇的發(fā)展及展望[J]. 航海技術(shù),2015,38(9):29-36.

[3] 熊亞洲, 張曉杰, 馮海濤，等. 一種面向多任務(wù)應(yīng)用的無人水面艇[J]. 船舶工程,2012，34(1):16-19.

[4] 鞏敦衛(wèi), 曾現(xiàn)峰, 張勇. 基于改進(jìn)模擬退火算法的機(jī)器人全局路徑規(guī)劃[J]. 系統(tǒng)仿真學(xué)報,2013,25(3):480-483.

[5] 于振中, 閆繼紅, 趙杰, 等. 改進(jìn)人工勢場法的移動機(jī)器人路徑規(guī)劃[J]. 哈爾濱工業(yè)大學(xué)學(xué)報,2011,43(1):50-55.

[6] 李擎, 張超, 韓彩衛(wèi), 等. 動態(tài)環(huán)境下基于模糊邏輯算法的移動機(jī)器人路徑規(guī)劃[J]. 中南大學(xué)學(xué)報(自然科學(xué)版),2013,44(2):104-108.

[7] Huang Y, Hu H, Liu X. Obstacles avoidance of artificial potential field method with memory function in complex environment: proceedings of the 8th World Congress on Intelligent Control and Automation, Jinan, July 7-9, 2010[C]. [S.l.]: IEEE,2010.

[8] 單寶明, 周培培. 基于改進(jìn)人工勢場法的機(jī)器人路徑規(guī)劃研究[J]. 信息技術(shù),2014,1(4)：170-173.

[9] 李海峰, 馬斌, 陳浩男, 等. 基于人工勢場法與入侵雜草法路徑規(guī)劃研究[J]. 控制工程,2015,22(1):38-44.

[10] 王芳, 李昆鵬, 袁明新. 一種人工勢場導(dǎo)向的蟻群路徑規(guī)劃算法[J]. 計(jì)算機(jī)科學(xué),2014,41(11A):47-50.

[11] Melinggui A, Merzouki R, Mbede J B, et al. A novel approach to integrate artificial field and fuzzy logic into a common framework for robots autonomous navigation [J]. Journal of Systems and Control Engineering,2014,228(10):787-801.

[12] Kim M H, Heo J H, Wei Y L, et al. A path planning algorithm using artificial potential field based on probability map: proceedings of the 8th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI), Incheon, November 23-26, 2011[C]. [S.l.]:IEEE,2011.

[13] Chiang H T, Malone N, Lesser K, et al. Path-guided artificial potential fields with stochastic reachable sets for motion planning in highly dynamic environments: proceedings of the 2015 International Conference on Robotics and Automation(ICRA), Washington, May 26-30, 2015[C]. [S.l.]:IEEE,2015.

收稿日期：2015-12-09

基金項(xiàng)目：海南省高等學(xué)?？茖W(xué)研究項(xiàng)目(Hnky2015ZD—6)；國家國際科技合作專項(xiàng)(2015DFR10510)；國家自然科學(xué)基金(61562018)

作者簡介：劉琨(1989-)，男，陜西西安人，海南大學(xué)2013級碩士研究生，研究方向：嵌入式智能系統(tǒng)與工程，E-mail：liukun-7@hotmail.com 通信作者： 張永輝(1974-)，男，山東寧津人，博士，教授，研究方向：嵌入式系統(tǒng)、智能檢測技術(shù)，E-mail:zhyhemail@126.com

文章編號：1004-1729(2016)02-0099-06

中圖分類號：TP 18

文獻(xiàn)標(biāo)志碼：ADOl：10.15886/j.cnki.hdxbzkb.2016.0016

Path Planning Algorithm for Unmanned Surface Vehicle Based on an Improved Artificial Potential Field Method

Liu Kun, Zhang Yonghui, Ren Jia

(College of Information Science and Technology, Hainan University, Haikou 573228, China)

Abstract：In the study, an improved artificial potential field method was proposed. The quadratic function was replaced by an exponential function to construct the potential field function, which reduces the change rate of the potential field intensity. A factor of the distance between the USV in the current position and the destination was added into the potential field function, which can solve the problem that the USV can not reach the goal when the obstacles are close to the goal. Additionally, according to different conditions, several potential field coefficient regulate factors were set and two judgment conditions were introduced to determine whether unmanned ship was involved in local minimum point, and on which the accordingly field coefficients were selected to solve the problem of local minimum point. The experimental results suggested that the proposed method was effective.

Keywords：unmanned ship; artificial potential field; local minimum point; path planning