遺傳算法在農(nóng)業(yè)移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用——基于矩陣二進(jìn)制編碼

薛文奎

(常州機(jī)電職業(yè)技術(shù)學(xué)院，江蘇 常州 213164)

0 引言

農(nóng)業(yè)移動(dòng)機(jī)器人技術(shù)的最終目標(biāo)是設(shè)計(jì)能夠自主規(guī)劃運(yùn)動(dòng)的自動(dòng)機(jī)器人，因此來(lái)運(yùn)動(dòng)規(guī)劃問(wèn)題受到了該領(lǐng)域研究人員的廣泛關(guān)注。一般而言，機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題是一個(gè)復(fù)雜而困難的問(wèn)題。例如，真實(shí)環(huán)境中的機(jī)器人能夠進(jìn)行三維平移和旋轉(zhuǎn)。通常，農(nóng)業(yè)移動(dòng)機(jī)器人的位置由與其自由度數(shù)量的多個(gè)參數(shù)來(lái)指定，運(yùn)動(dòng)規(guī)劃的理論復(fù)雜度是機(jī)器人自由度數(shù)量的指數(shù)函數(shù)，這就是高自由度機(jī)器人難以解決的問(wèn)題。為此在自然啟發(fā)式遺傳算法的基礎(chǔ)上，結(jié)合矩陣二進(jìn)制編碼技術(shù)，探討了一種解決自主機(jī)器人系統(tǒng)的路徑規(guī)劃與導(dǎo)航問(wèn)題的方法。

1 矩陣二進(jìn)制編碼的遺傳算法的實(shí)現(xiàn)

農(nóng)業(yè)移動(dòng)機(jī)器人在移動(dòng)過(guò)程中沒(méi)有絕對(duì)的最優(yōu)路線，在對(duì)其進(jìn)行路徑規(guī)劃過(guò)程中，一般是需要以最小代價(jià)計(jì)算出最優(yōu)的路徑。因此，本文采用基于矩陣二進(jìn)制編碼的遺傳算法，用于搜索農(nóng)業(yè)移動(dòng)機(jī)器人路徑導(dǎo)航和規(guī)劃的最佳路徑。本文提出的基于矩陣二進(jìn)制編碼的遺傳算法，在導(dǎo)航和路徑規(guī)劃中能夠?qū)σ幌盗械囊苿?dòng)操作進(jìn)行排序，從而使其在目標(biāo)搜索中成功避障，通過(guò)該算法可以容易地實(shí)現(xiàn)農(nóng)業(yè)移動(dòng)機(jī)器人的實(shí)時(shí)決策、導(dǎo)航和路徑優(yōu)化。矩陣二進(jìn)制編碼的遺傳算法的有效性取決于遺傳染色體及其操作者。該算法通過(guò)對(duì)雜交、變異、競(jìng)爭(zhēng)、選擇和變量的分組分析，實(shí)現(xiàn)矩陣編碼的變形及適應(yīng)度的求取，從而使該遺傳結(jié)構(gòu)成為實(shí)現(xiàn)最佳適應(yīng)性決策的基礎(chǔ)。農(nóng)業(yè)移動(dòng)機(jī)器人采集其左邊(LOD，Left Obstacle Distance)、前邊(FOD，F(xiàn)ront Obstacle Distance)和右邊(ROD，Right Obstacle Distance)的障礙物距離作為數(shù)據(jù)輸入(見(jiàn)圖1)，然后以航向角(HA，Heading Angle)的形式給出輸出，從而實(shí)現(xiàn)避障的過(guò)程。該轉(zhuǎn)換過(guò)程的核心主要包括生成編碼、適應(yīng)度函數(shù)、交叉和變異等4部分。

圖1 障礙物位置示意圖

1.1 矩陣二進(jìn)制編碼的生成

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

(1)

其中，矩陣P的各列表示遺傳算法結(jié)構(gòu)的各個(gè)特征，具體為

(2)

其中，SC為轉(zhuǎn)換符號(hào)。矩陣二進(jìn)制編碼的生成層的數(shù)學(xué)分析方法為：設(shè)定一個(gè)如下所示的新集合，即

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

(3)

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

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

Pi,jHA+Pi,jSC=0

(4)

假如一組矢量不是線性獨(dú)立的，那么它們被稱(chēng)為線性相關(guān)。

1.2 矩陣二進(jìn)制編碼的適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是遺傳算法進(jìn)化的關(guān)鍵，適應(yīng)度函數(shù)的生成和合理性對(duì)于實(shí)現(xiàn)導(dǎo)航和路徑規(guī)劃的最佳決策至關(guān)重要。農(nóng)業(yè)移動(dòng)機(jī)器人的避障機(jī)制和最優(yōu)路徑生成的效率取決于適應(yīng)度函數(shù)的精度。該控制算法遵循最佳功能為

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

(5)

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

Tr(p)的表達(dá)式為

(6)

(7)

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

矩陣二進(jìn)制編碼的適應(yīng)度函數(shù)數(shù)學(xué)分析方法為：基于FOD、LOD和ROD的線性無(wú)關(guān)集合主要由以下相應(yīng)的向量建立，即

S={cFOD,cLOD,cROD}

(8)

若集合中的矢量都不能被表示為其他矢量的線性組合，則稱(chēng)該集合S是線性無(wú)關(guān)的；反之，則稱(chēng)為線性無(wú)關(guān)。

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

(9)

如果一組矢量不是線性獨(dú)立的，那么它們被稱(chēng)為線性相關(guān)。

1.3 矩陣二進(jìn)制編碼的交叉

矩陣二進(jìn)制編碼的交叉主要是對(duì)概率分布進(jìn)行研究，在該過(guò)程中，最初從選擇的群體中選擇染色體，按某種方式單點(diǎn)交叉兩個(gè)父親染色體，產(chǎn)生兩條后代染色體?；诰仃嚩M(jìn)制編碼的遺傳算法在農(nóng)業(yè)移動(dòng)機(jī)器人路徑規(guī)劃中，主要是對(duì)到達(dá)新位置航向角的決策變量進(jìn)行判斷。二值向量{0,1}及語(yǔ)言變量為FOD、ROD及LOD編碼的交叉為

進(jìn)行矩陣二進(jìn)制編碼的交叉層的數(shù)學(xué)分析，交叉表達(dá)式為

如果一組矢量不是線性獨(dú)立的，那么它們被稱(chēng)為線性相關(guān)。

1.4 矩陣二進(jìn)制編碼的變異

基因組合負(fù)責(zé)著每一個(gè)遺傳操作，染色體的變化率常由變異算子測(cè)量和引用，變異算子為農(nóng)業(yè)移動(dòng)機(jī)器人避障行為提供參考。一般而言，一對(duì)一對(duì)應(yīng)的序列校正被稱(chēng)為突變操作，突變的過(guò)程被描述為一個(gè)隨機(jī)數(shù)。具體解釋如下：

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

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

chromosome vector mapping

在分析時(shí)，域?yàn)棣?，共域?yàn)閏，f的范圍為f(λ)。從遺傳基因的觀點(diǎn)來(lái)看，該假設(shè)是根據(jù)基因的自然行為來(lái)執(zhí)行操作。對(duì)于該突變過(guò)程，染色體的位置可以由以下矩陣表示，即

(10)

(11)

因此，變異算子向量為

D={D1,D2,…Dn}

(12)

進(jìn)行矩陣二進(jìn)制編碼的變異層的數(shù)學(xué)分析，采用式(12)中的元素向量來(lái)定義新集合為

S={D1,D2,…Dn}

(13)

若集合中的矢量都不能被表示為其他矢量的線性組合，則稱(chēng)該集合S是線性無(wú)關(guān)的；反之，則稱(chēng)為線性無(wú)關(guān)。

λiD1+λiD2+…λiDn=0

(14)

如果一組矢量不是線性獨(dú)立的，那么它們被稱(chēng)為線性相關(guān)。

根據(jù)基于矩陣二進(jìn)制編碼的遺傳算法，任何農(nóng)業(yè)移動(dòng)機(jī)器人的工作環(huán)境都可以從混沌轉(zhuǎn)變?yōu)橐粋€(gè)個(gè)陣列，然后實(shí)現(xiàn)導(dǎo)航和路徑規(guī)劃。

2 農(nóng)業(yè)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題分析

本章將詳細(xì)闡述農(nóng)業(yè)移動(dòng)機(jī)器人運(yùn)動(dòng)路徑規(guī)劃問(wèn)題。假設(shè)農(nóng)業(yè)移動(dòng)機(jī)器人的運(yùn)動(dòng)環(huán)境為E，也就是將障礙物和機(jī)器人運(yùn)動(dòng)環(huán)境視為E，E中的所有障礙物集合為O，其定義為

O={o1,o2,…,om}

(15)

其中，oi為農(nóng)業(yè)移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境中的第i個(gè)障礙物。另外，農(nóng)業(yè)移動(dòng)機(jī)器人禁止移動(dòng)的空間被定義為

(16)

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

農(nóng)業(yè)移動(dòng)機(jī)器人能夠自由移動(dòng)的空間用S自由表示，其定義為

Sfree=ESforb

(17)

農(nóng)業(yè)移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境和Sfree集合如圖3所示。其中，白色區(qū)域?yàn)镾free，灰色區(qū)域?yàn)镾forb。

圖3 農(nóng)業(yè)移動(dòng)機(jī)器人障礙物和自由區(qū)域示意圖

agricultural mobile robots

前面介紹農(nóng)業(yè)移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題的符號(hào)含義，具體定義為

(18)

其中，T(pstart,ptarget)為開(kāi)始(pstart)和目標(biāo)點(diǎn)(ptarget)之間的最佳路徑；集合Γ為Sfree集合中pstart與ptarget之間的所有可行路徑。此外，d(p)表示路徑P的長(zhǎng)度，其計(jì)算公式為

(19)

其中，‖pi-pi-1‖為點(diǎn)pi和pi-1之間的歐氏距離。

(20)

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

通過(guò)上述要點(diǎn)，能夠?qū)C(jī)器人運(yùn)動(dòng)規(guī)劃優(yōu)化問(wèn)題轉(zhuǎn)換成建模問(wèn)題。

3 農(nóng)業(yè)移動(dòng)機(jī)器人路徑規(guī)劃仿真分析

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

圖4 農(nóng)業(yè)移動(dòng)機(jī)器人作業(yè)環(huán)境示意圖

機(jī)器人開(kāi)始移動(dòng)直到達(dá)到目標(biāo)，且在環(huán)境無(wú)障礙時(shí)無(wú)需激活矩陣二進(jìn)制編碼的遺傳算法；但當(dāng)障礙物進(jìn)入機(jī)器人的路徑時(shí)，它會(huì)激活二進(jìn)制編碼的遺傳算法以避免障礙物。農(nóng)業(yè)移動(dòng)機(jī)器人在靜態(tài)環(huán)境中各種初始位置和目標(biāo)位置的路徑規(guī)劃，通過(guò)反復(fù)迭代學(xué)習(xí)，不斷逼近，求出了兩種不同模型區(qū)域的最優(yōu)運(yùn)動(dòng)軌跡。仿真求最優(yōu)軌跡的實(shí)驗(yàn)結(jié)果如圖5所示。農(nóng)業(yè)移動(dòng)機(jī)器人通過(guò)激活矩陣二進(jìn)制編碼的遺傳算法作為智能機(jī)制來(lái)觀察路徑中存在的障礙物并產(chǎn)生無(wú)障礙軌跡。

仿真結(jié)果顯示了農(nóng)業(yè)移動(dòng)機(jī)器人在存在復(fù)雜障礙物的情況下的路徑規(guī)劃與導(dǎo)航。當(dāng)農(nóng)業(yè)移動(dòng)機(jī)器人觀察其路徑上的移動(dòng)障礙物時(shí)，會(huì)調(diào)整速度，有時(shí)會(huì)停下來(lái)做出決定。采用矩陣二進(jìn)制編碼的遺傳算法進(jìn)行路徑規(guī)劃中，其迭代次數(shù)如圖6所示。

圖5 Matlab仿真實(shí)驗(yàn)結(jié)果

圖6 農(nóng)業(yè)移動(dòng)機(jī)器人路徑規(guī)劃迭代次數(shù)

圖6顯示了本文采用的矩陣二進(jìn)制編碼的遺傳算法對(duì)圖4中移動(dòng)環(huán)境迭代次數(shù)的行為。其中，x為迭代次數(shù)，y軸為100次實(shí)驗(yàn)中的平均值和最佳適應(yīng)值。

由圖6可以看出：針對(duì)兩種障礙物與路徑不同的模型區(qū)域，農(nóng)業(yè)移動(dòng)機(jī)器人成功地求解出從開(kāi)始到結(jié)尾并成功躲避障礙物的最優(yōu)軌跡規(guī)劃。根據(jù)多次實(shí)驗(yàn)對(duì)比，所求路徑是該條件下機(jī)器人穿過(guò)障礙物耗時(shí)最少、運(yùn)動(dòng)代價(jià)最小的路線。

4 結(jié)論

基于矩陣二進(jìn)制編碼的遺傳算法，通過(guò)采集左邊、前邊和右邊的障礙物距離作為數(shù)據(jù)輸入，輸出追蹤最佳路徑長(zhǎng)度和導(dǎo)航時(shí)間，形成最優(yōu)矩陣決策，實(shí)現(xiàn)農(nóng)業(yè)移動(dòng)機(jī)器人和目標(biāo)之間的映射關(guān)系。仿真實(shí)驗(yàn)結(jié)果表明：農(nóng)業(yè)移動(dòng)機(jī)器人在存在復(fù)雜障礙物的情況下能夠?qū)崿F(xiàn)路徑規(guī)劃與導(dǎo)航，且所求路徑是該條件下機(jī)器人穿過(guò)障礙物耗時(shí)最少、運(yùn)動(dòng)代價(jià)最小的路線。