一種增量式多目標優化的智能交通路徑誘導方法

文孟飛　彭軍　劉偉榮　李沖　張曉勇

摘要：路徑誘導是一種主動引導車輛合理分流來解決城市交通擁堵的方法.本文提出了一種基于增量搜索的多目標優化路徑誘導方法.該方法首先利用圖論法將復雜路網抽象為點線的賦權圖，引入多目標優化變量，建立路網模型；然后在啟發式搜索基礎上引入增量搜索，結合全局規劃和局部動態重規劃，實現車輛的實時路徑誘導.仿真結果表明該方法能有效地解決復雜路網中車輛的實時路徑誘導問題.

關鍵詞：動態重規劃；增量搜索；路徑誘導

中圖分類號：U491.123文獻標識碼：A

當前，緩解城市交通擁堵問題的方法主要有兩種：一是加大城市路網建設力度，提升路網吞吐量；二是發展智能交通系統（Intelligent Transportation Systems，ITS），提高道路運行效率.針對各大城市越來越有限的土地資源，以智能學習的方式，優化城市路網運營和管理，顯然是一種最實際的解決方案.動態交通路徑誘導系統是ITS的一個重要方向，對城市交通路網管理的效果愈發顯著.它采用檢測技術、計算機技術、網絡技術等高新手段，基于實時交通信息采集、處理與傳輸，通過中心式、分布式等多種誘導方式，為駕駛員提供交通事件、行程時間和優化路徑等動態信息，可引導駕駛員避開擁擠走最佳行駛路線，從而實現路網交通流的均衡動態分配，有效緩解交通擁擠.高效的路徑選擇算法是動態交通路徑誘導系統的關鍵技術.從本質上來說，路徑選擇算法需集中式收集整個路網信息，選擇恰當的交通流函數，通過高效的算法對路網進行快速更新，動態地找尋滿足一定約束條件的最優路徑.構建路網模型，選擇高效算法，動態地選擇源節點到目的節點的最優路徑，從局部來說對駕駛員路徑選擇作出最優安排，從總體上說可優化城市路網流量的均衡分配，解決路網的擁堵問題.

動態路徑誘導在ITS、通信系統和機器人等人工智能方面應用廣泛.若城市路網是靜態網絡，路段信息不變且可知，則很容易通過全局規劃找尋一條從源狀態到最終狀態的最佳路徑.但實際情況卻是，交通信息時刻都在變化，環境信息動態改變，實際行駛過程中的路網情況和初始情況差異很大，此時需不斷更新路網信息，實時找尋源狀態節點到最終狀態節點的動態最優路徑.一些學者已研究了在動態環境情況下找尋最優路徑的方案和算法思想1-4]，局部重規劃就是其中一種關鍵算法，能有效地實現動態環境下的路徑誘導，將歷史數據保留，通過算法重用，減少了重新獲取整個路網信息的工作量.

經典的路徑誘導方案通常只針對單個因素進行優化，但實際上現實問題往往由多方面因素相互制約，單個因素很難正確描述，因而路徑誘導往往需對多個因素進行同時處理和優化，即多目標路徑誘導.作為人工智能的關鍵方法，啟發式搜索已應用于多目標路徑誘導研究，很多學者進行了相關研究.Stewart和White將A*算法延伸到多個優化變量，并利用啟發式搜索解決路徑誘導，從而提出了多目標啟發式搜索模型5]；Dasgupta改進了多目標啟發式搜索，引入非單調的啟發信息用于解決VLSI設計難題6]；Mandow針對節點難以擴展問題，將路徑擴展引入多目標啟發式搜索，提高了搜索算法的準確性6-7]；Harikumar和Dasgupta總結了深度優先搜索算法在多目標路徑誘導上的應用8-10].通過對多個變量進行優化，多數狀態空間搜索規劃器改進了智能規劃技術11-13].

文獻14-16]將增量搜索思想引入路徑誘導局部重規劃.在許多相似度較高的多目標優化問題中，環境信息只是局部變化，若重新進行全局規劃會帶來不必要的計算復雜度，若能夠對歷史信息重用，則可提高算法效率.本文提出了一種當檢測到環境信息動態改變時，怎樣實時選擇最優路徑以實現全局最優規劃的路徑誘導方案，先由當前的靜態路網信息利用啟發式搜索算法作全局規劃，找尋最短路徑；車輛行進過程中，一旦路網信息變化，就需不斷更新歷史信息，在之前規劃的信息前提上再作增量搜索，減少計算復雜度，提高算法效率，從而利用動態局部重規劃找尋目前狀態到最終狀態的最優路徑方案.

1構建路網模型

城市交通網絡錯綜復雜，但都是由單個交叉路口構成的，可利用圖論法抽象為點線的網格拓撲，用點代表平面交叉口，用線代表路段，如圖1所示.這樣路網可以抽象為由節點集合、弧段集合和路權集合等構成的幾何賦權圖.

通過將實際交通路網抽象出來，以數學形式存儲路網模型.首先根據啟發式搜索算法找出從起始狀態節點到目標狀態節點的最優路徑；當車輛在行駛過程中某些路段權重發生變化，若全局更新則會降低系統實時性，本文通過動態重規劃算法對經過該路段的局部路徑網絡進行代價更新，從而可提高算法效率和系統實時性.

2多目標啟發式搜索算法

啟發式搜索算法應用到復雜交通網路，且當路況變化頻繁時，啟發式數量急劇增長，算法時間消耗較大，適應性降低.增量搜索算法能很好地利用路網變化的局部變化信息，避免全局更新，對提高算法的效率具有積極意義.

3基于增量搜索交通動態路徑誘導

城市復雜交通網絡日益擁堵，動態交通誘導思想可以很好地改善交通狀況.考慮城市交通環境時刻變化給算法效率帶來的問題，可在之前已有的搜索信息上只對變化的部分進行局部動態重規劃，從而提高算法效率.增量搜索算法可實現局部的動態重規劃，來解決環境時刻變化問題.本文將增量搜索算法引入到啟發式搜索算法，提出了動態多目標路徑誘導算法DMRGA（Dynamic Multiobjective Route Guidance Algorithm），該算法既保留了啟發式搜索快速高效的特點，又能適應于復雜的動態網路環境，進行動態路徑誘導.在本文提出的路網模型上，結合啟發式搜索算法和增量搜索算法的思想，進行全局規劃和動態局部重規劃，很好地解決了實時找尋最優路徑的問題，解決車輛動態路徑誘導問題.

DMRGA算法分為兩部分：全局規劃及局部動態重規劃.全局規劃根據已知的靜態城市網路信息找尋源狀態到最終狀態的最優路徑；局部規劃則是在路網環境信息動態變化時，先在局部做靜態規劃，然后在原有基礎上作增量搜索，進行動態重規劃，實時調整最優路徑.當檢測路網信息發生變化時，須馬上作出響應，動態調整目前節點到最終節點的最優路徑，以免造成不必要的延時，影響路網全局性能.

實驗結果表明，車輛在行駛過程隨著路網某路段權重的更新，其最優行駛路徑也在不斷更新，動態實時地調整行車路線，盡可能減少行車耗時.實驗以一個小型的部分路網作為場景，可以擴大到整個路網，實時給出車輛優化路徑.

5結論

本文針對時刻變化的路網信息，提出一種基于增量搜索的多目標路徑誘導方法.該方法首先利用圖論法將復雜路網抽象為點線的賦權圖，引入多目標優化變量，建立路網模型.然后在啟發式搜索基礎上引入增量搜索，結合全局規劃和局部動態重規劃，實現車輛的動態路徑誘導.首先進行全局規劃，利用多目標啟發式搜索算法找尋最優路徑集合；當檢測到環境信息變化時，進行動態局部重規劃，在盡可能保留前次規劃的基礎上進行增量搜索，減少算法復雜度，提高效率，實時更新最優路徑.最后仿真結果表明該方法能有效地實時解決復雜路網中車輛的動態路徑誘導問題.

參考文獻

[1]ZHU Q B. Ants predictive algorithm for path planning of robot in a complex dynamic environmentJ]. Chinese Journal of Computers， 2005， 28（11）： 1898-1906.

[2]KOENIG S， LIKHACHEV M， FURCY D. Lifelong planning A*J]. Artificial Intelligence， 2004， 155（1/2）： 93-146.

[3]YANG J， ZHANG M. A twolevel path planning method for onroad autonomous drivingC]//2th International Conference on Intelligent System Design and Engineering Application， Sanya， China：2012：661-664.

[4]XI Y G， ZHANG C G. Rolling path planning of mobile robot in a kind of dynamic uncertain environmentJ]. Acta Automatica Sinica， 2002， 28（2）： 161-175.

[5]STEWART S B，WHITE C C. Multiobjective A*J]. Journal of the ACM， 1991， 38（4）： 775-814.

[6]OLIVEIRA RIOS L H， CHAIMOWICZ L. A survey and classification of A* based bestfirst heuristic search algorithmsC]//Advances in Artificial IntelligenceSBIA.Sao Bernardo do Campo， Brazil： 2010：253-262.

[7]MANDOW L， PEREZ J L DE AL CRUZ. A new approach to multiobjective A* searchC]// Proceedings of the 19th International Joint Conference on Artificial Intelligence. San Francisco， USA：2005：218-223.

[8]DASGUPTA P， CHAKRABARTI P P， DESAKAR S C. Multiobjective heuristic searchM]. Morgan Kaufman，1999

[9]XU Y Y，YUE W Y. A generalized framework for BDDbased replanning A* searchC]// Artifical Intelligences， Networking and Parallel/Distributed Computing. 10th ACIN International Conference on Software Engineering.Daegu South Korea， 2009： 133-139.

[10]HARIKUMAR S， KUMAR S. Iterative deepening multiobjective A*J]. Information Processing Letters， 1996， 58（1）： 11-15.

[11]REFANIDIS， VLAHAVAS I. Multiobjective heuristic statespace planningJ]. Artificial Intelligence， 2003， 145（1/2）： 1-32.

[12]SO M B，KAMBHAMDATI S. Sapa： A multiobjective metric temporal plannerJ]. Journal of Artificial Intelligence Research， 2003， 20： 155-194.

[13]SVEN K， MAXIM L， LIU Y X， et al. Incremental heuristic search in AIJ]. AI Magazine，2004， 25（2）：99-112.

[14]WEI W， OUYANG D T， LU N， et al. A multiobjective incremental heuristic search algorithmJ]. Journal of Jilin University：Science Edition， 2009， 47（4）：752-758.

[15]LU Y B， HUO X M， OKTAY A ，et al. Incremental multiscale search algorithm for dynamic path planning with low worstcase complexityJ]. IEEE Trannactionn on Systems， Man， and Cyberneticspart B： Cybernetics， 2011， 41（6）：1556-1569.

[16]SVEN K， SUN X X. Comparing realtime and incremental heuristic search for realtime situated agentsJ]. Auton Agent MultiAgent Syst，2009， 18：313-341.