蔣柳鵬，戴南亭

（河海大學(xué)港口海岸與近海工程學(xué)院，江蘇 南京 210098）

0 引言

AGV（Automated Guided Vehicle），即自動導(dǎo)引車，憑借其智能高效的優(yōu)勢，被廣泛應(yīng)用于港口物流、城市交通和智能倉儲系統(tǒng)等領(lǐng)域。港口AGV 路徑規(guī)劃通常指為裝運(yùn)集裝箱的AGV 尋找從接貨點(diǎn)到卸貨點(diǎn)的最優(yōu)路徑。根據(jù)AGV 搬運(yùn)特點(diǎn)，該路徑需要綜合考慮搬運(yùn)距離短、避免碰撞、安全轉(zhuǎn)向等問題，以有序完成搬運(yùn)任務(wù)。港口AGV 路徑規(guī)劃是AGV 高效完成貨物搬運(yùn)的核心問題，需要高效的優(yōu)化算法求解其路徑規(guī)劃模型。

優(yōu)化算法可分為兩大類：一是以數(shù)學(xué)為基礎(chǔ)的經(jīng)典優(yōu)化算法，如單純形法、最速下降法[1]等；二是啟發(fā)式智能優(yōu)化算法，如遺傳算法、模擬退火算法、差分進(jìn)化算法等。經(jīng)典優(yōu)化算法計算復(fù)雜，無法求解高維度、復(fù)雜目標(biāo)函數(shù)的問題，因此AGV 路徑規(guī)劃中更多采用智能優(yōu)化算法。其中進(jìn)化算法（evolutionary algorithms，EA）是智能算法中的一個重要的“算法簇”，其產(chǎn)生的靈感源于大自然中生物的進(jìn)化[2]。與基于微積分的傳統(tǒng)方法和窮舉法等優(yōu)化算法相比，進(jìn)化算法更加成熟，且作為全局優(yōu)化方法具有魯棒性高、適用性廣及自組織、自適應(yīng)和自學(xué)習(xí)的特性，能夠有效處理傳統(tǒng)優(yōu)化算法難以求解的復(fù)雜問題，所以AGV 路徑規(guī)劃問題可以用EA 算法求解。

進(jìn)化算法主要有3 種類型：遺傳算法（genetic algorithm，GA），進(jìn)化規(guī)劃（evolutionaryprogramming，EP）和進(jìn)化策略（evolutionary strategies，ES）等[3]。其中ES 摒棄了梯度計算，強(qiáng)調(diào)個體級的行為變化，使用交叉算子，采用實(shí)數(shù)值作為基因，并且遵循零均值、某一方差高斯分布的變化產(chǎn)生新個體，在選擇和變異的操作上更為靈活，整體計算更加高效，適用于AGV 路徑規(guī)劃問題。

根據(jù)選擇方法的不同，進(jìn)化策略可以分為（1+1）進(jìn)化策略（（1+1）-ES）和（μ，λ）進(jìn)化策略（（μ，λ）-ES）兩種，其中（1+1）-ES 較為方便有效，被廣泛應(yīng)用。近年國內(nèi)外學(xué)者針對（1+1）-ES 算法的改進(jìn)做了大量研究，KAYHANI A 等[4-5]引入步長自適應(yīng)機(jī)制，并應(yīng)用于基準(zhǔn)函數(shù)和工程實(shí)例，結(jié)果表明，與其他算法相比，該算法具有高效性、魯棒性和全局尋優(yōu)能力；KRAMER O 等[6-7]提出一種可以自適應(yīng)改變算法中學(xué)習(xí)參數(shù)的方法，實(shí)驗結(jié)果表明該算法的總體性能有了顯著提高；JEBALIA M 等[8-9]基于（1+1）-ES 對球函數(shù)上的收斂性進(jìn)行了數(shù)學(xué)分析，并顯著提高其邊界下限，實(shí)現(xiàn)了對均勻突變算子的連續(xù)優(yōu)化。

在AGV 路徑優(yōu)化問題上，目前使用較多的有強(qiáng)化學(xué)習(xí)、A*算法、Dijkstra 算法、蟻群算法和遺傳算法等[10-14]，（1+1）-ES 算法在AGV 路徑規(guī)劃中的研究成果較少。因此，本文嘗試提出一種改進(jìn)的（1+1）進(jìn)化策略及相應(yīng)算法，應(yīng)用于AGV 路徑規(guī)劃問題，同時優(yōu)化該問題的適應(yīng)度函數(shù)，以提升AGV 路徑規(guī)劃的效果。

1 AGV 路徑規(guī)劃問題

1.1 AGV 路徑規(guī)劃環(huán)境建模

AGV 在港口碼頭進(jìn)行搬運(yùn)工作的實(shí)際環(huán)境如圖1 所示，集裝箱被AGV 從堆場運(yùn)至岸橋進(jìn)行裝卸，實(shí)際環(huán)境由AGV、障礙物和支路組成。為方便研究，將AGV 假設(shè)成一個質(zhì)點(diǎn)，將作業(yè)區(qū)的障礙物假設(shè)為同一尺寸，不考慮其實(shí)際尺寸。基于柵格地圖法操作較為簡單、易于理解和實(shí)現(xiàn)的優(yōu)點(diǎn)，本文采用柵格地圖法進(jìn)行環(huán)境建模，長為3個單位柵格長度、寬為1 個單位柵格長度的黑色柵格表示障礙物，空白柵格表示可自由移動的空間，地圖左下角的黑色柵格表示AGV 運(yùn)動的起點(diǎn)，地圖右上角的黑色柵格表示AGV 運(yùn)動的終點(diǎn)[15]，AGV 環(huán)境建模如圖1 所示。

圖1 AGV 工作環(huán)境實(shí)際地圖和建模地圖Fig.1 Actual map and modeling map of AGV working environment

將AGV 工作環(huán)境等分為20 行20 列的柵格地圖，單位柵格可完全容納AGV，地圖上的所有點(diǎn)都可用坐標(biāo)表示?？刂葡到y(tǒng)通過后臺控制向AGV發(fā)送搬運(yùn)任務(wù)，AGV 會沿著計算得出的路徑進(jìn)行運(yùn)動，將該路徑上的點(diǎn)用柵格中的坐標(biāo)表示，這些坐標(biāo)通過遺傳算法的編碼后變成一條路徑染色體，每一條染色體便代表了一個解即一條路徑。

1.2 AGV 路徑規(guī)劃適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)是篩選路徑的標(biāo)準(zhǔn)，用來評價路徑的優(yōu)劣，適應(yīng)度越高說明該路徑越符合設(shè)定的約束條件[16]。傳統(tǒng)路徑規(guī)劃的適應(yīng)度函數(shù)大多采用路徑長度最小為目標(biāo)函數(shù)，本文結(jié)合港口碼頭AGV 實(shí)際的工作情況，例如AGV 運(yùn)行過程中可能存在轉(zhuǎn)彎和與障礙物碰撞的情況，若轉(zhuǎn)彎角度過大或與障礙物碰撞將降低搬運(yùn)的工作效率，并造成AGV 的損壞，所以本文對目標(biāo)函數(shù)進(jìn)行了改進(jìn)，在路徑長度的基礎(chǔ)上增加了路徑平滑度和碰撞風(fēng)險函數(shù)，從路徑長度、路徑平滑度、碰撞風(fēng)險這3 個方面設(shè)計港口碼頭AGV 路徑規(guī)劃的適應(yīng)度函數(shù)。

1） 路徑長度

（xi，yi）表示地圖上第i個點(diǎn)的坐標(biāo)，Li表示（xi，yi）和（xi-1，yi-1）兩點(diǎn)之間的距離，相鄰兩點(diǎn)間的距離公式如下：

總的路徑長度公式如下：

將L無量綱化，并設(shè)置目標(biāo)函數(shù)為：

2） 路徑平滑度

在AGV 運(yùn)行過程中需要轉(zhuǎn)彎時，若轉(zhuǎn)彎角度過大將增加AGV 通過的時間，降低工作效率，并對AGV 本身造成一定的損耗，所以本文對路徑平滑度函數(shù)設(shè)置懲罰系數(shù)ω。當(dāng)轉(zhuǎn)彎角度θ<45°時，ω 設(shè)置為1；當(dāng)轉(zhuǎn)彎角度45°≤θ≤90°時，ω 設(shè)置為10；當(dāng)轉(zhuǎn)彎角度θ>90°時，ω 設(shè)置為1 000。將ωθ 無量綱化，并設(shè)置路徑平滑度函數(shù)如下：

3） AGV 與障礙物碰撞風(fēng)險

當(dāng)障礙物的位置與AGV 的位置越近時，AGV與障礙物的碰撞風(fēng)險越高，為防止AGV 與障礙物發(fā)生碰撞，本文設(shè)置位置風(fēng)險系數(shù)λ。本文選擇將距離AGV 最近的障礙物的中心點(diǎn)坐標(biāo)（xj，yj）與AGV 的位置坐標(biāo)（xi，yi）間的距離作為判斷標(biāo)準(zhǔn)，若距離小于1.5 個單位柵格長度則判斷為有較大的碰撞風(fēng)險，λ 設(shè)置為100，反之則λ=0。將λLij無量綱化，并設(shè)置障礙物與AGV 間的距離和碰撞風(fēng)險函數(shù)如下：

綜合上述因素，設(shè)計路徑評價函數(shù)為：

式中：a、b、c為權(quán)重系數(shù)，且三者和為1。

當(dāng)路徑評價函數(shù)數(shù)值越大時，說明該個體適應(yīng)度越高，被保留到下一代的概率越大；當(dāng)路徑評價函數(shù)數(shù)值越小時，說明該個體適應(yīng)度越低，被保留到下一代的概率越小，該染色體被淘汰的概率越大。

2 （1+1）-ES 的AGV 路徑規(guī)劃求解算法設(shè)計

（1+1）-ES 是進(jìn)化策略中較為簡單有效的一種[17]，是1 個父代通過高斯變異產(chǎn)生1 個子代尋優(yōu)的算法，即只有1 個父親且每次只產(chǎn)生1 個新的個體，然后從這2 個個體中保留較好的進(jìn)入后續(xù)的進(jìn)化[18]。為了能夠在AGV 路徑規(guī)劃巨大的解空間中探索更好的解，避免陷入局部最優(yōu)的情況，需要對變異過程進(jìn)行改進(jìn)，（1+1）-ES 是較好的方法。

（1+1）-ES 的變異強(qiáng)度由正態(tài)分布N（0，δ）決定，δ 為變異強(qiáng)度，通過控制分布，選取擾動，用擾動影響進(jìn)化強(qiáng)度；通過對比擾動帶來的反饋，選擇成功變異的擾動，控制進(jìn)化方向，能否找到最優(yōu)解很大程度上取決于δ[19]。（1+1）-ES 的收斂過程遵循1/5 成功原則，當(dāng)個體中有1/5 的變異個體比原始個體優(yōu)秀時即判斷為即將收斂。收斂過程中如若未達(dá)到收斂條件，則增大變異強(qiáng)度，如若即將達(dá)到收斂條件，則減小變異強(qiáng)度。該策略根據(jù)歷史成功變異能力不斷調(diào)控δ，在很大程度上解決了使用其他優(yōu)化算法會出現(xiàn)的陷入局部最優(yōu)的問題。本文提出的（1+1）-ES 算法流程圖見圖2。

圖2 （1+1）-ES 算法流程圖Fig.2 (1+1)-ES algorithm flowchart

該算法過程如下：

1） 通過樣本產(chǎn)生初始個體x；

2） 通過初始個體x和變異強(qiáng)度δ 產(chǎn)生新的解，公式如下：

3） 計算個體的適應(yīng)度函數(shù)值f（x）和f（y），如果f（y）>f（x），則用y替換x；

4） 調(diào)控變異強(qiáng)度大小，重復(fù)操作2） 和3）直到滿足輸出條件后輸出結(jié)果，變異強(qiáng)度的公式如下（δɡ表示第ɡ 代個體的變異強(qiáng)度，ps表示變異成功率，Cd為固定參數(shù)）[20]：

本文提出的（1+1）-ES 算法在原（1+1）-ES 算法基礎(chǔ)上改進(jìn)了其適應(yīng)度函數(shù)，提高了適應(yīng)度函數(shù)的綜合程度，使其更適用于本文要解決的AGV路徑規(guī)劃問題。

3 仿真實(shí)驗

本文使用的路徑規(guī)劃算法在Python 語言和spyder 平臺進(jìn)行開發(fā)，相關(guān)軟件及第三方庫的版本如下：Python 3.8.5，geatpy2.6.0。程序調(diào)試和算例求解均在1 臺CPU 主頻為1.80 GHz，GPU 為NVIDIA GeForce MX150，內(nèi)存為8.00 GB 的個人計算機(jī)上完成。

3.1 AGV 靜態(tài)路徑規(guī)劃仿真實(shí)驗

在AGV 靜態(tài)路徑規(guī)劃中只考慮所有障礙物都是靜止?fàn)顟B(tài)的情況，即地圖中不存在動態(tài)障礙。地圖中靜態(tài)障礙物的尺寸皆設(shè)置為長3 個單位柵格長度、寬1 個單位柵格長度，AGV 由1 個單位柵格表示，AGV 的仿真任務(wù)為從起點(diǎn)運(yùn)行到終點(diǎn)。起點(diǎn)和終點(diǎn)也由1 個單位柵格表示，起點(diǎn)的坐標(biāo)為（0，0），終點(diǎn)的坐標(biāo)為（20，20）。其他各參數(shù)設(shè)置見表1。

表1 參數(shù)設(shè)置信息Table 1 Parameter setting information

使用本文設(shè)計的（1+1）-ES 算法得到的部分最優(yōu)路徑見圖3，路徑具體信息見表2。

表2 基于（1+1）-ES 的部分路徑具體信息表Table Partial path specific information based on(1+1)-ES

圖3 基于（1+1）-ES 的AGV 靜態(tài)路徑規(guī)劃圖Fig.3 Static path diagram of AGV based on(1+1)-ES

由圖3 和表2 可以看出，使用本文提出的基于（1+1）-ES 的AGV 靜態(tài)路徑規(guī)劃得到的路徑在地圖中分布較廣，沒有出現(xiàn)大部分路徑高度重合的情況，即算法在整個過程中沒有出現(xiàn)陷入局部最優(yōu)的情況，搜索范圍較為廣泛。這4 條路徑雖然都被算法的適應(yīng)度評價指標(biāo)評價為最優(yōu)路徑，具體路線不同，但這些路徑的優(yōu)勢各不相同。路徑1 開始所行方向與終點(diǎn)相差較遠(yuǎn)，所以路徑長度是4 條路徑里最長的，轉(zhuǎn)彎次數(shù)較少且角度較小所以路徑平滑度較為優(yōu)秀；路徑2 的路徑長度最小，但由于AGV 三次轉(zhuǎn)彎的角度都偏大，所以路徑平滑度相對較差；路徑3 由于轉(zhuǎn)彎次數(shù)較多且轉(zhuǎn)彎角度較大，所以路徑平滑度是4 條路徑里最大的，但總體運(yùn)行方向相比于其他3 條路徑最為接近起點(diǎn)與終點(diǎn)的直線，所以路徑長度較短；路徑4 的轉(zhuǎn)彎角度較小，所以路徑4 的路徑平滑度最小即轉(zhuǎn)彎角度總和最小，轉(zhuǎn)彎次數(shù)較少，所以路徑長度也較小?？傮w來說這4 條路徑的2 種指標(biāo)都較為優(yōu)秀，且所有路徑的碰撞風(fēng)險皆為0。

由上述仿真實(shí)驗結(jié)果可以看出：在靜態(tài)的環(huán)境下，使用本文設(shè)計的基于（1+1）-ES 的方法可以實(shí)現(xiàn)較為優(yōu)秀的路徑規(guī)劃，該算法對各項指標(biāo)都能夠有一定程度上的優(yōu)化，很大程度上避免了其他算法可能出現(xiàn)的陷入局部最優(yōu)的問題。

3.2 AGV 動態(tài)路徑規(guī)劃仿真實(shí)驗

考慮到AGV 的實(shí)際工作場地除了靜態(tài)障礙物外，會有工作人員隨機(jī)出現(xiàn)的情況，在原始的地圖上增加5 個隨機(jī)生成的柵格來代表可能會出現(xiàn)的工作人員。靜態(tài)障礙物的尺寸設(shè)置和向AGV 發(fā)布的模擬任務(wù)同靜態(tài)路徑規(guī)劃相同，算法的各參數(shù)設(shè)置也相同，具體參數(shù)設(shè)置見表2。為更加直觀地看出本文設(shè)計的基于（1+1）-ES 的優(yōu)勢所在，本文選擇將其結(jié)果與差分進(jìn)化算法和遺傳算法所得結(jié)果進(jìn)行對比分析。3 種算法皆使用同樣的參數(shù)和柵格地圖，其中遺傳算法的變異概率設(shè)置為0.8，交叉概率設(shè)置為0.6，得到的某一條最優(yōu)路徑如圖4 所示，路徑信息如表3 所示，算法收斂如圖5 所示。路徑平滑度較大，路徑長度也較長，這會降低AGV 的工作效率和增加對AGV 的損耗，另外未考慮碰撞的風(fēng)險；由差分進(jìn)化算法得到的最優(yōu)DE 算法路徑在運(yùn)行過程中同樣出現(xiàn)多次轉(zhuǎn)彎角度過大的情況導(dǎo)致該條路徑的路徑平滑度較大，路徑長度較長，并且在運(yùn)行過程中有一處與障礙物相距過近，增加了AGV 與障礙物碰撞的風(fēng)險；由（1+1）-ES 得到的最優(yōu)（1+1）-ES 算法路徑運(yùn)行方向總體與起點(diǎn)和終點(diǎn)間的連線最為接近，所以路徑長度相較于其他2 條路徑最短，并且轉(zhuǎn)彎次數(shù)較少，所有轉(zhuǎn)彎角度皆小于45°，所以路徑平滑度最小，無碰撞風(fēng)險。

表3 基于不同算法的部分路徑的具體信息表Table 3 Partial path specific information based on different algorithms

圖4 3 種不同算法的AGV 動態(tài)路徑規(guī)劃圖Fig. 4 AGV dynamic path diagram with three different algorithms

圖5 算法收斂曲線Fig.5 Algorithmic convergence curve

由圖5 可以看出，遺傳算法的算法收斂曲線在迭代次數(shù)為0~38 次之間波動較大，運(yùn)行不穩(wěn)定，在迭代38 次時達(dá)到收斂狀態(tài)；差分進(jìn)化算法的收斂曲線在迭代次數(shù)為0~36 次之間波動較大，運(yùn)行同樣不夠穩(wěn)定，在迭代36 次時達(dá)到收斂狀態(tài)；（1+1）-ES 前期有一處波動，總體運(yùn)行較為穩(wěn)定，且收斂速度相比于其他2 種算法更快，在迭代20 次時達(dá)到收斂狀態(tài)。

綜合分析，可以看出本文設(shè)計的（1+1）-ES 在適應(yīng)度指標(biāo)、運(yùn)行穩(wěn)定和收斂速度這3 個方面都明顯優(yōu)于遺傳算法和差分進(jìn)化算法，優(yōu)勢總結(jié)具體見表4。

表4 不同算法結(jié)果的對比Table 4 Comparison results of different algorithm results

由圖4 和表3 可以明顯看出，在設(shè)置同樣的參數(shù)和地圖條件下，本文設(shè)計的（1+1）-ES 算法在路徑長度和路徑平滑度上明顯優(yōu)于遺傳算法和差分進(jìn)化算法。由遺傳算法得到的最優(yōu)GA 算法路徑在運(yùn)行過程中多次出現(xiàn)轉(zhuǎn)彎角度過大的情況，其中1 個轉(zhuǎn)彎的角度超過了90°，導(dǎo)致該條路徑的

4 結(jié)語

本文提出了一種基于（1+1）-ES 的AGV 路徑規(guī)劃改進(jìn)算法，從路徑長度、路徑平滑度和碰撞風(fēng)險3 個方面改進(jìn)了算法的適應(yīng)度函數(shù)，使其更加適用于AGV 的路徑規(guī)劃問題。

在仿真實(shí)驗中設(shè)計柵格地圖來模擬實(shí)際港口AGV 的工作環(huán)境，通過仿真實(shí)驗可以看出，在靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃中，本文提出的改進(jìn)后的（1+1）-ES 算法均提高了搜索效率，并有效解決了算法求解易陷入局部最優(yōu)的問題，驗證了本文提出的基于（1+1）-ES 在解決AGV 路徑規(guī)劃中的高效性和可靠性。

本文在有限障礙物和單個AGV 的前提下進(jìn)行了路徑規(guī)劃研究，在后續(xù)的研究中，本文將對障礙物的隨機(jī)性和不確定性進(jìn)行進(jìn)一步的復(fù)雜假設(shè)，并且加入其它的AGV 進(jìn)行多AGV 的路徑規(guī)劃問題研究。