摘 要： "針對(duì)頭腦風(fēng)暴優(yōu)化算法在求解機(jī)器人路徑規(guī)劃問題時(shí)存在初始解成功率低、運(yùn)算代價(jià)大且路徑不平滑等問題進(jìn)行了研究，從心理學(xué)角度出發(fā)，提出了一種新型頭腦風(fēng)暴優(yōu)化算法及其離散化方案。引入羊群效應(yīng)下的教與學(xué)思想增強(qiáng)個(gè)體學(xué)習(xí)的方向性，并通過基于自我選擇效應(yīng)的步長調(diào)節(jié)機(jī)制擴(kuò)大后期局部搜索比例，提升算法效率；離散處理階段采用貪婪移動(dòng)搜索法取得較優(yōu)初始解，重新定義運(yùn)算過程以雙向平滑路徑。仿真結(jié)果表明，新型頭腦風(fēng)暴優(yōu)化算法在離散化前后均有較優(yōu)的表現(xiàn)，在不同障礙物環(huán)境中均能規(guī)劃出較優(yōu)的路徑。數(shù)值實(shí)驗(yàn)驗(yàn)證了所提算法的有效性，該算法在路徑規(guī)劃領(lǐng)域的應(yīng)用值得進(jìn)一步探索。

關(guān)鍵詞： "機(jī)器人路徑規(guī)劃； 新型頭腦風(fēng)暴優(yōu)化算法； 教與學(xué)優(yōu)化算法； 社會(huì)心理學(xué)

中圖分類號(hào)： "TP301.6 """文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： "1001-3695（2022）02-013-0402-05

doi：10.19734/j.issn.1001-3695.2021.05.0213

Robot path planning with novel brain storm optimization algorithm

Wei Shiyu， Liu Yong

（Business School， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract： ""The brain storm optimization algorithm has the problems of low initial solution success rate，high computational cost and unsmooth path in solving robot path planning problem.Therefore，this paper proposed a novel brain storm optimization algorithm and its discretization scheme from the perspective of psychology.The teaching-learning idea under the herd effect enhanced the directionality of individual learning.The improved algorithm expanded the local search ratio in the later stage and improved efficiency through the step adjustment mechanism based on self-selection effect.In the discrete processing stage，it used a greedy moving search method to obtain better initial solutions.At the same time，the redefined calculation process smoothed the path in two directions.The simulation results show that the novel brain storm optimization algorithm has better performance before and after discretization，and can plan better paths in different environments.Numerical experiments verify the effectiveness of the proposed algorithm，and the application of the algorithm in the field of path planning deserves further exploration.

Key words： "robot path planning； novel brain storm optimization algorithm； teaching-learning based optimization algorithm； social psychology

0 引言

隨著科技的發(fā)展，機(jī)器人被應(yīng)用于多個(gè)領(lǐng)域，代替或協(xié)助人類完成多種工作，達(dá)到提升工作效率、在危險(xiǎn)或復(fù)雜的環(huán)境中探索的目的［1］。機(jī)器人的運(yùn)行環(huán)境不同，包含的障礙物形狀也多種多樣，并可能是靜態(tài)的或動(dòng)態(tài)的［2］，因此在機(jī)器人移動(dòng)過程中避免碰撞是路徑規(guī)劃的難點(diǎn)之一。機(jī)器人路徑規(guī)劃本質(zhì)上是NP完全問題，包含多個(gè)性能指標(biāo)且難以求得精確解，所以在特定場景下找到高效安全的方法，使其行走路徑得到優(yōu)化具有現(xiàn)實(shí)意義［3］。較為經(jīng)典的算法如Dijkstra算法、A*算法和遺傳算法等常被用來解決此類問題，如李翰等人［4］利用改進(jìn)A*算法實(shí)現(xiàn)了城市物流區(qū)的無人機(jī)路徑規(guī)劃。

隨著計(jì)算機(jī)性能的提升，群集類智能優(yōu)化算法發(fā)展迅猛，這類結(jié)果精度和計(jì)算時(shí)間雙優(yōu)的元啟發(fā)式算法在解決機(jī)器人路徑規(guī)劃問題時(shí)通常是不錯(cuò)的選擇，具有廣泛應(yīng)用［5］。由于人類相較于其他生物在溝通和學(xué)習(xí)方面具有極大優(yōu)勢，受人類行為啟發(fā)而被提出的算法如頭腦風(fēng)暴優(yōu)化算法（BSO）和教與學(xué)優(yōu)化算法（TLBO）在解決NP難問題時(shí)往往表現(xiàn)更優(yōu)［6］。但本文所研究的頭腦風(fēng)暴優(yōu)化算法在實(shí)際應(yīng)用中存在收斂速度慢、易陷入局部最優(yōu)等問題，研究人員針對(duì)不同場景提出了多種算法改進(jìn)策略，總體上說是對(duì)其聚類、變異、生成新個(gè)體三個(gè)過程進(jìn)行調(diào)整。Sun等人［7］引入放松選擇機(jī)制代替原有的貪婪選擇，使算法能夠加強(qiáng)搜索能力跳出局部最優(yōu)；吳亞麗等人［6］將云模型用于變異和新個(gè)體產(chǎn)生，顯著提升結(jié)果精度；Boamah等人［8］利用低方差頭腦風(fēng)暴優(yōu)化和脈沖響應(yīng)函數(shù)預(yù)測中國的二氧化碳排放量，實(shí)際數(shù)據(jù)說明不確定因素影響下BSO算法仍能取得較好結(jié)果。在路徑規(guī)劃領(lǐng)域中，馬威強(qiáng)等人［9］采用全局最優(yōu)、差分變異的思想改進(jìn)了頭腦風(fēng)暴優(yōu)化算法，實(shí)現(xiàn)了水下航行器的路徑規(guī)劃；Liu等人［10］采用頭腦風(fēng)暴—蟻群（BSO-ACS）混合算法求解車輛路徑規(guī)劃問題，驗(yàn)證了算法的有效性；Wu等人［11］介紹了一種元啟發(fā)式算子，將頭腦風(fēng)暴算法的討論過程抽象化，使其適用于解決離散的旅行商問題，為本文的算法改進(jìn)策略提供了思路；Tuba等人［2］結(jié)合蜂群算法優(yōu)化了BSO算法生成的初始路徑，在柵格網(wǎng)絡(luò)中規(guī)劃出了較優(yōu)的機(jī)器人路徑。盡管BSO算法是受人類問題討論過程啟發(fā)提出的，但考慮人類行為及心理活動(dòng)的相關(guān)改進(jìn)不足，且算法應(yīng)用場景較為有限，涉及機(jī)器人路徑優(yōu)化的研究仍然較少。

由于傳統(tǒng)柵格環(huán)境下的路徑尋優(yōu)方法計(jì)算簡單但重復(fù)工作多、優(yōu)化結(jié)果不理想，而啟發(fā)式算法路徑搜索空間大、結(jié)果精度高但隨機(jī)性較強(qiáng)、運(yùn)算速度慢，本文將兩者結(jié)合，在搜索環(huán)境柵格化的基礎(chǔ)上對(duì)BSO算法進(jìn)行改進(jìn)，提出結(jié)合教與學(xué)思想的BTSO算法，應(yīng)用于機(jī)器人路徑規(guī)劃時(shí)進(jìn)一步離散化處理，使其更匹配于柵格環(huán)境。算法生成較優(yōu)初始解，以減少不必要的學(xué)習(xí)時(shí)間，同時(shí)調(diào)整步長參數(shù)和個(gè)體更新策略進(jìn)一步提升算法收斂速度，最后討論不同環(huán)境中的路徑規(guī)劃結(jié)果，對(duì)BTSO算法的性能進(jìn)行驗(yàn)證。

1 算法設(shè)計(jì)

1.1 頭腦風(fēng)暴優(yōu)化算法

BSO算法采取分組討論的形式提升尋優(yōu)效率，設(shè)置多組概率參數(shù)調(diào)節(jié)局部搜尋和全局搜索的比例，加速收斂的同時(shí)盡量避免陷入局部最優(yōu)。算法的尋優(yōu)機(jī)制可以概括為聚類、變異、生成新個(gè)體和選擇四個(gè)過程［12］。算法的候選個(gè)體生成包括組內(nèi)討論和組間討論兩種形式，候選個(gè)體加上隨機(jī)擾動(dòng)得到新個(gè)體，個(gè)體更新公式如下：

X new=X c+ζ×N（η，σ） ""（1）

其中： X new 是新生成的個(gè)體， X c 是候選個(gè)體， ζ 代表擾動(dòng)系數(shù)， N（η，σ）是具有均值η和方差σ 的高斯隨機(jī)函數(shù)。擾動(dòng)系數(shù)的計(jì)算公式如下：

ζ =logsig（（0.5 I max-I current）/k ）×rand（0，1） "（2）

其中： I max 是最大迭代次數(shù)，而當(dāng)前迭代次數(shù)由 I current 表示， k 用于控制logsig（）函數(shù)的斜率，rand（0，1）是（0，1）內(nèi)的隨機(jī)值。由于BSO的概率選擇機(jī)制，其收斂速度受隨機(jī)數(shù)影響較大，本文基于社會(huì)心理學(xué)的理論基礎(chǔ)剖析BSO算法原理，同時(shí)考慮到TLBO算法同樣是源于人類行為提出的，所以將兩者的更新方式結(jié)合優(yōu)化。首先分析人類活動(dòng)中的效應(yīng)理論，再用合適的數(shù)學(xué)模型將其映射到編碼中以達(dá)到更優(yōu)的效果。

1.2 心理學(xué)效應(yīng)理論的應(yīng)用

羊群效應(yīng)是經(jīng)典的集群心理學(xué)現(xiàn)象，形容一個(gè)領(lǐng)域中的個(gè)體（羊群）對(duì)領(lǐng)先者（頭羊）的跟隨行為。在信息不對(duì)稱和預(yù)期不確定的條件下，模仿較優(yōu)個(gè)體進(jìn)行決策承擔(dān)的風(fēng)險(xiǎn)低，這在博弈論、納什均衡中也有所說明。BSO算法描述的群體決策場景中，參與討論的人群具備不同的社會(huì)背景，同時(shí)不確定討論結(jié)果是否為最優(yōu)，符合信息不對(duì)稱和預(yù)期不確定的條件。因此考慮將羊群效應(yīng)的優(yōu)勢體現(xiàn)在算法中，加強(qiáng)聚類中普通個(gè)體對(duì)較優(yōu)個(gè)體的學(xué)習(xí)，加速收斂。心理學(xué)中的自我選擇效應(yīng)是指人一旦選擇了某一條路就存在持續(xù)下去的慣性并自我強(qiáng)化，若轉(zhuǎn)向其他道路則將付出高額代價(jià)。將此理論映射到BTSO算法的搜索比例調(diào)節(jié)中，即在討論后期，大多數(shù)個(gè)體傾向于向已知的優(yōu)秀個(gè)體學(xué)習(xí)而不愿提出新的可行解，隨機(jī)擾動(dòng)在算法后期會(huì)影響收斂速度，提升運(yùn)算代價(jià)。

1.3 改進(jìn)更新策略

考慮羊群效應(yīng)，從加強(qiáng)聚類中普通個(gè)體對(duì)較優(yōu)個(gè)體學(xué)習(xí)的角度出發(fā)對(duì)更新策略進(jìn)行改進(jìn)。直觀上來說，受啟發(fā)于人類行為所提出的算法效果一定程度上優(yōu)于基于模擬其他集群活動(dòng)所提出的算法。 教與學(xué)優(yōu)化算法是近年來提出的較為新穎的集群優(yōu)化算法，該算法模擬了人類的集體學(xué)習(xí)行為，原理簡單，運(yùn)算高效［13］。TLBO算法具有兩個(gè)算子，分別表示最優(yōu)個(gè)體向其他個(gè)體執(zhí)行“教操作”和其他個(gè)體相互之間的“學(xué)”行為。算子1以領(lǐng)先者的身份引導(dǎo)種群其他個(gè)體快速向最優(yōu)收斂，算子2則保證了解的多樣性，避免算法早熟［14］。而BSO算法的更新過程不具有方向性，主要依靠不同范圍的討論取得迭代次數(shù)內(nèi)的最優(yōu)結(jié)果，因此將算子1引入BSO算法中以加速收斂，得到了混合算法BTSO。這樣無論是組間討論還是組內(nèi)討論，個(gè)體的更新都不再是隨機(jī)性的，而是指向聚類中心方向，具體公式為

X new=X c +rand（0，1）×（ X center-βX mean） ""（3）

β =round（1+rand（）） "（4）

其中： X mean 是聚類個(gè)體的平均水平， X center 表示聚類中心， β 是教學(xué)因子，round（）表示四舍五入取整?；谏鲜龈倪M(jìn)，較優(yōu)個(gè)體在位置附近搜索，普通個(gè)體向中心方向移動(dòng)，通過變異和擾動(dòng)避免早熟。

1.4 搜索比例調(diào)節(jié)

借助自我選擇效應(yīng)思想，BSO在迭代后期應(yīng)提升局部搜索比例，減小搜索步長。由分析可知， k 取值不同，步長的變化如圖1所示，即 k 取值小時(shí)，步長斜率大。 k 值較小意味著隨機(jī)擾動(dòng)在算法前期占比大，結(jié)合BSO的組間討論機(jī)制在全局進(jìn)行大范圍搜索確定較優(yōu)解位置；同時(shí)隨機(jī)擾動(dòng)在算法后期占比小，算法在較優(yōu)解的附近進(jìn)行精確搜索，此時(shí)組間交流保證各聚類中心的有效比較，防止算法陷入局部最優(yōu)的同時(shí)取得更優(yōu)的解。因此適當(dāng)減小 k 值利于加速收斂。

2 算法測試實(shí)驗(yàn)

對(duì)基于心理學(xué)原理同時(shí)融合教與學(xué)優(yōu)化算法提出的BSO改進(jìn)算法BTSO使用連續(xù)經(jīng)典測試函數(shù)進(jìn)行效果驗(yàn)證。本文經(jīng)過預(yù)測試依據(jù)經(jīng)驗(yàn)給出相關(guān)參數(shù)設(shè)置。初始種群規(guī)模 n 和聚類數(shù)量 m 分別取值50和5， k 取值15，聚類中心的變異概率 P vary 設(shè)置為0.2，組內(nèi)討論的概率 P cluster 設(shè)置為0.8，組內(nèi)討論和組間討論選取聚類中心的概率 P ndividual1、P individual2 分別設(shè)置為0.4和0.5，最大迭代次數(shù)為500。選取解決連續(xù)規(guī)劃問題的經(jīng)典算法粒子群優(yōu)化算法以及基本頭腦風(fēng)暴優(yōu)化算法、教與學(xué)優(yōu)化算法參與對(duì)比。基準(zhǔn)函數(shù)選取如表1所示。

測試主要在高維函數(shù)上進(jìn)行，前八個(gè)函數(shù)測試維度為30維， f 9、f 10、f 11 測試維度為2維，每個(gè)算法在所提出的測試函數(shù)上獨(dú)立運(yùn)行30次，以消除隨機(jī)性等其他因素的影響，對(duì)每次的優(yōu)化結(jié)果進(jìn)行記錄。表2總結(jié)了各個(gè)算法在兩組不同維度測試函數(shù)的30次獨(dú)立實(shí)驗(yàn)中的均值（ ""）和標(biāo)準(zhǔn)差（ s ），分別反映了算法的尋優(yōu)效果和所得結(jié)果相較于均值的穩(wěn)定程度。圖2直觀地展示了算法在前五個(gè)測試函數(shù)上的尋優(yōu)收斂特性曲線。

分析圖2和表2可知，相較于基于鳥群覓食行為提出的PSO算法，基于人類行為提出的其他三種算法明顯表現(xiàn)出了更優(yōu)的求解能力，在二維函數(shù) f 9、f 10、f 11 上，TLBO和BTSO能穩(wěn)定地取得最優(yōu)值；BSO的精度也在10-13及以下；PSO算法的表現(xiàn)則不穩(wěn)定，在 f 10、f 11 上的尋優(yōu)結(jié)果與最優(yōu)值有偏差，當(dāng)問題維度增加至30維時(shí)，PSO的效果大幅下降。綜合來看，BTSO算法性能在BSO的基礎(chǔ)上有了較大的提升，各維度平均值和方差都普遍高于其他算法，體現(xiàn)出了更強(qiáng)的魯棒性。

圖2顯示出BTSO算法相較于其他三種算法在高維多峰值函數(shù)尋優(yōu)中具有更優(yōu)的求解效果。算法的初期尋優(yōu)階段繼承了TLBO的有向性，收斂速度明顯快于BSO和PSO；迭代中期，收斂過程進(jìn)入停滯期，此時(shí)求解結(jié)果與相對(duì)比算法中的最優(yōu)結(jié)果相當(dāng)，說明BTSO取得了階段性最優(yōu)解；但隨著迭代次數(shù)超過300次，由于步長調(diào)節(jié)機(jī)制和討論原理改進(jìn)，BTSO憑借組間討論的優(yōu)勢跳脫局部最優(yōu)，持續(xù)擺脫隨機(jī)擾動(dòng)的影響，進(jìn)一步收斂，最終取得理想結(jié)果。實(shí)驗(yàn)結(jié)果證明BTSO算法在復(fù)雜高維的優(yōu)化問題中能夠跳脫局部最優(yōu)，快速精確地得到理想結(jié)果，具有較強(qiáng)的魯棒性，適用于多峰值問題。

3 算法應(yīng)用研究

在機(jī)器人的路徑規(guī)劃問題中，混合型算法所取得的效果大多優(yōu)于單一算法［15］，且Tuba等人［2］通過改進(jìn)BSO算法進(jìn)行機(jī)器人路徑規(guī)劃取得了不錯(cuò)的結(jié)果，但是該算法性能還可以進(jìn)一步提高，且測試環(huán)境障礙物較少，與實(shí)際情況有差距。由前面的實(shí)驗(yàn)結(jié)果可以看出，本文提出的BTSO算法在連續(xù)優(yōu)化問題上具有不錯(cuò)的求解效果，本文考慮在更為復(fù)雜的環(huán)境下采用BTSO算法求解機(jī)器人路徑規(guī)劃問題。

3.1 問題建模

本文用二維網(wǎng)格圖劃分機(jī)器人移動(dòng)場景，柵格地圖有利于便捷地描述機(jī)器人運(yùn)動(dòng)狀態(tài)，很好地反映了算法效果［16］，同時(shí)二值圖像記錄了像素格的特征和坐標(biāo)，利于障礙物的描述和初始解的優(yōu)化。雖然矩形較規(guī)則障礙物能簡化計(jì)算，但機(jī)器人實(shí)際的工作環(huán)境要復(fù)雜得多，如存在易使其卡死的凹形障礙物。因此本文進(jìn)一步對(duì)不同形態(tài)障礙物的地形進(jìn)行討論，以提升算法的實(shí)用價(jià)值。用長為 X max 、寬為 Y max 的矩形選取路徑規(guī)劃的搜索空間 U ，從橫向和縱向?qū)臻g進(jìn)行 a和b 等分，形成 a×b 個(gè)大小相等的正方形單元格，單元格的尺寸根據(jù)障礙物形狀和機(jī)器人的占地面積決定。在柵格化后的地圖中添加 o i 個(gè)障礙物，每個(gè)障礙物占用一個(gè)或多個(gè)柵格，當(dāng)其占用面積不足一個(gè)柵格時(shí)進(jìn)行膨脹處理，即將當(dāng)前整個(gè)單元格視為障礙物。由于障礙物進(jìn)行過膨脹處理，將機(jī)器人視為空間內(nèi)的質(zhì)點(diǎn)，且每次移動(dòng)后停留在下一目標(biāo)編號(hào)點(diǎn)的中心。

計(jì)算機(jī)存儲(chǔ)中，對(duì)單元格可以從狀態(tài)和索引兩方面進(jìn)行描述［17］。本文將障礙物單元格用1表示，顏色為黑色，自由單元格用0表示，顏色為白色，將搜索空間可視化為二值圖像。同時(shí)采用坐標(biāo)和序號(hào)進(jìn)行單元格的索引，初始化地圖信息和路徑的過程中采取坐標(biāo)索引，使場景映射更加準(zhǔn)確；解的尋優(yōu)和路徑記錄的過程中采取序號(hào)索引提升計(jì)算效率，便于結(jié)果記錄。假設(shè)單元格的邊長為 w，路徑規(guī)劃起點(diǎn)P s 位于地圖左下角，終點(diǎn) P t 位于地圖右上角。因機(jī)器人只在柵格中心點(diǎn)停留且本文考慮搜索邊界，所以選取邊界的左下角柵格中心為坐標(biāo)（0，0）點(diǎn)， w 為最小刻度，建立直角坐標(biāo)系。從距離原點(diǎn)最近的自由單元格開始編號(hào)，以序號(hào)1開始從左至右、由下往上依次遞增，編號(hào)時(shí)不考慮邊界。柵格的坐標(biāo)和序號(hào)索引可以相互轉(zhuǎn)換，第 i個(gè)柵格的坐標(biāo)（X i，Y i）和索引i 的關(guān)系可表示為

X i= ""mod （i，a） "mod （i，a）≠0

a "mod （i，a）≠0 """"（5）

Y i= ""mod （i，b） "mod （i，b）≠0

b "mod （i，b）≠0 """"（6）

i=m×（Y i-1）+X i ""（7）

柵格 i的中心點(diǎn)實(shí)際位置（x i，y i）與當(dāng)前柵格坐標(biāo)索引（X i，Y i） 的對(duì)應(yīng)關(guān)系可表示為

x i=X i×w

y i=Y i×w """（8）

綜上所述，本文的搜索空間 U 在20×20的網(wǎng)格圖中可表示如圖3所示。

在目標(biāo)區(qū)域內(nèi)連接起點(diǎn)和終點(diǎn)的序列點(diǎn)或曲線稱之為路徑，構(gòu)成路徑的策略稱之為路徑規(guī)劃。假設(shè)障礙物集合為 O ，機(jī)器人停留的當(dāng)前節(jié)點(diǎn)為 P i ，實(shí)際位置為 （x i，y i） ，移動(dòng)的過程中每段路徑均與障礙物無交點(diǎn)，則該問題數(shù)學(xué)描述如下：

∑ q-1 i=1 ［（ x-x i x i+1-x i = y-y i y i+1-y i ）∩O］=0 ""（9）

其中： q 為可行路徑節(jié)點(diǎn)數(shù)。本文的規(guī)劃目標(biāo)為總路程最短，則目標(biāo)函數(shù) f（P i） 可表示為

f（P i） =min （∑ q-1 i=1 "（x i+1-x i）2+（y i+1-y i）2 ） ""（10）

3.2 BTSO解決路徑規(guī)劃問題

根據(jù)心理學(xué)原理提出的BTSO算法適用于解決連續(xù)優(yōu)化問題，但若將其直接應(yīng)用于機(jī)器人的路徑規(guī)劃，則初始過程需要在目標(biāo)空間內(nèi)生成 d 個(gè)隨機(jī)點(diǎn)，要保證每個(gè)相鄰節(jié)點(diǎn)之間的直線路徑與障礙物均無交點(diǎn)難度較大。尤其是在障礙物較多、地形復(fù)雜的環(huán)境中，依靠隨機(jī)性生成初始種群的成功率較低，即使生成了可用于迭代的可行解集，后續(xù)的計(jì)算量也十分龐大，運(yùn)算代價(jià)較高。因此本文進(jìn)一步提出BTSO的離散化處理方案，使相關(guān)路徑規(guī)劃問題的解決更加準(zhǔn)確高效。離散型BTSO的算法整體思路框架如圖4所示，各運(yùn)算階段的具體改進(jìn)策略如下。

3.2.1 貪婪移動(dòng)搜尋策略

用BSO進(jìn)行機(jī)器人路徑規(guī)劃時(shí)，初始解生成階段結(jié)合蜂群算法（ABC）能有效提升解的質(zhì)量。ABC算法大量搜尋機(jī)器人周圍的隨機(jī)節(jié)點(diǎn)，同時(shí)結(jié)合與目標(biāo)點(diǎn)的接近性逐步生成無沖突路徑［18］。本文根據(jù)該思路提出了柵格環(huán)境中的移動(dòng)搜索策略獲取初始可行路徑。當(dāng)機(jī)器人移動(dòng)到當(dāng)前柵格 i 時(shí)，對(duì)周圍的八個(gè)柵格進(jìn)行排查，過程如圖5所示。圖中坐標(biāo)為被搜尋柵格相對(duì)于機(jī)器人所處當(dāng)前位置 P i 的柵格坐標(biāo)，為了提升初始解的質(zhì)量，每步優(yōu)先考慮將機(jī)器人移動(dòng)至距離目標(biāo)點(diǎn)最近的三個(gè)柵格，當(dāng)優(yōu)先柵格均為障礙物時(shí)再隨機(jī)選擇周圍的自由柵格，保證初始解的多樣性。本文的路徑規(guī)劃起止點(diǎn)分別設(shè)置在地圖的左下角和右上角，因此優(yōu)先柵格的相對(duì)位置為。若終點(diǎn)柵格出現(xiàn)在搜尋范圍內(nèi)則停止移動(dòng)，并通過路徑回溯直至起點(diǎn)柵格，從而得到可行路徑。

3.2.2 路徑平滑處理

由于機(jī)器人步進(jìn)具有隨機(jī)性，規(guī)劃時(shí)易出現(xiàn)冗余路線，降低后續(xù)迭代效率，所以對(duì)初始路徑進(jìn)行雙向平滑處理并保留較好結(jié)果。正向平滑時(shí)首先將 P s 作為當(dāng)前節(jié)點(diǎn) P i ，將 P i 與后續(xù)節(jié)點(diǎn)依次連線記錄所連線段與障礙物無交點(diǎn)的節(jié)點(diǎn)，其中下標(biāo)最大的點(diǎn)作為 P i+1 ，然后將 P i+1 點(diǎn)作為當(dāng)前節(jié)點(diǎn) P i ，重復(fù)上述過程直到 P i 為終點(diǎn) P t ，過程如圖6所示。反向平滑則初始時(shí)將 P t 作為當(dāng)前節(jié)點(diǎn)，平滑方向朝 P s 方向步進(jìn)。此外本文將障礙物看做直徑為柵格對(duì)角線長度的圓形區(qū)域，使路徑與實(shí)際障礙物有一定的安全間隔。

3.2.3 離散化個(gè)體更新

a）聚類階段。為保證每個(gè)小組有優(yōu)秀的帶領(lǐng)人，排除低效學(xué)習(xí)操作，將種群按適應(yīng)度由高到低進(jìn)行排序。選取適應(yīng)度較優(yōu)的 m 個(gè)個(gè)體作為聚類中心，其余按順序歸為 m 個(gè)聚類。這種聚類方式能夠保證組間學(xué)習(xí)的個(gè)體相互間具有一定的差異性，在進(jìn)化后期避免個(gè)體因相同或高度相似以至無效操作，影響算法收斂速度。

b）變異階段。對(duì)聚類中心的隨機(jī)點(diǎn)進(jìn)行位置變換，保證前后段路徑與障礙物無交點(diǎn)的同時(shí)用周圍的自由柵格替換當(dāng)前柵格，平滑后得到新的聚類中心，變異方向如圖7所示。考察當(dāng)前節(jié)點(diǎn)周圍的八個(gè)柵格，105號(hào)為障礙物，65、66、86號(hào)與前一節(jié)點(diǎn)連線不可行，104號(hào)與后一節(jié)點(diǎn)連線不可行，因此變異方向只能為64、84或106號(hào)柵格。

c）個(gè)體更新階段。學(xué)習(xí)過程采用單點(diǎn)交叉，在學(xué)習(xí)個(gè)體與被學(xué)習(xí)者的路徑標(biāo)號(hào)相同點(diǎn)進(jìn)行交叉。除 P s與P t 點(diǎn)外，若兩者的相同標(biāo)號(hào)不止一個(gè)則任選一點(diǎn)進(jìn)行交叉，過程如圖8所示。

3.2.4 仿真分析

使用IntelCoreTM i7-7700 CPU 2.80 GHz配置的電腦基于MATLAB R2019a軟件實(shí)現(xiàn)了用離散型BTSO解決機(jī)器人路徑規(guī)劃問題。在規(guī)模為20×20、40×40和60×60的柵格環(huán)境中測試離散型BTSO的路徑規(guī)劃效果。各個(gè)環(huán)境中分別隨機(jī)生成78、300和600個(gè)障礙物柵格，種群大小 n=16，聚類數(shù)量m=4，概率參數(shù)保留第1.4節(jié)中的設(shè)置，聚類中心變異概率P vary =0.2，組內(nèi)討論的概率 P cluster =0.8，組內(nèi)討論和組間討論選取聚類中心的概率 P ndividual1、P individual2 分別取值0.4和0.5，最大迭代次數(shù)為100。選取路徑規(guī)劃問題的經(jīng)典算法蟻群算法（ACO）和A*算法（AStar），以及文獻(xiàn)［2］中所使用的結(jié)合蜂群算法的改進(jìn)BSO算法（BBSO）進(jìn)行多場景對(duì)比。所提出的方法在每個(gè)測試環(huán)境中獨(dú)立運(yùn)行30次以排除隨機(jī)性的影響，較為準(zhǔn)確地評(píng)估了算法的求解性能。所得路線如圖9所示，路徑具體長度記錄于表4中。

具有78個(gè)障礙物的20×20柵格環(huán)境中，通過A*算法、ACO和BTSO算法規(guī)劃的機(jī)器人路徑如圖9（a）所示，說明即使在規(guī)模較小的網(wǎng)絡(luò)中BTSO也具有優(yōu)勢，求解路徑長度短且平滑。而ACO算法在凹型區(qū)域內(nèi)易出現(xiàn)鎖死現(xiàn)象，較于A*、BBSO和BTSO算法求解效果不理想。當(dāng)環(huán)境擴(kuò)大至圖9（b）所示的300個(gè)障礙物40×40柵格規(guī)模時(shí)，BBSO和BTSO算法仍表現(xiàn)較優(yōu)，但BSO算法相較于A*算法和BBSO能更好地處理路徑規(guī)劃中的折點(diǎn)，同時(shí)其規(guī)劃路線長度比ACO算法縮短5.7%。隨著環(huán)境復(fù)雜度進(jìn)一步提升至圖9（c）所示的600個(gè)障礙物60×60柵格時(shí)，BTSO算法的結(jié)果優(yōu)勢成正比上升，規(guī)劃路線長度比A*算法短4%，較于ACO算法短11.7%，與BBSO算法相比長度縮短的同時(shí)仍保持了路徑的相對(duì)平滑度。

4 結(jié)束語

本文得到的主要結(jié)論如下：

a）結(jié)合教與學(xué)思想的BTSO算法的實(shí)驗(yàn)結(jié)果表明，加強(qiáng)傳統(tǒng)BSO算法的個(gè)體更新方向性，同時(shí)提升算法后期的局部搜索比例能夠顯著提升算法的收斂速度和結(jié)果精度，所提出的BTSO算法能有效跳出局部最優(yōu)，具有較高的運(yùn)算效率。

b）在具有靜態(tài)障礙物的二維柵格網(wǎng)絡(luò)中，無論是簡單的或者更為復(fù)雜的環(huán)境，離散型BTSO都能實(shí)現(xiàn)機(jī)器人的路徑規(guī)劃，給出較優(yōu)方案。未來可將其應(yīng)用于實(shí)際場景，拓寬至動(dòng)態(tài)障礙物或三維環(huán)境下的路徑規(guī)劃問題。

c）基于人類行為提出的集群智能算法相較于傳統(tǒng)智能集群算法，在解決本文所假設(shè)環(huán)境中的規(guī)模較大且情況更復(fù)雜的機(jī)器人路徑規(guī)劃問題時(shí)具有優(yōu)勢，社會(huì)心理學(xué)和人類行為學(xué)有待進(jìn)一步與計(jì)算機(jī)應(yīng)用進(jìn)行結(jié)合。

參考文獻(xiàn)：

［1］ "Chen Wei，Zhao De’an.Path planning for spray painting robot of workpiece surfaces［J］. Mathematical Problems in Engineering， 2013， 2013 （8）：article ID 659457.

［2］ Tuba E，Strumberger I，Zivkovic D， et al .Mobile robot path planning by improved brain storm optimization algorithm［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2018：2203-2210.

［3］ Jeddisaravi K，Alitappeh R J，Guimaraes F G.Multi-objective mobile robot path planning based on A* search［C］//Proc of the 6th International Conference on Computer and Knowledge Engineering.Pisca-taway，NJ：IEEE Press，2016：7-12.

［4］ 李翰，張洪海，許衛(wèi)衛(wèi)，等.物流無人機(jī)路徑規(guī)劃及評(píng)估方法研究［J］.信息技術(shù)，2020（1）：1-6. （Li Han，Zhang Honghai，Xu Weiwei， et al .Research on route planning and evaluation method of logistics UAV［J］. Information Technology ，2020（1）：1-6.）

［5］ 于振中，李強(qiáng)，樊啟高.智能仿生算法在移動(dòng)機(jī)器人路徑規(guī)劃優(yōu)化中的應(yīng)用綜述［J］.計(jì)算機(jī)應(yīng)用研究，2019， 36 （11）：3210-3219. （Yu Zhenzhong，Li Qiang，F(xiàn)an Qigao.Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots［J］. Application Research of Computers ，2019， 36 （11）：3210-3219.）

［6］ 吳亞麗，焦尚彬.頭腦風(fēng)暴優(yōu)化算法理論及應(yīng)用［M］.北京：科學(xué)出版社，2017：68-82. （Wu Yali，Jiao Shangbin.Brainstorming optimization algorithm and its applications［M］.Beijing：Science Press，2017：68-82.）

［7］ Sun Yuehong，Wei Jianxiang，Wu Tingting， et al .Brain storm optimization using a slight relaxation selection and multi-population based creating ideas ensemble［J］. Applied Intelligence ，2020， 50 （10）：3137-3161.

［8］ Boamah K B，Du Jianguo，Adu D， et al .Predicting the carbon dioxide emission of China using a novel augmented hypo-variance brain storm optimization and the impulse response function［J］. Environmental Technology ，2020：doi：10.1080/09593330.2020.1758217.

［9］ 馬威強(qiáng)，高永琪，趙苗.基于全局最優(yōu)和差分變異的頭腦風(fēng)暴優(yōu)化算法[J/OL].系統(tǒng)工程與電子技術(shù)，2021.http：//kns.cnki.net/kcms/detail/11.2422.TN.20210531.0826.002.html. （Ma Weiqiang，Gao Yongqi，Zhao Miao.Global-best difference-mutation brain storm optimization algorithm[J/OL]. Systems Engineering and Electronics ，2021.http：//kns.cnki.net/kcms/detail/11.2422.TN.20210531.0826.002.html.）

［10］ Liu Mingde，Shen Yang，Zhao Qi， et al .A hybrid BSO-ACS algorithm for vehicle routing problem with time windows on road networks［C］//Proc of IEEE Congress on Evolutionary Computation.Pisca-taway，NJ：IEEE Press，2020.

［11］ Wu Yali，Wang Xiaopeng，Qi Jinjin， et al .An adaptive brain storm optimization algorithm based on heuristic operators for TSP［C］//Proc of the 14th International Conference on Bio-inspired Computing：Theories and Applications.Singapore：Springer，2020：662-672.

［12］ Shi Yuhui.Brain storm optimization algorithm［C］//Proc of the 2nd International Conference on Swarm Intelligence.Berlin：Springer-Verlag，2011：303-309.

［13］ 何杰光，彭志平，崔德龍，等.局部維度改進(jìn)的教與學(xué)優(yōu)化算法［J］.浙江大學(xué)學(xué)報(bào)：工學(xué)版，2018， 52 （11）：2159-2170. （He Jieguang，Peng Zhiping，Cui Delong， et al .Teaching-learning-based optimization algorithm with local dimension improvement［J］. Journal of Zhejiang University：Engineering Science ，2018， 52 （11）：2159-2170.）

［14］ 李麗榮，楊坤，王培崇.融合頭腦風(fēng)暴思想的教與學(xué)優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2020， 40 （9）：2677-2682. （Li Lirong，Yang Kun，Wang Peichong.Improved teaching amp; learning based optimization algorithm with brain storming［J］. Journal of Computer Application， 2020， 40 （9）：2677-2682.）

［15］ 林韓熙，向丹，歐陽劍，等.移動(dòng)機(jī)器人路徑規(guī)劃算法的研究綜述［J］.計(jì)算機(jī)工程與應(yīng)用，2021， 57 （18）：38-48. （Lin Hanxi，Xiang Dan，Ou Yangjian， et al .Review of path planning algorithms for mobile robots［J］. Computer Engineering and Applications， 2021， 57 （18）：38-48.）

［16］ "趙明，鄭澤宇，么慶豐，等.基于改進(jìn)人工場勢法的移動(dòng)機(jī)器人路徑規(guī)劃方法［J］.計(jì)算機(jī)應(yīng)用研究，2020， 37 （S2）：66-68，72. （Zhao Ming，Zheng Zeyu，Yao Qingfeng， "et al .Path planning method for multiple mobile robots based on modified potential field method［J］. Application Research of Computers ，2020， 37 （S2）：66-68，72.）

［17］ 胡章芳，馮淳一，羅元，等.改進(jìn)粒子群優(yōu)化算法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.計(jì)算機(jī)應(yīng)用研究，2021， 38 （10）：3089-3092. （Hu Zhangfang，F(xiàn)eng Chunyi，Luo Yuan， et al .Improved particle swarm optimization algorithm for mobile robot path planning［J］. Application Research of Computers， 2021， 38 （10）：3089-3092.）

［18］ Faridi A Q，Sharma S，Shukla A， et al .Multi-robot multi-target dyna-mic path planning using artificial bee colony and evolutionary programming in unknown environment［J］. Intelligent Service Robo-tics ，2018， 11 （4）：171-186.