摘 要：

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

關(guān)鍵詞：計(jì)算幾何；路徑規(guī)劃；巡邏；空閑時(shí)間；移動(dòng)機(jī)器人

中圖分類號(hào)：TP301.6"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號(hào)：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 引言

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

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

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

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

1 問題描述與相關(guān)算法

1.1 問題描述

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

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

巡邏過程中，機(jī)器人可在圓邊界或直徑上移動(dòng)，如圖1所示。當(dāng)機(jī)器人位于直徑與圓邊界交點(diǎn)時(shí)，有三種巡邏方向可供選擇，而在其他位置，只有兩種巡邏方向可供選擇。機(jī)器人可選方向的增加會(huì)使巡邏算法更為復(fù)雜。

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

機(jī)器人巡邏可穿越圓的目標(biāo)是使可穿越圓上任意一點(diǎn)連續(xù)兩次訪問的時(shí)間間隔最小。

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

本文以空閑時(shí)間I來計(jì)算機(jī)器人巡邏可穿越圓的效率，空閑時(shí)間越小，巡邏效率越高。

1.2 相關(guān)算法

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

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

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

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

c）機(jī)器人ai以最大速度vi交替訪問第i段線段的兩個(gè)端點(diǎn)，其中i=1，…，k。

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

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

a）選取r個(gè)機(jī)器人，使得r滿足max1≤i≤kivi=rvr。

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

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

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

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

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

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

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

2 兩個(gè)機(jī)器人巡邏可穿越圓算法

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

2.1 兩個(gè)相同最大速度機(jī)器人

2.1.1 巡邏算法

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

算法1 使用兩個(gè)相同最大速度機(jī)器人巡邏可穿越圓算法

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

輸出：空閑時(shí)間I。

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

b）將機(jī)器人分別放在兩個(gè)封閉半圓的任意位置。

c）機(jī)器人以最大速度沿封閉半圓逆時(shí)針巡邏。

d）計(jì)算空閑時(shí)間為（π+2）/v。

2.1.2 算法分析

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

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

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

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

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

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

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

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

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

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

在對(duì)s1由機(jī)器人 a1和a2巡邏分析的基礎(chǔ)上，進(jìn)一步分析可穿越圓內(nèi)部直徑的巡邏，機(jī)器人從路徑選擇點(diǎn)進(jìn)入圓內(nèi)部直徑，再從直徑回到圓邊界的方式有以下兩種。

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

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

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

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

2.2 兩個(gè)不同最大速度機(jī)器人

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

2.2.1 巡邏算法

算法2 兩個(gè)不同最大速度機(jī)器人巡邏可穿越圓算法

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

輸出：空閑時(shí)間I。

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

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

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

d）計(jì)算空閑時(shí)間。

2.2.2 算法分析

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

定理2 兩個(gè)機(jī)器人以算法2巡邏可穿越圓，可穿越圓的空閑時(shí)間為

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）

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

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

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

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

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

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

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

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

假設(shè)存在算法2′，使得巡邏的空閑時(shí)間I2′lt;I2?？纱┰綀A邊界上與直徑相距最遠(yuǎn)的兩個(gè)點(diǎn)為s1和s2，如圖7所示。

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

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

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

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

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

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

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

綜上，對(duì)于任意 t*≥0，至少有兩個(gè)不同的機(jī)器人訪問了s1，同理，至少有兩個(gè)不同的機(jī)器人訪問了s2。

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

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

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

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

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

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

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

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

定理3 兩個(gè)具備不同最大速度的機(jī)器人巡邏可穿越圓的空閑時(shí)間最小為I2。

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

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

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

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

3 三個(gè)機(jī)器人巡邏可穿越圓算法

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

3.1 巡邏算法

算法3 三個(gè)不同最大速度機(jī)器人巡邏可穿越圓算法

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

輸出：空閑時(shí)間I。

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

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

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

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

e） 計(jì)算空閑時(shí)間。

3.2 算法分析

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

定理4 三個(gè)不同最大速度機(jī)器人以算法3巡邏可穿越圓，可穿越圓的空閑時(shí)間為

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

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

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

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

綜上，三個(gè)機(jī)器人以算法3巡邏可穿越圓，可穿越圓的空閑時(shí)間為 I3。

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

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

4 仿真實(shí)驗(yàn)與對(duì)比分析

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

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

4.1 算法2驗(yàn)證及結(jié)果分析

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

為驗(yàn)證算法空閑時(shí)間，實(shí)驗(yàn)中選取了可穿越圓上具有代表性的6個(gè)采樣點(diǎn)分別統(tǒng)計(jì)空閑時(shí)間。采樣點(diǎn)坐標(biāo)分別為（－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）巡邏時(shí)在直徑上進(jìn)行轉(zhuǎn)向的位置。令s=1－（2v1－πv2）/（v1+v2），當(dāng)slt;－1時(shí)，該點(diǎn)不位于可穿越圓上。表1展示了10組v2不同取值下可穿越圓的空閑時(shí)間，數(shù)據(jù)表明，仿真所得空閑時(shí)間與理論空閑時(shí)間相符，且隨著機(jī)器人a2速度的增加，空閑時(shí)間逐漸降低。

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

4.2 算法3驗(yàn)證及結(jié)果分析

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

［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é)點(diǎn)重要度的多機(jī)器人分布式巡邏策 略 ［J］. 計(jì)算機(jī)應(yīng)用研究， 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.