馮京偉，陳海霞，劉天鵬

(三江學(xué)院 機械與電氣工程學(xué)院，江蘇 南京 210012)

0 引言

電子商務(wù)迅猛發(fā)展，為倉儲物流帶來了新的需求和挑戰(zhàn)。其發(fā)貨單位小型化，品種多、批量小、批次多、周期短，傳統(tǒng)依靠人工的倉儲物流難以適應(yīng)新的需求，基于移動機器人的自動化倉儲技術(shù)正在興起。將自主移動機器人引入倉儲空間中，代替人工搬運貨物，可以有效地減少工人的勞動強度，降低維護成本，提高運行效率。要實現(xiàn)一個機器人化的自動化倉儲環(huán)境，關(guān)鍵的問題就是移動機器人的路徑規(guī)劃，使機器人在自動避障的前提下，規(guī)劃最優(yōu)路徑到達(dá)目標(biāo)點。

1 A*算法路徑規(guī)劃的優(yōu)勢

1.1 常見的路徑規(guī)劃算法

目前，已有多種算法被應(yīng)用到路徑規(guī)劃中。傳統(tǒng)算法主要有圖形方法和智能方法，其中圖形方法包括路圖法、柵格法等；智能方法包括遺傳算法、蟻群算法、Dijkstra算法等智能算法及其混合形式也用來解決路徑規(guī)劃問題。在智能算法中，如遺傳算法存在編碼長度變化范圍大，求解效率低，求解規(guī)模小等問題[1]。Dijkstra算法直接搜索全局空間而不考慮目標(biāo)信息，導(dǎo)致路徑求解時間長，難以滿足快速規(guī)劃路徑的需求[2]。

1.2 平滑A*算法的基本思想和優(yōu)點

f(p)=g(p)+h(p)

(1)

其中，f(p)是代價函數(shù)，g(p)是起點到當(dāng)前節(jié)點p的最短路徑值，h(p)是當(dāng)前節(jié)點n到目標(biāo)的最短路徑的啟發(fā)值。當(dāng)新的g(p)值大于之前的g(p)，則用新g(p)代替之前的g(p)；而h(p)的替代原則剛好相反，當(dāng)新的h(p)小于之前的h(p)值才發(fā)生替代。應(yīng)用這樣的代價函數(shù)策略，是可以找到最短路徑的，也就是可采納的。這種應(yīng)用這種代價函數(shù)的最好優(yōu)先算法就是A*算法的基本思想。

A*算法規(guī)劃后的路徑存在一些問題，比如很多折線和轉(zhuǎn)折點，不適用于倉儲物流機器人的運行特點。為了提升線路質(zhì)量，深入研究A*算法并進行改善，建立平滑A*算法方法并給出比較結(jié)果。仿真結(jié)果表明，平滑A*算法進行的路徑規(guī)劃更適用于倉儲物流機器人的應(yīng)用領(lǐng)域。

2 A*算法程序仿真

2.1 設(shè)計概述

本設(shè)計將倉儲物流機器人作為研究對象，實現(xiàn)其路徑規(guī)劃。

2.1.1 建立柵格地圖

采用行列劃分的矩陣存儲方法在地圖上建立的柵格，每個方格的坐標(biāo)信息記錄在柵格存儲陣列中的第m行、第n列，記為G(m，n)。采用這種“柵格—存儲”的映射辦法，可以建立起整幅地圖。建立柵格后，對模型進行信息的編碼。編碼格式的基本思想如下：

1——當(dāng)前柵格有障礙；

0——當(dāng)前柵格無障礙。

在實際應(yīng)用中，機器人路徑規(guī)劃為二維結(jié)構(gòu)化空間，假設(shè)障礙物的位置和大小已知，并且在機器人運動過程中，障礙物的位置和大小都不發(fā)生變化；用尺寸相同的柵格對 機器人二維工作空間進行劃分，按照機器人及空間的大小確定柵格數(shù)目，柵格大小以機器人可以在其中運動為限[3]。

秉持分布式系統(tǒng)無法同時兼顧一致性、可用性與分區(qū)容忍性（CAP）原理[8]，中本聰設(shè)計了PoW共識機制?，F(xiàn)階段常見共識算法其中一類為證明類共識，即Proof of X共識方案，是在PoW共識方案之上的變種，將PoW改換為其余證明。PoW算法現(xiàn)階段依然盛行，使用PoW共識的代表貨幣比特幣依然占據(jù)最大市值。

2.1.2 算法流程

當(dāng)從初始點向目標(biāo)點移動時，據(jù)前述f(p)=g(p)+h(p)，A*算法會權(quán)衡g(p)和h(p)的值，每次進行主循環(huán)時，它檢查f(p)最小的結(jié)點p，將在當(dāng)前的open list中選擇f值最小的相鄰柵格作為下一個已選定柵格，并將當(dāng)前已選定柵格作為該相鄰柵格的父柵格，移入close list，將父柵格依次連接起來，完成尋路。

2.2 基本A*算法仿真

通過程序來在柵格地圖上設(shè)置障礙物來模擬倉儲空間中的貨架，然后進行A*算法路徑規(guī)劃，如圖1所示。

圖1 障礙物格局

從圖1可以看出，利用A*算法自動規(guī)劃路徑的轉(zhuǎn)折較多，如果在實際應(yīng)用中使用這個程序來控制機器人調(diào)度，雖然可以完成任務(wù)，但是在機器人每次遇到障礙物需要轉(zhuǎn)彎時，就必須減速到零轉(zhuǎn)彎，然后再啟動加速，如果連續(xù)遇到多個障礙物，那么機器人的運行時間將會加長；而且不斷地啟動停止，不僅使機器人的能耗增加，而且對機器人本身的壽命也有所影響，所以必須對機器人的路徑進行平滑。

2.3 路徑平滑方法

本文研究了多種路徑平滑方法，以下兩種平滑方法的路徑模擬運行仿真如圖2所示。

圖2 平滑后曲線

(1)利用MATLAB軟件自帶的函數(shù)smooth函數(shù)。yy=smooth(y，span，sgolay)，式中yy為平滑后的縱坐標(biāo)值，y為原縱坐標(biāo)值，span為移動平均濾波器的窗寬，span為奇數(shù)，sgolay為Savitzky-Golay濾波器的窗寬，由span參數(shù)指定；橫坐標(biāo)也做相同的處理。

(2)自定義函數(shù)SmoothPath?；舅枷胧菍υ窂竭M行分析，設(shè)置權(quán)重和平滑因子，根據(jù)原路徑與新路徑當(dāng)前點的差值進行加權(quán)，并對路徑中上一個點、下一個點與當(dāng)前點的差值乘平滑因子，在一定的容忍度范圍內(nèi)，自動進行重復(fù)計算，得到平滑后的新路徑。

3 結(jié)語

針對A*路徑規(guī)劃算法在倉儲物流機器人應(yīng)用中的不足，提出了改進的A*路徑規(guī)劃算法，引入平滑路徑的處理，不僅優(yōu)化了路徑，且能平滑轉(zhuǎn)折角度，仿真結(jié)果驗證了算法的有效性。實際應(yīng)用中平滑A*算法為障礙物隨機分布、大規(guī)模柵格情況下機器人規(guī)劃出的路徑有轉(zhuǎn)折次數(shù)少、轉(zhuǎn)折角度小等優(yōu)點，能滿足工程需求。