基于平滑A*算法的倉儲物流機器人路徑規劃

馮京偉，陳海霞，劉天鵬

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

0 引言

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

1 A*算法路徑規劃的優勢

1.1 常見的路徑規劃算法

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

1.2 平滑A*算法的基本思想和優點

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

(1)

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

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

2 A*算法程序仿真

2.1 設計概述

本設計將倉儲物流機器人作為研究對象，實現其路徑規劃。

2.1.1 建立柵格地圖

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

1——當前柵格有障礙；

0——當前柵格無障礙。

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

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

2.1.2 算法流程

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

2.2 基本A*算法仿真

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

圖1 障礙物格局

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

2.3 路徑平滑方法

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

圖2 平滑后曲線

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

(2)自定義函數SmoothPath。基本思想是對原路徑進行分析，設置權重和平滑因子，根據原路徑與新路徑當前點的差值進行加權，并對路徑中上一個點、下一個點與當前點的差值乘平滑因子，在一定的容忍度范圍內，自動進行重復計算，得到平滑后的新路徑。

3 結語

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