基于遺傳算法的移動機器人路徑規(guī)劃及人機協(xié)同控制研究

楊國慶，方振江，吳 昊

（天津城建大學控制與機械工程學院，天津300384）

針對目前移動機器人在作業(yè)時，對環(huán)境的適應和理解能力仍有不足，提出采取人機協(xié)同控制來適應環(huán)境，提高移動機器人作業(yè)效率的方案.在進行人機協(xié)同控制之前，機器人的路徑規(guī)劃問題是第一個要解決的問題.路徑規(guī)劃是為了讓機器人在一定的約束條件下（距離最短，耗時最小等），從起始地點向終點移動，最終找到一條可行路徑[1].

目前，按照對周圍環(huán)境信息是否已知，將路徑規(guī)劃問題分成全局、局部規(guī)劃兩類.當環(huán)境已知時，可采用可視圖法、自由空間法、柵格法等.反之，就需借助傳感器獲取環(huán)境信息，并對機器人進行局部路徑規(guī)劃.常用的局部規(guī)劃方法有人工勢場法[2]、速度分解法、神經(jīng)網(wǎng)絡算法等.但是它們都由于自身的局限性和獨特性而無法通用.遺傳算法依靠其自身較強的全局搜索能力、強適應力、靈活性、魯棒性等在路徑規(guī)劃方面有一定的成果，但也存在容易得到“最優(yōu)解”和易陷入局部最優(yōu)的缺點.文獻[3]改進了傳統(tǒng)遺傳算法中的交叉和變異算子，增強了全局和局部搜索能力，提高了算法計算效率，但在復雜環(huán)境下效果一般.文獻[4]通過生成可行路徑輔助點的方法加速遺傳算法收斂，但是其采用二維實數(shù)編碼，這樣做使得編碼方式與一維實數(shù)編碼相比更復雜，隨著種群的增加，增加了系統(tǒng)的存儲量，使后續(xù)計算更復雜[5]，使尋優(yōu)速度下降.

本文將采用先全局再局部的規(guī)劃方法，采用傳感器感知環(huán)境信息，并對遺傳算法[6]進行以下改進：優(yōu)化初始種群，使其開始就獲得比較好的父代，根據(jù)要求建立適應度函數(shù)，優(yōu)化選擇、交叉、變異算子，通過災變防止遺傳算法過早得到“最優(yōu)解”.最后結(jié)合實際發(fā)現(xiàn)其在狹窄、路況不佳的路段，機器人無法自主找到真正的最優(yōu)解，于是提出人機協(xié)同控制，對其進行進一步優(yōu)化.

1 基于改進遺傳算法的機器人路徑規(guī)劃

遺傳算法的并行性，以及操作時的靈活性、適用性使其成為了一種被廣泛采用的算法[7].在進行路徑規(guī)劃時，將傳統(tǒng)的遺傳算法進行改進后，設(shè)計的流程圖如圖1所示.

圖1 改進遺傳算法的流程圖

第一步，確定種群中每個個體的編碼方式，并初始化種群；第二步，判斷是否滿足終止條件，若滿足終止條件則退出，并得到最優(yōu)解；第三步，若不滿足終止條件，則由適應度函數(shù)計算種群中各個個體的適應度；第四步，進行基本遺傳操作（選擇、交叉、變異）；第五步，進行有限次數(shù)的災變；第六步，生成新種群并轉(zhuǎn)到第二步，依次循環(huán).

1.1 環(huán)境建模和編碼處理

用柵格法[8]對移動機器人的移動空間進行二維環(huán)境建模[9]，其周圍環(huán)境信息（障礙數(shù)量、方位等）已知.為了方便建模，將其看成可以隨機移動的質(zhì)點.建立環(huán)境模型時，忽略機器人可以越過的障礙.白色部分為可以到達的區(qū)域，紅色部分為障礙物區(qū)域，記原點處柵格序號為1，每層按照從左到右遞增1的規(guī)律，依次標出各格柵的序號，相鄰的上、下層柵格中上層的柵格序號比下層的大15.設(shè)起點為S，終點為G，機器人的工作環(huán)境模擬圖如圖2所示.

圖2 機器人的工作環(huán)境模擬圖

編碼時采取一維實數(shù)編碼，該編碼方式跟二維編碼方式相比在存儲時減少了內(nèi)存的消耗，計算時也更簡單[10].記起始柵格序號為S，目標柵格序號為G，然后由N個點組成一條，則其中一條染色體如圖3所示.

圖3 路徑編碼圖

1.2 初始化種群優(yōu)化

隨機初始化種群，雖然使得種群可以多樣性，但會造成父代種群質(zhì)量偏低，減慢了求最優(yōu)解的速度.因此對該操作做出改進，即先產(chǎn)生一條可行路徑.記0區(qū)域為移動機器人當前所在的位置，其周圍柵格如圖4所示.

圖4 周圍柵格

具體方法如下：

第一步，選取機器人周圍{1，8，6，7}這4個柵格作為下一步所要到達的柵格，記下一步要到達的點到終點的距離為i，該點被選中的概率為pm.考慮到當前柵格位置可能處于最外圈，{1，8，6，7}當中會有一些柵格不存在，因此分成兩種情況.若下一步所要到達的點無法到達，記i=+∞，則pm=0.若下一步的點可以到達，則表示為

第二步，隨機生成一個兩位數(shù)n（n≠0），然后k=.選一個最接近概率值pm的柵格作為下一步的目標柵格.

第三步，若下一個柵格是可行柵格則跳到第一步繼續(xù)尋找下一個柵格.若當前找到的柵格為不可行柵格則淘汰當前柵格并不再使用，并轉(zhuǎn)到第二步.若備選的柵格都是障礙柵格，則全部淘汰并選擇新的方向柵格{2，3，4，5}，并轉(zhuǎn)到第一步計算被選中的概率pm.

第四步，判斷是否到達目標點，若到達，則保存當前路徑，并生成下一個個體直到到達種群規(guī)模.

1.3 適應度函數(shù)的建立

建立合適的適應度函數(shù)對提升遺傳算法的穩(wěn)定性有很大的幫助，不夠好的適應度函數(shù)會使算法無法快速地找到最優(yōu)解甚至陷入局部最優(yōu).適應度值大小反映了路徑的優(yōu)良程度且與其成正比[11].為了更快地到達目標點，改進后的適應度函數(shù)為

l為起始點到目標點的路徑長度，其具體公式為

式中：xi表示第i個點的橫坐標；xi+1表示第i+1個點的橫坐標；yi表示第i個點的縱坐標；yi+1表示第i+1個點的縱坐標.

1.4 遺傳算子的設(shè)計

1.4.1 選擇算子的設(shè)計

選擇操作是為了保證種群內(nèi)優(yōu)秀的基因得以留存.輪盤賭法使得個體適應度大的容易被選擇，但是由于其隨機性可能導致種群中適應度差的個體易被選擇.因次，若單一的采用輪盤賭法并不可靠，因此提出了一種改進方案，在首次選擇時先進行錦標賽選擇法，取2個個體進行比較，并保留具有最高適應度的個體.在下次選擇時采用輪盤賭法進行選擇，并與上一次留下的個體進行適應度比較，大的保留并進行下一輪選擇，在后面選擇時，都須采取此種策略[12].

1.4.2 交叉算子的設(shè)計

交叉算子的設(shè)計是為了提升子代基因的優(yōu)良程度，即在繁殖時，保留較好的基因.目前交叉方式有多點交叉、單點交叉[13]、部分映射交叉等.采用除起點外第一個相同的點進行單點交叉，是為了盡可能保證路徑的連續(xù)性和可行性.在交叉時隨機兩兩交叉然后父子代個體按照適應度值排序，設(shè)置一定的淘汰率如10%，使種群更好地朝著最優(yōu)方向發(fā)展.

1.4.3 變異算子的設(shè)計

由于變異具有不確定性，可能使得原本可以通過的線路在變異后無法通過，結(jié)果如圖5所示.

圖5 不確定變異圖

為了保障路徑的可行性，采用一種改進的變異策略.隨機選擇可行路徑上的某一柵格（除起點、終點外），將其視為障礙柵格并刪除，然后原路徑就會一分為二，含有起點的路徑稱為前向路徑，含有終點的路徑稱為后向路徑，最后重新尋找一條連接路徑將之前得到的兩條獨立路徑連接，就能得到一條完整的可行路徑.連接路徑的起點就是前向路徑的終點，連接路徑的終點就是后向路徑的起點.連接路徑的尋找策略：采用本文1.2初始化種群優(yōu)化的策略來得到一條連接路徑.

1.4.4 自適應交叉、變異策略

自適應遺傳算法[14]使得種群進化時對交叉、變異率的選取更加科學.因為在進化前期，一定的交叉、變異率將會讓種群朝著更好的方向發(fā)展，但是在種群進化后期，固定的交叉、變異率就會顯得過高，從而使得本已優(yōu)秀的個體進行不穩(wěn)定的進化，反而使得種群退化.

傳統(tǒng)的余弦自適應交叉、變異函數(shù)如下

式（4）-（5）中：Pc、Pm為選取的交叉率、變異率；Pcmax、Pcmin為交叉率的最大值、最小值；Pmmax、Pmmin為變異率的最大值、最小值；fmin、fmax是種群當中最差、最優(yōu)個體的適應度值；favg為種群的平均適應度值；f為當前個體的適應度值；f′為兩個個體進行交叉操作時，適應度值較大者的適應度值.

logistic函數(shù)如下

logistic函數(shù)在起始階段和末尾階段有著很好的平滑度，這兩個階段的函數(shù)值的減小速度十分緩慢，logistic函數(shù)值都在0到1的范圍內(nèi)，跟交叉率與變異率的取值范圍一致.因此可以引入該函數(shù)來優(yōu)化余弦自適應遺傳策略.

在種群實際進化時，隨著迭代的進行，交叉率、變異率不斷變化，種群在不斷進化.因此，在自適應公式中加入迭代次數(shù)這個因素很有必要.改進后的自適應交叉、變異函數(shù)如下

式中：ic為當前迭代次數(shù)，且從1開始；im為迭代次數(shù)上限；λ為衰減系數(shù).

該公式說明在進化后期，種群個體不斷趨于最優(yōu)時，隨著迭代次數(shù)的增加，變異率在不斷地衰減.

上述提到的兩種自適應遺傳策略進行對比時，二者的交叉率與變異率曲線變化趨勢一致，因此只要比較該自適應函數(shù)與余弦自適應函數(shù)的變異率變化曲線的優(yōu)缺點就能類推二者交叉率變化曲線的優(yōu)缺點.變異率變化曲線如圖6所示.

圖6 logistic自適應和余弦自適應變異率變化曲線

通過分析圖6，發(fā)現(xiàn)改進的自適應遺傳策略在種群進化前期，即適應度值在區(qū)間[favg，（favg+fmax）/2]的個體變異率高于余弦自適應遺傳策略的變異率，在種群進化前期保持較高的變異率，有利于種群的進化；在種群進化的穩(wěn)定階段，即適應度值在區(qū)間[（favg+fmax）/2，fmax]改進的自適應遺傳策略的個體變異率要小于余弦自適應遺傳策略的變異率，在種群進化后期，較低的變異率有利于保護種群當中的優(yōu)良個體.另外，其變異率的減小速度與余弦自適應遺傳策略相比也更平穩(wěn).這樣分布的變異率說明本算法更加科學.

1.4.5 災變算子

災變[15]就是殺死種群內(nèi)最優(yōu)的個體，使得種群遠離局部最優(yōu)，避免了種群過早得到“最優(yōu)解”，同時也使得種群更加多樣化.但是如果種群一直在經(jīng)歷無限次的災變，那么種群將無法得到最優(yōu)個體，種群的結(jié)構(gòu)也會被破壞，種群會無法進化，這樣做顯然是不可取的.因此本文設(shè)置了最大的災變次數(shù)如下

設(shè)計的災變公式如下

式中：INT表示取整操作；n表示種群大?。籑表示種群進行災變時設(shè)置的計數(shù)器的初始計數(shù)值，當發(fā)生災變時，M值就會減1.如果M值在沒有變成0之前就產(chǎn)生了新的最優(yōu)個體，取當前M值記為cnt，并引入權(quán)重系數(shù)γ，γ取1.5.重新設(shè)置新的計數(shù)值為M′，不斷重復災變過程直到達到災變次數(shù)的最大值.

1.5 未協(xié)同時的路徑規(guī)劃模擬仿真

設(shè)3種算法的最大迭代次數(shù)im為180，種群大小n為200.第一種算法為一般遺傳策略，交叉率為0.4，變異率為0.04，后兩種算法分別為余弦自適應遺傳策略以及改進的自適應遺傳策略，Pcmax為0.4，Pcmin為0.3，Pmmax為0.08，Pmmin為0.04.一般遺傳策略、余弦自適應遺傳策略、改進的自適應遺傳策略路徑模擬圖和各自的迭代次數(shù)與路徑長度關(guān)系圖如圖7-12所示.

分析圖7、9、11發(fā)現(xiàn)一般遺傳策略的路徑存在明顯的缺陷（柵格113、128），由圖8、10、12可知，一般遺傳策略在第75次迭代才找到最短路徑，比余弦自適應策略多了約42次，比改進的自適應策略多了約60次，且改進的自適應遺傳策略最優(yōu)路徑起始距離最短.為了確保實驗的可靠性分別對每種算法進行15次測試，統(tǒng)計后的數(shù)據(jù)如表1所示.

表1 各算法測試結(jié)果

圖7 一般遺傳策略路徑模擬仿真圖

圖8 一般遺傳算法迭代次數(shù)與路徑長度關(guān)系圖

圖9 余弦自適應遺傳策略路徑模擬仿真圖

圖10 余弦自適應遺傳算法迭代次數(shù)與路徑長度關(guān)系圖

圖11 改進的自適應遺傳策略路徑模擬仿真圖

圖12 改進的自適應遺傳算法迭代次數(shù)與路徑長度關(guān)系圖

通過對表1數(shù)據(jù)的分析，發(fā)現(xiàn)改進的自適應遺傳算法在平均穩(wěn)定迭代次數(shù)近似值、平均最短路徑近似值等方面都比一般遺傳算法要好而且跟第二種算法相比其能更快地穩(wěn)定，所找到的最短路徑變化相對穩(wěn)定，所需時間也短于其他兩種算法.

2 協(xié)同控制處理

人機協(xié)同[16]的關(guān)鍵在于由人和機器一起控制，采用遠、近端控制機器人的方法代替機器人自主規(guī)劃路徑.人機控制界面用Python和Eric6設(shè)計完成，主要采取4種工作模式.

第一種為主從模式，全程由遠端操作人員根據(jù)傳回的現(xiàn)場圖像進行遠程遙控.

第二種為全自動模式（未進行協(xié)同控制），操作人員先在遠端設(shè)定好起始位置和終止位置，通過計算機生成最優(yōu)路徑，然后把規(guī)劃好的路徑傳送給移動機器人，移動機器人再通過自身解析變成各種運行命令，最后移動機器人按照規(guī)劃好的路線運行.

第三種為監(jiān)控半自動模式（采用人機協(xié)同控制），監(jiān)控半自動模式跟全自動模式類似，是在全自動模式運行的基礎(chǔ)上加上監(jiān)控.當遠端操作人員覺得當前路徑不可行時，可以按照人機交互界面上的控制按鈕進行控制，重新規(guī)劃路徑.

第四種為關(guān)鍵點監(jiān)控模式，當環(huán)境數(shù)據(jù)采集機器人要進行作業(yè)時，一定會對移動機器人運行環(huán)境內(nèi)多處位置進行數(shù)據(jù)采集，那么這些點就是路徑關(guān)鍵點.遠端操作人員擬合這些路徑關(guān)鍵點并設(shè)計出一條可行路徑.

第五種為語音控制模式，在以上控制模式的基礎(chǔ)上加入了語音控制，近端人員根據(jù)現(xiàn)場環(huán)境控制移動機器人運動.為了防止在控制移動機器人運行時出現(xiàn)順序錯亂的問題，設(shè)置語音模式優(yōu)于其他控制模式.

實驗場景如圖13所示.

圖13 實驗場景圖

2.1 實驗內(nèi)容及過程

（1）設(shè)置移動機器人的起始點S和目標點G，獲取移動機器人當前的環(huán)境信息（障礙物的位置、障礙物的數(shù)量等），用膨脹法對障礙物進行處理，即將小于一格柵格的障礙柵格變?yōu)橐徽駯鸥?，記障礙柵格為紅色，自由柵格為白色，采用15×15大小的柵格來表示移動機器人的運行環(huán)境.在環(huán)境建模時，假設(shè)柵格195、柵格210為環(huán)境復雜的路段（路況差、存在不停移動的障礙、有人攔路等情況，在初始環(huán)境模擬圖上未進行特殊標注），在未經(jīng)過人為判斷時，機器人認為其能通過，實際上無法通過，其初始環(huán)境模擬圖如圖14所示.

圖14 初始環(huán)境模擬圖

（2）采用全自動模式（未進行人機協(xié)同控制）以及監(jiān)控半自動模式（人機協(xié)同控制模式）分別進行10次實驗并對周圍環(huán)境數(shù)據(jù)采集.

（3）對人機協(xié)同實驗的結(jié)果進行分析.

2.2 實驗結(jié)果分析

采用全自動模式時，某一次實驗過程中的上位機界面如圖15所示.

圖15 全自動模式下的上位機界面圖

采用監(jiān)控半自動模式時，某一次實驗過程中的上位機界面如圖16所示.

圖16 監(jiān)控半自動模式下的上位機界面圖

采用上述兩種模式進行10次實驗后得到的數(shù)據(jù)結(jié)果如表2所示.

表2 10次實驗數(shù)據(jù)結(jié)果

采取上述兩種控制模式下的運動軌跡對比圖如圖17所示.

通過觀察分析表2中的數(shù)據(jù)，可以發(fā)現(xiàn)：當采取監(jiān)控半自動模式時，移動機器人均避過了環(huán)境復雜路段，而在全自動模式下的10次實驗里只有3次避過了環(huán)境復雜路段.通過分析圖17，發(fā)現(xiàn)全自動模式下移動機器人規(guī)劃的路徑將柵格195、210視為無障礙路段，與實際不符，且經(jīng)過了環(huán)境復雜路段195、210，實際上應避過這些路段.而監(jiān)控半自動模式下，移動機器人通過人的決策，會將上述兩個柵格當作障礙柵格，從而避過了障礙物，安全到達了目標點.通過上述分析可以證明當移動機器人采取人機協(xié)同控制時，機器人可更好地在復雜的環(huán)境當中進行作業(yè).

圖17 未協(xié)同和協(xié)同控制路徑軌跡對比圖

3 結(jié)語

在進行人機協(xié)同控制之前，需先進行路徑規(guī)劃.在路徑規(guī)劃時，為了解決遺傳算法過早得到“最優(yōu)解”、易陷入局部最優(yōu)、收斂速度慢的問題，提出了一種改進的自適應遺傳算法.對適應度函數(shù)、種群初始化、傳統(tǒng)遺傳算子進行了優(yōu)化，并引入災變算子，設(shè)計自適應變異，通過仿真證明了該算法的可行性.在利用機器人進行數(shù)據(jù)采集和預警作業(yè)時，為了使其更好適應復雜多變的實際環(huán)境，以及提高機器人作業(yè)時的效率，提出采取多模式人機協(xié)同控制，在實驗中發(fā)現(xiàn)采用人機協(xié)同控制的機器人能夠更好地完成作業(yè)，證明了該方法的有效性.