遺傳算法在農業移動機器人路徑規劃中的應用——基于矩陣二進制編碼

薛文奎

(常州機電職業技術學院，江蘇 常州 213164)

0 引言

農業移動機器人技術的最終目標是設計能夠自主規劃運動的自動機器人，因此來運動規劃問題受到了該領域研究人員的廣泛關注。一般而言，機器人運動規劃問題是一個復雜而困難的問題。例如，真實環境中的機器人能夠進行三維平移和旋轉。通常，農業移動機器人的位置由與其自由度數量的多個參數來指定，運動規劃的理論復雜度是機器人自由度數量的指數函數，這就是高自由度機器人難以解決的問題。為此在自然啟發式遺傳算法的基礎上，結合矩陣二進制編碼技術，探討了一種解決自主機器人系統的路徑規劃與導航問題的方法。

1 矩陣二進制編碼的遺傳算法的實現

農業移動機器人在移動過程中沒有絕對的最優路線，在對其進行路徑規劃過程中，一般是需要以最小代價計算出最優的路徑。因此，本文采用基于矩陣二進制編碼的遺傳算法，用于搜索農業移動機器人路徑導航和規劃的最佳路徑。本文提出的基于矩陣二進制編碼的遺傳算法，在導航和路徑規劃中能夠對一系列的移動操作進行排序，從而使其在目標搜索中成功避障，通過該算法可以容易地實現農業移動機器人的實時決策、導航和路徑優化。矩陣二進制編碼的遺傳算法的有效性取決于遺傳染色體及其操作者。該算法通過對雜交、變異、競爭、選擇和變量的分組分析，實現矩陣編碼的變形及適應度的求取，從而使該遺傳結構成為實現最佳適應性決策的基礎。農業移動機器人采集其左邊(LOD，Left Obstacle Distance)、前邊(FOD，Front Obstacle Distance)和右邊(ROD，Right Obstacle Distance)的障礙物距離作為數據輸入(見圖1)，然后以航向角(HA，Heading Angle)的形式給出輸出，從而實現避障的過程。該轉換過程的核心主要包括生成編碼、適應度函數、交叉和變異等4部分。

圖1 障礙物位置示意圖

1.1 矩陣二進制編碼的生成

設置矩陣二進制編碼的總集合P={P1，P2，…，Pn}。其中，Pi中染色體數目為5，元素結構為(i，j)，則該二進制編碼的矩陣為

(1)

其中，矩陣P的各列表示遺傳算法結構的各個特征，具體為

(2)

其中，SC為轉換符號。矩陣二進制編碼的生成層的數學分析方法為：設定一個如下所示的新集合，即

S={FOD,LOD,ROD,HA,SC}

(3)

在公式(3)中，線性獨立性是必需的，該集合避免了具有線性相關特性的元素。假設集合中的矢量都不能被表示為其他矢量的線性組合，則稱該集合是線性無關的，因此FOD、LOD、ROD、HA和SC組成的集合S被稱為線性無關。

Pi,jFOD+Pi,jLOD+Pi,jROD+

Pi,jHA+Pi,jSC=0

(4)

假如一組矢量不是線性獨立的，那么它們被稱為線性相關。

1.2 矩陣二進制編碼的適應度函數

適應度函數是遺傳算法進化的關鍵，適應度函數的生成和合理性對于實現導航和路徑規劃的最佳決策至關重要。農業移動機器人的避障機制和最優路徑生成的效率取決于適應度函數的精度。該控制算法遵循最佳功能為

fTotal=(c1,c2,c3,c4,c5)Tr(p)

(5)

其中，Tr(p)為跡線，即p的對角元素之和。

Tr(p)的表達式為

(6)

(7)

假設目標角度是TA，航向角度是HA，那么最適合的群體為(cFOD-pci,1)、(cLOD-pci,2)和(cROD-pci,3)。

矩陣二進制編碼的適應度函數數學分析方法為：基于FOD、LOD和ROD的線性無關集合主要由以下相應的向量建立，即

S={cFOD,cLOD,cROD}

(8)

若集合中的矢量都不能被表示為其他矢量的線性組合，則稱該集合S是線性無關的；反之，則稱為線性無關。

Pci,jcFOD+Pi,jLOD+Pi,jROD=0

(9)

如果一組矢量不是線性獨立的，那么它們被稱為線性相關。

1.3 矩陣二進制編碼的交叉

矩陣二進制編碼的交叉主要是對概率分布進行研究，在該過程中，最初從選擇的群體中選擇染色體，按某種方式單點交叉兩個父親染色體，產生兩條后代染色體。基于矩陣二進制編碼的遺傳算法在農業移動機器人路徑規劃中，主要是對到達新位置航向角的決策變量進行判斷。二值向量{0,1}及語言變量為FOD、ROD及LOD編碼的交叉為

進行矩陣二進制編碼的交叉層的數學分析，交叉表達式為

如果一組矢量不是線性獨立的，那么它們被稱為線性相關。

1.4 矩陣二進制編碼的變異

基因組合負責著每一個遺傳操作，染色體的變化率常由變異算子測量和引用，變異算子為農業移動機器人避障行為提供參考。一般而言，一對一對應的序列校正被稱為突變操作，突變的過程被描述為一個隨機數。具體解釋如下：

假設變異向量集為λ={λ1,λ2,...,λn}，染色體集合為c={c1,c2,...,cn}。令f(λ)為一個變異算子，其映射從λ到c，如圖2所示。

圖2 變異向量和染色體向量映射示意圖

chromosome vector mapping

在分析時，域為λ，共域為c，f的范圍為f(λ)。從遺傳基因的觀點來看，該假設是根據基因的自然行為來執行操作。對于該突變過程，染色體的位置可以由以下矩陣表示，即

(10)

(11)

因此，變異算子向量為

D={D1,D2,…Dn}

(12)

進行矩陣二進制編碼的變異層的數學分析，采用式(12)中的元素向量來定義新集合為

S={D1,D2,…Dn}

(13)

若集合中的矢量都不能被表示為其他矢量的線性組合，則稱該集合S是線性無關的；反之，則稱為線性無關。

λiD1+λiD2+…λiDn=0

(14)

如果一組矢量不是線性獨立的，那么它們被稱為線性相關。

根據基于矩陣二進制編碼的遺傳算法，任何農業移動機器人的工作環境都可以從混沌轉變為一個個陣列，然后實現導航和路徑規劃。

2 農業移動機器人路徑規劃問題分析

本章將詳細闡述農業移動機器人運動路徑規劃問題。假設農業移動機器人的運動環境為E，也就是將障礙物和機器人運動環境視為E，E中的所有障礙物集合為O，其定義為

O={o1,o2,…,om}

(15)

其中，oi為農業移動機器人運動環境中的第i個障礙物。另外，農業移動機器人禁止移動的空間被定義為

(16)

其中，Sforb為E中所有障礙物的結合體。

農業移動機器人能夠自由移動的空間用S自由表示，其定義為

Sfree=ESforb

(17)

農業移動機器人運動環境和Sfree集合如圖3所示。其中，白色區域為Sfree，灰色區域為Sforb。

圖3 農業移動機器人障礙物和自由區域示意圖

agricultural mobile robots

前面介紹農業移動機器人運動規劃問題的符號含義，具體定義為

(18)

其中，T(pstart,ptarget)為開始(pstart)和目標點(ptarget)之間的最佳路徑；集合Γ為Sfree集合中pstart與ptarget之間的所有可行路徑。此外，d(p)表示路徑P的長度，其計算公式為

(19)

其中，‖pi-pi-1‖為點pi和pi-1之間的歐氏距離。

(20)

其中，(xi,yi)為pi的坐標。

通過上述要點，能夠將機器人運動規劃優化問題轉換成建模問題。

3 農業移動機器人路徑規劃仿真分析

前文介紹了矩陣二進制的遺傳算法在農業移動機器人路徑規劃中的潛力。本章在具有I7處理器(3GHz)、8GB RAM、500GB硬盤、Windows7(64位)OS和NVIDIA(1GB)圖形卡的PC上進行了MatLab仿真分析。在模擬過程中，農業移動機器人不知道環境中障礙物的位置。最初，農業移動機器人僅提供了有關其起始位置和目標位置的信息。在模擬過程中，農業移動機器人顯示為一個小圓圈，并裝載有傳感器模塊來計算FOD、LOD、ROD和HA。農業移動機器人作業環境如圖4所示。其中，黑色部分為障礙物。試驗中，二維空間的作業區域的起點位置為start，終點位置為target。

圖4 農業移動機器人作業環境示意圖

機器人開始移動直到達到目標，且在環境無障礙時無需激活矩陣二進制編碼的遺傳算法；但當障礙物進入機器人的路徑時，它會激活二進制編碼的遺傳算法以避免障礙物。農業移動機器人在靜態環境中各種初始位置和目標位置的路徑規劃，通過反復迭代學習，不斷逼近，求出了兩種不同模型區域的最優運動軌跡。仿真求最優軌跡的實驗結果如圖5所示。農業移動機器人通過激活矩陣二進制編碼的遺傳算法作為智能機制來觀察路徑中存在的障礙物并產生無障礙軌跡。

仿真結果顯示了農業移動機器人在存在復雜障礙物的情況下的路徑規劃與導航。當農業移動機器人觀察其路徑上的移動障礙物時，會調整速度，有時會停下來做出決定。采用矩陣二進制編碼的遺傳算法進行路徑規劃中，其迭代次數如圖6所示。

圖5 Matlab仿真實驗結果

圖6 農業移動機器人路徑規劃迭代次數

圖6顯示了本文采用的矩陣二進制編碼的遺傳算法對圖4中移動環境迭代次數的行為。其中，x為迭代次數，y軸為100次實驗中的平均值和最佳適應值。

由圖6可以看出：針對兩種障礙物與路徑不同的模型區域，農業移動機器人成功地求解出從開始到結尾并成功躲避障礙物的最優軌跡規劃。根據多次實驗對比，所求路徑是該條件下機器人穿過障礙物耗時最少、運動代價最小的路線。

4 結論

基于矩陣二進制編碼的遺傳算法，通過采集左邊、前邊和右邊的障礙物距離作為數據輸入，輸出追蹤最佳路徑長度和導航時間，形成最優矩陣決策，實現農業移動機器人和目標之間的映射關系。仿真實驗結果表明：農業移動機器人在存在復雜障礙物的情況下能夠實現路徑規劃與導航，且所求路徑是該條件下機器人穿過障礙物耗時最少、運動代價最小的路線。