，，，，，

(1.蘇州科技大學(xué) 電子與信息工程學(xué)院 建筑智慧節(jié)能江蘇省重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215009；2.常州工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213002)

0 引言

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

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

1 分揀搬運(yùn)機(jī)器人的硬件設(shè)計(jì)

1.1 分揀搬運(yùn)機(jī)器人的整體結(jié)構(gòu)

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

圖1 搬運(yùn)機(jī)器人的結(jié)構(gòu)圖

1.2 顏色傳感器模塊設(shè)計(jì)

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

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

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

(1)

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

2 A*算法原理

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

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

(2)

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

(3)

其中:xi、yi設(shè)定為起始位置，xj、yj設(shè)定為目標(biāo)位置[5-6]。

3 改進(jìn)的A*算法

3.1 蟻群算法

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

3.2 與蟻群算法相結(jié)合改進(jìn)A*算法

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

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

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

X(R)=kc

(4)

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

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

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

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

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

(5)

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

(6)

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

O=random，jk(r)∈n

(7)

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

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

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

4.1 場地模擬

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

4.2 路徑規(guī)劃

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

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

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

圖4 人工勢場法仿真 圖5 改進(jìn)后A*算法仿真

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

4.3 實(shí)際路徑規(guī)劃實(shí)驗(yàn)

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

圖6 本文設(shè)計(jì)的分揀搬運(yùn)機(jī)器人的實(shí)物圖

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

表1 3種算法在時(shí)間、出錯(cuò)率、能耗率對比表

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

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

圖7 搬運(yùn)機(jī)器人自主路徑規(guī)劃實(shí)驗(yàn)

5 結(jié)論

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

參考文獻(xiàn)：

[1] 譚 民, 王 碩. 機(jī)器人技術(shù)研究進(jìn)展[J]. 自動化學(xué)報(bào), 2013, 39(7):963-972.

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

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

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

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

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

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

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

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

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