基于改進遺傳算法的多直角貼裝機器人路徑協同規劃

陳 寶，田 斌，周占偉，陳 靜，陳雪婷，李經民

(1.大連理工大學 遼寧省微納米技術及系統重點實驗室，遼寧 大連 116024；2.北京衛星制造廠有限公司，北京 100048)

0 引言

復合結構板的尺寸較大，若采用傳統單機器人帶多貼片頭的方式進行貼片，將產生過多往復取片的空行程，大大降低機器人貼片效率[1，2]；若采用多直角貼裝機器人協同貼片雖能滿足需求，但需采用遺傳算法進行協同路徑規劃。

采用傳統遺傳算法進行協同路徑規劃存在易陷入局部最優解和早熟的問題，目前雖然一些學者針對遺傳算法存在的問題進行了改進與優化，如引入局部算子[3]、最小準則[4]、災變算子[5]、自適應交叉和變異算子[6]等，但是針對多直角貼裝機器人共用X軸且貼裝環境復雜的情況，以上算子在編碼、避免碰撞、收斂速度等方面仍有提高空間。

本文充分考慮多機器人碰撞的問題，建立多直角貼裝機器人協同貼片的數學模型，引入碰撞懲罰、分組進化、部分匹配交叉、自適應變異算子對遺傳算法進行改進，并采用MATLAB對3個直角機器人協同路徑規劃問題進行仿真實驗。

1 多直角貼裝機器人協同貼片數學模型建立

圖1為3個直角貼裝機器人在復合結構板上的分布情況，并以此建立數學模型。

圖1 3個直角貼裝機器人在復合結構板上的分布

將直角貼裝機器人看做是多旅行商問題中的旅行商，復合結構板上的貼片點看做是城市集合。定義如下：總共有3個直角貼裝機器人，N個待貼片點，每個貼片點有被貼片且只被貼一次。由于貼裝效率的高低取決于所有直角貼裝機器人走的路徑總長度，因而本文的優化目標是使得機器人走的路徑總長度D最短，建立的數學模型為：

.

(1)

約束條件為：

xijk∈{0,1}.

(2)

(3)

(4)

(5)

式(3)確保每一個需貼片點都被貼上料片；式(4)和式(5)確保每個貼片點只被貼一次。

2 改進的遺傳算法

2.1 編碼與生成初始種群

由于復合結構板上的貼裝區域類似于柵格地圖，因而可以將貼裝區域用柵格地圖表示，如圖2所示。

圖2中,白色區域表示貼片區域，黑色區域表示障礙物，每1格代表貼1片40 mm×40 mm料片，半格為貼1片40 mm×20 mm料片，并將貼片點按順序以數字集E=1,2,3,…，N編號。將貼片點編號隨機分配給3個機器人，以此生成一條染色體。重復此過程，生成種群池所需數量的染色體，以這些染色體組成初始種群，存儲到三維矩陣中，如圖3所示。

圖2 柵格地圖

圖3 初始種群三維矩陣

2.2 基于時間序列的碰撞懲罰適應度函數

本文是選用3個機器人進行協同貼片，采用遺傳算法優化路徑，并且路徑不可產生碰撞，否則將造成設備的損壞。因而選取直角貼裝機器人總路徑長度D的倒數作為適應度函數的一個分量f1：

(6)

可通過加速度函數反計算得到某個直角坐標機器人在任意時刻的位置集合Pk={Pk1,Pk2,…Pkn}，重復此過程，可得到各機器人的時間序列總集合{P1,P2,P3}。如果3個機器人的時間序列交集M為空集，則碰撞懲罰系數ui為1，否則為0，將其作為適應度函數的另一個分量：

M=P1∩P2∩P3.

(7)

(8)

綜合式(6)和式(8)，本文遺傳算法所構造的適應度函數為：

minf=ui·f1.

(9)

2.3 基于分組進化的選擇算子

本文在傳統遺傳算法基礎上引入分組的思想，將總種群分為精英組、優質解組以及劣質解組進行分組進化。首先對初始種群按照適應度值進行排序，選出適應度值最靠前的幾個解放入精英組，不參與后續遺傳操作直接放入下一代新種群；選出適應度值排名前半部分(除去精英組成員)的解放入優質解組，后續采用單點交叉和單點變異；剩余的解則放入劣質解組，后續采用單點交叉和多點變異。

2.4 部分匹配交叉算子

結構板上每個貼片點必須保證有且只有一次訪問，因而需采用部分匹配交叉算子來保證這一約束條件。部分匹配交叉算子類似于單點交叉算子，隨機生成一個交叉點，將交叉點之后的交叉區域進行交換。此時，生成的兩條染色體一般存在重復和缺失的基因，為了修復染色體需要在交叉區域內建立基因的映射關系，根據此關系消除重復基因和增加缺失基因，操作過程如圖4所示。

圖4 部分匹配交叉算子操作過程

2.5 自適應變異算子

遺傳算法前期主要通過交叉算子產生新的優良染色體，需要采用低的變異概率來保持，從而實現優良個體的快速積累；到算法后期由于種群全是類似的染色體，如若還是采用靜態變異概率，則算法易陷入局部最優解。因而，本文采用一種自適應變異算子，隨著當前進化代數g從1增大到最大進化代數gmax，變量t逐步從0增大到1，與此同時變異概率Gm也逐步增大到初始變異概率Gm0的2倍，從而產生更多新個體，提高種群豐富度，避免陷入局部最優解，即：

(10)

Gm=Gm0·2t.

(11)

3 仿真實驗與結果分析

3.1 實驗準備與參數設計

根據本文的算法，采用MATLAB程序對3個直角貼裝機器人進行協同路徑規劃仿真實驗。機械硬件采用直線電機組成的直角坐標機器人，速度為2 m/s，加速度為12 m/s2；每個機器人Z軸末端都帶有兩個真空吸盤，復合結構板如圖2所示。

電腦開發環境為Win11和MATLAB2020a。仿真設定的種群規模為500，最大迭代次數為600；精英解組選擇概率為0.01；優質解組的交叉概率為0.8，初始變異概率為0.1；劣質解組交叉概率為0.9，初始變異概率為0.2。

3.2 實驗結果與分析

采用傳統遺傳算法和本文改進遺傳算法得到的路徑優化曲線如圖5所示。

圖5 遺傳算法優化曲線

由圖5可知，采用本文的改進遺傳算法在389代得到長118 196 mm的最優路徑，而采用傳統遺傳算法在526代得到局部最優解，路徑長度為124 383 mm。本文遺傳算法較傳統平均分配貼片區域的路徑長度152 771 mm優化了22.6%，較傳統遺傳算法路徑長度優化了4.9%，收斂速度加快26.1%。

圖6為3個機器人最優路徑的時間序列曲線,可以看出，任意時刻的3條曲線都沒有交點，表明3個機器人在協同貼裝結構板的過程中不會發生碰撞。

圖6 3個機器人最優路徑的時間序列曲線

4 結論與展望

本文針對多直角貼片機器人協同路徑規劃的問題，提出了適合本問題的帶有碰撞懲罰、分組進化、部分匹配交叉和自適應變異的改進遺傳算法。經3個直角貼裝機器人仿真實驗得到，本算法相對平均分配貼片區域，降低了路徑長度；相對傳統遺傳算法，加快收斂速度，不易陷入局部最優解。接下來將著重于研究加入其他交叉算子和變異算子，以進一步提高算法的收斂速度和穩定性；或者研究本算法在其他種類貼片機器人協同路徑規劃中的應用。