一種基于改進貝爾曼方程的最短路徑規(guī)劃算法

魯 韻 王 姣

(武昌首義學院機械與自動化學院 武漢 430074)

0 引 言

無人駕駛技術的快速發(fā)展給城市交通帶來了一定壓力.隨著交通網絡的規(guī)模越來越大，其路徑規(guī)劃也越來越復雜.最短路徑規(guī)劃作為提高無人駕駛車輛通行效率、緩解城市交通壓力的基本方法已成為研究熱點.

郭興海等[1]采用多目標與速度控制的方法提出了一種全局路徑規(guī)劃方法，該方法對靜態(tài)全局路徑規(guī)劃的效率提升明顯.趙衛(wèi)東等[2]通過添加約束的方法提出了一種兩階段搜索的A～*全局路徑規(guī)劃算法，相比于傳統算法，該算法改進了動態(tài)全局路徑規(guī)劃計算問題的效率.然而，全局路徑規(guī)劃考慮了地圖上所有的節(jié)點信息，通常非常耗時，因此提出最短全局路徑算法，如Voronoi圖方法[3]，單元分解法[4]和隨機規(guī)劃法[5]等.盡管這類算法執(zhí)行速度很快，但對于如何生成足夠的樣本以覆蓋和連接配置空間，以及如何優(yōu)化生成路徑等問題并未得到很好解決.在路徑規(guī)劃問題中效率和可達性的平衡一般要根據項目的實際情況進行取舍，這給工程實際帶來了一定的困難.

本文提出一種最短路徑規(guī)劃算法，該算法將目標集看作有限維的歐幾里德空間并采用改進貝爾曼方程選擇當前最佳的適宜型控制策略以解決其效率和精度問題.

1 最短路徑問題的數學描述

假設一個具有有限集合節(jié)點的圖為X∪{t}，一組有限的有向弧為A?{(x,y)|x,y∈X∪{t}}，其中t為目標節(jié)點.在每個x∈X節(jié)點處，可以從非空集合U(X)中選擇一個控制或動作u，它是有限集合U的子集.然后，從非空集Y(x,u)?X∪{t}中選擇一個后續(xù)節(jié)點y.那么對于所有的y∈Y(x,u)都有(x,y)∈A，此過程中的成本函數記為g(x,u,y).目標節(jié)點t具有可吸收性并且生成過程中不產生成本.所以從這個意義上說，目標節(jié)點t的唯一輸出弧是(t，t)且對所有的u∈U(t)都有g(t,u,t)=0.

為每個節(jié)點x∈X分配一個控制μ(X)∈U(x)，其中μ(X)為控制策略函，用M表示所有控制策略的有限集.在控制策略μ下從節(jié)點x0∈X開始的一條可能的規(guī)劃路徑可視為弧序列p：

p={(x0,x1),(x1,x2),…,}

(1)

對所有的k≥0都有xk+1∈Y(xk,μ(xk)).P(x0,μ)為從x0開始的控制策略μ下的所有可能路徑的集合.路徑p∈P(x0,μ)的長度為

(2)

若式(2)中的級數收斂，則有

(3)

當x0≠t時，對給定的控制策略μ，若路徑p∈P(x0,μ)見式(4)，則稱其為路徑終止.

p={(x0,x1),(x1,x2),…,(xm,t),(t,t),…}

(4)

式中：m為定義范圍內的一個正整數，x0,…,xm為不同的非目的節(jié)點.因為對所有u∈U(t)都有g(t,u,t)=0，控制策略μ下具有式(4)形式的終止路徑p的長度為

Lμ(p)=g(xm,μ(xm),t)+

(5)

有限弧子集描述了控制策略μ的一個重要特征信息：

Aμ=∪x∈X{(x,y)|y∈Y(x,μ(x))}

(6)

因此，在某種意義上Aμ與自弧(t,t)共同構成一組唯一路徑∪x∈XP(x,μ).若對每個x∈X都在P(x,μ)中存在一個終止路徑，則稱Aμ為目的地可連接型.如果弧Aμ的子圖是非循環(huán)的(即不包含循環(huán))，則稱Aμ為適宜型.因此，到目的節(jié)點時當且僅當∪x∈XP(x,μ)中所有路徑都是簡單路徑，則稱μ為適宜型.等價于當且僅當Aμ為目的地可連接型并且不存在循環(huán)時，μ為適宜型.“適宜型”策略的定義與隨機最短路徑問題中的定義一致，表示以概率1到達目的地的策略[6-8].如果μ為不適宜型，則稱尋求路徑的整個過程為不適宜過程，在這種情況下，弧Aμ的子圖會至少包含一個循環(huán)，見圖1.

對于適宜型的控制策略μ，對每個x∈X從x開始的有限可能路徑集合上最壞情況的路徑長度為

(7)

式中：Jμ(x)為弧Aμ的非循環(huán)子圖中從x到t的最長路徑的長度.由于此非循環(huán)圖中有有限多條路徑，因此，在簡單情況下可以通過枚舉并比較這些路徑長度的方法來找到Jμ(x).因此對于所有的x∈X，在經典最短路徑問題的假設下，需要找到一個適宜型的最佳控制策略μ使Jμ(x)最小.將此稱為魯棒最短路徑選擇問題(RSP)，且RSP中的極小化只建立在適宜型的控制策略之上[9-11].

2 基于改進貝爾曼方程的極值算法

2.1 研究假設

研究假設如下：①對每個有向圖集，至少存在一個適宜型的控制策略；②對于每個不適宜型的控制策略μ，弧Aμ子圖中的所有循環(huán)的長度都為正.

該假設與經典的確定性最短路徑問題中的假設一致，即Y(x,μ)由單個節(jié)點組成.假設①等價于假設每個節(jié)點都有一個路徑連接到目的地；假設(2)等價于假設圖中的所有有向循環(huán)的長度均為正.對假設②進一步補充為假設圖中的所有有向循環(huán)的長度均為非負數.該假設適用于所有弧長g(x,u,y)均為非負的情況，此情況下保留了存在零長度循環(huán)的可能性.

2.2 改進貝爾曼方程的極值算法

將函數Jμ(x)的定義擴展到不適宜型的情況中去.對于適宜型控制策略μ，Jμ(x)可由式(7)計算，對路徑p∈P(x,μ)，最長路徑的長度為

定義：

(8)

(9)

(10)

通過式(9)～(10)，對于一個適宜型的控制策略μ，任何最短路徑算法均可用于解決該最長路徑問題.對不適宜型的μ，Jμ(x)→∞, 相應的解決最長路徑問題的算法也就不再適用.此時，需要尋求一種最小化算法找到目標函數式(11)的最小值，使之同時適用于所有的x∈X.這與第一節(jié)中魯棒最短路徑選擇問題不同，該最小化算法要對所有的控制策略成立.

(11)

將式(11)所描述的極值問題抽象化，改寫為匹配貝爾曼方程式(8)～(9)的形式，從而將其轉化為抽象動態(tài)規(guī)劃問題.用E(X)表示函數集J:X→[-∞,∞]；用R(X)表示函數集J:X→(-∞,∞).注意，因為X是有限集，所以R(X)可以看作有限維的歐幾里德空間.引入映射H:X×U×E(X)→[-∞,∞]，為

(12)

(13)

對任意的控制策略μ，定義映射Tμ:E(X)→E(X)為

(TμJ)(x)=H(x,μ(x),J),x∈X

(14)

注意到不動點方程Jμ=TμJμ與貝爾曼方程(8)相同，映射Tμ:E(X)→E(X)可寫為

(15)

等價于

(16)

引入一個零函數：

(17)

(18)

將上式帶入式(8)，可得到：

(19)

這樣就所得到了在2.1的假設下經典確定性最短路徑問題的主要分析結果，即改進貝爾曼方程的極值算法，該算法可以抽象形式表述如下：

1)J*為T在R(X)內的唯一不動點，對所有的J∈R(X)，Tk(J)可以將轉換為J*.

2) 對最短路徑規(guī)劃問題，存在一個最佳的適宜型控制策略，并且只有在該適宜型控制策略下才能得到最優(yōu)解.

3) 當J=J*時，當且僅當對式(16)中所有的x∈X它都能取得最小值，那么控制策略μ即為最優(yōu).

3 試驗結果與分析

3.1 標準最短路徑規(guī)劃仿真結果與分析

通過仿真模擬比較改進貝爾曼方程的極值算法和快速行進算法在四個不同種類地圖上的最短路徑尋跡結果，見圖1～4.

圖1 快速行進算法與極值算法在地圖1的最短路徑規(guī)劃仿真結果對比

圖2 快速行進算法與極值算法在地圖2的最短路徑規(guī)劃仿真結果對比

圖3 快速行進算法與極值算法在地圖3的最短路徑規(guī)劃仿真結果對比

圖4 快速行進算法與極值算法在地圖4的最短路徑規(guī)劃仿真結果對比

由仿真結果可知，改進貝爾曼方程的極值算法生成的路徑比快速行進算法生成的路徑更精確，尤其是在垂直和水平方向.這是因為快速行進算法中所使用的2階龍格-庫塔法的累計誤差影響了原始常微分方程在路徑恢復中的數據精度.此外，極值算法所仿真出的最短路徑的起始位置和終點位置非常精確，但快速行進算法只在特定范圍內比較準確.然而，如果缺少適當的線性插值誤差校正，極值算法路徑的某些中間段部分會變得比快速行進算法路徑稍差.導致這種結果的原因在于路徑上的一個附加有限弧節(jié)點可能被錯誤地分配給另一個有限弧節(jié)點的父有限弧節(jié)點.

表1為當最大成本值較大時，極值算法和快速行進算法的計算時間.通過仿真分析，因此當最大成本值設置為較大數值時，極值算法的總時間比快速行進算法快.極值算法的計算速度是穩(wěn)定的，其計算速度僅取決于圖大小的比例，計算復雜度僅取決于有限弧節(jié)點的個數.極值算法對最大成本值沒有影響，因此其總時間幾乎等于有限弧節(jié)點的前向傳播時間.雖然快速行進也具有穩(wěn)定的傳播速度，但其路徑計算時間將取決于環(huán)境的復雜性，其收斂速度也受最大成本值的影響.

表1 極值算法和快速行進算法的計算時間比較 單位：s

3.2 涉及追蹤的動態(tài)路徑規(guī)劃仿真結果與分析

通過應用極值算法和路徑恢復規(guī)則，對涉及追蹤規(guī)避問題的動態(tài)路徑規(guī)劃進行了仿真.地圖尺寸也為100×100網格，藍色標記的路徑為追蹤者，綠色標記的路徑為躲避者，二者的速度均設置為1單位/s.躲避者的行動模式設置為試圖逃離追蹤者的追捕，結果見圖5.在第12 s，因為躲避者稍微向上移動，可以看到新規(guī)劃路徑在公共有限弧節(jié)點重置后被立即更新，說明極值算法具有較好的動態(tài)性能.從最后追捕結果可以得到如果躲避者的躲避路徑總使得障礙物出現在躲避者和追趕者之間，則當躲避著和追蹤者速度相同時該方法不能保證捕獲成功.然而，如果追蹤者的速度更快，由于極值算法在每個時隙都提供了最短的追蹤路徑，所以無論躲避者如何移動，該方法都能保證成功.

圖5 涉及追蹤的動態(tài)路徑規(guī)劃仿真結果

4 結 束 語

考慮到無人駕駛車輛的安全性和城市交通通行效率，其靜態(tài)和動態(tài)路徑規(guī)劃需要兼顧準確性、可靠性和快速性.文中提出了一種基于改進貝爾曼方程最短路徑規(guī)劃算法，該算法可以選擇當前最佳的適宜型控制策略以解決其效率和精度的平衡問題.仿真實驗結果表明，極值算法生成的路徑比快速行進算法生成的路徑更精確，尤其是在垂直和水平方向.極值算法的計算速度是穩(wěn)定的，其計算速度僅取決于圖大小的比例，計算復雜度僅取決于有限弧節(jié)點的個數，其動態(tài)路徑規(guī)劃性能優(yōu)于快速行進算法.但該方法在任務分配復雜的情況下，其協同能力仍有提升空間，有待后續(xù)進一步研究.