基于多智能體系統(tǒng)的應急車輛路徑誘導策略研究

趙 欣，陳珊珊

（武漢理工大學 交通學院，湖北 武漢 430063）

基于多智能體系統(tǒng)的應急車輛路徑誘導策略研究

趙 欣，陳珊珊

（武漢理工大學 交通學院，湖北 武漢 430063）

以協(xié)助應急車輛通行為目的，從交叉口信號優(yōu)先控制與路徑誘導兩方面進行統(tǒng)一考慮，建立了基于多智能體系統(tǒng)（Multi-Agent System，MAS）的應急車輛路徑誘導策略。應用相位智能體和管理智能體實現(xiàn)應急車輛在交叉口的信號優(yōu)先權，在路段上提出了車載智能體和路段智能體，與交叉口兩智能體相協(xié)同，并以改進的Dijkstra算法為決策算法，共同完成應急車輛路徑誘導過程。最后通過Starlogo軟件并借助Matlab完成了對應急車輛誘導過程的驗證。仿真結果證明了該方法的有效性。

應急車輛；信號優(yōu)先；路徑誘導；多智能體系統(tǒng)

1 引言

近些年來由于自然災害和人為因素而導致的突發(fā)事件頻繁發(fā)生，為盡可能降低這些突發(fā)事件帶來的人身財產損失，應急車輛如何更安全、高效地到達災難現(xiàn)場是各國應急部門共同關注的問題。目前國內外學者就應急車輛在交叉口的信號優(yōu)先權設置及路徑誘導兩方面都取得了一定的成果。Kwon等[1]先運用Dijkstra算法優(yōu)化了應急車輛的出行路線，再對已選路線上所經過的交叉口信號進行優(yōu)化設置；Yang等[2]針對某一區(qū)域發(fā)生的突發(fā)事件提出了應急車輛調度的建議，并建立了路線優(yōu)化的模型；Yuan[3]針對應急物流建立了一個以時間最短為目標的路徑優(yōu)化模型，該模型考慮了應急車輛通行時間與災害擴散程度之間的關系；Wang等[4]提出了在車

路協(xié)同的環(huán)境下應急車輛信號優(yōu)先系統(tǒng)的設計和實現(xiàn)；鐘源[5]在假設路徑最短的前提條件下,結合多智能體協(xié)調技術，應用多級模糊決策算法，對應急車輛的信號優(yōu)先控制問題進行了研究；劉帆[6]通過對應急物流車輛在路徑優(yōu)化中所需考慮的主要因素進行歸納分析后，以行駛成本和安全違背成本最小為目標，建立了路徑優(yōu)化模型，并運用遺傳算法對該模型進行求解。從國內外的研究現(xiàn)狀來看，應急車輛的相關研究一般都是側重于某一方面，如應急車輛檢測手段、應急車輛信號優(yōu)先控制策略、路徑優(yōu)化等，并未在尋求合理的信號優(yōu)先控制前提下對應急車輛出行路線建立完善的誘導體系。本文試圖通過對解決交通問題有一定優(yōu)越性的多智能體技術來對基于交叉口信號優(yōu)先控制的應急車輛路徑誘導策略進行研究。

2 問題描述

本文問題可描述為：假設一個有向路網N=(V，A)，其中V={1,2,…,i,i+1,…,n-1,n}是節(jié)點集合，1代表救援中心的所在地；2,…,n-1表示路網的中間節(jié)點，即交叉口；n代表災難現(xiàn)場。A為弧集合，表示應急車輛可能走的路段集合。如其中(i,i+1)∈A(i=1,…,n-1)表示路網中相鄰交叉口中間的路段。

此外，在計算應急車輛的路段行程時間時，由于本文考慮的是動態(tài)路徑誘導，故車輛在路段的行駛速度數據將結合歷史數據和實時路段信息獲得，并采取時段分析法得到速度離散曲線，具體如下：將一天分成若干個相同長度的時間段在時段Tj內車輛在路段(i,i+1)的行駛速度相同，記為而在交叉口的行程時間記為假設應急車輛在時刻離開第i個交叉口，則在路段(i,i+1)的應急車輛行駛時間計算公式為[7]：

則：

本文主要考慮應急車輛行駛的時間效應，故以時效性為決策屬性，目標函數式可表示為：

其中l(wèi)i,i+1表示相鄰交叉口之間的路段長度，ti,i+1表示應急車輛通過路段(i,i+1)的時間，ti表示應急車輛通過交叉口的時間表示車輛在第j個時段內通過路段(i,i+1)的平均速度

應急車輛通過交叉口i的時間ti由于本文信號優(yōu)先控制方法未投入使用，故無歷史數據，可根據不同時段的交通信息仿真模擬得到。

3 基于交叉口信號優(yōu)先控制的應急車輛路徑誘導系統(tǒng)

本文結合了文獻[8]對應急車輛在交叉口信號優(yōu)先進行控制的研究，其以MAS為基礎，建立了相位智能體（Phase Agent，PA）和管理智能體(Management Agent，MA)兩種模型，依托MAS的靈活性、強適應性特征及內部可協(xié)調性的原理，并運用模糊推理完成了系統(tǒng)的決策過程，實現(xiàn)了相序可變的交叉口信號優(yōu)先控制策略，在有效保證了應急車輛優(yōu)先權和安全性的前提下減小了對常規(guī)車輛的影響。下面重點介紹與交叉口信號優(yōu)先控制相結合的應急車輛路徑誘導系統(tǒng)。

路徑誘導的處理方法可分為集中式和分布式，本文希望借助智能體和改進的Dijstra算法來實現(xiàn)信息收集

分布式和計算集中式共同處理應急車輛動態(tài)路徑誘導問題。

3.1 多智能體系統(tǒng)（MAS）

MAS是由多個單一的智能體組合而成，該系統(tǒng)內的智能體之間能夠通過信息共享實現(xiàn)相互學習，并協(xié)調統(tǒng)一，對實現(xiàn)復雜系統(tǒng)的控制優(yōu)化尤為有效。近些年來，MAS大量應用在智能交通、交通控制及電子商務等領域中，而本文中研究的應急車輛在交叉口的信號優(yōu)先控制及路徑誘導也尤為適合MAS的應用。因為交通網絡中具有明顯較強的物理關聯(lián)性，而這種關系能夠為多智能體間進行選擇性地相互交流和協(xié)商帶來便利，故而可以大大簡化各智能體間的信息傳遞問題。因此本文將采用MAS技術解決應急車輛的信號優(yōu)先控制及路徑誘導問題。

3.2 應急車輛路徑誘導的多智能體模型

根據需要，建立兩種智能體模型，即車載智能體模型（Vehicle Agent，VA）和路段智能體模型（Road Agent，RA），VA按經過計算得到的最短路徑方案運行并嚴格按照信號燈的指示進行停駛，RA為車輛運行智能體提供各路段實時的交通信息以供VA進行實時行駛路徑決策。

VA的運作流程為：首先，結合車輛屬性，VA按照其內部存儲獲得的最短路線方案開始運行。運行過程中，VA通過通訊器接收RA發(fā)送的路段交通信息，本文中指車輛運行平均速度信息，通過在控制器中計算來進行路線選擇決策。此外，VA還可以實時地向PA發(fā)送車輛的行駛狀態(tài)。一旦從通訊器獲得信號指令，車輛將嚴格依照信號指令行駛。VA的建立很好地將應急車輛路徑誘導系統(tǒng)與信號優(yōu)先控制系統(tǒng)結合在一起。

RA的工作流程為：控制器通過感應器獲得路段實時交通信息，并根據知識庫中存有的道路基本信息計算得到車輛的平均速度信息，再運用通訊器實現(xiàn)各相鄰RA之間以及RA與VA的信息交互，每隔5min該路段智能體將各路段反饋的信息發(fā)送給應急車輛VA，VA即可通過新的交通數據進行路線決策。

各智能體之間的關系如圖1所示。

3.3 改進Dijkstra算法

為實現(xiàn)車輛運行智能體的動態(tài)路線生成功能及根據救援系統(tǒng)的短距離特征，本文引入改進Dijkstra算法，該路徑誘導只針對應急車輛，故不會產生潛在的“交通聚集”和“擁擠漂移”等問題，加大了該算法的準確有效性。

（1）改進的Dijkstra算法流程圖如圖2所示。其中權值包括應急車輛路段行程時間和通過后續(xù)交叉口時間。

圖1 多智能體關系

圖2 改進的Dijkstra算法流程

（2）應急車輛動態(tài)路徑行駛方案。指揮中心確定救援車輛行駛時段及災害地點后，根據相關歷史數據，按照上述方法確定出以救援中心和災害地點為起終點的應急救援車輛路徑的初始方案。但由于在實際交通路網中會有各種不確定因素存在，如交通事故或臨時道路維修等，故應急車輛行駛車速不可能完全符合歷史規(guī)律，因此需要根據實時交通信息即路段車速變化情況對車輛在行駛途中的路徑進行調整。而交通數據的采集

及平均速度的計算可借助路段智能體來完成。如果由獲得的實時數據計算得到的車輛最優(yōu)路徑與初始方案不同，并且新路線比原路線的節(jié)省時間達到可接受的范圍，那么就接受新的路徑行駛方案；否則，維持原路線方案不變。

4 仿真實驗

本文將借用宋輝華[8]仿真得到的應急車輛在交叉口定時信號控制和信號優(yōu)先控制下通過時間的數據，運用仿真軟件Starlogo并借助Matlab對基于交叉口信號優(yōu)先控制的應急車輛路徑誘導過程進行仿真，目的是為了說明本文給出方法的可行性與有效性。

4.1 路徑誘導仿真實驗條件說明

為使實驗簡化，且方便編程實現(xiàn)，對仿真環(huán)境作如下標定：

（1）仿真道路為雙向2車道。

（2）由于本實驗采用人工數據，在不影響實驗目的的前提下，本實驗中各路段不同時段內應急車輛速度由random形式隨機產生，并在30-45km/h之間產生，時段間隔設置為5min。

（3）社會車輛對應急車輛在路段上的影響已由應急車輛平均速度反映，故本實驗在路段上將不產生社會車輛。

（4）本實驗假設各個交叉口的應急車輛通過時間不變且相同，在定時控制和信號優(yōu)先控制下分別為宋輝華[8]仿真實驗得到的平均通過時間43s和36s。

Starlogo有良好的可視化仿真及編程界面，通過程序控制中心、仿真執(zhí)行窗口及各種輸出窗口獲得所需的數據及結果。

4.2 路徑誘導對比實驗設計及結果分析

由于采用人工數據，故本實驗采取隨機生成的方式得到各路段車輛平均行駛速度，以總行程時間為評價指標，在相同仿真環(huán)境下，分別對基于信號定時控制和信號優(yōu)先控制下的路徑誘導、初始路徑誘導模式和應急車輛動態(tài)路徑誘導模式兩組進行對比實驗，各情況運行10次，其中前者以總行程時間為評價指標進行比較，后者分別基于不同的車速降低量和不同的車速突變路段率對兩方案進行對比，以總行程時間節(jié)省量為評價標準，這里的車速突變路段率指應急車輛在誘導路徑上行駛一段時間后車速降低10km/h以上的未經過路段占總未經過路段的百分比。

（1）初始路徑誘導模式基于信號定時控制和信號優(yōu)先控制條件下的實驗對比。該實驗是基于宋輝華[8]在仿真實驗中得到在定時信號控制和信號優(yōu)先控制下應急車輛通過交叉口的時間，分別為43s和36s，且在應急車輛行駛過程中突變車速道路百分比為0,即本文提出的初始路徑誘導模式下進行的。

①各路段不同時段歷史速度生成。本實驗以5min為時段間隔，由Starlogo軟件采用random形式隨機產生的歷史速度如圖3所示，圖中各路段上三個速度值從左至右對應時段分別為系統(tǒng)時間0:00-0:05、0:05-0.10、0:10-0:15。

圖3 各時段對應速度（km/h）

②各路段行程時間計算。應急車輛從0時出發(fā)前，根據應急車輛通過交叉口的時間和路段行駛時間公式預測到各路段應急車輛的行駛時間。在定時信號控制和信號優(yōu)先控制條件下各路段應急車輛行駛時間分別如圖4、圖5所示，圖中Node表示交叉口，各相鄰交叉口間的數值即應急車輛路段行駛時間值，由于本實驗中從救援點到受災點的總路程較短，總行程時間不超過15min，而時段間隔為5min，故圖4、圖5對應路段中大部分路段應急車輛到達時間都在同一時段內，根據公式得到的路段行駛時間值相同，但不影響兩者之間總行程時間的對比。

由Matlab得出的最短路徑結果見表1。

圖4 定時信號控制下行駛時間（s）

圖5 信號優(yōu)先控制下行駛時間(s)

表1 最短路徑輸出結果表

由Matlab得出最短路徑分別為1-2-5-9-12-15-16，1-2-5-9-13-15-16。其行程總時間分別為533s和489s，節(jié)省44s，該實驗表明了基于信號優(yōu)先控制的路徑誘導系統(tǒng)的有效性，同時也驗證了路徑誘導系統(tǒng)的實時性。

（2）基于信號優(yōu)先控制條件下的初始路徑誘導和實時路徑誘導模式實驗對比。該實驗是在基于宋輝華[8]的信號優(yōu)先控制下交叉口通過時間即36s的前提下進行的，并以初始交叉口做決策點為例。

①不同車速突變量下的誘導方案對比。以基于信號優(yōu)先控制下的初始路徑誘導方案為初始方案，即初始路線方案為1-2-5-9-13-15-16，假設路線的交通信息發(fā)生變化，如交通事故或該時段正處于交通狀況轉變期，致使該路段車輛平均速度發(fā)生突變，分別以10km/h、20km/h及30km/h的下降量為例進行實驗。得出結果見表2。

表2 不同車速突變量下的行程時間對比表

由表2可以看出，隨著路段車速下降量的增大，運用調整的路徑誘導方法節(jié)省的時間越多，當降低30km/ h時，節(jié)省量可達到33%。故本文所述方案在突發(fā)路段交通事故時或路段交通狀況正處于轉變期時更為有效。

②不同的車速突變路段率下的誘導方案對比。該實驗以20km/h的車速下降量為突變量，當車速突變路段率分別為1/3、2/3及1的情況下進行的，各運行10次。

表3分別為車速突變路段率為1/3時初選方案與調整方案總行程時間對比表。

表3 初選方案與調整方案總行程時間對比表

不同車速突變路段率下的時間節(jié)省量整理見表4。

表4 不同車速突變路段率下的時間節(jié)省量（%）

分別以15%、20%、25%及30%的時間節(jié)省量作為

路線改變方案的基準，其路線改變需求率如圖6所示，圖中路線改變需求率是指在本實驗不同車速突變路段率情況下各運行10次中不同時間節(jié)省量為基準時應急車輛需要改變路線的次數與總次數（即10次）的比值。

圖6 路線改變需求率

從表4可以看出，隨著應急車輛行駛路線上未經過路段的車速突變路段率的增高，調整路徑誘導方案下的最短路徑的時間節(jié)省量越大，最大時可達43%，而從圖6可以看出，隨著路線改變方案基準的減低，應急車輛對路線改變的需求率越高。

5 結束語

本文主要研究了應急車輛在應急響應中以交叉口的信號優(yōu)先控制為前提的路徑誘導問題，運用多智能體系統(tǒng)與改進的Dijkstra算法相結合的方式對問題進行建模與求解。目的在于在交叉口保證應急車輛享有時間優(yōu)先權的同時實現(xiàn)常規(guī)車輛運行效率的優(yōu)化，在路段上變靜態(tài)路徑誘導為根據實時交通變化而改變的動態(tài)路徑誘導，以實現(xiàn)應急車輛運行最優(yōu)化。

[1]Kwon E L,Kim S.Development of Dynamic Route Clearance Strategies for Emergency Vehicle Operations,Phase I[R].Minneapolis:Center for Transportation Studies and Department of Computer Science,University of Minnesota,2003.

[2]Yang S,Hamedi M,Haghani A.Online dispatching and routing model for emergency vehicles with area coverage constraints[J]. Transportation Research Record,2005,(1 923):1-9.

[3]Y Y,D W.Path Selection model and algorithm for emergency logistics management[J].Computer and Industrial Engineering, 2008,56(3):1 081-1 094.

[4]Wang Y,Wu Z,Yang X,et al.Design and Implementation of an Emergency Vehicle Signal Preemption System Based on Cooperative Vehicle-Infrastructure Technology[J].Advances in Mechanical Engineering,2013,(December).

[5]鐘源.多交叉口應急車輛信號優(yōu)先協(xié)調控制研究[D].哈爾濱:哈爾濱工業(yè)大學,2011.

[6]劉帆.基于遺傳算法的應急物流車輛路徑問題研究[D].西安:西安科技大學,2012.

[7]劉建美,馬壽峰,馬帥奇.基于改進的Dijkstra算法的動態(tài)最短路計算方法[J].系統(tǒng)工程理論與實踐,2011,(6):1 153-1 157.

[8]宋輝華.基于多智能體的多應急車輛信號優(yōu)先控制問題研究[D].哈爾濱:哈爾濱工業(yè)大學,2008.

Study on Emergency Vehicle Path Guidance Strategy Based on Multi-agent System

Zhao Xin,Chen Shanshan
(School of Communications,Wuhan University of Technology,Wuhan 430063,China)

In this paper,in order to ensure the smooth passage of the emergency vehicles and considering from the aspects of crosssection signal priority control and path guidance,we built the MAS-based emergency vehicle path guidance strategy.First we used the phase agent and management agent to realize the signal priority of the emergency vehicles at road cross-sections and then proposed the on-board agent and road section agent to collaborate with the foregoing two agents to finish the path guidance of the emergency vehicles.At the end, using Starlogo and Matlab,we demonstrated the emergency vehicle path guidance process which showed the validity of the method proposed in this paper.

emergency vehicle;signal priority;path guidance;multi-agent system

F253.9;U116.2

A

1005-152X(2016)10-0042-06

10.3969/j.issn.1005-152X.2016.10.012

2016-09-12

教育部留學回國人員科研啟動基金“基于時間窗約束的實時交通網絡流應急增載優(yōu)化研究”（44130041）

趙欣（1979-），男，湖北人，副教授，研究方向：智能交通系統(tǒng)、交通控制優(yōu)化；陳珊珊（1990-），女，安徽人，交通運輸規(guī)劃與管理專業(yè)碩士，主要研究方向：智能交通系統(tǒng)、交通控制優(yōu)化。