多機器人巡邏可穿越圓的算法研究

摘 要：

對已知環(huán)境進行巡邏，是機器人的基本任務之一，在現(xiàn)實中有著廣泛應用。相關問題在計算幾何學和機器人學的研究中得到了廣泛關注。機器人巡邏問題要求對規(guī)定區(qū)域長時間連續(xù)地進行覆蓋，以空閑時間判斷機器人巡邏效率，空閑時間越短，巡邏效率越高。針對變速機器人需同時巡邏區(qū)域邊界和內部的情況，設計了可穿越圓模型，即機器人需要對圓邊界和內部一條直徑進行巡邏。針對該模型首先提出使用兩個變速機器人的巡邏算法。在對模型幾何特征分析的基礎上，分析了最優(yōu)算法應具備的一般要求，證明了所提算法的最優(yōu)性。在研究兩個變速機器人巡邏算法的基礎上，提出了三個變速機器人相互配合巡邏可穿越圓的算法，并證明了在最好情況下空閑時間為分區(qū)算法的19/25。最后，通過實驗仿真驗證了理論分析的正確性。

關鍵詞：計算幾何；路徑規(guī)劃；巡邏；空閑時間；移動機器人

中圖分類號：TP301.6"" 文獻標志碼：A""" 文章編號：1001-3695（2024）12-007-3579-08

doi： 10.19734/j.issn.1001-3695.2024.04.0128

Algorithm for patrolling traversable circle with multiple robots

Zhang Ruiyue， Wei Qi， Zhang Wenxin， Wu Haonan

（School of Computer Science amp; Artificial Intelligence， Liaoning Normal University， Dalian Liaoning 116081， China）

Abstract：

Patrolling is one of the basic tasks of robots which has a wide range of applications in reality. The related issues have received much attention in the research of computational geometry and robotics. The problem of robot patrolling requires continuous coverage of designated areas for a long time， and this paper employed idle time to express the patrol efficiency of robots. The shorter the idle time， the better the efficiency. Therefore， this paper designed a traversable circle model， where the robot needs to patrol the boundary and the diameter of the circle. This paper firstly proposed an algorithm which used two va-riable speed robots for this model. On the basis of analyzing the geometric features of the model， this paper proved the optimality of the algorithm according to its requirements. Then， this paper proposed an algorithm for three variable speed robots to coo-perate with each other to patrol traversable circle and proved the optimal idle time of this algorithm is 19/25 of the partition algorithm. Finally， this paper verified the correctness of the theoretical analysis through simulation experiments.

Key words：computational geometry; path planning; patrolling; idle time; mobile robots

0 引言

機器人對已知區(qū)域巡邏是計算幾何學和機器人學中的熱點問題［1～3］。多機器人巡邏是指一組機器人在給定區(qū)域內部或邊界來回移動以保護或監(jiān)督該區(qū)域，目的是確保區(qū)域內的每個點都不會長時間無人看管［4～6］。機器人巡邏問題具有實際應用價值，如公共區(qū)域安保巡邏、邊境巡邏、工廠巡邏等。因此，研究機器人巡邏算法兼具理論價值和實際意義。

常見巡邏問題可以分為對區(qū)域邊界的巡邏和對區(qū)域內部的巡邏。機器人對區(qū)域邊界進行巡邏，防止入侵者從邊界進入?yún)^(qū)域內部。Czyzowicz等人［7］首先將機器人所需巡邏的邊界簡化為單位線段和單位圓模型，以空閑時間作為衡量巡邏效率的依據(jù)。他們提出k個最大速度分別為v1，v2，…，vk（其中v1≥v2≥…≥vk）的變速機器人a1，a2，…，ak，采用分區(qū)算法巡邏單位線段的效率最高，即按照機器人最大速度之比為其分配對應長度線段，機器人以最大速度交替訪問線段端點；采用循環(huán)算法巡邏單位圓邊界的效率最高，即將機器人等距地在圓邊界上以相同速度逆時針巡邏。其研究表明，即使在最簡單的場景下，機器人巡邏算法也具備復雜性。為便于描述，本文用Ia表示機器人以分區(qū)算法巡邏單位線段的空閑時間，Ia=2/（v1+v2+…+vk）；用Ib表示機器人以循環(huán)算法巡邏單位圓邊界的空閑時間，Ib=1/（max1≤i≤kivi）。隨后，Kawamura等人［8］提出新的線段巡邏算法，其效率是分區(qū)算法的4/3倍，同時證明了與線段巡邏相關的點巡邏問題是NP完全問題；針對單位圓巡邏，證明了存在一種機器人部署的算法，其巡邏效率是循環(huán)算法的1.05倍。Haeupler等人［9］通過機器人巡邏線段的實例，證明了存在εgt;0，使得巡邏效率是分區(qū)算法的2（1－ε）倍。Chuangpishit等人［10］研究了對線段中所需巡邏的點加以頻率約束的巡邏算法，在提出的近似算法中，巡邏效率最高算法的空閑時間為機器人巡邏該區(qū)域一次最少時間的 3倍。Damaschke［11］在此基礎上加以深入研究，提出了利用PTAS獲得整數(shù)值的近似算法。Dumitrescu等人［12］對圓巡邏類似的跑步者問題進行了研究，提出了不同速度跑步者沿圓運動的一般規(guī)律。Morales-Ponce［13］針對區(qū)域中位置重要性的不同，研究k個機器人無限次頻繁地訪問低優(yōu)先級片段的同時使得高優(yōu)先級片段空閑時間盡可能小的算法，借助強雙蓋子和單蓋子的概念證明了空閑時間的上下界，并且提出了在O（max（n，k）log n）的運行時間內計算蓋子長度的算法。

機器人對區(qū)域內部巡邏，完成保護、檢查、維修等任務。Das等人［14］研究了一組機器人協(xié)作巡邏動態(tài)環(huán)網(wǎng)的問題，其中節(jié)點固定，邊是動態(tài)的，給出了空閑時間的下界，證明了所提算法的高效性?？紤]到點在巡邏中所占權重的不同，Mallya等人［15］首先提出了基于時間周期的巡邏算法TPBP以解決優(yōu)先級巡邏問題，機器人在完成對區(qū)域巡邏的同時，使得高優(yōu)先級點在給定周期內被訪問。隨后，Mallya等人［16］將節(jié)點集分為優(yōu)先級節(jié)點和非優(yōu)先級節(jié)點，證明了一個機器人返回優(yōu)先級節(jié)點的時間間隔的下界，提出了返回優(yōu)先節(jié)點的時間是下界的2α倍的巡邏策略，并在不同的網(wǎng)格圖上驗證了算法的可行性。

考慮在實際應用場景中，機器人不僅需要對區(qū)域邊界進行巡邏，還需要對區(qū)域內部進行監(jiān)視［17，18］。例如，在軍事基地的安全管理中，機器人不僅需要巡邏基地邊界以防止未經授權的進入，還需要對基地內的主要道路進行監(jiān)測，確?；貎炔吭O施的安全。同樣，在城市公共空間，如公園和大型廣場，機器人不僅要在公共空間的邊界進行巡邏以確保整體安全，還需要巡視行人較多的主要道路，起到幫助游客、提供信息服務、監(jiān)控設施狀況的作用。因此，本文設計了可穿越圓模型，即所需巡邏的區(qū)域變?yōu)榱恕皥A邊界+直徑”。相比圓邊界的巡邏和線段巡邏，變速機器人在可穿越圓上面臨的決策更加復雜，提出高效算法更具挑戰(zhàn)。本文通過與機器人以分區(qū)算法巡邏可穿越圓的空閑時間進行比較，證明了所提算法的高效性。

1 問題描述與相關算法

1.1 問題描述

本節(jié)從巡邏場景、機器人數(shù)量、機器人速度等方面給出多機器人協(xié)作巡邏可穿越圓的模型描述。

定義1 可穿越圓CL（圖1）。C為半徑為1的圓，L為C的一條直徑，圓 C和直徑L構成的圖形稱為可穿越圓CL。

巡邏過程中，機器人可在圓邊界或直徑上移動，如圖1所示。當機器人位于直徑與圓邊界交點時，有三種巡邏方向可供選擇，而在其他位置，只有兩種巡邏方向可供選擇。機器人可選方向的增加會使巡邏算法更為復雜。

定義2 路徑選擇點。在可穿越圓中，直徑L與圓邊界的交點稱為路徑選擇點，左側路徑選擇點記作p，右側路徑選擇點記作q。

機器人巡邏可穿越圓的目標是使可穿越圓上任意一點連續(xù)兩次訪問的時間間隔最小。

定義3 空閑時間I［7］。設Euclid Math OneAAp為一種巡邏算法，使用k個最大速度分別為 v1，v2，…，vk（其中 v1≥v2≥…≥vk）的機器人a1，a2，…，ak巡邏可穿越圓?？纱┰綀A上的任意一點 x，任意連續(xù)兩次被訪問的時間間隔都小于等于T，T的最小值即為空閑時間I。

本文以空閑時間I來計算機器人巡邏可穿越圓的效率，空閑時間越小，巡邏效率越高。

1.2 相關算法

分區(qū)算法和循環(huán)算法是解決巡邏問題的兩個基本算法，其中分區(qū)算法在線段上有較好的巡邏效率，循環(huán)算法在圓上有較好的巡邏效率。

分區(qū)算法的基本思想是，根據(jù)機器人速度之比劃分線段，每個機器人負責巡邏一段線段。k個最大速度分別為 v1，v2，…，vk（其中 v1≥v2≥…≥vk）的變速機器人a1，a2，…，ak以分區(qū)算法巡邏長度為L的線段的步驟如下：

a）將長度為L的線段劃分為k段，使得第i段的長度si=Lvi∑ki=1vi。

b）將機器人ai放在第i段線段的任意位置，其中i=1，…，k。

c）機器人ai以最大速度vi交替訪問第i段線段的兩個端點，其中i=1，…，k。

每個機器人各自巡邏對應線段，除端點位置外，線段內的每個點只被一個機器人訪問。每一段訪問頻次最低的點為端點位置，在機器人ai連續(xù)兩次訪問同一側端點的時間間隔內，機器人對第i段遍歷了兩次，則端點位置空閑時間等于整條線段的空閑時間，I=2Lvi∑ki=1vi/vi=2L∑ki=1vi。

循環(huán)算法的基本思想是，選取一部分機器人等距地放置在圓邊界上，機器人以相同速度逆時針巡邏。k個最大速度分別為v1，v2，…，vk（其中 v1≥v2≥…≥vkgt;0）的變速機器人a1，a2，…，ak以循環(huán)算法巡邏周長為C的圓的步驟如下：

a）選取r個機器人，使得r滿足max1≤i≤kivi=rvr。

b）將機器人a1，a2，…，ar逆時針等距地放置在圓邊界上，相鄰兩個機器人的距離為C/r。

c）機器人a1，a2，…，ar以速度vr沿圓邊界逆時針巡邏。

假設在時刻t，機器人aj訪問了點x，由于機器人aj+1與aj的距離為C/r，機器人aj+1以速度vr巡邏，則機器人aj+1訪問點 x的時刻為t+C/（rvr），該點空閑時間為C/（rvr）。同理可得整個圓的空閑時間為I=C/（max1≤i≤kivi）。

文獻［7］分別證明了機器人數(shù)量為2時分區(qū)算法的高效性和機器人數(shù)量小于5時循環(huán)算法的高效性。

引理1［7］ 兩個最大速度分別為v1、v2的機器人以分區(qū)算法巡邏單位線段S=［0，1］使得空閑時間最小，Iopt=2/（v1+v2）。

引理2［7］ 最大速度分別為v1，v2，…，vk（其中 v1≥v2≥…≥vkgt;0）的k個機器人，當 klt;5時，以循環(huán)算法巡邏單位圓的空閑時間最小，Iopt=1/（max1≤i≤kivi）。

如果機器人僅采用分區(qū)算法巡邏可穿越圓，可穿越圓（除分區(qū)所形成的端點）在一個空閑時間內被遍歷了兩次，可穿越圓上空閑時間最大的點位于機器人所巡邏線段的端點處，忽略了可穿越圓的封閉性，故巡邏效率不能達到最優(yōu)。如果機器人僅采用循環(huán)算法巡邏可穿越圓，則在兩個機器人速度相差較大時，速度較慢的機器人未能起到作用；同時若將可穿越圓構成一個封閉回路，則某一段需要重復巡邏兩次，故巡邏效率不能達到最優(yōu)。因此，本文考慮結合分區(qū)算法和循環(huán)算法，給出兩個機器人和三個機器人巡邏可穿越圓的高效算法。

2 兩個機器人巡邏可穿越圓算法

本章根據(jù)可穿越圓的幾何特性，分別給出使用兩個相同最大速度和不同最大速度的機器人巡邏可穿越圓的算法，并通過空閑時間分析證明算法的最優(yōu)性。

2.1 兩個相同最大速度機器人

2.1.1 巡邏算法

考慮機器人最大速度相同的情況，本文給出了一種簡單巡邏策略，將分區(qū)算法與循環(huán)算法相結合，使得兩個機器人在巡邏過程中作出同樣的貢獻。

算法1 使用兩個相同最大速度機器人巡邏可穿越圓算法

輸入：半徑為1的可穿越圓CL；機器人的最大速度v。

輸出：空閑時間I。

a）以直徑為分界線將可穿越圓分為兩部分，每一部分由圓邊界的一半和直徑組成一個封閉半圓。

b）將機器人分別放在兩個封閉半圓的任意位置。

c）機器人以最大速度沿封閉半圓逆時針巡邏。

d）計算空閑時間為（π+2）/v。

2.1.2 算法分析

在上述算法中，每個機器人各自負責一個封閉半圓，每個封閉半圓完成一次巡邏的最少時間相同，兩個機器人并不需要考慮彼此之間的協(xié)助。直徑在任意一段空閑時間內被巡邏了兩次，經過證明，這種重復巡邏不可避免。

定理1 兩個相同最大速度的機器人巡邏可穿越圓的空閑時間最小為（π+2）/v。

證明 如果只巡邏可穿越圓CL一次，最好的策略是將巡邏路徑平均分配給兩個機器人，即每個機器人負責巡邏π+1長度的路徑，在此過程中，整個模型的所有點只被訪問了一次，所需時間為（π+1）/v。為保證所有點在（π+1）/v時間內被訪問且僅被訪問一次，為兩個機器人分配巡邏區(qū)域。其分配方式可概括為兩類，如圖2所示，以虛線和實線來區(qū)分兩個機器人的巡邏路徑。

分配方式1，每個機器人巡邏圓邊界的一半以及直徑的一半，又由于巡邏路徑必須是連續(xù)的，所以只能以圓心為分界點劃分巡邏路徑；分配方式2，一個機器人巡邏π+1長度的圓邊界，另一個機器人巡邏直徑和π－1長度的圓邊界，又由于所有點只能被訪問一次，如果起點和終點都不在路徑選擇點，將導致其中一個機器人的巡邏路徑包含兩個路徑選擇點，此時另一個機器人的巡邏路徑并非連續(xù)。所以兩個機器人的起點和終點一定有一個是在圓心或路徑選擇點。

巡邏需要對區(qū)域不斷探查，在一次巡邏基礎上考慮周期性巡邏。當機器人始終以一種分配方式進行巡邏，可穿越圓的空閑時間為（2π+2）/v，大于（π+2）/v。當兩個機器人起點都在路徑選擇點時，兩種分配方式可以進行切換，如圖3所示，在進行切換的兩次巡邏過程中，圓邊界上兩個機器人相遇位置兩次訪問時間間隔為2π/v，大于（π+2）/v。

考慮將開放的巡邏區(qū)域構成一個最小的封閉圖形由機器人分別巡邏，由于第二種分配方式使得其中一個機器人需要巡邏長度為2π的圓邊界，而在分配方式1基礎上形成的最小閉環(huán)周長都為π+1，則第一種分配方式效率高于第二種分配方式。

根據(jù)引理2，如果只考慮圓邊界的巡邏，兩個相同最大速度的機器人采用循環(huán)算法對圓邊界巡邏的空閑時間最小。根據(jù)引理1，如果只考慮圓內部的巡邏，采用分區(qū)算法巡邏直徑的空閑時間最小，直徑在任意一個空閑時間內被巡邏了兩次。

假設存在算法1′，使得可穿越圓的空閑時間I1′小于（π+2）/v。不失一般性，對圓邊界上距離直徑最遠的點s1進行分析，其被巡邏情況主要分為以下兩類。

第一種情況：s1只由機器人a1巡邏。如果 a1沿最小閉環(huán)再次訪問s1，s1的空閑時間為（π+2）/v，大于I1′。如果 a1 不沿閉環(huán)進行巡邏，a1最多使得vI1′/2長度的路徑的空閑時間滿足巡邏要求，可穿越圓未被巡邏區(qū)域長度為2π+2-vI′1/2，又因為 I′1lt;（π+2）/v，有vI′1/2lt;（π+2）/2，則（2π+2-vI1′/2）/v gt; （3π+2）/（2v），a2不能使得未被巡邏區(qū)域的空閑時間滿足巡邏要求。

第二種情況：s1由機器人a1和 a2巡邏。如果兩個機器人只沿圓邊界循環(huán)巡邏，由于兩個機器人的最大速度相同，且圓邊界上巡邏策略的調整無法覆蓋圓邊界所有點，對圓邊界的空閑時間沒有幫助，所以兩個機器人在圓邊界上保持等距地以最大速度沿相同的方向巡邏，使得s1以及圓邊界上任意一點的空閑時間為π/v，小于I1′。

在對s1由機器人 a1和a2巡邏分析的基礎上，進一步分析可穿越圓內部直徑的巡邏，機器人從路徑選擇點進入圓內部直徑，再從直徑回到圓邊界的方式有以下兩種。

a）機器人反向從進入可穿越圓內部的路徑選擇點返回圓邊界。機器人巡邏可穿越圓的路徑如圖4（a）所示，等價于可穿越圓模型擴展成為了2π+4的圓，兩個機器人以循環(huán)算法進行巡邏。可穿越圓的空閑時間為（π+2）/v。

b）機器人沿直徑從另一個路徑選擇點返回圓邊界，如圖4（b）所示。由于機器人在圓邊界上巡邏方向的調整不能覆蓋所有區(qū)域，圓邊界整體的空閑時間不能減少，且兩個機器人在圓邊界上沿同一個方向巡邏，即一個機器人沿包含直徑的最小閉環(huán)進行巡邏，另一個機器人沿圓邊界進行巡邏，導致圓邊界的一半始終只有一個機器人巡邏，可穿越圓的空閑時間為2π/v，大于I1′。

綜上，不存在算法1′，使得可穿越圓的空閑時間小于（π+2）/v。因此，機器人分別沿封閉半圓進行巡邏的效率最高，空閑時間為（π+2）/v。

由定理1可知，算法1為兩個相同最大速度的機器人巡邏可穿越圓的最優(yōu)算法。

2.2 兩個不同最大速度機器人

考慮機器人最大速度不同的情況，如果采用算法1進行巡邏，那么兩個半圓的空閑時間在兩個機器人最大速度相差較大時也將相差較大，算法的巡邏效率將由速度較慢的機器人所在半圓的空閑時間決定?；谶@種思考，本文提出了機器人相互協(xié)助的算法，在某些情況下，速度較快的機器人需要去幫助速度較慢的機器人。

2.2.1 巡邏算法

算法2 兩個不同最大速度機器人巡邏可穿越圓算法

輸入：半徑為1的可穿越圓CL；兩個機器人a1、 a2的最大速度v1、 v2，其中v1≥v2。

輸出：空閑時間I。

a）如果0lt;v2/v1≤2/π，則機器人a1從路徑選擇點p出發(fā)，逆時針巡邏圓邊界，當a1到達路徑選擇點q時，沿直徑方向巡邏（2v1－πv2）/（v1+v2）距離，再返回路徑選擇點 q 繼續(xù)逆時針巡邏圓周；機器人 a2 從路徑選擇點p沿直徑巡邏2－（2v1－πv2）/（v1+v2）的距離后返回路徑選擇點p，重復此過程，如圖5（a）所示。

b）如果2πl(wèi)t;v2v1≤π+22π，則機器人a1從路徑選擇點p出發(fā)逆時針巡邏圓周。機器人a2以最大速度從路徑選擇點q出發(fā)沿直徑交替訪問路徑選擇點，重復此過程，如圖5（b）所示。

c）如果π+22πl(wèi)t;v2v1≤1，則機器人a1以最大速度從路徑選擇點p出發(fā)逆時針巡邏封閉上半圓，機器人a2以最大速度從路徑選擇點p出發(fā)逆時針巡邏封閉下半圓，如圖5（c）所示。

d）計算空閑時間。

2.2.2 算法分析

在算法2中，根據(jù)兩個機器人最大速度之比確定巡邏策略，計算不同比值下的空閑時間，可得定理2。

定理2 兩個機器人以算法2巡邏可穿越圓，可穿越圓的空閑時間為

I2=2π+4v1+v2" 0lt;v2v1≤2π

2πv1 2πl(wèi)t;v2v1≤π+22π

π+2v2 π+22πl(wèi)t;v2v1≤1（1）

證明 不失一般性，速度較快的機器人以最大速度沿逆時針方向巡邏圓邊界，速度較慢的機器人以最大速度在直徑上交替訪問路徑選擇點。

當兩個機器人的最大速度v2：v1≤2：π時，圓邊界空閑時間小于直徑，為提高巡邏效率，速度較快的機器人應幫助速度較慢的機器人，即機器人a1擴大巡邏的范圍，機器人a2縮小在直徑上巡邏的范圍，如圖5（a）所示。假設a1在直徑上巡邏長度為x1，則a1巡邏區(qū)域的空閑時間為 2π+2x1v1；a2在直徑上所需巡邏長度為2－x1，則a2巡邏區(qū)域的空閑時間為 2×（2－x1）v2。當2π+2x1v1=2×（2－x1）v2，即x1=2v1－πv2v1+v2時，協(xié)助巡邏效率最高，可穿越圓的空閑時間為2π+4v1+v2 。又a1在直徑上所覆蓋的路徑最多為2，2v1－πv2v1+v2≤2，即0lt;v2v1≤2π。所以，當0lt;v2v1≤2π時，可穿越圓的空閑時間為2π+4v1+v2。

當機器人的最大速度之比v2：v1gt;2：π時，直徑上的空閑時間小于圓邊界。根據(jù)兩個機器人最大速度的比值選擇巡邏策略，當兩個機器人速度之比在2/π和（π+2）/（2π）之間時，以步驟b）巡邏可穿越圓的空閑時間為2π/v1，小于以步驟c）巡邏的空閑時間（π+2）/v2，如圖5（b）所示。當兩個機器人速度之比超過（π+2）/（2π）時，以步驟c）巡邏可穿越圓的空閑時間為（π+2）/v2，小于以步驟b）巡邏的空閑時間2π/v1，如圖5（c）所示。

針對直徑空閑時間小于圓邊界空閑時間的情況，對兩個機器人的巡邏策略進行分析。直徑上的機器人a2應幫助圓邊界上的機器人。機器人a2需要從路徑選擇點向圓邊界巡邏，如圖6所示，機器人a2離開直徑一段距離后有兩種方式返回直徑，返回方式1中機器人沿原路返回路徑選擇點，返回方式2中機器人a2沿圓邊界從另一側路徑選擇點返回直徑。

當機器人a2以返回方式1返回直徑，機器人a1無法直接跳過被機器人a2協(xié)助巡邏的圓邊界區(qū)域，圓邊界上沒有被機器人a2巡邏的區(qū)域空閑時間不變，整個可穿越圓的空閑時間不變，機器人a2無法協(xié)助機器人a1，如圖6（a）所示。當機器人a2以返回方式2返回直徑，機器人a2巡邏了圓邊界的一半，即機器人a2巡邏了半圓的封閉圖形，該半圓的空閑時間為（π+2）/v2，若機器人a1不改變巡邏區(qū)域，仍繞圓邊界巡邏，則不被機器人a2巡邏的區(qū)域空閑時間為2π/v1，并沒有改變可穿越圓的空閑時間，如圖6（b）所示。因此，要使可穿越圓空閑時間發(fā)生改變，機器人a1也必須改變巡邏區(qū)域。如果機器人a2以返回方式2返回直徑，那么機器人a1采用循環(huán)策略巡邏另一個封閉半圓可以有效提高巡邏效率，此時機器人a1所巡邏的圓邊界的空閑時間為（π+2）/v1，整個可穿越圓的空閑時間為（π+2）/v2。

因此，當兩個機器人速度之比為2∶πl(wèi)t;v2∶v1≤2+π∶2π時，以步驟b）的策略進行巡邏。當兩個機器人速度之比v2∶v1gt;2+π∶2π時，以步驟c）的策略巡邏可穿越圓。

綜上，兩個不同最大速度機器人以算法2巡邏可穿越圓的空閑時間為I2。

在算法2中，分區(qū)算法和循環(huán)算法以不同的方式相結合，機器人合作完成對可穿越圓CL的巡邏。本文利用反證法，證明了算法2是具備不同最大速度的兩個機器人巡邏可穿越圓的最優(yōu)算法之一，沒有其他算法的空閑時間能夠小于I2。

假設存在算法2′，使得巡邏的空閑時間I2′lt;I2。可穿越圓邊界上與直徑相距最遠的兩個點為s1和s2，如圖7所示。

引理3 對于任意t*≥0，算法2′中至少有兩個不同的機器人訪問了 s1和 s2。

證明 不失一般性，假設在t*時刻之后只有機器人ai訪問s1，為使s1的空閑時間小于I2，需要對ai在（t*，t*+I2′）的巡邏路徑加以條件限制。對ai在（t*，t*+I2′）返回s1的巡邏路徑進行分類，有四種可能的返回方式，如圖8所示：a）繞圓邊界返回 s1；b）繞上半圓返回s1；c）繞下半圓返回s1；d）ai在巡邏不超過viI2′/2長度后原路返回 s1。返回方式1和2是ai再次繞封閉圖形訪問 s1 的最短路徑。在巡邏過程中，ai也可以對封閉圖形邊界重復巡邏或巡邏可穿越圓CL的其他區(qū)域。

對四種返回方式分別進行分析，根據(jù)空閑時間的要求，對于ai在（t*，t*+I2′）沒有被覆蓋的巡邏區(qū)域aj應在（t*，t*+I2′）完成巡邏。

a）ai以返回方式1返回s1所需時間最少為2π/vi。當i=1時，2π/vi取最小值為2π/v1，與算法2步驟c）相對應，即 a1巡邏圓邊界，a2巡邏直徑，則可穿越圓的空閑時間至少為2π/v1，s1的空閑時間并不能小于I2。

b）ai以返回方式2返回s1所需時間最少為（π+2）/vi。當 i=1時，（π+2）/vi取最小值為（π+2）/v1，圓邊界的下半部分未被巡邏，aj繞下半圓巡邏使得圓邊界的下半部分空閑時間最小，與算法2步驟d）相對應，可穿越圓的空閑時間為（π+2）/v2，則s1的空閑時間并不能小于I2。

c）ai以返回方式3返回s1所需時間最少為（2π+2）/vi，圓邊界的1/4未被巡邏，aj交替訪問區(qū)域端點使得這部分空閑時間最小為π/vj。當i=1時的可穿越圓空閑時間小于i=2時，空閑時間為max2π+2v1，πv2，max2π+2v1，πv2始終大于 I2。

d）ai以返回方式4返回 s1，則ai在每個空閑時間內最多覆蓋viI′2/2的區(qū)域路徑，aj應覆蓋 ai在每個空閑時間內未被覆蓋的區(qū)域。又因為I2′lt;I2，則當0lt;v2v1≤2π，有2π+2v1+v2lt;I2′lt;2π+4v1+v2，即2π+2lt;I2′（v1+v2）lt;2π+4；當2πl(wèi)t;v2v1≤π+22π，有2π+2v1+v2lt;I2′lt;2πv1，即2π+2lt;I2′（v1+v2）lt;2πv1×（v1+v2）lt;3π+2；當π+22πl(wèi)t;v2v1≤1，有2π+2v1+v2lt;I2′lt;π+2v2，即2π+2lt;I2′（v1+v2）lt;π+2v2×（v1+v2）lt;3π+2。當I2′（v1+v2）最大時，a2的最大速度等于 a1的最大速度，I2′（v1+v1）lt;3π+2，即v1I2′2lt;3π+24；當i=1時，viI′22最大，viI′22lt;3π+24，考慮圓邊界的巡邏情況，至少還有 2π－（3π+2）/4的區(qū)域未被巡邏，又因為 2π－（3π+2）/4gt;π，則機器人以繞圓循環(huán)的方式巡邏效率最高，此時圓邊界的空閑時間為2π/vj，j=1時圓邊界空閑時間為2π/v1，大于I2′。

綜上，對于任意 t*≥0，至少有兩個不同的機器人訪問了s1，同理，至少有兩個不同的機器人訪問了s2。

引理4 在算法 2′執(zhí)行過程中，任意一個空閑時間內一定存在路徑被a1重復巡邏。

證明 在不考慮對區(qū)域內部直徑巡邏的情況下只對s1和s2進行巡邏，由于s1和s2在圓邊界上相距最遠，所以根據(jù)引理2，對圓邊界采用循環(huán)策略使得空閑時間最小，空閑時間為2πmax1≤i≤2ivi。當v1≥2v2，圓邊界巡邏只使用a1，則圓邊界上的空閑時間為2π/v1，與算法2中步驟c）一致。

當v1lt;2v2，兩個機器人以相同速度繞圓邊界巡邏，a2在圓邊界的巡邏中以最大速度進行，充分利用了a2的性能；a1降低了最大速度進行巡邏，因此如果要在滿足圓邊界巡邏的同時對內部進行巡邏，a1需要覆蓋更多巡邏區(qū)域。設在t時刻a1訪問了s1，在時間段（t，t+I2′］不存在路徑被機器人a1重復巡邏，考慮時間段t+I2′2，t+3I2′2可穿越圓被巡邏情況。

a1在離開 s1 后，巡邏了v1I2′長度的路徑，至少經過了一次路徑選擇點，因為v1I2′ gt; π+1。圖9表示了時間段（t，t+I2′）內機器人a1兩種可能的巡邏路徑。當a1經過路徑選擇點時，只能選擇一個方向進行巡邏，a1在時間段（t，t+I2′］沒有覆蓋的區(qū)域必須由a2進行巡邏，則a2在時間段（t，t+I2′］至少需要巡邏2π+2-v1I2′長度的區(qū)域，又因為v1I2′2lt;3π+24，關于該不等式的證明，已在引理3中詳細闡述，所以2π+2-v1I2′ gt;2π+2-3π+22=π+22。根據(jù)空閑時間的定義，在任意一個空閑時間內，任意一個點至少被訪問了一次，則a1在時間段（t，t+I2′］沒有被訪問的位置由a2進行巡邏。但a2不能在（2π+2-v1I2′）/v2的時間完成巡邏，因為a2巡邏圖9（a）中未被a1訪問的區(qū)域時，會對a1在圓邊界上已經訪問的區(qū)域進行重復巡邏；a2巡邏圖9（b）中未被a1訪問的區(qū)域時，由于未被巡邏區(qū)域并不是連續(xù)的，從路徑選擇點分開的三條路徑，其中一條被重復巡邏才能訪問其余兩條路徑。

對可穿越圓在時間段［t+I2′/2，t+3I2′/2］的巡邏情況以及空閑時間進行分析。因為在時間段（t，t+I2′］不存在路徑被a1重復巡邏，可以確定a1在（t+I2′/2，t+I2′］巡邏了viI′2/2長度的路徑。對時間段［t+I2′，t+3I2′/2］ a1 的巡邏進行分析，a1在t+I′2時刻可以繼續(xù)向前也可以反向巡邏。

如果a1在［t+I2′，t+3I2′/2］存在沿原路反向巡邏的情況，則機器人a1在時間段（t+I2′/2，t+3I2′/2］最多只能使v1I2′/2長度的路徑滿足空閑時間小于等于I2′的巡邏要求。根據(jù)可穿越圓空閑時間的要求，a1在時間段（t+I2′/2，t+3I2′/2］未能覆蓋的區(qū)域a2應完成巡邏。因為對路徑來回巡邏時端點位置空閑時間最大，為2倍路徑長度與速度的比值，a1在時間段（t，t+I2′/2］所巡邏的區(qū)域無法在時間段（t+I2′/2，t+3I2′/2］由a1再次巡邏，為了使該區(qū)域的巡邏滿足空閑時間，a2應對該區(qū)域進行巡邏。根據(jù)分區(qū)算法和循環(huán)算法的特點，對a2巡邏方向進行分析：如果機器人a2與a1巡邏該區(qū)域方向相同，那么a2最遲t+I2′應到達s1；如果方向不同，那么a2最遲在t+I2′/2時刻的位置到達a1在t+I2′/2時刻的位置，這樣s1的空閑時間才能小于等于I2′。a2在時間段（t，t+I2′］的巡邏區(qū)域被限制在a1于時間段（t，t+I2′/2］所巡邏的區(qū)域附近。又因為v2I2′2≤v1I2′2lt;3π+24，a2距離a1在時間段（t，t+I2′/2］所巡邏區(qū)域的路徑不能超過v2I2′/2，導致a1在時間段（t，t+I2′］沒有覆蓋的區(qū)域未能被a2巡邏。

如果a1在［t+I2′/2，t+3I2′/2］不存在反向巡邏的情況，則a2須沿著a1的巡邏方向進行巡邏，與a1保持一定距離，對于a1訪問過的位置在空閑時間內再次訪問，否則a1再次訪問其在（t，t+I2′］所巡邏的區(qū)域時，空閑時間已大于I2′。這種類似追趕的巡邏過程等價于將可穿越圓擴展為一個周長最小為2π+4的封閉圓，采用循環(huán)算法對其巡邏使得空閑時間為2π+4max1≤i≤2ivi，大于I2′。

綜上，在算法2′執(zhí)行過程中，任意一個空閑時間內一定存在路徑被a1重復巡邏。

定理3 兩個具備不同最大速度的機器人巡邏可穿越圓的空閑時間最小為I2。

證明 引理3證明了在算法2′執(zhí)行過程中，可穿越圓CL邊界上相距最遠的s1和s2會被兩個機器人相繼訪問。在機器人巡邏s1和s2的基礎上對機器人在圓邊界的巡邏情況進行分析，a1和a2以循環(huán)算法巡邏圓邊界使得圓邊界的最小空閑時間為2πmax1≤i≤2ivi。當v1≥2v2，機器人a1以最大速度v1沿圓邊界循環(huán)，圓邊界的空閑時間為2π/v1，大于I2′；當v1lt;2v2，a1和a2等距地在圓邊界上以v2的速度沿相同方向巡邏，圓邊界的空閑時間為π/v2，小于等于I2′。

由引理4證明了在算法2′執(zhí)行過程中，任意一個空閑時間內一定存在路徑被a1重復巡邏，對兩個機器人最大速度v1lt;2v2時算法2′的執(zhí)行情況進一步分析，如果a1重復巡邏區(qū)域在圓邊界上，其重復巡邏區(qū)域不能覆蓋整個圓邊界，不能減少圓邊界的空閑時間，因此a1重復巡邏區(qū)域位于直徑上。a1從路徑選擇點進入圓內部直徑，應從同一個路徑選擇點返回圓邊界，否則存在一半的圓邊界a1無法沿同方向巡邏。a1和 a2 協(xié)助巡邏可穿越圓，由于圓是閉環(huán)，所以a1和a2在圓邊界上的距離始終保持在一定范圍內，使得圓邊界的空閑時間小于等于I2′；只由a1巡邏直徑，直徑的空閑時間為（2π+4）/v1，因此 a2 也需要對直徑進行巡邏。在算法2′執(zhí)行過程中，a1和 a2 在每個巡邏周期都要巡邏一次圓邊界和兩次直徑，即巡邏了2π+4的閉環(huán)，根據(jù)引理2，以循環(huán)算法巡邏使得空閑時間最小為（2π+4）/（2v2），與I2′lt;I2矛盾。

綜上，不存在算法2′使得可穿越圓的空閑時間小于I2，即兩個具備不同最大速度的機器人巡邏可穿越圓的空閑時間最小為I2，定理3得證。

由定理3可知，算法2為兩個不同最大速度的機器人巡邏可穿越圓的最優(yōu)算法。

3 三個機器人巡邏可穿越圓算法

在兩個機器人巡邏可穿越圓的算法中，機器人各自負責所在巡邏區(qū)域，而在對三個機器人巡邏可穿越圓算法的研究過程中，發(fā)現(xiàn)在某些情況下，機器人調整其巡邏速度配合其他機器人，可以使巡邏效率提高。

3.1 巡邏算法

算法3 三個不同最大速度機器人巡邏可穿越圓算法

輸入：半徑為1的可穿越圓CL；三個機器人a1，a2，a3的最大速度分別為v1，v2，v3，其中v1≥ v2≥ v3。

輸出：空閑時間I。

a） 如果v3lt;2v2/π，則機器人a2在巡邏過程中以v2=πv3/2的速度進行巡邏；如果v3≥2v2/π，則機器人a3在巡邏過程中以v3=2v2/π的速度進行巡邏。

b） 如果v1≥v2（2+π）/π，則機器人a1在巡邏過程中以v1=v2×（2+π）/π的速度進行巡邏。

c） a1 的起始位置為路徑選擇點p，a2的起始位置為路徑選擇點q，a3的起始位置在直徑上與路徑選擇點q相距（（πv1/v2）－2π）×（v3/（4v1））處。

d） a1從路徑選擇點p沿直徑方向巡邏（（2πv1/v2）－2π）/4的距離后返回路徑選擇點p，然后沿圓邊界逆時針巡邏至路徑選擇點q，從路徑選擇點q沿直徑方向巡邏（（2πv1/v2）－2π）/4的距離后返回路徑選擇點q，繼續(xù)沿圓邊界逆時針巡邏返回路徑選擇點p，重復此過程。a2從路徑選擇點q一直逆時針繞圓周巡邏。a3從起始位置先向路徑選擇點q進行巡邏，在直徑上交替訪問兩個路徑選擇點。

e） 計算空閑時間。

3.2 算法分析

在算法3中，最大速度較慢的兩個機器人分別巡邏圓邊界和直徑，速度最快的機器人巡邏圓邊界的同時也去幫助直徑上的機器人。如果只有一個機器人巡邏直徑，那么直徑兩端是直徑上空閑時間最大的位置，因此由其他機器人協(xié)助訪問直徑兩端，能降低直徑的空閑時間。

定理4 三個不同最大速度機器人以算法3巡邏可穿越圓，可穿越圓的空閑時間為

I3=max 2πv2-πv1，π（v1+v2）2v1v2，4πv2-π2（v1-v2）2v22 （2）

證明 在算法3的步驟a）中，為使三個機器人能夠更好協(xié)作，a2與a3調整巡邏速度，使得v2：v3=π：2，與同時兼顧圓邊界和直徑部分區(qū)域的a1相互配合。

將a1與a2在圓邊界的巡邏看作追趕的過程。a1在圓邊界上追趕a2，當a1與a2相距π的時候，a1沿直徑方向巡邏一段距離后再返回圓邊界上，那么a1返回到路徑選擇點時， a1 與a2相距最大，路徑選擇點距離上一次被a2訪問的時間間隔最大，所以圓邊界上空閑時間最大的點無限逼近路徑選擇點。根據(jù)速度之比，可得a1每次在直徑上需要巡邏的長度為（2πv2×v1－2π）×12×12，2πv2×v1－2π為a1在a2巡邏圓邊界一圈的時間里能夠比a2多覆蓋的路徑長度，將其平均分配給兩個路徑選擇點附近的直徑，又（2πv2×v1－2π）×12×12應小于等于1，有v1≤v2（π+2）/π。路徑選擇點的空閑時間為（2πv2×v1－2π+π）÷v1，化簡為2πv2－πv1。

如果只有a3在直徑上來回訪問直徑端點，直徑上空閑時間最大的位置是路徑選擇點，空閑時間最小的位置是直徑的中點。參考圓循環(huán)算法，機器人等距分布在圓邊界上以相同速度沿同方向巡邏效率較高，因此為使a1更好地協(xié)助a3，a1在直徑上的巡邏方向始終與a3相同。在這種情況下，直徑上的空閑時間只需要考慮直徑端點位置和a1在直徑上折返的位置，端點位置空閑時間為2v3－（2πv2×v1－2π）×14÷v1，折返位置空閑時間為2－（2πv2×v1－2π）×14÷v3，化簡后分別為π（v1+v2）2v1v2和4πv2-π2（v1-v2）2v22。

綜上，三個機器人以算法3巡邏可穿越圓，可穿越圓的空閑時間為 I3。

圖10為三個機器人以算法3的步驟巡邏可穿越圓實例的時間位置圖，其中v1=π+2，v2=π，v3=2，x軸表示可穿越圓CL，將可穿越圓看作一條 2π+2長度的線段，在線段的p、q位置可以進行路徑選擇；y 軸表示時間。如果以分區(qū)算法巡邏，則Ia=（2π+2）×2∑3i=1vi=2π+2π+2；而在給出的實例中采用算法3進行巡邏使得空閑時間I3=（4+π）/（π+2）lt;Ia，巡邏效率高于分區(qū)算法。

當空閑時間與一次巡邏的最小時間比值最小時，算法3效率最高。此時三個機器人的最大速度之比為v1∶v2∶v3=1∶π216+π2－π4∶14+2π－12，可穿越圓空閑時間 I3=2πv2-πv1，與分區(qū)算法空閑時間的比值最小，約為19/25，巡邏效率明顯提高。

4 仿真實驗與對比分析

為更好地檢驗機器人以算法2和3巡邏可穿越圓的效率，進行了仿真實驗，對比了機器人在不同速度下，所提算法與分區(qū)算法、循環(huán)算法的空閑時間。仿真實驗使用的設備配置為：Windows 11 64位操作系統(tǒng)，Core Ultra 5處理器，主頻為3.6 GHz，安裝內存為32 GB，仿真運行平臺為MATLAB R2020b。

在模型設置中，將可穿越圓的圓心置于坐標系原點，直徑重合于x軸。在 t 時刻機器人ai（i=1，2，3）的位置用（xi（t），yi（t））表示；坐標為 （x，y）的點的空閑時間為 T（x，y）。

4.1 算法2驗證及結果分析

設兩個機器人a1、 a2的最大速度分別為v1、v2，其中v1≥v2gt;0，在實驗中令 v1=1，則v2的取值為（0，1］，共測試了200組不同速度取值下的空閑時間。圖11以最大速度分別為1和0.4的兩個機器人為例，呈現(xiàn)了直角坐標系上的機器人巡邏軌跡。

為驗證算法空閑時間，實驗中選取了可穿越圓上具有代表性的6個采樣點分別統(tǒng)計空閑時間。采樣點坐標分別為（－1，0），（1，0），（0，1）， （0，－1），（0，0），（1－（2v1－πv2）/（v1+v2），0），其中（1－（2v1－πv2）/（v1+v2），0）為a1在算法2中以步驟a）巡邏時在直徑上進行轉向的位置。令s=1－（2v1－πv2）/（v1+v2），當slt;－1時，該點不位于可穿越圓上。表1展示了10組v2不同取值下可穿越圓的空閑時間，數(shù)據(jù)表明，仿真所得空閑時間與理論空閑時間相符，且隨著機器人a2速度的增加，空閑時間逐漸降低。

通過上述實驗方式，分別計算了分區(qū)算法和循環(huán)算法的空閑時間，并與算法2進行對比，證明了所提算法的最優(yōu)性，如圖12所示。

4.2 算法3驗證及結果分析

設三個機器人a1，a2，a3的最大速度分別為v1，v2，v3，其中 v1≥ v2≥ v3gt;0，在實驗中令v2=3.14，v1∈［3.14，6.28］，v3∈（0，3.14］，在算法3中，機器人 a1每次在直徑上所巡邏的長度不超過圓心，a1的巡邏速度不超過v2（2+π）/π≈5.139，為使測試過程中 v1和 v3的維度相等，故將v1的取值設置為［3.14，6.28］，共測試了900組不同速度取值下的空閑時間。圖13以最大速度分別為4.55、3.14、2的三個機器人為例，呈現(xiàn)了直角坐標系上的機器人巡邏軌跡。

使用采樣點選取方法計算空閑時間，分別與分區(qū)算法和循環(huán)算法比較，對比結果如圖14和15所示。通過線性模型對算法3與分區(qū)算法的交界點擬合曲線（實驗中空閑時間相差不超過0.03的點即視為交界點），v3gt;1.5的擬合曲線函數(shù)表達式為f（x，y）=p00+p10x+p01y（其中x表示v1，y表示v3，f（x，y）表示 T ），根據(jù)擬合結果，常數(shù)項p00估計值為3.672，95%置信區(qū)間在3.449～3.896；關于x的系數(shù)p10估計值為－0.021 93，95%置信區(qū)間在－0.093 97～0.050 11；關于 y的系數(shù)p01估計值為－1.566，95%置信區(qū)間在－2.083～－1.049。另一條擬合曲線表達式同樣為f（x，y）=p00+p10x+p01y，其中常數(shù)項p00估計值為3.564，95%置信區(qū)間在3.533～3.595；關于 x的系數(shù)p10估計值為－0.487 4，95%置信區(qū)間在－0.503～－0.471 9；關于 y的系數(shù)p01估計值為－0.014 4，95%置信區(qū)間在－0.024 36～－0.004 446。在擬合曲線范圍內的速度取值組合下，算法3的巡邏效率高于分區(qū)算法。圖14中三個機器人最大速度之比為5.141∶3.14∶2.001時，算法3的效率達到最優(yōu)。

在圖15中，對循環(huán)算法與算法3的交界點進行分析，可將其分為三部分。圖15中顯示在v1≤6.241且v3≤2.101時，空閑時間始終為1.631 47，則該平面上的一條擬合曲線可以直接得出，其參數(shù)方程為x=1.201T=1.631 47；平面上另一條擬合曲線函數(shù)表達式為y=1.1623x2－7.1501x+12.2624。v3gt;2.101的擬合曲線函數(shù)表達式為f（x，y）=p00+p10x+p01y（其中x表示v1，y表示v3，f（x，y）表示T），根據(jù)擬合結果，常數(shù)項p00估計值為3.573，95%置信區(qū)間在3.573～3.574；關于x的系數(shù)p10估計值為－0.500 9，95%置信區(qū)間在－0.501 2～－0.500 6；關于y的系數(shù)p01估計值為－0.000 496 9，95%置信區(qū)間在0.000 173 8～0.000 820 1。在擬合曲線范圍內的速度取值組合下，算法3的巡邏效率高于循環(huán)算法。

5 結束語

本文對速度可變機器人巡邏可穿越圓的算法進行了研究，分別提出了具備相同最大速度的兩個機器人和具備不同速度的兩個機器人協(xié)作巡邏可穿越圓的算法，并通過理論分析與實驗仿真，證明了算法的最優(yōu)性。在此基礎上，進一步研究具備不同最大速度的三個機器人巡邏可穿越圓的算法，提出的巡邏算法在機器人最大速度之比約為1∶0.69∶0.44的情況下效率達到最優(yōu)，遠高于分區(qū)算法和循環(huán)算法。本文研究的巡邏算法限制了機器人數(shù)量，下一步將在機器人數(shù)量不確定的情況下研究更一般的高效算法；此外，在特殊巡邏場景中，局部區(qū)域的重要性是不同的，因此根據(jù)重要程度為局部區(qū)域加上權重，研究多機器人協(xié)作巡邏加權區(qū)域算法也是重要的后續(xù)研究工作。

參考文獻：

［1］Jana M， Vachhani L， Sinha A. A deep reinforcement learning app-roach for multi-agent mobile robot patrolling ［J］. International Journal of Intelligent Robotics and Applications， 2022， 6（4）： 724-745.

［2］Chircop P A， Surendonk T J， Van Den Briel M H L， et al. On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage ［J］. Annals of Operations Research， 2022， 312（2）： 723-760.

［3］Huang Li， Zhou Mengchu， Hao Kuangrong， et al. Multirobot coope-rative patrolling strategy for moving objects ［J］. IEEE Trans on Systems， Man， and Cybernetics： Systems， 2023， 53（5）： 2995-3007.

［4］霍耀彥， 李宗剛， 高溥. 基于節(jié)點重要度的多機器人分布式巡邏策 略 ［J］. 計算機應用研究， 2022， 39（2）： 510-514. （Huo Yaoyan， Li Zonggang， Gao Pu. Distributed multi-robot patrolling strategy based on importance of nodes ［J］. Application Research of Computers， 2022， 39（2）： 510-514.）

［5］Bui T， Lidbetter T. Optimal patrolling strategies for trees and complete networks ［J］. European Journal of Operational Research， 2023， 311（2）： 769-776.

［6］Caraballo L E， Díaz-Báez J M， Fabila-Monroy R， et al. Stochastic strategies for patrolling a terrain with a synchronized multi-robot system ［J］. European Journal of Operational Research， 2022， 301（3）： 1099-1116.

［7］Czyzowicz J， Gsieniec L， Kosowski A， et al. Boundary patrolling by mobile agents with distinct maximal speeds ［M］// Demetrescu C， Halldórsson M M. Algorithms-ESA 2011. Berlin： Springer， 2011： 701-712.

［8］Kawamura A， Soejima M. Simple strategies versus optimal schedules in multi-agent patrolling ［J］. Theoretical Computer Science， 2020， 839： 195-206.

［9］Haeupler B， Kuhn F， Martinsson A， et al. Optimal strategies for patrolling fences ［EB/OL］. （2018-09-18）. https：//arxiv.org/abs/1809.06727.

［10］Chuangpishit H， Czyzowicz J， Gsieniec L， et al. Patrolling a path connecting a set of points with unbalanced frequencies of visits ［M］// Tjoa A， Bellatreche L， Biffl S， et al. SOFSEM 2018： Theory and Practice of Computer Science. Cham： Springer， 2018： 367-380.

［11］Damaschke P. Two robots patrolling on a line： integer version and app-roximability ［M］// Gsieniec L， Klasing R， Radzik T. Combinatorial Algorithms. Cham： Springer， 2020： 211-223.

［12］Dumitrescu A， Tóth C D. Problems on track runners ［J］. Computational Geometry， 2020， 88： 101611.

［13］Morales-Ponce O. Optimal patrolling of high priority segments while visiting the unit interval with a set of mobile robots ［J］. Theoretical Computer Science， 2022， 911： 1-18.

［14］Das S， Di Luna G A， Gasieniec L A. Patrolling on dynamic ring networks ［M］// Catania B， Krlovi R， Nawrocki J， et al. SOFSEM 2019： Theory and Practice of Computer Science. Cham： Springer， 2019： 150-163.

［15］Mallya D， Sinha A， Vachhani L， et al. Priority patrolling using multiple agents ［C］// Proc of IEEE International Conference on Robo-tics and Automation. Piscataway， NJ： IEEE Press， 2021： 8692-8698.

［16］Mallya D， Sinha A， Vachhani L. Priority patrol with a single agent—bounds and approximations ［J］. IEEE Control Systems Letters， 2023， 7： 1321-1326.

［17］Czyzowicz J， Gasieniec L， Kosowski A， et al. When patrolmen become corrupted： monitoring a graph using faulty mobile robots ［J］. Algorithmica， 2017， 79（3）： 925-940.

［18］Georgiou K， Kundu S， Praat P. The fagnano triangle patrolling problem （extended abstract） ［M］// Dolev S， Schieber B. Stabilization， Safety， and Security of Distributed Systems. Cham： Springer， 2023： 157-171.