基于蟻群算法的多采摘機器人路徑規劃與導航系統

張 璐，王 慧

(河南工業職業技術學院，河南 南陽 473000)

0 引言

近年來，人工智能已成為新一輪工業革命的基石，不僅廣泛應用于工業控制領域，在農業生產中的應用越來越普及。在農忙時節，農場往往會出現勞動力大量匱乏的現象，因此機器人在農業上的應用需求越來越明顯。研發出一種能進行遠程控制的采摘機器人，代替傳統人力的作業操作，對提高農業生產水平及種植效率具有重要意義，也是現代化農業的發展趨勢。為此，根據采摘機器人作業環境，采用蟻群算法，結合先全局后局部的路徑規劃方法，設計了一種多采摘機器人路徑規劃和導航系統。

1 蟻群算法簡述

蟻群算法是意大利學者Dorigo在20世紀90年代模擬和總結螞蟻尋找食物的一系列行為過程，得出的一種解決復雜組合優化問題的方法。該方法從螞蟻、蜜蜂這些昆蟲尋找食物的行為入手，其實對于一個個體而言，它們的行為非常容易分析，但當它們組合成一個龐大的群體后，群體行為分析難度就大大增加了。其原因是因為螞蟻個體間是由一種分泌物作為信息素進行交流通信，螞蟻在行走的路線上會留下這些物質，而所有的螞蟻都能夠感知這些物質的濃度，并根據該物質濃度的強弱選擇自己的運動方向。因此，蟻群的集體行為會形成一種特定的信息正反饋場景，即某路線上經過的螞蟻數量越大，則后面選擇該路線的螞蟻就會越多。螞蟻間根據感知這種信息素物質的強弱實現搜索食物的整個過程，這也就是蟻群算法的緣由。蟻群尋找食物過程示意圖如圖1所示。

圖1 蟻群尋找食物過程示意圖Fig.1 The schematic diagram of ant colony searching for food process

圖1中，假設A為蟻群群居的位置，E為有食物的地方，MN為AE之間的一個阻擋物。由于從A到E之間存在障礙物MN，那么蟻群在搬運食物的過程中只能是從BCD或者BFD兩條路徑。其中，兩條路徑的長度分別為10和20。假設在1min內有200只螞蟻從A運動到E，螞蟻經過后信息素總數增加為20，為了讓計算比較簡單，設定信息素從產生到消失的時間為10min。在最開始時，沒有信息素物質的存在，螞蟻選擇兩條路線的概率相同；但因為BCD路徑短，螞蟻選擇BCD需要的時間較少，因此在相同時間內，走過BCD的螞蟻會多一些；這樣BCD路徑上的信息素物質比BFD要多，也會吸引后面的螞蟻從BCD走，從而實現從A到E的最優路徑。

蟻群算法最初是應用于解決TSP問題，其原理為：在最初時刻，所有螞蟻都在同一起點，每條可供選擇前進路徑的信息素物質都為零，設定行程最短的路徑距離為smin，距離最長的為smax，經過的螞蟻數量為M。其中，經過smin和smax的螞蟻數量分別為M1和M2，則

M=M1+M2

(1)

那么，當M只螞蟻經過smin和smax后，接下來的螞蟻從smin經過的概率為

(2)

其中，Psmin(M+1)為低M+1次螞蟻從smin經過的概率；a和h為參數。

2 多采摘機器人路徑規劃

在多采摘機器人作業過程中，障礙物較多，機器人間相互影響，成為彼此的障礙物，因此多機器人路徑規劃難度較大。在實際研究中，多個采摘機器人在同一種植區作業，需要規劃多條最優路徑，但在具體的作業過程中，由于障礙物的存在，最優路徑會發生變化，也會影響其他機器人的移動路徑。基于上述問題，為了保證多采摘機器人實現無碰撞作業，該系統需要實時規劃路線，防止機器人間、機器人與障礙物間的碰撞。

2.1 多采摘機器人路徑規劃整體設計

由于產業種植園區環境不確定性因素較大，如種植人員園區工作以及其他機械的隨機移動，且傳感器探測具有一定的局限性，機器人在最初規劃時往往很難獲取全部的信息，采用簡單的規劃往往難以獲得理想的最優路徑。因此，可在獲得一定園區環境信息的基礎上，進行作業前的全局規劃，并將其作為理想的最優路線。在采摘機器人群的實際運動作業中，根據后續探測的環境信息，規劃出局部的最優路徑，進行簡單的微調，使機器人避開所有碰撞物，并最快地到達目的地?；谝陨蠁栴}，該系統采用全局和局部的規劃方法，實現多采摘機器人的路徑規劃。多采摘機器人路徑規劃框架如圖2所示。

1)全局路徑規劃。本章研究的是多采摘機器人在實際園區作業過程中的路徑規劃算法，對于其全局路徑規劃，首先要做到的是按照具體作業要求，根據已知環境信息，給每個機器人分配任務，并確定每個機器人作業的起始點和終點，然后結合多機器人間的合作機制，在兩點之間規劃一條無碰撞的優化路線。在整個算法中，最重要的是提高路線規劃速度和實現路徑規劃的最優性。由于螞蟻算法路徑規劃效率比較高，且其對于障礙物變化的適應性較強，因此本文將采用蟻群算法對多采摘機器人進行全局路徑規劃。

2)局部路徑規劃。有了全局路徑規劃之后，采摘機器人群就可以開始各自的作業任務。開始階段，采摘機器人將按照各自的規劃路徑進行作業，并實時采集周邊環境信息，根據采集到的動態信息，進行分析處理，根據碰撞檢測、決策算法和行為檢測等進行局部的路徑修改，從而使自身具有更強的環境適應能力。

本系統采用的局部規劃算法是利用機器人的車載傳感器對周邊環境信息進行實時檢測，并與全局規劃時的信息進行對比分析，根據碰撞檢測子系統對是否存在碰撞風險進行評估。若存在撞機危險，則對局部路徑進行一定的調整，在調整過程中，始終以作業終點為最終目標，避免出現局部的極值點而忽略機器人整體規劃。另外，在局部規劃過程中，行為檢測子系統需要實時對采摘機器人規劃的路徑進行判斷，確定其是否符合全局規劃的目標，若符合，則執行。在機器人成功避開障礙物后，則可以按照全局規劃的路線繼續進行作業操作，在執行期望路徑的過程中，向最近的子路徑節點移動。如此反復，不管局部規劃路徑怎么實施，采摘機器人最終的目標終點不會發生改變，直到其成功到達終點。

圖2 路徑規劃框架圖Fig.2 The path planning framework

2.2 路徑規劃的適應度函數

在進行路徑規劃中，除保證各機器人前進路徑最優外，還需要各機器人間協調，以避免出現兩采摘機器人發生碰撞。路徑規劃的適應度函數是影響蟻群算法能否高效的計算出最優解的主要原因，多采摘機器人路徑規劃要求包含避障和距離最短。因此，適應度函數重點要考慮路徑長度、路徑平滑度及可行性，計算方法如下：

路徑長度為

(3)

其中，d(p)為路徑長度；i為路徑子節點編號；n為障礙物數量。

d(p)的倒數是決定路徑規劃是都最短的適應度函數fit1，其表達式為

(4)

路徑平滑度為

(5)

其中，h(p)為路徑平滑度。在路徑規劃過程中，在選擇目標函數時，要結合采摘機器人移動性能、光滑適應性作為主要參數，盡可能使生成的路徑變化均勻，取h(p)的倒數為路徑平滑度的適應度函數fit2為

(6)

躲障是采摘機器人工作的首要條件，是其正常作業的保證，因此可行性是指采摘機器人群是否能夠安全地避開障礙物并得到終點。以下是采摘機器人在最優路徑行駛中會出現的幾種情況：

1)在優化路徑中沒有出現障礙物，則可以按照蟻群算法確定其適應度函數fit3為

(7)

由式(7)可以看出：當規劃的路徑中沒有出現障礙物時，fit3值為1，否則為0。

2)假設一采摘機器人從路徑子節點i移動到路徑子節點i+1，則其與障礙物不想交的適應度函數fit4為

(8)

綜上所述，采摘機器人最終可行性為

Fi1t=fit3·fit4

(9)

3 多采摘機器人導航系統

3.1 導航系統整體方案

多采摘機器人導航系統是指在執行任務期間，對各采摘機器人的作業路線進行導航，即根據空間位置的做出全局規劃，結合在前進過程中感知到的部分環境信息，實時對路線進行恰當的修改，引導各機器人安全前進到指定位置。該方案主要包括環境建模、自主定位和路徑規劃3部分。由于路徑規劃已在前一章詳細的闡述，這里不再重復。

1)環境建模。環境建模是指采用數學模型的方法，對采摘作業區域進行詳細描述，并將其抽象成計算機系統能夠直接識別的數據信息。本文所采取的導航系統數據信息存在于后臺服務器中，并由該信息抽象出拓撲圖，對路線信息進行簡單的描述。另外，也方便各采摘機器人識別道路之間的聯系，準確實現全局、局部路徑規劃和實時導航。

2)采摘機器人定位。采摘機器人定位是指根據周邊環境信息和GPS確定其在作業區域相對于全局坐標的具體位置，其流程圖如圖3所示。

圖3 采摘機器人定位流程圖Fig.3 The positioning flow chart of picking robot

3.2 環境建模的具體實現

環境建模的空間信息對實現多采摘機器人的導航具有決定性的意義，本文所采用的方法是將地圖信息存在后臺服務器，通過后臺服務器的數據庫進行拓撲圖的繪制，并采用循環鏈表的方式將數據信息進行保存。因此，后臺服務器中的數據庫存放有地圖的全部信息，可用于多采摘機器人的實時定位與導航，而拓撲圖則可以用于結合螞蟻算法實現路徑的最優規劃。

1)地圖信息數據庫。先將地圖信息分為站和道路兩種，其中站面積比較大，占地較多，可以用來讓機器人進行短暫的停留；而道路則是機器人前進的路線，用來連接各個站。其次，在策略算法進行規劃的過程中，可以將站和道路看成一段段或者一塊塊的矩陣，將其連接起來就可以用來表示地圖。地圖信息如圖4所示。

圖4 搭建導航地圖信息圖Fig.4 The establishment of navigation cartographic information

2)建立拓撲圖。建立拓撲圖需要以服務器中的數據信息為依據，其主要是用來描述各站點與道路之間的連接狀態，在內存中以循環鏈表的方式進行儲存。導航地圖拓撲圖如圖5所示。

圖5 導航地圖的拓撲圖Fig.5 The topological graph of navigation map

循環鏈表是數據結構中一種常用的保存數據信息的方法，可以靈活地表示數據間的前后關系，找到其中一個信息，便可以知道其前后內存里面的信息。在導航過程中，需要經常訪問節點間的連接信息，因此采用該方法可以大大提高數據讀取信息。

4 實驗結果與分析

為了驗證多采摘機器人路徑規劃與導航系統的準確性可靠性，本文利用MatLab仿真軟件對其進行了仿真實驗。其中，蟻群迭代步長設置為0.02，迭代次數為100次，運行環境為200m×200m的區域，本實驗中采摘機器人數量為3個。實驗目的：在采摘作業區域，該系統經過改變執行和迭代次數，判斷多采摘機器人群是否能夠成功避開障礙物，并且安全達到目的地。仿真結果如圖6所示。

圖6 仿真結果圖Fig.6 The simulation result diagram

由圖6可以看出：實驗中各采摘機器人均安全從起點到達終點，當一條線路只能允許一臺機器人通過時，其他機器人能夠避讓到站點休息，然后再進行前進操作，成功解決了路徑沖突的問題。從路徑長度和光滑度可以看出，該系統優化效果明顯，具有很強的避障、路徑規劃和導航能力，且可行性高。

5 結論

1)針對多采摘機器人聯合作業容易出現路徑沖突和碰撞的問題，采用蟻群算法，設計了多采摘機器人路徑規劃和導航系統。

2)針對產業種植園區環境不確定性因素較大及機器人在最初規劃的時候往往很難獲取全部的信息的問題，提出了先全局后局部的路徑規劃方法，實現了多采摘機器人移動路徑的實時動態規劃。

3)提出了多采摘機器人環境下，各機器人利用環境建模和自主定位進行自主導航的方法，通過建立地圖信息數據庫和拓撲圖，實現了對多采摘機器人的安全引導。最后，運用MatLab軟件仿真對路徑規劃和導航成功進行了驗證。