多機器人從正六邊形區域在線撤離算法研究

收稿日期：2022-04-26；修回日期：2022-06-13" 基金項目：國家自然科學基金資助項目（61702242）

作者簡介：張妍（1997-），女，遼寧朝陽人，碩士研究生，主要研究方向為計算幾何；魏琦（1982-），男（通信作者），遼寧沈陽人，副教授，博士，主要研究方向為計算幾何、算法及其復雜性（qwei2009@163.com）；劉鑾（1998-），女，遼寧鐵嶺人，碩士研究生，主要研究方向為計算幾何；孫潔（1997-），女，遼寧大連人，碩士，主要研究方向為機器人路徑規劃；張文馨（1998-），女，遼寧丹東人，碩士研究生，主要研究方向為計算幾何.

摘 要：

針對多機器人在線撤離未知多邊形區域展開研究，在原有撤離區域模型（三角形、正方形、圓形）的基礎上提出多機器人從正六邊形區域在線撤離問題。設置出口在正六邊形區域的邊界上，2k（k≥1）個具有無線通信能力的機器人從相同起點出發，協作搜索出口并撤離。使用機器人全部從出口撤離的時間作為算法的開銷，分析算法的效率。根據機器人數量和初始位置分情況討論，k=1時，機器人的初始位置分別位于正六邊形區域的邊界和內部；kgt;1時，機器人初始位置在正六邊形區域的邊界。針對上述幾種情況，分別給出了高效的多機器人協作在線撤離算法，并證明在機器人起點相同的情況下，增加機器人數量對減少算法開銷具有正向的意義。

關鍵詞：計算幾何；在線搜索；正六邊形區域；移動機器人；無線通信

中圖分類號：TP301.6"" 文獻標志碼：A""" 文章編號：1001-3695（2022）12-018-3644-07

doi：" 10.19734/j.issn.1001-3695.2022.04.0199

Online algorithms of multi-robot evacuation from regular hexagon

Zhang Yan， Wei Qi， Liu Luan， Sun Jie， Zhang Wenxin

（School of Computer amp; Information Technology， Liaoning Normal University， Dalian Liaoning 116033， China）

Abstract：

Aiming at multi-robot online evacuation from unknown polygon， this paper proposed the problem of multi-robot online evacuation from a regular hexagon based on the original evacuation model （triangle， square， circle）. 2k （k≥1） robots with wireless communication start from the same starting point， search for the exit on the regular hexagon boundary cooperatively and evacuate. The evacuation cost was the time that took for all robots to be evacuated from the exit. This paper analyzed the efficiency of the algorithm using evacuation overhead. According to the number of robots and the initial position， when k=1， robots were initially at the regular hexagonal boundary or inside; when kgt;1， robots were initially at the regular hexagon boundary. This paper proposed respectively efficient online algorithms of multi-robot evacuation for the above situations. It proves that increasing the number of robots has a positive significance in reducing the algorithm overhead when the starting point of the robots is the same.

Key words：computational geometry; online search; regular hexagonal region; mobile robot; wireless communication

0 引言

在線搜索平面上的未知區域是計算幾何學和機器人學中的基本問題［1～3］，是指單個或多個機器人在預先不知道搜索區域幾何信息的前提下，根據攜帶的感應器收集到的局部信息動態規劃路徑以搜索指定目標［4，5］，受到國內外眾多研究學者的廣泛關注。

本文研究的多機器人在線撤離問題［6～8］是在線搜索問題的一類，搜索目標為未知多邊形區域邊界上的出口，多個機器人通過無線通信，協作搜索出口并撤離，撤離過程的開銷為最后一個機器人從出口撤離所用的時間。該問題的研究可應用于模擬在超市、商場等大型人員密集場所發生地震、火災等險情后，人們在極端環境下尋找逃生出口，并盡可能快地撤離被困人員的場景［9］；此外還可應用于逃生游戲的設定中，防守方將出口設置在不易被發現的位置，攻擊方按規則盡可能快地尋找防守方設置的出口位置等。

Czyzowicz等人［10］最先提出機器人在圓盤上搜索未知出口并撤離的問題，并將機器人的通信類型分為無線通信類型和面對面通信類型兩類。在無線通信模型下，機器人可以在任何時間點進行通信，一旦其中一個機器人發現出口，可以立即將出口的位置通知給其他機器人；在面對面通信模型下，機器人只有在碰面時才能彼此交換信息。Czyzowicz等人［10］在無線通信模型下給出了最大疏散時間為3+π/k的算法；在面對面通信模型下，給出了最大疏散時間為3+2π/k－O（k－2）的算法，其中k為機器人的數量。隨后Czyzowicz等人［11］又對該問題進行延展，設置圓盤上有n個出口，研究了從同一位置出發的兩個具有無線通信能力的機器人搜索出口并撤離的問題。Pattanayak等人［12］針對該問題限制出口數量為2，并給出相應的在線撤離算法。Lamprou等人［13］變化機器人的速度，研究兩個不同速度的機器人在圓盤上的撤離情況，并得出了一些有趣的結論。

Czyzowicz等人［14］在圓盤模型的基礎上改變了撤離區域，分別研究了k個具有無線通信能力的機器人在等邊三角形和正方形中的撤離問題，并給出使用兩個具有無線通信能力的機器人從等邊三角形邊界和內部出發的最優算法，證明其最優撤離時間是x+3/2，其中x為機器人起點到邊界中點的距離；正方形中撤離時間為1+x+1+（1－2x）2，其中x為起點到頂點的距離。Chuangpishit等人［15］證明了k個面對面通信的機器人在等邊三角形模型中所需撤離時間的下界為3+3/k。Bagheri等人［16］將移動機器人的通信能力進行改進，規定機器人的通信能力半徑為r的范圍，并且給出有趣的結論。

上述研究將撤離模型抽象為圓形、正方形和三角形，實際撤離場景不局限于這些基本模型，正六邊形同樣具有對稱性等特點，而且因其邊數增加，場景模型更加復雜；正六邊形的結構也因其穩定性的特點被廣泛應用到建筑領域，在實際應用中正六邊形模型更接近實際情況。

因此，本研究將撤離場景設置為正六邊形區域，并提出具有無線通信能力的多個機器人從正六邊形區域的在線撤離問題。機器人從正六邊形的邊界或內部同一位置出發，在預先不知道出口位置的情況下搜索出口并撤離，以最后一個機器人從出口撤離所用的時間為算法的開銷。本研究不將機器人的搜索路徑局限于區域的邊界，使其可在區域內部通過弦更快地到達目標搜索區域，避免多機器人的無效搜索，解決了多機器人的閑置問題，給出了2k（k≥1）個具有無線通信能力的機器人從正六邊形區域在線撤離的高效算法，并分析了算法的效率。

1 模型描述

本章將從機器人搜索區域、機器人能力、撤離算法三個方面給出撤離問題的模型描述。

本研究中機器人的搜索區域為一個封閉的正六邊形，出口位置在其邊界上，可看做邊界上的一個點，記為e。機器人事先不知道出口位置，只有在到達出口點時才能將出口識別出來。機器人被正六邊形的搜索區域邊界包圍，只能從正六邊形搜索區域邊界上的出口離開。

根據完成搜索任務的機器人數量，每臺機器人具有編號，機器人最大移動速度為1。機器人在搜索區域內的運動軌跡不受限制，可以在任意時間改變方向且不需要額外的開銷，當機器人到達邊界時可以識別邊界，并在邊界上尋找出口。假定所有機器人的初始位置位于同一位置，機器人知道自身的初始位置以及搜索區域的信息，但是機器人不知道位于邊界上出口的具體位置，只有當機器人到達邊界上的出口點時才可以識別出口。機器人具有無線通信能力，當其中一個機器人發現出口時，可以立即發出信息，其他機器人可以在任意位置接收到信息，并通過所在位置到出口的最短距離向出口移動。

撤離算法為每一個機器人提供一個特定的撤離軌跡，每個機器人要遵循特定軌跡在指定的搜索區域進行搜索，不同的機器人可以遵循不同的搜索軌跡。每個機器人都知道出口位于搜索區域的邊界以及完整的撤離算法，并且可以在任何時候確定自身或者其他機器人的位置。一旦有一個機器人在邊界發現出口后，該機器人會向其他機器人發送一個消息“找到出口”以及該機器人的編號。然后其他機器人根據發送消息的機器人的編號計算出口的位置，并在最短時間內（每個機器人位置到出口的最短距離）移動到出口，直到最后一個機器人到達出口并撤離，此時撤離算法完成。最后一個機器人從出口撤離的時間記為該撤離算法的時間開銷，本研究由時間開銷來衡量撤離算法的效率。

性質1 在正六邊形ABCDEF中，線段MN等于線段MM′與線段M′N′相加之和，即|MN|=|MM′|+|M′N′|。

證明 如圖1所示，在正六邊形ABCDEF中，從點M′和點N′分別向線段MN做垂線，由勾股定理和正六邊形性質可得線段MN等于線段MM′與線段M′N′相加之和，即|MN|=|MM′|+|M′N′|。

性質2 在正六邊形ABCDEF中，線段MC的長度小于線段MM′與線段M′C′相加之和，即|MC|lt;|MM′|+|M′C′|。

證明 如圖1所示，已知|NC|=|N′C′|且|MM′|=|CC′|，在△MNC中|MC|lt;|MN|+|NC|，在△M′N′C′中|M′C′|lt;|M′N′|+|N′C′|，那么|MC|－|M′C′|lt;|MN|－|M′N′|，由性質1的|MN|=|MM′|+|M′N′|，可知|MC|－|M′C′|lt;|MM′|，因此|MC|lt;|MM′|+|M′C′|。

2 兩個機器人從正六邊形區域撤離算法

本章主要針對兩個機器人分別從正六邊形區域的邊界、內部和中心三類起點出發，給出相應撤離算法，并通過最大開銷分析了算法的效率。

2.1 兩個機器人從正六邊形邊界出發

具有無線通信能力的兩個機器人從正六邊形撤離的策略，如算法1所示。

算法1 兩個無線通信能力機器人從邊界上撤離算法

輸入：正六邊形區域Q；機器人起點s。

輸出：出口e；撤離路徑。

a）兩個機器人r1和r2從正六邊形邊界上的任意位置s點出發。

b）機器人從s點沿著邊界向相反方向移動并搜索出口e

/* 機器人r1沿逆時針方向移動，機器人r2沿順時針方向移動。 */

c）if（r1或r2發現出口e）

通知出口e所在位置，另一個機器人以最短路徑到達出口e撤離；

d）算法結束。

引理1 機器人從邊界上距離中點為x的任意位置撤離，所耗費的最大開銷為4x2+2x+1－x+5/2。

證明 引理1的證明主要考慮機器人遵循算法1所消耗的最大時間。因為機器人的速度相同且為1，那么機器人遇到出口前行走的路程和所用的時間相同。不失一般性，設機器人的起點s在邊ED上，如圖2所示，點s到邊界中點的距離設為x，逆時針箭頭標出的為機器人r1的軌跡，順時針箭頭標出的為機器人r2的軌跡，算法的開銷為后離開出口的機器人所走路徑長度。結合模型設定可知，使開銷達到最大的出口位置在線段FC以下，若設r1先發現出口，出口可能在邊AF上，也可能在邊AB上。下面針對這兩種情況進行分析。

首先考慮出口在邊AF上的情況。設機器人過F點到出口所走的距離為a，取值為［0，1］，撤離開銷為4x2+（2－a）2+2x（2－a）－x+a+3/2。由性質2得，當a=1時最大開銷為4x2+2x+1－x+5/2。

再考慮出口在邊AB上的情況。如圖3所示，設機器人過A點到達邊AB所走的距離為b，取值為0≤b≤x+1/2，撤離開銷為（2x－b）2+（1－b）2+（2x－b）（1－b）－x+b+5/2，對x求偏導，導數為

（4x－3b+1）/（2x－b）2+（1－b）2+（2x－b）（1－b）-1，當x=b-1/2時，此時有極大值，開銷為7/2－x。

以上分析可以得出最大開銷為4x2+2x+1－x+5/2。圖2中出口e所在位置為兩個機器人從s點出發耗費最大開銷的位置。綜上，引理得證。

定理1 兩個機器人的起點在正六邊形邊界上，撤離開銷的下界為4x2+2x+1－x+5/2。

證明 設有任意算法A，記為A（e，T）表示機器人遵循算法A沿六邊形邊界搜索出口并完成撤離，e表示出口，T表示機器人沿邊界找到出口e到完成撤離的終止時間。機器人在六邊形邊界上撤離的時間主要由機器人搜索出口所用的時間和另一個機器人得到通知到達出口的時間兩部分組成。設算法A中機器人在邊界上完成撤離的時間為T，找到出口的時間為T1，另一個機器人收到通知到達出口的時間為T2，即T=T1+T2。設算法1中機器人在邊界上完成撤離的時間為T′，找到出口的時間為T′1，另一個機器人收到通知到達出口的時間為T2′，即T′=T1′+T2′。因為出口設在區域邊界上，所以機器人在邊界上越快找到出口，并且另一個機器人接到通知后越快到達出口，機器人完成撤離所用的時間越小。那么分情況討論：

a）假設T2=0，那么有以下兩種情況：

（a）機器人從邊界同起點向相同方向搜索并完成撤離。考慮算法的最大開銷，機器人搜索段重疊，那么T′≤T。

（b）機器人從邊界不同起點向相反方向搜索，相遇點就是出口所在位置。因為機器人在不同起點出發，所以機器人搜索段被分為兩段，考慮最壞情況出口位于機器人第二搜索段，那機器人完成第一搜索段的搜索后，機器人在區域內部要通過一段路程到達第二搜索段并完成搜索，那么T′≤T。

b）假設T2≠0，有以下兩種情況：

（a）機器人從邊界上不同起點向相同方向搜索并完成撤離。考慮算法最大開銷機器人在搜索過程中，軌跡會產生重疊，那么T′≤T。

（b）機器人從邊界不同起點向相反方向搜索，算法A中撤離完成時間為T，考慮最壞情況機器人在第二搜索段發現出口，那么機器人從上一搜索段到第二段搜索段之前，一定要通過一條弦才能到達第二搜索段并找到出口，那么此時T1=T′1+ε，因為εgt;0，T2、T2′取值最大情況為2，所以T′≤T。

綜上，算法1中所得到的最大開銷為下界。定理得證。

引理2 機器人在邊界上任意位置出發時，考慮最大開銷的最好情況起點位于邊界中點位置，最壞情況位于頂點位置。

證明 由引理1得機器人撤離的最大開銷為T=4x2+2x+1－x+5/2，對公式中的x求導。當0≤x≤1/2時，導數大于0，函數為單調遞增，所以當初始位置位于邊界中點（x=0）時，所花費的最大開銷取值最小為7/2，當初始位置位于邊界頂點（x=1/2）時，取值最大為2+3。因此，引理2得以證明。

2.2 兩個機器人從正六邊形內部出發

引理3 兩個機器人從正六邊形區域內部同起點撤離時，機器人一同走向距離最近的邊界撤離比機器人直接在起點向不同方向撤離開銷更小。

證明 設機器人從正六邊形內部同起點進行撤離，完成時間為Tq，機器人從內部到邊界的時間Tn，到達邊界后的撤離時間T。設機器人一同走到邊界的情況所用的時間為Tq1=Tn+T，機器人在起點直接向不同方向撤離的情況所用的時間為Tq2=min{T′n1，T′n2}+T′。假設機器人從內部到邊界的時間都取最小值且Tn=min{T′n1，T′n2}，由定理1得，從邊界上同起點撤離為下界，那么T≤T′，所以Tq1lt;Tq2，引理得證。

綜合引理2和3，兩個機器人從正六邊形內部撤離策略如算法2所示。

算法2 兩個無線通信能力機器人從內部撤離的算法

輸入：正六邊形區域Q；機器人起點s。

輸出：出口e；撤離路徑。

a）兩個機器人r1和r2從正六邊形區域內部任意位置s點出發。

b）switch（情況）

case1：機器人從s點一同走向距離出發點最近的邊界中點M;

break;

case2：機器人從s點一同沿距離最近的邊界垂線到達邊界p點;

break;

c） if（機器人到達正六邊形邊界）

調用算法1;

end if

d） 算法結束。

兩個機器人在正六邊形內部撤離，機器人的初始位置在正六邊形內部的s點。p點是機器人到達邊界的初始點，假設p點距離邊界中點的距離為x，線段sp的距離為y。當x、y滿足以下條件時，判斷算法2中兩種情況：

當0≤x≤0.271 4且0.395 8≤y≤3/2時，采用算法2中case1；

當0.271 4≤x≤1/2或0≤y≤0.395 8時，采用算法2中case2。

定理2 在算法2中，兩個機器人從正六邊形內部任意位置撤離所需要的最大開銷為4.366 0。

證明 機器人選擇case1，如圖4所示。從s點到達邊界中點M的距離為x2+y2。由引理2得，機器人到達邊界后從中點找到出口并完成撤離所需的最大時間為7/2，所以case1所需的全部時間為T1=x2+y2+7/2。

機器人選擇case2，如圖5所示。從s點出發，沿s點向邊界做垂線，機器人沿垂線到達邊界p點的距離為y，由引理1得，機器人到達邊界后，從p點向相反方向搜索出口，所需要的最大時間為4x2+2x+1－x+5/2，所需要的總時間為T2=y+4x2+2x+1－x+5/2。

由模型設定x、y的取值為0≤x≤1/2，0lt;y≤3/2-3x，繪制函數圖像得出，當0≤x≤0.271 4且0.395 8≤y≤3/2時，T1lt;T2，此時采用算法2中case1；當0.271 4≤x≤1/2或0≤y≤0.395 8時，T1gt;T2，采用算法2中case2；當x=0，y=3/2時，該算法的最大開銷為4.366 0。綜上，定理得證。

2.3 兩個機器人從正六邊形中心出發

機器人從正六邊形中心撤離，該情況為機器人從內部撤離的一種特殊情況。兩個機器人從中心撤離的策略如算法3所示。

算法3 兩個無線通信能力機器人從中心撤離的算法

輸入：正六邊形區域Q；機器人起點s。

輸出：出口e；撤離路徑。

a）兩個機器人r1和r2從正六邊形區域中心O點出發，一起通過任意方向到達機器人邊界p點。

b）if（兩個機器人到達邊界）

調用算法1;

end if

c） 算法結束。

定理3 當兩個機器人初始位置在正六邊形中心時，撤離最大開銷為x2+3/4+4x2+2x+1－x+5/2。

證明 根據正六邊形幾何性質，將正六邊形分割成12個全等的三角形，主要分析在△OAM中，其他位置與該區域完全相同。如圖6所示兩個機器人從O點出發到邊界的距離為OP，機器人到達邊界p點與邊界中點M的距離為x。

在△OPM中，由勾股定理有：OP=x2+3/4，OP的取值為［3/2，1］，機器人到達P點后，調用算法1，撤離的最大時間為T=x2+3/4+4x2+2x+1－x+5/2，對T求導，在0≤x≤1/2內單調遞增，所以當x=0（即機器人從正六邊形中點直接走向邊界中點）時，為兩個機器人在正六邊形中心撤離的最優情況。因此，定理得證。

3 2k個機器人從正六邊形區域撤離算法

上一章介紹了兩個機器人在正六邊形區域中任意位置撤離的情況，本章主要介紹當機器人的數量擴展為2k（kgt;1）時，從正六邊形區域撤離的情況。

通過上一章內容能清晰地得到，機器人從正六邊形區域邊界任意位置撤離時，起點位于邊界的中點為最優情況，所以本章直接采用邊界的中點為機器人的初始位置，探究多個機器人在初始位置相同的情況下，如何合作進行撤離，如圖7所示。

定義1 距離機器人出發點M最近且未被探索的邊界為目標邊界。

定義2 機器人在目標邊界完成搜索任務后，離開目標邊界的點為轉折點。

定義3 所有機器人被平均分為兩組：組G1和組G2。并且每組分別有k個機器人，每個機器人有兩個標簽，分別是組編號和機器人在每組中的順序編號，表示為Gi-Rn，（i=1，2；n=1，2，…，k）。

定義4 機器人在每個邊界的搜索長度等于該目標邊界的總長度除以搜索該目標邊界的機器人總數量，每組機器人整體的搜索段相加是半個六邊形邊界長度。

定義5 機器人的順序編號如R1，R2，…，Rn（n=1，2，…，k）。所有機器人同時從正六邊形區域某一邊界中點出發，分別走向兩個目標邊界，每個機器人按組和順序編號出發的軌跡與起始邊界形成的角度為

α=arcsin3（n－1）k2+2k（n－1）+4（n－1）2" n=1，2，…，k；k∈Euclid ExtraeBp+

3.1 算法描述

算法4 2k個無線通信能力機器人從正六邊形區域撤離算法

輸入：正六邊形區域Q；機器人起點s。

輸出：出口e；撤離路徑。

a）將所有機器人平均分為兩組：組G1和組G2。

b）組G1和組G2中的所有機器人同時按照角度α向相反方向的第一目標邊界出發。

c） if（機器人Gi-R1發現出口）

所有機器人直接通過最短距離走向出口;

end if

d） while（機器人Gi-Rn未發現出口）

機器人到達第j（j=1，2，3）目標邊界，機器人沿邊界向著轉折點搜索規定長度;

if（機器人發現出口）

break;

else

機器人到達轉折點;

if（j==3）

機器人繼續沿邊界搜索;

end if

if（j==2）

機器人沿轉折點與邊界呈β（β=arcsin（21/4））的角度，向第j+1目標邊界行走;

end if

if（j==1）

從轉折點與邊界呈30°的方向，向第j+1目標邊界行走;

end if

end if

end while

e）該機器人立即發出通知，其他機器人接到通知后，沿最短路徑到出口。

f）所有機器人從出口離開。

g）算法結束。

圖8給出了上述算法在正六邊形區域中撤離多機器人的一個實例，圖中內部箭頭方向表示機器人的行進路線，外圍虛線箭頭表示機器人在邊界搜索時的行進方向。為便于表達，將機器人數量設置為六個，分為組G1和組G2，每組有三個機器人R1、R2和R3執行搜索任務。為展示機器人在撤離區域的完整路徑，將出口設置在圖中第三條目標邊界的e點上。因為正六邊形的對稱性，以下搜索過程以組G1的機器人為例進行說明。

所有機器人從同一起點M出發，按算法4沿箭頭方向開始搜索任務，G1-R1直接在邊界上搜索ME段，到達第一目標邊界的E點后繼續沿邊界搜索EG段，G1-R2沿圖中內部的虛線箭頭到達邊界G點沿邊界搜索GH段，G1-R3沿圖中點線箭頭到達邊界H點沿邊界搜索HF段，如果機器人在第一對目標邊界沒有搜索到出口，那么G1-R1和G1-R2將遇到由邊界向內部行走的轉折點G和H，根據算法4判斷轉折點G和H為第一目標邊界轉折點，轉折角度為30°，G1-R1和G1-R2分別沿著GK段和HI段向下一目標邊界行走。G1-R3到達第二目標邊界F點繼續沿邊界搜索FI段，G1-R2到達I點后沿邊界搜索IK段，G1-R1到達K點后沿邊界搜索KA段，如果機器人在第二目標邊界沒有搜索到出口，G1-R3和G1-R2遇到轉折點I和K，根據算法4判斷轉折點I和K為第二目標邊界轉折點，G1-R3和G1-R2沿轉折點轉折分別沿著IN段和KL段向下一目標邊界行走。G1-R1到達A點后繼續沿邊界搜索AL段，G1-R1在AL段發現出口e，此時，G1-R1立刻通知其他機器人出口e所在位置并從出口撤離，G1-R3和G1-R2分別從圖中位置x點和y點沿最短路徑到達出口e，G2-R1從出口e的對稱位置到達出口，G2-R3和G2-R2從圖中位置x′點和y′點沿最短路徑到達出口e，所有機器人到達出口后立即離開，最終所有機器人將從出口全部撤離。

3.2 效率分析

因為正六邊形區域具有對稱性的特點，所以機器人在任意邊界出發所得到的效率都是相同的。如圖9所示，2k個機器人同時從M點出發，箭頭所標記的軌跡為其中一個機器人搜索出口的完整軌跡。為了分析算法效率，將正六邊形區域分為上半部分和下半部分兩部分。

第一對目標邊界：在機器人上半部分，假設第n個機器人當前到達第一對目標邊界的搜索段為第n段，第n個機器人在第n段發現出口，并且發出通知，其他機器人接到通知后，不考慮消耗立即從當前位置向著出口位置以最短距離移動，并從出口撤離。撤離算法所考慮的開銷為在最壞情況下最后一個從出口撤離的機器人所消耗的總時間。

引理4 根據算法4分析機器人的撤離軌跡，到達目標邊界之前第n個機器人所走的路程為

（n－1）2/k2+（n－1）/2k+1/4

證明 根據算法4機器人的撤離軌跡，將軌跡與正六邊形邊界圍成一個鈍角三角形。n為機器人編號下標（即表示第n個機器人搜索該目標邊界的第n個搜索段），k表示每組機器人的總數量。根據余弦定理得，到達目標邊界前所走的路程為

（12）2+（n－1k）2－2×12×n－1k×cos120°=（n－1）2k2+n－12k+14

引理5 在搜索第一對目標邊界時，機器人按編號升序相繼到達目標邊界，在某一時刻搜索其中一個目標邊界的機器人數量最多為2個且這兩個機器人相鄰，如Gi-Rn和Gi-Rn+1。

證明 根據引理4假設第n（n≤k－1）個機器人到達第一個目標邊界，并完成搜索任務的時間為

Tn+1/k=（n－1）2/k2+（n-1）/（2k）+1/4+1/k，

如圖10所示，由三角形性質得，第n+1個機器人在第n個機器人還沒完成搜索任務時已經到達相應的搜索段，而第n+2個機器人此時是否到達目標邊界是未知的。通過計算得第n+2個機器人剛好到達目標邊界的

時間為

Tn+2=（n+1）2/k2+（n+1）/（2k）+1/4。

假設Tn+2gt;Tn+1/k，由此得T2n+2gt;（Tn+1/k）2，即

（（n+1）2/k2+（n+1）/（2k）+1/4）2gt;（（n－1）2/k2+（n－1）/（2k）+1/4+1/k）2

因為ngt;0且k≥2，4n/k2+2/k·（n－1）2/k2+（n－1）/（2k）+1/4+1/（2k）gt;0，在n和k的取值內不等式成立，所以Tn+2gt;Tn+1/k成立。當機器人搜索邊界時，最多只存在相鄰的兩個機器人到達目標邊界。因此，引理5得以證明。

定理4 在正六邊形區域的上半部分，最大撤離時間的位置是將出口設在C點或F點上，開銷為

1/k2-5/（2k）+7/4+1/k+2。

證明 如果機器人在正六邊形上半部分發現出口，算法的開銷主要為發現出口的機器人從起點到出口的時間與最后一個通過最短距離到達出口的機器人所消耗的時間之和（不考慮接收“通知”的時間消耗）。如圖11所示，考慮最壞情況下將出口設置在C點或者F點，此時開銷最大。由引理4得，設此時的撤離時間為（n－1）2/k2+（n－1）/（2k）+1/4+x，n表示機器人編號，x表示搜索段長度，k（在該公式中設為定量）表示機器人的總數量。對n（1≤n≤k）求偏導，導數為（4n+k-4）/（2k4（n－1）2+2（n－1）k+k2），導數值大于0；對x（0≤x≤1/k）求偏導，導數值大于0。假設k為定值時，撤離時間隨著n和x的增大而增加，所以發現出口的最大時間為1/k2-5/（2k）+7/4+1/k。當n=k時，說明出口在正六邊形區域上半部分的第k個搜索段中，即C點或者F點上。此時接到通知的機器人到達出口所走的最大時間為2。所以2k個機器人在正六邊形上半部分的最大撤離時間為1/k2-5/（2k）+7/4+1/k+2。

第二對目標邊界：如果機器人在第一對目標邊界的搜索段中沒有發現出口，那么完成第一段搜索的機器人按照軌跡向下一對目標邊界移動，到達下一搜索段后繼續進行搜索。

引理6 在搜索第二對目標邊界時，機器人按編號的降序相繼到達目標邊界，在某一時刻搜索其中一個目標邊界的機器人數量最多為2個且這兩個機器人是相鄰的，如Gi-Rn+1和Gi-Rn。

證明 當機器人完成第一段搜索任務后，按照算法4的軌跡向第二對目標邊界移動，并完成第二段搜索任務。第n個機器人剛好到達第二個目標邊界所用的時間為Tn=（n－1）2/k2+（n－1）/（2k）+1/4+1/k+3（1－n/k），對n（1≤n≤k）求偏導，導數為4n+k－42k4（n－1）2+2（n－1）k+k2－3/k，導數值小于0，所以到達第二搜索段的時間隨n的增大而減少，說明機器人按照編號的降序相繼到達第二對目標邊界。同引理5證明第n個機器人和第n+2個機器人是否同時到達邊界的方法，得到Tn+2+1/klt;Tn。如圖12所示，當機器人搜索邊界時，最多只存在相鄰的兩個機器人到達目標邊界。引理6得以證明。

定理5 在整個正六邊形區域中，最壞撤離情況下的最大開銷為1/k2-5/（2k）+7/4+1/k+2。

證明 機器人按照算法4的軌跡在下半部分進行撤離時，算法的開銷主要為發現出口的機器人從起點到出口的時間與最后一個通過最短距離到達出口的機器人所消耗的時間之和（不考慮接收“通知”時間消耗）。由正六邊形的幾何性質，接收出口信息的其他機器人中，距離出口最遠的機器人應該在正六邊形的邊界位置。由引理6得，最多會有兩個機器人同時位于邊界，所以機器人在接收通知后，到達出口有兩種情況。

情況1 假設發現出口的機器人為G1-Rn，那么接收到通知最后到達出口的機器人編號為G2-Rn（關于軸對稱位置機器人）。機器人從第二目標邊界撤離實例如圖13所示。

假設第一組第n個機器人在第二個目標邊界發現出口所用的時間為（n－1）2/k2+（n-1）/（2k）+1/4+1/k+3（1-n/k）+x。如圖13所示，第二組第n個機器人從當前位置到達出口需要的時間為n/k－x+1，所以Tn=（n－1）2/k2+（n－1）/（2k）+1/4+1/k+3（1－n/k）+n/k+1，對n求偏導，導數為4n+k－42k4（n－1）2+2（n－1）k+k2－3k+1k，當1≤n≤3k－23k+2k2132－18+83－124412－12時，導數值小于0；當3k－23k+2k2132－18+83－124412－12≤n≤k時，導數值大于0。總時間隨著n的增大先減后增，函數有最小值。因為n∈［1，k］，所以當n=1或n=k時，函數有極大值。當n=1時，T1=（2－3）/k+3/2+3；當n=k時，Tk=1/k2-5/（2k）+7/4+1/k+2。當kgt;2時Tkgt;T1，所以情況1中最壞情況發生在第k個機器人在正六邊形的區域下半部分的搜索段中發現出口。

情況2 假設發現出口的機器人為G1-Rn，那么接收到通知最后到達的機器人編號為G2-Rn-1。

當機器人數量不斷增加時，兩個機器人會同時位于邊界。滿足的條件為

（n－1）2k2+n－12k+14－（n－2）2k2+n－22k+14+1－3kgt;0

化簡得ngt;「（3+1）（23－3）k2－163+284－k4+32，

機器人的編號為n時，會出現同時搜索情況，并且機器人搜索范圍越靠近中軸線，越容易出現這種情況。假設機器人在圖14中位置發現出口，因為機器人發現出口之前所用的時間是一致的，但是接到“通知”后向出口行走的距離不同，由模型設定的最壞情況依然發生在圖中的對稱位置，那么情況2不成立。結合情況1和性質2可得，在第二目標邊界上，最大開銷是將出口設在該位置。

第三對目標邊界：通過以上分析，機器人到達第三對目標邊界，依然是按機器人編號的升序順序到達邊界，執行搜索。

機器人在第三目標邊界完成撤離所用的總時間為Tn=（n－1）2k2+n－12k+14+（2+7－23）n+2－72k+3，對n求偏導，導數為4n+k－42k4（n－1）2+2（n－1）k+k2+2+7－232k，當1≤n≤k時，導數大于0，所以總時間隨n的增大而增大。假設機器人在最后的搜索段發現出口，即n=k，如圖15所示Tn=1k2－52k+74+2－72k+72+1，該時間小于機器人在第二目標邊界完成撤離所用的總時間。綜上，定理5得以證明。

由定理5可知，機器人數量k與撤離開銷成反比，撤離開銷隨機器人數量增多逐漸減小，如表1所示。

表1中

k表示每個搜索組機器人的數量。從表中的數據可以得出，隨著有效搜索機器人的數量增多，撤離開銷呈現一種遞減狀態，證明機器人數量增加對算法效率提高具有正向意義。

對比已有的圓形、三角形、正方形模型上的多機器人撤離算法，本文正六邊形模型同樣具有極強的對稱性，且因邊數的增加，使其具有更復雜的研究環境，同時正六邊形也因為結構穩定的特點被廣泛應用于建筑領域，所以正六邊形模型更具實際研究意義。本研究將撤離區域設置為正六邊形，首次提出正六邊形區域上的多機器人協作撤離算法。此外，已有基本模型中多機器人協作算法，都將機器人的初始位置設置在模型的中心，這樣的初始設定模擬的情況相對單一，而本研究將機器人的初始位置設置在邊界的同一點上，進一步增加了多機器人協作的復雜性。經與其他模型下的算法對比分析得出，模型邊界數量增加與撤離開銷成正相關。

對比已有的其他模型上的多機器人在線撤離策略，本研究提出的算法不將機器人的搜索路徑局限于區域邊界，使機器人可以在內部通過弦更快地到達搜索區域，使得在搜索過程中，機器人在模型內部有序搜索，機器人之間的距離得到合理控制，使其接收通知后可以盡快到達出口，避免多機器人的無效搜索，解決了多機器人的閑置問題，提升了搜索效率。

4 結束語

本文提出具有無線通信能力的2k（k≥1）個機器人從正六邊形區域在線撤離問題，針對機器人的初始位置和數量分情況給出相應的在線撤離算法，并通過最大開銷分析了算法的效率。本文在研究中設置機器人具有相同速度且起點相同，在后續的研究中可以改變機器人的速度、起點位置、通信能力等。當機器人具有不同速度，或者僅具有面對面通信能力，針對這些情況展開研究，都是很有趣的后續研究工作。

參考文獻：

［1］Georgiou K，Karakostas G，Kranakis E. Search-and-fetch with one robot on a disk ［C］// Proc of the 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks. Cham： Springer，2017： 80-94.

［2］Wei Qi，Yao Xiaolin，Liu Luan，et al. Exploring the outer boundary of a simple polygon ［J］. IEICE Trans on Information and Systems，2021，104（7）： 923-930.

［3］Wei Qi，Sun Jie，Tan Xuehou，et al. The simple grid polygon exploration problem ［J］. Journal of Combinatorial Optimization，2021，41（3）： 625-639.

［4］謝玉瑩，包敏澤，胡秀婷，等. 一種改進的網格多邊形online探索算法 ［J］. 計算機應用與軟件，2022，39（3）： 218-222，315. （Xie Yuying，Bao Minze，Hu Xiuting，et al. An improved online exploration algorithm for exploring grid polygons ［J］. Computer Applications and Software，2022，39（3）： 218-222，315.）

［5］魏琦，林韋達，吳彤，等. 雙弱感知能力機器人在線協作街道搜索算法 ［J］. 計算機科學與探索，2020，14（9）： 1571-1579. （Wei Qi，Lin Weida，Wu Tong，et al. Online two-robot coordination algorithm for searching in streets with limited sensing ［J］. Journal of Frontiers of Computer Science and Technology，2020，14（9）： 1571-1579.）

［6］Georgiou K，Karakostas G，Kranakis E. Treasure evacuation with one robot on a disk ［J］. Theoretical Computer Science，2021，852（5）： 18-28.

［7］Li Songhua，Xu Yinfeng. Online strategies for evacuating from a convex region in the plane ［C］// Proc of the 11th International Workshop on Frontiers in Algorithmics. Cham： Springer，2017： 151-162.

［8］Wei Qi，Tan Xuehou，Jiang Bo. Competitive strategies for evacuating from an unknown affected area ［J］. IEICE Trans on Information and Systems，2016，E99.D（10）： 2585-2590.

［9］胡秀婷，謝玉瑩，包敏澤，等. 單源點疏散問題的online探索算法研究 ［J］. 小型微型計算機系統，2020，41（11）： 2282-2285. （Hu Xiuting，Xie Yuying，Bao Minze，et al. Research on online exploration algorithm for single source evacuation problem ［J］. Journal of Chinese Computer Systems，2020，41（11）： 2282-2285.）

［10］Czyzowicz J，Gsieniec L，Gorry T，et al. Evacuating robots via unknown exit in a disk ［C］// Proc of the 28th International Symposium on Distributed Computing. Berlin： Springer，2014： 121-136.

［11］Czyzowicz J，Dobrev S，Georgiou K，et al. Evacuating two robots from multiple unknown exits in a circle ［J］. Theoretical Computer Science，2018，709： 20-30.

［12］Pattanayak D，Ramesh H，Mandal P S，et al. Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication ［C］// Proc of the 19th International Conference on Distri-buted Computing and Networking. New York： ACM Press，2018： 1-4.

［13］Lamprou I，Martin R，Schewe S. Fast two-robot disk evacuation with wireless communication ［J］. Theoretical Computer Science，2020，846： 38-60.

［14］Czyzowicz J，Kranakis E，Krizanc D，et al. Wireless autonomous robot evacuation from equilateral triangles and squares ［C］// Proc of the 14th International Conference on Ad hoc Networks and Wireless. Cham： Springer，2015： 181-194.

［15］Chuangpishit H，Mehrabi S，Narayanan L，et al. Evacuating equilateral triangles and squares in the face-to-face model ［J］. Computational Geometry，2020，89（4）： 101624.

［16］Bagheri I，Narayanan L，Opatrny J. Evacuation of equilateral triangles by mobile agents of limited communication range ［C］// Proc of the 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks. Cham： Springer，2019： 3-22.