魯 韻 王 姣

(武昌首義學(xué)院機(jī)械與自動(dòng)化學(xué)院 武漢 430074)

0 引 言

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

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

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

1 最短路徑問題的數(shù)學(xué)描述

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

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

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

(1)

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

(2)

若式(2)中的級(jí)數(shù)收斂，則有

(3)

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

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

(4)

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

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

(5)

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

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

(6)

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

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

(7)

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

2 基于改進(jìn)貝爾曼方程的極值算法

2.1 研究假設(shè)

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

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

2.2 改進(jìn)貝爾曼方程的極值算法

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

定義：

(8)

(9)

(10)

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

(11)

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

(12)

(13)

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

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

(14)

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

(15)

等價(jià)于

(16)

引入一個(gè)零函數(shù)：

(17)

(18)

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

(19)

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

1)J*為T在R(X)內(nèi)的唯一不動(dòng)點(diǎn)，對(duì)所有的J∈R(X)，Tk(J)可以將轉(zhuǎn)換為J*.

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

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

3 試驗(yàn)結(jié)果與分析

3.1 標(biāo)準(zhǔn)最短路徑規(guī)劃仿真結(jié)果與分析

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

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

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

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

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

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

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

表1 極值算法和快速行進(jìn)算法的計(jì)算時(shí)間比較 單位：s

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

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

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

4 結(jié) 束 語

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