基于改進A*算法的分揀搬運機器人路徑規(guī)劃

，，，，，

(1.蘇州科技大學 電子與信息工程學院 建筑智慧節(jié)能江蘇省重點實驗室，江蘇 蘇州 215009；2.常州工學院 計算機信息工程學院，江蘇 常州 213002)

0 引言

隨著我國工業(yè)生產(chǎn)的不斷進步與發(fā)展，分揀搬運機器人越來越多的參與到了工廠的貨物分揀和搬運等應用中[1]。它的作用不局限于處理貨物的搬運問題，更能夠減輕人力工作的壓力，提高整體的工作效率，從而降低不必要的成本。張巖巖等人針對搬運機器人的路徑尋優(yōu)問題，通過將人工免疫算法中的相關參數(shù)進行迭代優(yōu)化后，將其與蟻群算法相結合，提出了一種改進的蟻群路徑規(guī)劃算法[2]。然而，該算法雖然能夠較為準確地找到最優(yōu)路徑，但是該算法中的參數(shù)迭代優(yōu)化計算量較大，影響到了路徑規(guī)劃算法的實時性。呂太之等人提出在路徑規(guī)劃過程中加入同步構造可視圖環(huán)節(jié)，有效地降低了路徑規(guī)劃的耗時[3]。然而該算法能夠擴展的節(jié)點數(shù)量比較有限，無法用于范圍較大的障礙物環(huán)境。孫煒等人在路徑規(guī)劃時首先采用柵格方法建立環(huán)境模型，接著將A*算法用于初步的路徑規(guī)劃，并按較小的分割步長進行分割，剔除中間路徑點的方法實現(xiàn)最優(yōu)路徑規(guī)劃[4]。然而，該算法中的分割步長需要人工確定，無法實現(xiàn)自主的路徑規(guī)劃。

針對上述問題，本文提出了一種將蟻群算法與A*算法相結合的改進了A*算法用于解決自主最優(yōu)路徑規(guī)劃問題，并自主開發(fā)設計了一種以改進A*算法為核心的分揀搬運機器人用于算法驗證。該機器人使用STM32單片機為核心控制器，能夠為電機運動、機械臂的夾取提供靈活的控制。機器人使用的顏色傳感器，具備在一定的誤差范圍內(nèi)能夠分辨不同類型障礙物的功能。機器人采用S型加減速控制法來控制運行速度，使用PID控制法對電機進行調(diào)控，使得整體機器的運行更加穩(wěn)定[5]。

1 分揀搬運機器人的硬件設計

1.1 分揀搬運機器人的整體結構

機器人以STM32芯片的電路板為平臺搭建。驅動模塊控制電機的行動和機械臂的抓取。機械臂上部安裝了鐵針，用來配合機械臂夾取。機器臂的底部裝有顏色傳感器，用來辨識不同的物料。機器人共有3個電機，左右輪電機作為主動輪運行，中間電機則作為萬向輪對方向進行調(diào)整。

圖1 搬運機器人的結構圖

1.2 顏色傳感器模塊設計

本文設計的機器人使用了TCS230顏色傳感器，CMOS電路上集成了硅光電二極管和電流頻率轉化器，且單一芯片上有紅、藍、綠3種濾光器，在沒有A/D轉換電路的情況下，能夠與微處理器直接連接。傳感器上共64個光電二極管，分別為紅色、藍色、綠色、全透。當選定一種色彩的濾波器后，便只能通過這類的顏色，其余顏色不能夠通過，從而得到此顏色的光強，并能夠進行區(qū)分。

在顏色識別開始前，需要對顏色識別模塊進行白平衡。白平衡調(diào)整檢測系統(tǒng)，使其對三原色的敏感度相同，從而確保測量的準確性。當顏色的計算值在一定誤差范圍內(nèi)，可以得出對應顏色的檢測結果，從而能夠正確判斷不同的障礙物。

本文中的顏色傳感器采用笛卡爾距離算法來辨別不同顏色。公式如下：

(1)

Rr、Gr、Br為不同顏色的傳感器參考值，Ru、Gu、Bu為未知色彩的傳感器實際測量值。

2 A*算法原理

A*算法是一種直接的啟發(fā)式搜索算法，常用于在靜態(tài)路網(wǎng)中求解最短路線[6]。啟發(fā)式搜索就是在一定范圍空間內(nèi)，每一個地位都進行搜索，得出最好的位置，再以此持續(xù)進行搜尋，直到到達目標點。A*算法的路線規(guī)劃由估價函數(shù)決定，每走一段距離就需要進行估算。在不斷前進的路線上，舍去死節(jié)點，而保留最優(yōu)的節(jié)點，并且不斷比較新節(jié)點與舊節(jié)點的優(yōu)劣。得出價值最低的節(jié)點，向此節(jié)點前進，并進行下一步的計算，最終逐步到達目標點。公式如下：

f(n)=g(n)+h(n)

(2)

f(n)為全局環(huán)境中最優(yōu)化理論消耗值，g(n)為實際操作中額外的消耗值，h(n)為理論上最優(yōu)化路線的消耗值，整體估價函數(shù)h(n)占主導地位。因此簡化h(n)的具體算法，便可在理論上減小f(n)的量。為了匹配本文的模擬環(huán)境，采用歐幾里得距離算法作為啟發(fā)函數(shù)，能夠在復雜環(huán)境里計算出最優(yōu)解。歐幾里得距離算法即兩點之間的距離，能夠簡化二維模型里的距離問題，從而化簡整體的運算。公式如下：

(3)

其中:xi、yi設定為起始位置，xj、yj設定為目標位置[5-6]。

3 改進的A*算法

3.1 蟻群算法

蟻群算法是一種啟發(fā)式全局優(yōu)化算法。此算法來源于意大利學者Dorigo、Maniezzo等人對蟻群搬運食物路線的研究[7]。螞蟻在搬運食物的路徑上，會留下信息素。蟻群對信息素具有很強的感知力，根據(jù)之前蟻隊留下的信息素，后來的蟻隊能夠花費更少的時間到達食物點。蟻群算法簡單而實用，但相較于A*算法，多了盲目性與不穩(wěn)定性。

3.2 與蟻群算法相結合改進A*算法

A*算法在路徑規(guī)劃中有極高的價值，但算法本身存在一定的問題，在路徑規(guī)劃中存在多個最小解的情況下，無法做到選擇最優(yōu)化。蟻群算法是一種廣度優(yōu)先搜索，在進行初次搜索時，采用信息素均勻分布，各條路線上的信息素均定義為一個常數(shù)C。因此在搜索的初期，收斂速度會較慢，算法的搜索時間也較長。A*算法的啟發(fā)函數(shù)能夠明確從起點到目標點搜索的方向，本文中利用簡化的A*算法，對地圖初始位置信息素進行設置，從而加快算法初期收斂速度，避免了大量無意義的計算。

本文介紹算法的主要改進在于使用A*算法篩選出一條合適的路線來分布信息素，從而簡化A*算法在之后路線規(guī)劃上的計算。從起點出發(fā)，選取多個適合的無障礙節(jié)點，從中選取估價函數(shù)最低的節(jié)點。再以此節(jié)點為中心，選取下一個估價函數(shù)最低的節(jié)點，從而能夠順利篩選出一條從起點到目標點估價函數(shù)最低的路線。而簡化了新節(jié)點與舊節(jié)點的比較的過程。

將f(n)作為評價函數(shù)得出的最優(yōu)化的路線R。將此路線的初始信息素設置為：

X(R)=kc

(4)

c為其他路線信息素的分布，k為大于1的常數(shù)。

3.3 改進后A*算法的路徑規(guī)劃

設定兩個決定數(shù)a、b。ab屬于(0,1)。設p為決定概率。O為最終決定節(jié)點。

情況一：蟻群算法受信息素與啟發(fā)信息的影響，所以在a

O=max{[X(m,n)α]*[Y(m,n)]β}

(5)

情況二：在決定參數(shù)ap條件下，可以采用輪盤賭策略選擇節(jié)點。公式如下：

(6)

情況三：當決定參數(shù)a>p條件下，在柵格中隨機選擇非障礙物的柵格作為前進路線。公式如下：

O=random，jk(r)∈n

(7)

m對應信息素因數(shù)，n對應能見度因數(shù)，X對應信息數(shù)，Y對應能見度或者啟發(fā)因數(shù)，jk(r)對應下一步到達的柵格位置。

采用改進后的A*算法，結合了蟻群算法，指引出一條高于平均信息素分布的一條路線，解決了A*算法在存在多個最小值時的路徑優(yōu)化問題，并且讓整個算法系統(tǒng)更加靈活，能夠應對各種復雜的環(huán)境[8]。

4 場地模擬與路徑規(guī)劃

4.1 場地模擬

在實際的搬運過程中，物料與生產(chǎn)車間總有一定的距離，且沿途都會有相應的阻礙物。在仿真實驗中設置紅圈為障礙物，start為起始點，target為目標點。機器人需在方格內(nèi)避開紅圈，并找出一條最短的行徑，從而實現(xiàn)物料搬運。

4.2 路徑規(guī)劃

分揀搬運機器人將從起點start出發(fā)，避過途中設置的不同的障礙，將物料送入目標位置target，從而完成搬運任務。在相同大小10*10的柵格模型中進行比較，如圖2所示。從圖3、圖4和圖5這三組對應不同方法的實驗中可以看出，在圖2所示的障礙物環(huán)境條件相同的情況下，機器人都能夠成功規(guī)避相應的障礙物，最終準確把物料搬運到目的地。

對比3種算法，也能很容易發(fā)現(xiàn)在前期的運動軌跡中3種算法并沒有太多區(qū)別。在運動后期，圖3中的A*算法在路徑規(guī)劃上能做到避開障礙物，將貨物搬運到指定目標點，但在搬運的最后階段，沿直角行走，并不能做到路線的最優(yōu)化。圖4中的人工勢場法能夠在運動的最后階段簡化路線，但在路線最后的規(guī)劃上受最后障礙物分布的影響，對最后路線的選擇有一定的干擾，因此不能做到抉擇最優(yōu)化。而圖5中本文提出的改進A*算法在規(guī)避障礙的同時也做到了路線的最優(yōu)化。

圖2 障礙物分布圖 圖3 A*算法仿真

圖4 人工勢場法仿真 圖5 改進后A*算法仿真

最終實驗結果的區(qū)別源于這3種算法本身的差異。人工勢場法在路徑規(guī)劃后期受到障礙物影響較大，容易出現(xiàn)無法實現(xiàn)路徑最優(yōu)化的情況[9-10]。A*算法由于帶入大量重復數(shù)據(jù)和復雜的估價函數(shù)，未能找到最佳路徑。而本文提出的改進A*算法利用在路徑上分布信息素的方法，簡化了節(jié)點抉擇最優(yōu)解的計算量，因此最后的障礙物安放位置不會影響到最優(yōu)路線的規(guī)劃。

4.3 實際路徑規(guī)劃實驗

將本文設計的分揀搬運機器人用于實際實驗，其具體結構如圖6所示。由夾持器、電機、STM32開發(fā)板、顏色傳感器和蓄電池組成。其中鐵針配合著半圓形塑料臂組成夾持器夾取物料。機器人整體結構簡單，運動流暢，能夠在實際實驗環(huán)境中完成分揀搬運任務。

圖6 本文設計的分揀搬運機器人的實物圖

在相同的實驗環(huán)境下，分別采用了A*算法、人工勢場法算法、改進后A*算法，分別進行了實際的實驗，從搬運時間、出錯率、能耗3個方面進行比較。在多次實驗后得到以下數(shù)據(jù)。

表1 3種算法在時間、出錯率、能耗率對比表

從表1中可以看出，A*算法與人工勢場法在時間方面相差不多，出錯率方面A*算法較低，而能耗較大。人工勢場法出錯率較高，但能耗略低。改進后的A*算法時間大大縮短，而且在出錯率和能耗方面都優(yōu)于A*算法和人工勢場法，本文提出的改進A*算法比A*算法、人工勢場法更適合分揀搬運機器人使用。

在實際實驗中，機器人從圖7(a)起點位置出發(fā)，將貨物夾緊后，開始搬運任務。如圖7(b)與圖7(c)所示，機器人順利規(guī)避了沿途設置的障礙。選擇本文提出的改進A*算法3種情況中的一種，自主的規(guī)劃最優(yōu)行進路徑。最終，圖7(d)中機器人搬運貨物并沿著最優(yōu)路線準備到達目的地，從而完成了搬運任務。機器人在實驗過程中沒有與障礙物發(fā)生碰撞，且最優(yōu)路徑選擇準確率高、速度快。從而驗證了本文提出的改進A*算法在路徑規(guī)劃時具有較強的準確性與實用性。

圖7 搬運機器人自主路徑規(guī)劃實驗

5 結論

本文設計的基于STM32單片機控制的分揀搬運機器人，在2016年中國機器人大賽暨RobotCup公開賽中獲得了分揀搬運組一等獎的成績。本文利用該平臺圍繞改進后的A*算法進行模擬和實際實驗，驗證了改進后的A*算法能夠能好地提高機器人規(guī)避障礙能力。然而由于本文采用的機器臂較小，一次搬運物料有限，當需要搬運的物料較多時，效率便會有所降低。因此，本文設計的分揀搬運機器人仍需進一步改進，不斷提升其實用性。

參考文獻：

[1] 譚 民, 王 碩. 機器人技術研究進展[J]. 自動化學報, 2013, 39(7):963-972.

[2] 張巖巖, 侯媛彬, 李 晨. 基于人工免疫改進的搬運機器人蟻群路徑規(guī)劃[J]. 計算機測量與控制, 2015, 23(12):4124-4127.

[3] 呂太之, 趙春霞, 夏平平. 基于同步可視圖構造和A*算法的全局路徑規(guī)劃[J].南京理工大學學報(自然科學版), 2017,41(3):313-321.

[4] 孫 煒, 呂云峰, 唐宏偉, 等. 基于一種改進A*算法的移動機器人路徑規(guī)劃[J]. 湖南大學學報(自科版), 2017, 44(4):94-101.

[5] 陶重犇, 劉壯宇, 孫云飛. 基于嵌入式系統(tǒng)的搬運機器人設計與路徑規(guī)劃研究[J], 計算機測量與控制, 2016, 24(8):215-217

[6] 宗成星, 陸 亮, 雷新宇,等. 一種基A*算法的空間多自由度機械臂路徑規(guī)劃方法[J]. 合肥工業(yè)大學學報：自然科學版, 2017, 40(2):164-168.

[7] 裴振兵, 陳雪波. 改進蟻群算法及其在機器人避障中的應用[J]. 智能系統(tǒng)學報, 2015(1):90-96.

[8] 黃 辰, 費繼友, 劉 洋,等. 基于動態(tài)反饋A*蟻群算法的平滑路徑規(guī)劃方法[J]. 農(nóng)業(yè)機械學報, 2017, 48(4):34-40.

[9] 溫素芳, 郭光耀. 基于改進人工勢場法的移動機器人路徑規(guī)劃[J]. 計算機工程與設計, 2015(10):2818-2822.

[10] 石為人, 黃興華, 周 偉. 基于改進人工勢場法的移動機器人路徑規(guī)劃[J]. 計算機應用, 2010, 30(8):2021-2023.