計(jì)及路網(wǎng)權(quán)值時(shí)變特性的全局最優(yōu)路徑規(guī)劃

黎萬洪，胡明輝,b，陳 龍，饒 坤

(重慶大學(xué) a.汽車工程學(xué)院；b.機(jī)械傳動(dòng)國家重點(diǎn)實(shí)驗(yàn)室, 重慶 400044)

路徑規(guī)劃作為智能汽車的決策層，對(duì)于提高駕駛?cè)顺鲂行省⒕徑獬鞘袚矶戮哂兄匾饔谩Ｆ鹩欬c(diǎn)行程時(shí)間是人們出行普遍較為關(guān)心之處，因此也成為了路徑規(guī)劃的首要需求[1]，其評(píng)價(jià)指標(biāo)是路段行程時(shí)間的累加值。根據(jù)路段行程時(shí)間是否變化，可以將路徑規(guī)劃劃分為靜態(tài)路徑規(guī)劃(static path planning，SPP)和滾動(dòng)路徑規(guī)劃(rolling path planning，RPP)。

SPP主要研究起訖點(diǎn)的累積最小權(quán)值，如最短路程或最短靜態(tài)行程時(shí)間，較經(jīng)典的研究方法有Dijkstra算法、A*算法、蟻群算法等[2]，但都各有缺陷。近年來，國內(nèi)外學(xué)者針對(duì)上述算法提出了對(duì)應(yīng)的改進(jìn)策略，以提高算法的運(yùn)行效率和規(guī)劃精度。如針對(duì)A*算法易陷入局部最優(yōu)、搜索速度較慢的缺陷，顧青等[3]設(shè)計(jì)了新的啟發(fā)式估計(jì)能源成本函數(shù)以改善A*算法；Fu等[4]通過改進(jìn)當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的搜索策略提高了A*算法的搜索成功率；王維等[5]對(duì)估計(jì)路徑代價(jià)進(jìn)行指數(shù)衰減的方式加權(quán)，使得A*算法自適應(yīng)地搜索目標(biāo)點(diǎn)。蟻群算法同樣存在收斂速度慢、容易陷入局部最優(yōu)的缺點(diǎn)，王志中等[6]提出了螞蟻相遇和螞蟻回退策略，并改進(jìn)了信息素殘留方法。此外，文獻(xiàn)[7-8]也都對(duì)蟻群算法進(jìn)行了相應(yīng)的改進(jìn)。A*算法、蟻群算法等都屬于智能啟發(fā)式算法，無論如何改進(jìn)算法，其包含的隨機(jī)因子總有可能使路徑搜索陷入局部最優(yōu)，因而也就無法保證所得路徑是全局最優(yōu)解。盡管經(jīng)典的Dijkstra算法冗余度較高，但當(dāng)前計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)通信技術(shù)的巨大發(fā)展有效地彌補(bǔ)了這一不足，考慮到該算法能保證找到全局最優(yōu)解，仍不失為一種較好的方法。……