單源點(diǎn)疏散問題的Online探索算法研究

胡秀婷，謝玉瑩，包敏澤，蔣 波，楊玉晗

1(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026) 2(華為技術(shù)有限公司 華為北京研究所，北京 100000)

1 問題描述

本文研究的問題是關(guān)于單源點(diǎn)疏散問題的online快速撤離算法.所謂單源點(diǎn)疏散問題，簡稱“單源點(diǎn)問題”，是指受災(zāi)人員位于危險(xiǎn)區(qū)域中的同一位置，需要快速地撤離出該區(qū)域并到達(dá)安全區(qū)域.由于危險(xiǎn)區(qū)域的邊界(安全區(qū)域)對受災(zāi)人員而言往往是未知的，所以受災(zāi)人員需要采取某種策略探索出安全邊界.一般而言，稱邊界信息未知的一類搜索問題為online探索問題，而邊界信息已知的搜索問題則稱為offline搜索問題.由于缺乏邊界信息的引導(dǎo)，使得online探索問題相對于一般搜索問題而言要復(fù)雜很多.近年來，人們提出了很多疏散問題的撤離策略，本文的研究目標(biāo)是設(shè)計(jì)出一個(gè)更為高效的探索危險(xiǎn)區(qū)域安全邊界的撤離算法.

為了衡量撤離算法的效率，人們提出了競爭比的概念.所謂競爭比，是指online探索策略所花費(fèi)的代價(jià)與該問題在邊界信息已知情形下所設(shè)計(jì)出的最優(yōu)搜索策略(offline搜索策略)的代價(jià)之比.顯然，所謂“快速”或“好”的online探索策略是指競爭比較小的求解方法.探索策略的代價(jià)可用耗費(fèi)的時(shí)間或路徑長度來衡量，因?yàn)榍蠼膺@類問題時(shí)的移動(dòng)速度一般都假設(shè)是勻速的.

本文研究單源點(diǎn)疏散問題，將受災(zāi)人員分為1組或多組，分別提出了三角形疏散策略和半圓疏散策略，以降低撤離算法的競爭比，提升撤離算法的效率，同時(shí)解決了受災(zāi)區(qū)域?yàn)榉峭苟噙呅蔚膯卧袋c(diǎn)疏散問題.

2 單源點(diǎn)疏散問題的探索策略

針對單源點(diǎn)疏散問題的研究，約定如下：

1)對1組疏散問題，將受災(zāi)區(qū)域的邊界設(shè)定為凸多邊形；

2)受災(zāi)人員的撤離速度是相同的；

3)受災(zāi)區(qū)域的邊界與受災(zāi)人員的初始位置是未知的，但在疏散過程中，受災(zāi)人員之間可以相互通信，共享位置信息；

4)在疏散過程中，當(dāng)其中一組受災(zāi)人員探索到未知區(qū)域邊界時(shí)，其余組人員可以獲得該信息并立即(沒有時(shí)間延誤)改變疏散方向，朝著已發(fā)現(xiàn)的邊界移動(dòng).

假設(shè)將危險(xiǎn)區(qū)域記為P，它是一個(gè)簡單多邊形.受災(zāi)人員在P中的初始位置記為O，點(diǎn)m與點(diǎn)n間的線段長度記為|mn|，Dopt表示最優(yōu)的offline路徑長度，S(m，n)表示m點(diǎn)與n點(diǎn)之間的路徑.競爭比記為k，可通過公式(1)計(jì)算：

(1)

其中，Sonline表示online探索的路徑長度；Soffline表示offline搜索的路徑長度.

2.1 單源點(diǎn)單組三角形疏散策略

假設(shè)受災(zāi)人員首先沿橫坐標(biāo)向右移動(dòng)單位長度d，然后按逆時(shí)針方向旋轉(zhuǎn)45°，繼續(xù)移動(dòng)長度d，接著再按逆時(shí)針方向旋轉(zhuǎn)108°18′，并移動(dòng)d，這時(shí)受災(zāi)人員又到達(dá)了橫坐標(biāo)上，完成了一次三角曲線移動(dòng)(從橫坐標(biāo)軸到橫坐標(biāo)軸，并做了兩次旋轉(zhuǎn)).接著，按逆時(shí)針方向旋轉(zhuǎn)71°42′(與橫坐標(biāo)軸的夾角為45°)，并移動(dòng)2d，再按逆時(shí)針方向旋轉(zhuǎn)108°18′，并移動(dòng)2d，又一次回到橫坐標(biāo)軸并完成了第2次三角曲線移動(dòng).重復(fù)這個(gè)過程，直到發(fā)現(xiàn)P的邊界.

一個(gè)三角曲線移動(dòng)的示例如圖1所示.由于∠ODA=45°，若|OC|=|OD|，則∠CAD為直角.在OC延長線上確定點(diǎn)B，使得|OC|=|BC|，則有|OB|=2*|OD|，且∠CAB=18°18′，所以在點(diǎn)A處旋轉(zhuǎn)108°18′的目的是構(gòu)造|OB|=2*|OD|的移動(dòng)策略，以便計(jì)算移動(dòng)路徑的長度.由于移動(dòng)過程中按照逆時(shí)針方向旋轉(zhuǎn)了兩次，所以移動(dòng)路線與水平方向上呈三角形形狀，故稱其為三角形疏散策略.

圖1 三角曲線移動(dòng)的示例Fig.1 Instance of moving in trigonometric curve

由于第i項(xiàng)是第i-1項(xiàng)長度的2倍(i≥2)，所以三角形策略實(shí)際上是“雙倍策略”[6]在平面上的拓展應(yīng)用，受災(zāi)人員移動(dòng)的路線在平面上可以看成是一個(gè)個(gè)三角形.受災(zāi)人員的疏散過程如圖2所示.

圖2 三角形疏散策略的移動(dòng)過程Fig.2 Moving process of triangle evacuation strategies

為計(jì)算疏散策略的競爭比，需要分析相應(yīng)策略在最壞情形下的移動(dòng)路徑程度，以及在邊界信息已知情形下的最短移動(dòng)路徑，即Soffline.如圖2所示，online情形的最壞情形是：上一次三角曲線移動(dòng)已經(jīng)很接近P的邊界，但沒有碰到邊界，如圖2中的粗虛線所示.進(jìn)入當(dāng)前三角曲線移動(dòng)后，在點(diǎn)F處也很接近P的邊界，連接EF，從O點(diǎn)向P邊界做垂線，分別交線段EF和P邊界于M和D點(diǎn)，|OD|是O到P邊界的最短距離，即Soffline.由于受災(zāi)人員在M點(diǎn)沒有碰到P邊界，所以有 |OM|<|OD|.又因?yàn)槭転?zāi)人員做第n次三角曲線移動(dòng)時(shí)已經(jīng)非常接近但沒有碰到P邊界，考慮到P是凸多邊形，因此最壞情形是受災(zāi)人員在第n+1次三角曲線移動(dòng)時(shí)仍然碰不到P邊界，但在第n+2次三角曲線移動(dòng)過程中必然穿過P的邊界，如圖2中點(diǎn)T所示.因此，受災(zāi)人員的移動(dòng)路徑長度Sonline可按如下方法計(jì)算：

受災(zāi)人員所走的路徑為：

(2)

其中，|N′T|表示最后一次做三角曲線移動(dòng)時(shí)(沒有完成)所移動(dòng)的距離，它等于第n+1次三角曲線移動(dòng)的短邊長度，有：

(3)

Soffline=|OD|是邊界信息已知情形下的最短路徑，且有|OM|<|OD|，所以可計(jì)算出|OM|并用它代替Soffline計(jì)算競爭比.如圖2所示，在ΔOEF中，由于|OF|=2|OE|，所以可計(jì)算出∠OFE的角度，進(jìn)而利用相似三角形的特性，可計(jì)算出|OM|長度.考慮一般情形，有：

(4)

因此有競爭比為：

上述結(jié)果表明，單源點(diǎn)單組三角形疏散策略的競爭比不超過19.48，它優(yōu)于文獻(xiàn)[6]給出的競爭比為19.64的半圓疏散策略，但又比“雙倍策略”的競爭比理論下界9高出1倍多.當(dāng)然，和所有單組疏散策略一樣，單組三角形疏散策略也不能很好地處理危險(xiǎn)區(qū)域P是非凸多邊形的情形.

2.2 單源點(diǎn)2組半圓疏散策略

對于分組數(shù)為2的單源點(diǎn)疏散問題，由于兩組人員始終沿著相反的方向進(jìn)行疏散，所以最終肯定會(huì)有一組人員探索到距離其最近的邊界，因此，分組數(shù)為2的單源點(diǎn)半圓疏散策略可以解決受災(zāi)區(qū)域?yàn)榉峭苟噙呅蔚氖枭栴}.圖3給出了簡單非凸多邊形的部分邊界.

圖3 半圓疏散策略的移動(dòng)過程Fig.3 Moving process of semicircle evacuation strategies

當(dāng)疏散人員被分為n(n≥2)組時(shí)，半圓搜索策略的多組人員通過由內(nèi)向外疏散，其疏散路徑構(gòu)成了一個(gè)圓，所以無論凹頂點(diǎn)出現(xiàn)在平面內(nèi)的任意位置，總會(huì)有一組疏散人員可以發(fā)現(xiàn)疏散區(qū)域中凹頂點(diǎn)所在的邊界，圖3給出了分組數(shù)為2時(shí)的一種疏散情形.當(dāng)其中一組疏散人員無限接近于Q處的凹頂點(diǎn)但始終未碰到邊界時(shí)，另一組人員在后續(xù)疏散過程中一定會(huì)在點(diǎn)T處發(fā)現(xiàn)該邊界.

當(dāng)疏散區(qū)域邊界為非凸(凹)多邊形時(shí)，可采用與凸多邊形競爭比類似的分析方法.在分析競爭比時(shí)，使Soffline的長度盡可能小，而Sonline的長度則盡可能大，這樣計(jì)算出的競爭比才能真正體現(xiàn)“最壞”情形.如圖4所示，一組受災(zāi)人員沿橫坐標(biāo)向右移動(dòng)單位長度d，然后沿逆時(shí)針方向移動(dòng)一個(gè)半圓弧長，并再次到達(dá)橫坐標(biāo)，完成了一次半圓移動(dòng).接著，再走一段單位長度d，并按逆時(shí)針方向移動(dòng)一個(gè)半圓，又一次回到橫坐標(biāo)軸上，完成了第2次半圓曲線移動(dòng),其中半圓的半徑長度采用雙倍策略遞增，并且這些半圓共用一個(gè)圓心點(diǎn)O.與此同時(shí)，另一組人員始終沿著與上一組人員的相反疏散方向進(jìn)行疏散，直到發(fā)現(xiàn)凹多邊形P的邊界.當(dāng)點(diǎn)T在S(O，B)內(nèi)時(shí)，Soffline的長度接近于第一個(gè)圓的半徑時(shí)是最優(yōu)的，即凹點(diǎn)無限接近于第一個(gè)圓周.可以看出，當(dāng)T點(diǎn)無限接近于B點(diǎn)時(shí)，各組人員的疏散路徑是最長的，也即Sonline的長度最大.所以，當(dāng)某組疏散人員在點(diǎn)B處碰到多邊形邊界(相交于點(diǎn)T)時(shí)，計(jì)算出的競爭比是最大的.

圖4 凹多邊形內(nèi)分組數(shù)為2的半圓疏散策略Fig.4 Semicircle evacuation strategy with grouping of2 in concave polygon

若假設(shè)某組人員在第n+1次疏散時(shí)碰到多邊形邊界，完成疏散，則Dopt是第n個(gè)圓周的半徑長度，所以競爭比可按如下方法計(jì)算：

通過計(jì)算半圓疏散策略的競爭比計(jì)算，說明半圓策略是解決凹多邊形疏散問題的一個(gè)高效可行方法.

3 算法的實(shí)現(xiàn)

上述算法已通過程序?qū)崿F(xiàn).針對不同疏散策略，計(jì)算出不同頂點(diǎn)數(shù)的多邊形的探索路徑長度，并計(jì)算出競爭比，以便對比分析，如表1所示.其中(凸)與(凹)表示多邊形的形狀，P表示疏散人員所探索的不同頂點(diǎn)數(shù)的多邊形，即不同形狀的多邊形.

算法的有效性是通過競爭比來衡量的，競爭比越低算法越有效.關(guān)于凸多邊形的問題，文獻(xiàn)[14]提出了單源點(diǎn)單組半圓疏散算法，但本文的單源點(diǎn)單組三角形疏散策略卻得到了一個(gè)更低的競爭比，改進(jìn)了凸多邊形情形下的疏散問題求解算法.針對非凸多邊形情形下的疏散問題，文獻(xiàn)[15]提出的兩組半方形疏散策略的競爭比不超過24，本文提出的兩組半圓疏散算法的競爭比則不超過18.56，與半方形疏散策略相比，半圓策略進(jìn)一步改進(jìn)了非凸多邊形情形的疏散算法.同時(shí)，由表1可知，在不同的多邊形疏散區(qū)域中，凸多邊形情形下的三角形策略的競爭比低于半圓策略，所以三角形疏散算法優(yōu)于半圓疏散算法；非凸多邊形情形下的半圓策略競爭比低于半方形策略，所以半圓疏散算法優(yōu)于半方形疏散算法.

表1 不同疏散策略的實(shí)驗(yàn)結(jié)果比較Table 1 Comparison of experimental results of differentevacuation strategies

4 結(jié) 論

本文主要研究了受災(zāi)區(qū)域?yàn)楹唵瓮苟噙呅魏秃唵畏峭苟噙呅吻樾蜗聠卧袋c(diǎn)疏散問題的疏散策略，其中探索凸多邊形區(qū)域的單源點(diǎn)單組疏散策略的競爭比為19.48，低于單源點(diǎn)單組半圓疏散策略的19.64[14].由于單組疏散策略只適用于凸多邊形區(qū)域的問題求解，對于非凸多邊形的情形，必須采用多組疏散策略，為此，我們提出了單源點(diǎn)2組半圓疏散策略用于求解非凸多邊形的單源點(diǎn)疏散問題，得到了競爭比為18.56的研究結(jié)果，優(yōu)于已有的撤離算法.針對單源點(diǎn)疏散問題的online探索算法，雖然已有一些解決方案，但仍然存在較大的改進(jìn)空間，需要做進(jìn)一步研究，以找出更好的疏散方法，獲得更低的競爭比，減少疏散成本并方便應(yīng)用.