基于改進正余弦算法的機器人路徑規(guī)劃

馬瑩瑩，杜暖男

(1. 天津市機電工藝技師學(xué)院 信息傳媒系，天津 300350； 2. 天津海運職業(yè)學(xué)院 信息工程系，天津 300350)

0 引 言

機器人路徑規(guī)劃，簡稱RPP，旨在決策給定起終點間的最優(yōu)路徑，從而使得線路長度、機器人能耗等指標(biāo)達到最優(yōu)[1]。近年來，智能移動機器人獲得了廣泛應(yīng)用，業(yè)務(wù)場景包含智慧生產(chǎn)、貨物搬運、異常環(huán)境探測等[2]。因此，開發(fā)RPP問題的決策算法意義重大。

傳統(tǒng)RPP決策方法有視圖法、自由空間法以及人工勢場法等[3]。在各類實際工程場景中，以上算法逐步暴露出亟待改善的問題點。視圖法所求路徑棱角明顯，因而所得線路難以構(gòu)成全局最優(yōu)；自由空間法的計算復(fù)雜度很大，難以應(yīng)對復(fù)雜障礙空間的情況。近年來進化算法的發(fā)展為解決RPP問題提供了新思路，諸如遺傳、蟻群等算法均在此問題上獲得了成功應(yīng)用，但也存在些許不足。比如：遺傳算法生成線路容易包含障礙物在內(nèi)，使得結(jié)果容易違反約束；基本蟻群算法的搜索時間相對過長、容易停滯。顯而易見，上述缺陷使得進化算法求解RPP的效率較為低下。因此，有必要針對上述缺陷開發(fā)基于進化算法的高效RPP決策方法。

正余弦算法(sine cosine algorithm，SCA)是2016年由學(xué)者S. MIRJALILI[4]提出的一種新型進化算法。SCA算法具有架構(gòu)簡單、計算效率高等特點，且研究表明，SCA算法的整體搜索性能較螢火蟲算法、花朵授粉算法、粒子群算法等更具優(yōu)勢[5]。SCA算法在眾多經(jīng)典優(yōu)化問題上效果顯著，例如圖像分割、目標(biāo)跟蹤、電力系統(tǒng)調(diào)度等[6-8]。為此，筆者將該算法運用到RPP這一重要工程問題的求解。

SCA算法模擬了正余弦函數(shù)的震蕩特征，據(jù)此進行迭代搜索，同時其初始化過程采用隨機方法，這一定程度上限制了算法的表現(xiàn)性能，同時SCA的種群更新過程過度依賴于當(dāng)前已知最優(yōu)解，且不同解個體間缺乏強有力的信息交流，這弱化了算法后期的求解能力。為解決以上問題，筆者構(gòu)建的HSCA算法采用反學(xué)習(xí)初始化方法，用于產(chǎn)生優(yōu)質(zhì)初始解；在迭代環(huán)節(jié)中，該算法以優(yōu)化目標(biāo)為依據(jù)進行模因分組進而構(gòu)建多種群，并通過融合TLBO進化機制強化個體交流，力求增強算法的局部挖掘能力。另外，筆者將HSCA算法與Spline插值法相結(jié)合，力求在確保RPP問題路徑規(guī)劃精度的同時降低優(yōu)化難度，從而獲得高質(zhì)量的平滑路徑曲線。

1 機器人路徑規(guī)劃建模

1.1 環(huán)境模型

圖1給出了RPP的示意，起終點分別以正方形和三角形表示，障礙物用圓表示。

圖1 RPP示意Fig. 1 Schematic diagram of RPP

基于二維平面坐標(biāo)系，每個圓可表示為：

(x-a)2+(y-b)2=r2

(1)

式中：參數(shù)(a,b)為圓中心；r為半徑。

RPP要求確定一條由連接起點(x0,y0)和終點(xn+1,yn+1)的路徑H={(x0,y0),(x1,y1),…,(xn,yn),(xn+1,yn+1)}，從而使得決策目標(biāo)最優(yōu)。其中，(x1,y1),(x2,y2),…,(xn,yn)為待優(yōu)化的導(dǎo)航點坐標(biāo)。基于以上描述可知，導(dǎo)航點的數(shù)目n決定了當(dāng)前待優(yōu)化問題的維度。同時，直接將路徑點相連繪制的線路圖形棱角較為明顯。為此，筆者引入Spline方法構(gòu)造線路[9-10]。如圖2，算法所需優(yōu)化的坐標(biāo)點為采樣導(dǎo)航點，而插值導(dǎo)航點表示通過Spline方法得到的坐標(biāo)。

圖2 Spline插值示意Fig. 2 Schematic diagram of spline interpolation method

1.2 路徑評價函數(shù)

筆者在RPP模型以線路長度作為目標(biāo)函數(shù)，在線路評價函數(shù)構(gòu)建中引入懲罰函數(shù)法以解決線路避開障礙物這一約束：

(2)

(3)

式中：ω為懲罰系數(shù)，取值為正；K為障礙物總數(shù)；(ak,bk)為障礙物k的坐標(biāo)中心；rk為半徑；Vi,k∈[0,1]為當(dāng)前線路中第i個導(dǎo)航點(xi,yi)與第k個障礙物間避障約束值；Vi,k=0為滿足避障約束。基于此，評價函數(shù)L取值越小，線路長度越短且違反避障約束程度越小，該線路的質(zhì)量越優(yōu)。

2 SCA與TLBO算法

2.1 SCA算法

(4)

式中：d=1,…,D;i=1,…,N。

在表達式中，xi=(xi1,xi2,…,xiD)為第i個解的表達式，xid為xi第d維的取值，rand(0,1)為[0,1]上的隨機數(shù)。

在迭代過程中，針對解xi，迭代更新公式為：

(5)

式中：g為當(dāng)前迭代次數(shù)；x*為已知最好解；參數(shù)r2、r3和r4為隨機量，取值范圍設(shè)置為r2∈[0,2π]、r3∈[0,2]、r4∈[0,1]。控制參數(shù)r1定義為：

(6)

式中：a為常數(shù)；G為算法的最大迭代次數(shù)。

SCA算法流程為：

Step 1初始化：借助隨機方法生成初始種群。

Step 2目標(biāo)函數(shù)計算：計算每個解的目標(biāo)函數(shù)值。

Step 3確定最優(yōu)個體：將算法迭代至當(dāng)前階段所搜得的目標(biāo)函數(shù)值最小個體標(biāo)記為已知最優(yōu)解。

Step 4更新算法參數(shù)：更新系數(shù)r1、r2、r3和r4。

Step 5更新個體位置：依據(jù)式(5)生成子代種群。

Step 5終止判斷：若滿足終止條件，停止迭代并輸出最好解；否則轉(zhuǎn)Step 2。

2.2 TLBO算法

在TLBO算法中，個體更新包括 “教學(xué)階段”和“學(xué)習(xí)階段”兩部分[11]。

(7)

在學(xué)習(xí)階段，TLBO通過將候選解與其他解進行位置差分，并據(jù)此進行位位置更新，表達式為：

(8)

TLBO算法流程為：

Step 1初始化：采用隨機方法生成初始解。

Step 3學(xué)習(xí)階段：對于當(dāng)前種群中的每個解，借助該個體與其他解向量之間的差分量生成新個體，并借助貪婪保留策略生成子代解。

Step 4終止判斷：若達到終止條件，停止搜索并給出最優(yōu)解；否則轉(zhuǎn)Step 2。

3 HSCA算法

SCA的隨機初始化方法一定程度上制約了其搜索效率，同時其迭代過程僅借助已知最優(yōu)解和候選解之間的差分量更新個體位置，忽略了其他個體間的信息交流。鑒于此，HSCA以反向?qū)W習(xí)方法構(gòu)建質(zhì)量較高的初始種群，同時憑借模因分組和TLBO進化機制強化不同個體信息交流，旨在增強基本SCA算法的搜索性能。

3.1 反向?qū)W習(xí)初始化方法

HSCA采用反學(xué)習(xí)方法構(gòu)建種群：首先，利用隨機方法生成N個解，并為每個解生成對應(yīng)的反向解，最后選取最好的N個解作為初始種群[12]。

圖3為對比了兩種初始化方法在二維解空間的隨機分布情況。顯然，反向?qū)W習(xí)初始化方法在均勻、全面地探索解空間方面更具優(yōu)勢。

圖3 初始化方法對比Fig. 3 Comparison of initialization methods

算法的初始解構(gòu)造過程為：

Step 1定義參數(shù)i←1和參數(shù)d←1。

Step 2若表示式i≤S成立，轉(zhuǎn)Step 3，否則轉(zhuǎn)Step 7。

Step 3若表達式d≤D成立，轉(zhuǎn)Step 4，否則轉(zhuǎn)Step 5。

Step 5定義參數(shù)d←d+1，若d>D成立，轉(zhuǎn)Step 6；否則轉(zhuǎn)Step 3。

Step 6定義參數(shù)i←i+1，隨后轉(zhuǎn)Step 2。

3.2 模因分組與種群進化

HSCA算法保留了基本SCA算法的進化機制，利用式(5)更新個體位置，即借助已知最優(yōu)解和候選解之間的差分量更新種群。基于此，按照目標(biāo)值排序，并以q個解為一組劃分為p個模因組[13]。分組過程歸納如下：①將最優(yōu)解放在第一組，第二優(yōu)解放在第二組，依次類推；②將排位第p+1位的個體將被置入第一組，排位第p+2位的個體將被置入第二組；③重復(fù)以上分配過程，直至將最后一個解置入第p組。

隨后，HSCA算法采用TLBO的“教學(xué)階段”更新組內(nèi)的非局部最優(yōu)解，并以TLBO的“學(xué)習(xí)階段”更新組內(nèi)的所有解。給定一個解x，式(9)、式(10)分別為HSCA算法中“教學(xué)階段”和“學(xué)習(xí)階段”涉及的更新公式：

(9)

(10)

3.3 HSCA算法流程

HSCA算法的實現(xiàn)流程梳理如下：

Step 1初始化：利用反向?qū)W習(xí)法創(chuàng)建初始解。

Step 2SCA更新：確定當(dāng)前種群中的最優(yōu)解，利用SCA算法更新式(2)生成新個體的位置。

Step 3模因分組：依據(jù)個體的路徑評價函數(shù)值將種群劃分為p個子種群。

Step 4組內(nèi)教學(xué)：對于各個子種群，采用TLBO的“教學(xué)階段”更新組內(nèi)的非局部最優(yōu)解。

Step 5組內(nèi)學(xué)習(xí)：對于各個子種群，借助TLBO的“學(xué)習(xí)階段”更新組內(nèi)的各個解。

Step 6終止判斷：若滿足HSCA決策算法所設(shè)置的終止條件，停止迭代并輸出最好解；否則轉(zhuǎn)到Step 2。

4 實驗結(jié)果與分析

為分析HSCA的性能，開展基準(zhǔn)函數(shù)和RPP問題測試，并進行多種同類算法的對比。利用MATLAB2016b編程，平臺參數(shù)為內(nèi)存8 GB、CPU為Intel Core i5-2430M 2.4 Hz。

4.1 基準(zhǔn)函數(shù)測試

選取文獻[14]中的函數(shù)進行測試(表1)，參數(shù)n為函數(shù)維度。首先，對比HSCA與SCA算法，目的在于分析驗證改進措施的有效性。考慮n分為20和40的情形，對于每組算例，兩種決策方法分別跑20次。HSCA與SCA的種群置為60，迭代終止次數(shù)置為2 000，同時HSCA的q值設(shè)為10。表2給出了測試結(jié)果的均值和標(biāo)準(zhǔn)差數(shù)值比較。

表1 函數(shù)定義Table 1 Function definition

由表2可知，HSCA相比于SCA所取得的均值更小。換而言之，HSCA算法的整體尋優(yōu)效果更優(yōu)。同時，HSCA算法20次獨立運行所得結(jié)果的標(biāo)準(zhǔn)差較SCA更小，說明HSCA算法魯棒性更佳。

表2 SCA與HSCA算法目標(biāo)函數(shù)值對比Table 2 Objective function value comparison of SCA andHSCA algorithm

進一步地，將HSCA與其他幾種改進SCA算法對比，包括MSCA[8]、OBSCA[15]和SCA-DE[7]。維度n=40，對于各測試算例，所有方法分別跑20次，種群規(guī)模取60，迭代終止次數(shù)置為2 000，HSCA算法的子種群規(guī)模設(shè)置為10，其他參數(shù)設(shè)置同文獻[7,8,15]。表3對4種算法的仿真結(jié)果進行了分析，圖4為4種算法求解基準(zhǔn)測試函數(shù)的平均進化曲線。

由表3可知，HSCA算法所得結(jié)果的均值優(yōu)于MSCA、OBSCA和SCA-DE算法，表明反向?qū)W習(xí)初始化方法以及基于TLBO的多種群進化策略的嵌入使得SCA的搜索性能更強。同時，HSCA算法的標(biāo)準(zhǔn)差更小則驗證了其運行狀態(tài)更穩(wěn)定。另外，由圖4可知， HSCA算法初始階段的種群質(zhì)量更優(yōu)，且最終所尋得的解更具競爭性。

表3 4種改進SAC算法目標(biāo)函數(shù)值對比Table 3 Objective function value comparison of four kinds ofimproved SCA algorithms

圖4 平均進化曲線對比Fig. 4 Comparison of mean evolution curves

4.2 路徑規(guī)劃仿真

分別將HSCA、MSCA、OBSCA和SCA-DE算法運用于簡單(以Case 1表示)和復(fù)雜環(huán)境(以Case 2表示)的路徑規(guī)劃實驗。問題參數(shù)設(shè)置如下：Case 1障礙數(shù)和導(dǎo)航點數(shù)為6和10，Case 2中相應(yīng)參數(shù)為12和100。算法設(shè)置如下：決策方法運行次數(shù)置為20，種群規(guī)模和迭代次數(shù)為30和300， HSCA子種群規(guī)模為6，對比算法的其他參數(shù)同各文獻[7,8,15]。實驗結(jié)果歸納如圖5、圖6和表4。

圖5 最優(yōu)路徑Fig. 5 Optimal paths

圖6 最優(yōu)進化曲線Fig. 6 Optimal evolution curves

表4 兩種環(huán)境下4種測試算法線路長度對比Table 4 Comparison of the path length with four kinds oftest algorithms in two environment m

圖5對比了4種SCA算法在Case 1和Case 2中所得的最佳路徑，HSCA算法所規(guī)劃出的路徑最優(yōu)。特別是在Case 2對應(yīng)的復(fù)雜障礙環(huán)境中，筆者所提出的HSCA算法優(yōu)勢明顯。進一步的，圖6對比了4種SCA算法在Case 1和Case 2下的最優(yōu)進化曲線。據(jù)此可知，反向?qū)W習(xí)方法使得HSCA算法在迭代初期解的質(zhì)量更佳；同時，模因分組以及基于TLBO的多種群進化方法有效提升了算法的搜索性能。表4為4種改進SCA算法的優(yōu)化結(jié)果，顯然筆者提出的HSCA在優(yōu)化目標(biāo)優(yōu)越性和穩(wěn)定性兩方面很具有競爭性。

5 結(jié) 論

提出了一種混合正余弦算法來求解機器人路徑規(guī)劃問題。算法采用反向?qū)W習(xí)初始化方法，用于構(gòu)建高質(zhì)量的初始種群；同時在迭代搜索過程中，以優(yōu)化目標(biāo)為依據(jù)進行模因分組進而構(gòu)建多種群；并通過融合TLBO算法強化各子種群內(nèi)的信息交流，達到了增強算法局部挖掘能力的目的。在仿真實驗部分，結(jié)合基準(zhǔn)函數(shù)開展了HSCA算法的橫向和縱向的對比實驗，同時將HSCA算法應(yīng)用于簡單和復(fù)雜障礙環(huán)境的機器人路徑規(guī)劃問題。測試結(jié)果表明，HSCA算法的收斂效果顯著，具有良好的尋優(yōu)精度和穩(wěn)健的魯棒性。