基于拍賣機制的災害多主體合作搜救仿真研究

唐 健，郭海湘，龔承柱，諸克軍

(1．西南大學經濟管理學院，重慶 400715；2.中國地質大學(武漢)經濟管理學院，湖北 武漢 430074；3.西安財經大學管理學院，陜西 西安 710100；4.中國地質大學(武漢)中國礦產資源戰(zhàn)略與政策研究中心，湖北 武漢 430074)

1 引言

大規(guī)模災害發(fā)生以后高效地開展救援工作是一個十分重要的問題。目前，關于災害應急救援的研究成果可根據其所處階段分為三類，“災前準備”，“災中應急”和“災后恢復”。相關研究成果多集中在“災前準備”階段的物資儲備選址[1-2]、應急預案設計[3]，“災中應急”階段的人員疏散[4]、應急物資調度[5-6]，以及“災后恢復”階段的應急能力評估[7]。應該肯定，這些研究從各個環(huán)節(jié)為災害救援工作的開展提供了重要的理論支撐，一定程度上提高了救援效率。本文的研究內容是“災中應急”階段的災后合作搜救，災后搜救是災害發(fā)生后復雜應急系統(tǒng)中的一個重要組成部分，然而，有關災后合作搜救的研究比較匱乏。

搜救隊伍間的合作救援，本質上是一個任務分配問題。關于主體間的任務分配模型較多[8]，有學者提出了基于合同網模型的任務分配機制[9-10]。也有學者將智能算法用于解決任務分配問題[11-12]，張朝潮[11]利用了遺傳算法求解了消防智能體之間的任務分配問題，琚春華和陳庭貴[12]提出了擴展的蟻群勞動分工模型?，F階段發(fā)展很快的是基于拍賣的任務分配算法[11, 13-16]，Nanjanath等[15]采用了連續(xù)單一物品拍賣方案。Nair等[14]研究了集中式的組合拍賣機制和分布式的拍賣機制。Ramchurn等[17]則將任務分配用聯(lián)盟形成來表示，通過F-Max-Sum算法解決這樣一個分布式約束優(yōu)化問題。

文中需要解決的任務分配問題是一個NP難問題[16]，可通過智能算法這樣的集中式任務分配方法求解。該類方法適用于環(huán)境已知并且確定的小規(guī)模問題，但是應用于災害現場搜救有一定的局限性，比如模型復雜性，決策延遲性等。拍賣算法這樣的分布式算法用來解決任務分配效率較高，靈活性強，容錯性好，非常適合于動態(tài)不確定性環(huán)境中的快速任務分配[8]。災害現場搜救場景的動態(tài)性，復雜性以及對時效性的需求使得拍賣算法成為一種較優(yōu)的選擇。

針對搜救隊伍在災害現場的搜索路徑，通過類似于Lév ywalks這樣的隨機游走模型[18-19]進行模擬。很多研究提出或者論證了Lévy walks在目標點隨機分布，可重復性或者不可重復性搜索，目標點靜止或運動等條件下，是較優(yōu)的隨機搜索策略[20-21]。胡超和李克平[22]在地震災害中引入了Lévy Flight模型對搜索過程進行模擬，結合基于救援物資調運的合作策略，分析了不同規(guī)模的搜救隊伍配置對救援效率的影響。

現有的研究大多只囊括了傷員的搜索，或者只研究了合作救援，兩者集成研究的較少。不難看到傷員的搜索本質上是路徑規(guī)劃與隨機游走模型，合作救援的模型實際上是一個任務分配問題，在救援過程中，兩者往往是密不可分的。

本文研究的是一個基于隨機游走的傷員搜索與合作救援的集成問題。構建了一個包含傷員和搜救隊伍的多Agent災害環(huán)境，假定被困傷員生存概率會隨時間增加依據特定函數發(fā)生變化[22-23]，用改進后的Truncated Lévy walks[20]模型對搜救隊伍的搜索行為進行仿真，提出了基于分布式拍賣機制的合作救援方案。這里以某滑坡災害頻發(fā)地區(qū)為例進行仿真，研究了該搜救方案對救援效果的影響，并將其與基于F-Max-Sum算法的合作救援機制進行對比。最后對所提出的搜救方案的魯棒性和敏感性進行了分析。

本文與其他同類研究的主要區(qū)別在于：

(1)采用多主體仿真方法構建了災害的搜索救援環(huán)境，與傳統(tǒng)救援模型相比，可以更好的體現災害場景的非線性性、動態(tài)性和復雜性。

(2)將搜索與救援結合起來進行研究，用Truncated Lévy walks模型模擬搜索行為，更適用于災后的環(huán)境特點，并改進了模型中參數，增加了模型靈活性。

(3)采用拍賣機制模擬了搜救隊伍間的合作關系，以整體最優(yōu)為目標，縮短了救援時間，提高了救援效率。

2 多主體模型描述

2.1 模型概述

模型包括兩類主體，分別是傷員Agent和搜救隊伍Agent。災害發(fā)生后，掩埋點在災害區(qū)域中隨機分布，每個掩埋點的掩埋程度不同，傷員Agent散落在不同的掩埋點中，每個掩埋點中可能存在一個或多個傷員Agent。搜救隊伍Agent在受災區(qū)域內進行搜索，當搜索半徑內存在傷員Agent時，搜救隊伍Agent能以一定概率發(fā)現它，發(fā)現傷員的搜救隊伍Agent成為拍賣者，合作范圍內的其他搜救隊伍Agent成為競拍者，當需要合作時，拍賣者與競拍者通過Agent間交互機制實現信息傳遞，包括傷員掩埋點坐標，掩埋情況等信息，合作達成后，針對該點展開救援，如圖1。

圖1 災害救援多主體仿真邏輯模型

2.2 研究假設

假設1(效率累加假設)：所有搜救隊伍的人員結構組成相同，救援能力相同，多支搜救隊伍合作救援時效率累加。

假設2(信用假設)：競拍者針對某項任務進行報價時，不存在虛假報價，即報價反映了對該任務難易程度、緊迫程度的真實評價。

2.3 傷員(Agent)屬性

傷員Agent的基本屬性有“掩埋程度vrubble”、 “掩埋點坐標vxy” 和“受傷程度vsi”。其中，

掩埋程度vrubble表示傷員進行救援的難度，同一個掩埋點下的傷員掩埋程度vrubble相同；

掩埋點坐標vxy表示傷員在災害發(fā)生后被掩埋的具體位置。

受傷程度vsi有四個取值，分別為“死亡”，“重傷”，“輕傷”，“無受傷”，具體取值由專業(yè)人員根據掩埋者的意識，呼吸，體溫等生命體征予以判斷。下文會將受傷程度每個取值所占的比例與災害情景結合起來，并分為“極嚴重”，“嚴重”和“普通”三種情景進行分析。

2.4 搜救隊伍(Agent)行為規(guī)則

搜救隊伍Agent主要參數有 “搜索半徑sr”、“最大轉動角度sa”、“救援速度srubble”、“合作范圍sc”、“移動步長sl”、“移動方向sθ”。其中，搜索半徑sr表示搜救隊伍當前位置的最大搜索范圍；最大轉動角度sa表示搜救隊伍下一步轉動方向的最大范圍；救援速度srubble表示的是每支搜救隊伍在確定傷員的位置以后，搶救傷員的速度；合作范圍sc表示只在半徑為sc的圓形區(qū)域內的搜救隊伍才能合作；搜救隊伍依據特定的概率分布分別選擇移動方向sθ和移動步長sl，然后沿著選定的方向sθ移動相應的距離sl，直至在搜索半徑sr內搜索到目標，搜索一個步長后，重新選擇下一步的移動[18]。

圖2 搜救隊伍搜索方案

(1)

滑坡災害現場中基本全部覆蓋著泥土碎石，初期救援隊伍難以獲得傷員掩埋位置的準確信息，Lévy walks比較適合對搜索行為進行模擬。本文采取改進后的Truncated Lévy walks對搜索過程進行仿真，可以對搜索過程中最小、最大步長施加一定的限制，其步長的概率密度函數如式(1)[20]，其中，μ是特征指數，lmin和lmax分別表示該隨機游走模型中的最小和最大步長，由于搜索半徑sr內的目標可以被搜索者發(fā)現，因此該模型中的步長sl至少應大于搜索半徑sr，即lmin=sr，最大步長則受到環(huán)境大小的限制[20, 24]。在仿真中，通過反函數法(Inverse Transform Sampling)得到抽樣函數：

(2)

Lévy walks模型中搜索的移動方向sθ服從U(0, 2π)分布，對每一個方向都給予相等的可能性，但是在文中接下來用的隨機游走模型中，移動方向sθ服從均勻分布，sθ～U(0,sa)，將sa作為一個可控制的參數進行研究。

搜救隊伍的具體搜索方案如圖2所示。

3 合作救援機制

本研究中每支搜救隊伍由大致相同的人員組成，每支隊伍都包含了搜索人員、破拆頂撐人員、醫(yī)療人員等，每支隊伍都有獨立完成救援任務的能力。隊伍內部不同類型的救援人員之間有合作，即隊內合作；不同搜救隊伍之間也有合作，即隊間合作。隊內合作是既定的，本文研究隊伍間基于拍賣機制的合作。拍賣作為一種基于市場的任務分配機制，效率較高。該研究中搜救隊伍之間通過分布式拍賣實現救援任務的分配，過程中主要有兩種角色，任務的發(fā)布者Ai和任務的響應者Bj，分別相當于拍賣中的拍賣者和競拍者。模型中主要符號及定義如表1所示。

表1 模型中主要符號及定義

3.5 拍賣者

當搜救隊伍發(fā)現目標后，即成為拍賣者Ai，合作范圍sc內的其他沒有發(fā)現目標的搜救隊伍成為任務的競拍者Bj。拍賣者Ai先對Ti掩埋情況進行評估，假設需要在時間tneed內完成任務，則確定完成任務Ti需要的搜救隊伍數量為

(3)

當ni>1時，拍賣者Ai通過Agent間通信的方式在一定范圍內發(fā)布拍賣任務Ti，收到拍賣消息后，競拍者Bj根據自身所處的狀態(tài)確定投標價格pij。拍賣者選取投標價格比較高的前ni-1個競拍者。一輪拍賣有一定的時間限制tl，當拍賣時間超過tl或者拍賣目的得到滿足，則該輪拍賣結束，先開始救援工作。在救援過程中，若拍賣目的未能滿足，再次發(fā)起拍賣。

3.2 競拍者

3.2.1 競拍者的效用評價

競拍者參加任務Ti的效用ui通過救援任務的救援優(yōu)先級評價結果進行衡量，救援優(yōu)先級越高，救援越具緊迫性，效用越大。任務Ti的救援優(yōu)先級評價采用模糊綜合評判法進行分析。

評價因素集用集合Z表示，Z={z1,z2,…,zq}，其中za(a=1, 2,…,q)表示第a個評價因素，q是因素數。確定評價集，一般選取3-5個評價級別，用集合V表示，V={v1,v2,…,vp}，其中vb(b=1, 2,…,p)表示第b個評價級別，p是評價級別劃分的數量。

H=WR=(h1,h2,…,hp)

(4)

3.2.2 競拍者的成本分析

模型中考慮了成本，是為了根據傷員的位置分布、掩埋情況的輕重緩急合理分配救援力量，減少搜救隊伍浪費在路上的時間，提高整體救援效率。這里主要涉及到兩類成本，直接成本和機會成本。與傳統(tǒng)的成本含義不同，直接投入成本cij主要由搜救隊伍離掩埋點的距離dij和完成救援任務所需時間tij決定，即

cij=f(dij,tij)

(5)

(6)

3.2.3 競拍者的投標策略

(7)

3.3 拍賣機制的動態(tài)調整

4 仿真分析——以滑坡災害為例

為了研究文中基于拍賣機制的合作救援方案的有效性，先將其與非合作救援進行對比，然后與基于F-Max-Sum[17]算法的救援方案進行比較。F-Max-Sum也是一種分布式算法，在Max-Sum算法的基礎上進行了改進，適用于解決類似的動態(tài)任務分配問題，并且性能出色。F-Max-Sum算法先將需要解決的問題轉化成因子圖的表達形式，通過不斷對因子圖中變量節(jié)點和函數節(jié)點之間信息傳遞的值進行迭代，直至收斂或者迭代了一定次數。

4.1 參數設定

這里以滑坡災害為例進行分析，采用R和NetLogo軟件進行計算與仿真。仿真模型中災害區(qū)域取自某一滑坡災害頻發(fā)地區(qū)，將該區(qū)域的GIS矢量數據文件導入仿真平臺NetLogo，界面如圖3所示。該仿真中主要利用到了該區(qū)域的道路信息，如圖4所示，其中最粗的線條刻畫了該區(qū)域道路分布情況。一定數量的傷員散落分布在區(qū)域內若干個掩埋點中。仿真步長ticks以min 為單位，當現場沒有存活的傷員時，仿真結束，每次仿真周期最長為72 h。

圖3 NetLogo仿真平臺界面

圖4 災害區(qū)域的矢量格式地圖

結合近幾年滑坡災害的傷亡數據統(tǒng)計結果(來源：http://www.emdat.be/database)，假設不同情景下滑坡災害受傷程度的具體分布如表2所示，如在“極嚴重”情景下，傷員死亡比例40%，重傷比例25%，輕傷比例15%，無受傷比例20%。

表2 不同情景下的受傷程度分布

輸入變量包括：每個掩埋點的傷員人數ns～U(1,3)；每個傷員的受傷程度vsi根據表2進行初始化；每個掩埋點的壓埋情況vrubble～N(120,30)；掩埋點限定的挖掘時間tneed=30；搜救隊伍數量m=40，均勻分布在災害區(qū)域的周圍；搜索速度為3m/min；搜索半徑sr=3m；救援速度srubble=0.5；移動步長sl根據式(2)確定，其中參數μ=2；移動方向sθ～U(0,π)；當搜索半徑內存在傷員掩埋點時，每一步仿真搜救隊伍能以一定概率發(fā)現它，假設概率prob=20%；合作范圍sc為40 m；每一輪拍賣的時間限制tl=3 min。

救援任務優(yōu)先級評價的影響因素主要由“壓埋人員”和“救援難度”兩類因素構成[25]，在此分類下，相關研究中考慮到的具體影響因素有掩埋人數，房屋結構，倒塌方式[25]；掩埋深度，傷員生理狀況，建筑物類型[26]等。結合滑坡災害的現場環(huán)境特點，考慮了數據的可獲得性，最終選取掩埋人數、受傷嚴重程度兩個評價標準以衡量“壓埋人員”因素，選取掩埋程度以衡量“救援難度”。

掩埋程度體現出救援難度；掩埋人數即該點被掩埋傷員數量；受傷嚴重程度為該點被掩埋傷員嚴重程度之和，每個傷員受傷嚴重程度值“3”，“2”，“1”和“0”，分別對應受傷程度“重傷”，“輕傷”，“無受傷”和“死亡”。評價標準如表3。救援優(yōu)先級研究中評價標準的權重并不是唯一確定的，多是通過專家評分法確定[25]。通?！皦郝袢藛T”因素的權重應大于“救援難度”，在該前提下，綜合考慮專家的意見和計算的簡化，本文將權重初步設定為W=(1/3, 1/3, 1/3)，即“壓埋人員”和“救援難度”的權重比為2∶1。

表3 掩埋點優(yōu)先級評價準則

針對每個影響因素za，采用半梯形分布函數計算隸屬于每個評價級別vb的程度rab，即隸屬度rab。以掩埋程度z1，評價級別v1“優(yōu)先”為例，計算隸屬度r11，如下所示：

(8)

生存概率vsp是與受傷程度vsi相關的一個變量。被困于掩埋物中的傷員，在未被救出之前，生存概率會隨著時間流逝逐漸減小[22-23]，并受傷員的受傷類型和所處的環(huán)境影響。滑坡與地震災害中被掩埋傷員的生存概率亦受以上相同因素影響，考慮到兩種災害之間的聯(lián)系，被掩埋傷員所處環(huán)境和受傷類型的相似性，本文擬借鑒地震災害的生存概率函數。假設滑坡災害中被掩埋傷員生存概率vsp隨時間變化的程度如式(9)所示[23]，其中，vsp-hi，vsp-si和vsp-ni分別表示重傷人員，輕傷人員，未受傷人員的生存概率，t表示受困時間(單位：h)。

vsp-hi=e-(t/3.324)3.71

vsp-si=e-(t/26.59)3.71

vsp-ni=e-(t/66.48)3.71

(9)

4.2 仿真結果

表4 不同情景下兩種救援方案的仿真結果對比

注：“*”、“**”、“***”依次表示顯著性水平為0.1、0.05、0.01時檢驗結果顯著。

表5是基于拍賣機制與基于F-Max-Sum算法的兩種合作救援方案的仿真結果對比，前者的部分指標在部分場景下略優(yōu)于后者并通過了T檢驗，說明在統(tǒng)計上是顯著的，另外部分指標則并無顯著差異。表明在該案例中，基于拍賣機制的合作救援方案與知名的F-Max-Sum算法相比，其性能并無遜色，甚至部分指標略優(yōu)于后者，并且其優(yōu)勢之一在于計算過程的低復雜性。F-Max-Sum算法在迭代過程中，函數節(jié)點需要遍歷周圍變量節(jié)點的各種組合，會消耗大量時間，尤其當協(xié)作集較大，即待救援任務周圍可調配的救援隊伍較多的時候，耗時更久。另外，F-Max-Sum最初是為具有計算功能的設備之間的合作而設計，如機器人、傳感器等，將其直接運用于災害現場搜救隊伍之間的合作存在適應性問題。

表5 基于拍賣機制與基于F-Max-Sum算法的兩種救援方案仿真結果對比

注：“*”、“**”、“***”依次表示顯著性水平為0.1、0.05、0.01時檢驗結果顯著。

圖5-7是分別進行200次仿真后，三種不同情景下，約1600個仿真步長內基于拍賣機制的合作救援與非合作救援過程中相對生存概率、傷員救出比例隨時間變化的平均情況。橫坐標表示仿真中每個時間點，左邊縱軸表示相對生存概率，次縱軸表示傷員救出比例?？梢钥闯觯仍某跏茧A段，相對生存概率下降較快，隨著救援工作的開展，約在200min以后，相對生存概率下降速度放緩，并且整個過程中合作救援的相對生存概率一直高于非合作救援。

圖5 “極嚴重”情景下相對生存概率與救出率的變化

圖6 “嚴重”情景下相對生存概率與救出率的變化

圖7 “普通”情景下相對生存概率與救出率的變化

以上仿真結果表明，基于拍賣機制的合作救援方案相比非合作救援，相對生存概率同比提高8.0%～14.5%，傷員救出比例同比提高7.4%～16.7%，各掩埋點平均救援完成時間同比減少25%～26.7%，并且隨著災情的嚴重程度增加，救援效果提高越趨于明顯。

5 模型評價

5.1 魯棒性分析

魯棒性描述的是救援效率會在多大程度上受到一些意外因素的影響，當改變模型的一些初始設定后，然后進行多次仿真，通過以下指標對模型的魯棒性進行評價[27]：

(10)

其中,(xi,Ei)指被研究的仿真參數設定值和對應的救援效率值。LRS值越顯著，絕對值越大，說明該參數對救援效率的影響越大。

進行魯棒性分析時，要研究的影響因素包括搜索半徑sr，合作范圍sc。當搜救工作發(fā)生在晚上，或者因為其他某些不可抗力，搜索半徑必然會發(fā)生變化。在受到某些干擾因素時，如環(huán)境惡劣、受通訊條件所限，合作范圍的減小是不可避免的。圖8與圖9是基于拍賣機制的合作救援方案的魯棒性分析結果。

圖8 搜索半徑對救援效率的影響

圖8中，搜索半徑sr從3m以0.3m的間隔遞增至9m，一共21輪仿真，每輪仿真重復200次，縱軸表示救援效率，橫軸表示每輪仿真的序號，在其他參數不變的情況下，隨著搜索半徑的變大，救援效率明顯改善。其魯棒性指標LRS值為0.03，并在0.01的顯著性水平下是顯著的。表明搜索半徑的變化對救援效率有顯著的影響，這種影響呈線性關系，即當搜救工作發(fā)生在晚上，或者因為其他不可抗力，導致搜索半徑變小，那么救援效率會降低。

圖9 合作范圍對救援效率的影響

5.2 敏感度分析

仿真模型中的不確定性，體現在一些模型參數的選取上，這些參數在多大范圍內的改變會對仿真結果產生影響，則需要進行敏感度分析。主要研究的參數有最大轉動角度sa和掩埋點限定的挖掘時間tneed。圖10與圖11為基于拍賣機制的合作救援方案敏感度分析結果。

圖10 掩埋點限定的挖掘時間與救援效率之間的關系

圖11 最大轉動角度與救援效率之間的關系

6 結語

災害救援過程中，不斷的有新的掩埋點被發(fā)現，同時又不斷有掩埋點完成救援，整個系統(tǒng)狀態(tài)在不斷快速變化。本文所要解決的就是在這樣一個動態(tài)的災害環(huán)境中，救援隊伍間針對某一個具體掩埋點(救援任務)如何形成合作關系的問題，通過制定合理的災后合作搜救方案，在這種不確定性的災害環(huán)境中尋求較優(yōu)的救援效果。以某滑坡災害頻發(fā)地區(qū)的災害搜救為例的仿真結果證明了所提出的基于分布式拍賣機制的合作搜救方案的有效性，與類似的F-Max-Sum算法對比，性能并不遜色，并且該合作機制的低復雜度，高效性使其更適用于應急決策過程的要求。

模型評價部分的魯棒性分析結果表明外部環(huán)境變化導致的搜索半徑變化會對救援效果產生影響，但合作范圍的擴大并不會對救援效率有明顯影響。因此，當外部環(huán)境惡化時，只要合作范圍不小于一個臨界值，救援效果就比較穩(wěn)定。敏感度分析結果表明最大轉動角度和掩埋點限定的挖掘時間兩個參數均存在最優(yōu)值，使得救援效率最高。即在現場搜救過程中，搜救隊伍不僅需要確保搜索范圍的全面性，還需要權衡保證自己的前進方向是往前的，減小搜救過程的隨意性。在合作救援時，針對每個掩埋點需要分別確定合適的隊伍需求數量，以保證合作救援的整體高效性。

本文提出的基于分布式拍賣機制的合作救援方案可以運用到其他類似的災害救援中，解決其中的搜救隊伍間合作問題，以上結論基本適用，但是值得一提的是，一些參數的具體取值可能會因為災害場景的不同而有區(qū)別。比如上面提到的合作范圍臨界值，這個臨界值在不同的災害場景下，比如不同的搜救隊伍數量、不同的受災區(qū)域面積等，可能會存在差異。同樣地，敏感度分析中的兩個參數的最優(yōu)值確定是一個折中、權衡(Trade off)的過程，參數取值的增加或者減小均存在利弊，不同的災害場景中，權衡結果有可能不一致，因此決策者需要根據實際災害場景做出選擇。在未來的研究工作中，需要分析這些重要參數的取值主要受到哪些因素的影響，并挖掘其中的關系，以輔助救援指揮中心更高效快速地作出決策。另外，仿真中需要注意參數的校正問題，但是實際數據的稀缺性限制了我們使用傳統(tǒng)的方法進行校正，接下來將注重救援案例數據的收集，通過新的方法對參數進行校正，以提高模型對實際問題的適用性。