考慮特殊區(qū)域的離散區(qū)域劃分方法

摘 要：

基于多機(jī)器人系統(tǒng)的區(qū)域覆蓋中的區(qū)域劃分問題，分析現(xiàn)有區(qū)域覆蓋任務(wù)發(fā)現(xiàn)，在任務(wù)區(qū)域中存在危險(xiǎn)區(qū)域或優(yōu)先級(jí)更高的特殊區(qū)域。針對(duì)特殊區(qū)域需要分配給最少的機(jī)器人的情況，設(shè)計(jì)了一種基于Morse分解的離散區(qū)域劃分方法。該方法用放射狀Morse分解來定義離散任務(wù)區(qū)域的空間結(jié)構(gòu)，并提出一種改進(jìn)回溯法來確定最優(yōu)分割線，以避免分割特殊區(qū)域并保持多機(jī)器人工作量均衡。仿真給出了在特殊區(qū)域分布不同、機(jī)器人數(shù)量不同的場(chǎng)景下的區(qū)域劃分結(jié)果，并與兩種現(xiàn)有算法進(jìn)行了比較。結(jié)果表明，所提方法能夠生成穩(wěn)定的解，有效減少特殊區(qū)域的分割，合理分配多機(jī)器人的工作量。

關(guān)鍵詞：

多機(jī)器人; 區(qū)域劃分; 特殊區(qū)域; Morse分解; 回溯法

中圖分類號(hào)：

TP 242

文獻(xiàn)標(biāo)志碼： A""" DOI：10.12305/j.issn.1001-506X.2024.05.18

Discrete area partitioning method considering special regions

CAI Chang1， CHEN Jianfeng1，*， YAN Qingli2， LIU Fen1

（1. School of Marine Science and Technology， Northwestern Polytechnical University， Xi’an 710072， China;

2. School of Computer Science and Technology， Xi’an University of Posts and Telecommunications， Xi’an 710121， China）

Abstract：

Based on the problem of area partitioning in multiple robot system area coverage， analyzing existing area coverage tasks， it is found that there are special areas or special areas with higher priority in the task area. A discrete area partitioning method based on Morse decomposition is designed for the case where special areas require the allocation of the least number of robots. The method uses radial Morse decomposition to define the spatial structure of discrete task areas and proposes an improved backtracking method to determine the optimal partitioning line， in order to avoid segmenting special areas and maintain workload balance among multiple robots. The simulation provides the results of region partitioning in scenarios with different distributions of special areas and different numbers of robots， and compares them with two existing algorithms. The results show that the proposed method can generate stable solutions， effectively reduce the partitioning of special regions， and allocate the workload of multiple robots reasonably.

Keywords：

multi-robot; area partitioning; special zone; Morse decomposition; backtracking method

0 引 言

機(jī)器人的區(qū)域覆蓋技術(shù)利用移動(dòng)機(jī)器人遍歷整個(gè)作業(yè)區(qū)域［1-2］，常用于搜救［3-4］、地形監(jiān)測(cè)［5-6］、地板清潔［7］、表面噴涂［8］、智慧農(nóng)業(yè)［9］等領(lǐng)域。單機(jī)器人的區(qū)域覆蓋存在效率低、續(xù)航時(shí)間有限、可靠性差等問題。隨著通信、定位及自動(dòng)化等技術(shù)的迅速發(fā)展，將多機(jī)器人系統(tǒng)（multiple robot system， MRS）應(yīng)用到區(qū)域覆蓋中可很好彌補(bǔ)單機(jī)器人作業(yè)的缺陷與不足［10-12］。在多機(jī)器人的區(qū)域覆蓋任務(wù)中，通常將任務(wù)分成兩部分：區(qū)域劃分和單區(qū)域覆蓋，尤其是不同機(jī)器人之間存在干擾的情況，例如不同水下機(jī)器人搭載的聲納之間的干擾。本文重點(diǎn)研究其中的區(qū)域劃分技術(shù)，目的是將整個(gè)區(qū)域覆蓋任務(wù)劃分成多個(gè)子區(qū)域，并分配給多機(jī)器人。

目前，區(qū)域劃分的傳統(tǒng)方法有Voronoi劃分法［13-14］、Delaunay三角剖分法、基于牛耕法的劃分方法［15］等。Voronoi劃分法是將空間按照歐式距離分配給最近的機(jī)器人;Delaunay三角剖分法則是對(duì)離散的空間構(gòu)造Delaunay三角網(wǎng)，使所有子區(qū)域?yàn)橥苟噙呅?基于牛耕法的劃分方法主要針對(duì)空間中有障礙物的情況，可將空間根據(jù)障礙物形狀劃分成多個(gè)子區(qū)域，然后確定各子區(qū)域的訪問順序，最終覆蓋整個(gè)空間。傳統(tǒng)區(qū)域劃分方法是從空間幾何圖形角度提出的，此類方法雖然簡單，但是在多機(jī)器人的區(qū)域劃分問題中往往存在更多實(shí)際限制。為此，在傳統(tǒng)區(qū)域劃分基礎(chǔ)上，國內(nèi)外專家學(xué)者進(jìn)一步研究了基于多機(jī)器人系統(tǒng)及任務(wù)特點(diǎn)的區(qū)域劃分方法。考慮到機(jī)器人的不同探測(cè)能力和非結(jié)構(gòu)化任務(wù)區(qū)域，Hassan等［13］提出一種基于Voronoi的區(qū)域劃分和分配算法。然而，這種方法引入的重疊區(qū)域增加了機(jī)器人的工作量。Kapoutsis等［16］提出一種基于機(jī)器人的初始位置劃分區(qū)域（divide areas based on Robot’s initial positions，DARP）區(qū)域劃分方法，旨在根據(jù)機(jī)器人的初始位置分配網(wǎng)格化任務(wù)區(qū)域。然而，以水下機(jī)器人的覆蓋任務(wù)為例，所有機(jī)器人從同一位置布放，而非提前部署在不同位置。Balampanis等［17］提出的約束Delaunay三角剖分方法側(cè)重于考慮復(fù)雜的區(qū)域形狀時(shí)和多機(jī)器人之間的工作量均衡。Coombes等［18］提出基于Morse的分解方法，利用移動(dòng)劃線分割復(fù)雜區(qū)域。Morse分解提供了靈活的區(qū)域劃分框架，可根據(jù)需要選擇不同劃線，實(shí)現(xiàn)最優(yōu)劃分。

大部分現(xiàn)有研究側(cè)重于解決工作量均衡、任務(wù)區(qū)域的形狀復(fù)雜等問題，并默認(rèn)任務(wù)區(qū)域是一個(gè)整體，對(duì)內(nèi)部位置一視同仁［19-22］。然而，在實(shí)際應(yīng)用中，任務(wù)區(qū)域中經(jīng)常存在一些特殊區(qū)域。除此之外，其他含有特殊區(qū)域的覆蓋任務(wù)包括重點(diǎn)監(jiān)測(cè)區(qū)域、對(duì)抗性覆蓋任務(wù)中的危險(xiǎn)區(qū)域［23］、地板清潔任務(wù)中的地毯區(qū)域及航空中設(shè)定的潛在危險(xiǎn)區(qū)［24］。對(duì)于這些場(chǎng)景，特殊區(qū)域是整個(gè)任務(wù)區(qū)域的重要組成部分，需要在區(qū)域劃分方法中單獨(dú)處理。

在一些包含特殊區(qū)域的任務(wù)場(chǎng)景中，將特殊區(qū)域分配給少數(shù)機(jī)器人有助于提升覆蓋性能。以對(duì)抗覆蓋為例，將特殊區(qū)域（即危險(xiǎn)區(qū)域）分配給較少的機(jī)器人，使得更少機(jī)器人暴露于危險(xiǎn)中，從而確保MRS的安全［23］。另外，在使用側(cè)掃聲納的水下搜救任務(wù)中，將重點(diǎn)搜索區(qū)域集中到少數(shù)水下機(jī)器人中，通過優(yōu)先解讀這些機(jī)器人采集的聲納圖像，有助于盡早發(fā)現(xiàn)目標(biāo)。

基于以上背景，針對(duì)當(dāng)特殊區(qū)域避免被分割時(shí)的區(qū)域劃分問題，本文提出一種基于Morse分解的離散區(qū)域劃分方法。首先，將傳統(tǒng)的Morse分解擴(kuò)展到離散任務(wù)區(qū)域中，提出了基于放射狀Morse分解的離散任務(wù)區(qū)域的空間結(jié)構(gòu)。然后基于該結(jié)構(gòu)，考慮機(jī)器人的不同可用能量及避免分割特殊區(qū)域原則，提出了一種改進(jìn)回溯法，獲得粗略的區(qū)域劃分結(jié)果。最后，對(duì)于生成的子區(qū)域不連續(xù)的情況，通過對(duì)連接子區(qū)域的單元格進(jìn)行重新分配，構(gòu)建連續(xù)子區(qū)域。為了驗(yàn)證本文方法的性能，在仿真中設(shè)計(jì)了包含不同特殊區(qū)域的兩個(gè)場(chǎng)景，并將其劃分成子區(qū)域分配給每個(gè)機(jī)器人。從仿真結(jié)果可以看出，劃分得到的子區(qū)域可以保持工作量均衡，并避免分割特殊區(qū)域。

本文算法的優(yōu)勢(shì)在于可擴(kuò)展性強(qiáng)且計(jì)算量較低。一方面，本文算法可以擴(kuò)展到多種模式下的Morse分解，如圓形模式、方形模式等，最終獲得不同區(qū)域劃分結(jié)果。另一方面，傳統(tǒng)回溯法存在算法復(fù)雜度較高的問題，本文通過引入對(duì)特殊空間不分割的約束條件，增加算法回溯條件，降低了計(jì)算量。

1 區(qū)域劃分問題定義

假設(shè)任務(wù)區(qū)域A為一無障礙物的凸區(qū)域，該區(qū)域已被分解為NG個(gè)大小相同的單元格，用G={G1，G2，…，GNG}表示。單元格形狀須能無縫覆蓋區(qū)域，如六邊形、四邊形等，其大小由所搭載傳感器的范圍決定，下文以六邊形分解為例進(jìn)行描述。任務(wù)區(qū)域中存在NZ個(gè)特殊區(qū)域，記作Z={Z1，Z2，…，ZNZ}。本文主要針對(duì)特殊區(qū)域需要最少的機(jī)器人覆蓋的情況開展研究。

該覆蓋任務(wù)需要NR個(gè)同構(gòu)機(jī)器人協(xié)作完成，機(jī)器人用Rr表示，其中r=1，2，…，NR表示每個(gè)機(jī)器人的編號(hào)。另外，每個(gè)機(jī)器人的可用能量不同，用EC={EC1，EC2，…，ECNR}表示。ECr的范圍為0到1，其中0表示電量完全耗盡，1表示滿電。顯然，機(jī)器人的可用能量應(yīng)該與承擔(dān)的工作量成正比。因此，根據(jù)可用能量，預(yù)期分配給機(jī)器人Rr的單元格數(shù)NGr為

NGr=ECr∑NRr=1ECr·NG（1）

假設(shè)機(jī)器人的可用能量足以覆蓋相應(yīng)數(shù)量的單元格。此外，由于不是所有機(jī)器人都可以提前放置在合適的初始位置，所以本文不討論如何確定機(jī)器人的初始位置，而是假設(shè)所有機(jī)器人都從一個(gè)起始位置出發(fā)。因此，每個(gè)機(jī)器人分到的子區(qū)域應(yīng)該是連續(xù)的、靠近起始位置的，以減少到達(dá)任務(wù)區(qū)域過程中的能耗。圖1給出了本文中區(qū)域覆蓋任務(wù)的場(chǎng)景，包括離散任務(wù)區(qū)域、特殊區(qū)域、多個(gè)機(jī)器人及其起始位置。

2.2 改進(jìn)的回溯法

本節(jié)不直接求解最優(yōu)θ*，而是將求解θ*問題巧妙轉(zhuǎn)換成調(diào)整機(jī)器人順序的問題，按照預(yù)期分配給機(jī)器人Rr的單元格數(shù)NGr，沿著偏角從0°到90°的方向，劃分對(duì)應(yīng)數(shù)量的單元格。同時(shí)，通過調(diào)整機(jī)器人在該方向上的順序，控制分割線不落在特殊區(qū)域中。此次轉(zhuǎn)換可以最大限度保證工作量的均衡和特殊區(qū)域的完整，且不需要復(fù)雜的計(jì)算。

前文提到機(jī)器人的編號(hào)表示為{1，2，…，NR}，與可用能量的順序相對(duì)應(yīng)。機(jī)器人的順序記作S={S1，S2，…，SNR}，其中Si表示第i個(gè)分配的機(jī)器人的編號(hào)，例如S2=5，則機(jī)器人R5將是給定方向上的第2個(gè)被分配任務(wù)的機(jī)器人。以圖5所示場(chǎng)景為例，一個(gè)任務(wù)區(qū)域由3個(gè)機(jī)器人覆蓋，根據(jù)機(jī)器人能量可知其分別需要負(fù)責(zé)整個(gè)任務(wù)區(qū)域的{0.326，0.261，0.413}?？梢钥闯?，通過調(diào)整機(jī)器人的順序可以避免特殊區(qū)域的分割，并保證每個(gè)機(jī)器人分得最合適的工作量。

與用回溯法解決N-Queen問題［27］相類似，本節(jié)提出了改進(jìn)回溯法來調(diào)整機(jī)器人的順序。N-Queen問題是在N×N的棋盤上為N個(gè)Queen找到合適位置，使所有Queen在行、列和對(duì)角方向均無攻擊［28］?；厮莘ㄊ且环N深度優(yōu)先搜索策略［29］，通過嘗試每個(gè)位置，確定所有Queen可行的位置?；谏鲜鰝鹘y(tǒng)N-Queen問題，改進(jìn)的回溯法修改了位置選擇策略，忽略兩個(gè)Queen之間的對(duì)角攻擊，并加入了式（8）的約束。

算法1給出了改進(jìn)回溯法的偽代碼，其中核心步驟（第3～11行）是迭代選擇每個(gè)機(jī)器人的位置，直到確定所有機(jī)器人位置。其中，i和j分別記錄位置和機(jī)器人編號(hào)，tempS為回溯過程中記錄的機(jī)器人順序，tempf2和tempf1為程序執(zhí)行過程中的緩存f2和f1，nS記錄使f1取得最小值的tempS。在嘗試不同位置時(shí)，需要計(jì)算相應(yīng)的θ*，如果符合式（8），則繼續(xù)，若不符合，則換其他候選機(jī)器人。若所有候選機(jī)器人均不符合，則改變上一個(gè)位置上的機(jī)器人。反復(fù)嘗試，直到確定滿足條件的所有機(jī)器人位置。如果必須分割特殊區(qū)域，即沒有不分割特殊區(qū)域的解，則選擇具有最小f1的解決方案作為最優(yōu)解。

2.3 構(gòu)造連通子區(qū)域

上述過程可以將任務(wù)區(qū)域大致劃分為NR個(gè)子區(qū)域，但當(dāng)相鄰兩個(gè)θ*差值很小時(shí)，不能保證子區(qū)域的連續(xù)性，例如圖7中分配給機(jī)器人R3的單元格。為此，引入了一個(gè)附加操作來構(gòu)造連通區(qū)域。首先，計(jì)算每個(gè)子區(qū)域的主體區(qū)域Pr和其他區(qū)域Qr。然后，計(jì)算連接Pr和Qr兩區(qū)域的所有單元格，記作GConnected，并從中選擇已分配給Sr-1且對(duì)ASr-1連通性無影響的單元格，分配給Sr，直到不存在其他區(qū)域Qr。以圖6為例，GConnected單元格用藍(lán)色標(biāo)記，從中選擇左側(cè)藍(lán)色單元格分配給R3。對(duì)所有子區(qū)域進(jìn)行上述操作，可保證所有子區(qū)域的連續(xù)性。

2.4 復(fù)雜度分析

本文所提出的算法包含3個(gè)步驟，即用放射狀Morse分解定義空間結(jié)構(gòu)、用回溯法確定機(jī)器人順序和單元格重分配，下面對(duì)每個(gè)步驟的復(fù)雜度進(jìn)行分析。首先，第1個(gè)步驟為每個(gè)單元格計(jì)算對(duì)應(yīng)的偏角值，因此復(fù)雜度為O（NG）;其次，第2個(gè)步驟是通過回溯法求解最優(yōu)的機(jī)器人順序，此步驟復(fù)雜度與機(jī)器人個(gè)數(shù)NR有直接關(guān)系，為O（NR！）;最后，單元格重分配步驟中，僅作用于存在不連續(xù)區(qū)域的情況，循環(huán)次數(shù)較少，復(fù)雜度較低，可以忽略不計(jì)。綜合以上分析，本文提出算法的復(fù)雜度為O（NG+NR?。?。

3 仿真試驗(yàn)與分析

本章將通過兩個(gè)不同場(chǎng)景下的仿真，驗(yàn)證提出算法的性能。仿真結(jié)果給出了不同個(gè)數(shù)機(jī)器人的區(qū)域劃分結(jié)果及與兩個(gè)現(xiàn)有區(qū)域劃分方法的性能比較。結(jié)果表明，提出的算法能夠均衡多機(jī)器人的工作量，避免分割特殊區(qū)域。

在仿真中，假設(shè)有NR個(gè)水下機(jī)器人共同執(zhí)行水下搜救任務(wù)，覆蓋一個(gè)5 000 m×2 500 m的矩形海域。區(qū)域內(nèi)分布了一個(gè)或多個(gè)搜救專家劃定的目標(biāo)可能區(qū)域（即本文提到的“特殊區(qū)域”），用少數(shù)水下機(jī)器人覆蓋目標(biāo)可能區(qū)域有助于快速識(shí)別到目標(biāo)。現(xiàn)采用本文提出的算法確定每個(gè)水下機(jī)器人的作業(yè)區(qū)域。任務(wù)區(qū)域被分解成了半徑為100 m的正六邊形單元格。機(jī)器人的起始位置位于任務(wù)區(qū)域左下角。另外，任務(wù)區(qū)域中還設(shè)置了特殊區(qū)域。采用提出的區(qū)域劃分方法，整個(gè)任務(wù)區(qū)域?qū)⒈粍澐譃镹R個(gè)分區(qū)。另外，多機(jī)器人的可用能量隨機(jī)設(shè)定為EC={0.93，0.98，0.65，0.97，0.85，0.4，0.7，0.9，1，0.82}。若NRlt;10，則EC取前NR個(gè)元素。

在此背景下，設(shè)計(jì)了兩個(gè)不同場(chǎng)景中，并采用3～10個(gè)機(jī)器人執(zhí)行區(qū)域覆蓋任務(wù)。兩個(gè)場(chǎng)景是在相同的任務(wù)區(qū)域中分別設(shè)定了不同的特殊區(qū)域。場(chǎng)景1如圖5所示，只在矩形中心位置設(shè)置了一個(gè)特殊區(qū)域（橙色單元格）。場(chǎng)景2則是在相同的任務(wù)區(qū)域中設(shè)置了多個(gè)分散特殊區(qū)域。

為了驗(yàn)證算法的先進(jìn)性，將本文提出的方法與現(xiàn)有的兩種區(qū)域劃分方法進(jìn)行了比較，即廣義Voronoi圖（generalized Voronoi diagram，GVD）方法［14］和牛耕回溯（boustrophedon and backtracking，BoB）方法［15］，因?yàn)檫@兩種算法可用于不計(jì)算機(jī)器人初始位置的柵格區(qū)域劃分。GVD是一種最常用的區(qū)域劃分方法，已應(yīng)用于各種區(qū)域覆蓋領(lǐng)域。BoB方法是一種基于牛耕法覆蓋方法的區(qū)域劃分方法，與本文算法類似，亦考慮了多機(jī)器人的工作量均衡。

本文方法、GVD方法和BoB方法的對(duì)比包括兩個(gè)方面：保持特殊區(qū)域不被分割和工作量均衡，與目標(biāo)函數(shù)f1和f2相對(duì)應(yīng)。f1越小，即被分割的特殊區(qū)域越少。f2越小，即實(shí)際分配的單元格數(shù)與預(yù)期分配的單元格數(shù)之間的平方差越小，工作量越均衡。

3.1 場(chǎng)景1（一個(gè)特殊區(qū)域）

本節(jié)將對(duì)圖4所示的場(chǎng)景進(jìn)行區(qū)域劃分，其中設(shè)有一個(gè)特殊區(qū)域。表1列出了使用本文方法進(jìn)行區(qū)域劃分的數(shù)值結(jié)果，包括最終機(jī)器人順序S、分割線角度θ*，其中機(jī)器人數(shù)量為3～10個(gè)。根據(jù)表1的數(shù)值結(jié)果，圖7給出了對(duì)應(yīng)的區(qū)域劃分結(jié)果，特殊區(qū)域中的單元格用紅星標(biāo)記，分配給不同機(jī)器人的子區(qū)域用不同顏色填充?？梢钥闯?，NR取3，5，6，8時(shí)，特殊區(qū)域保持完整;在NR取4，7，9時(shí)，特殊區(qū)域僅被分為了兩部分，在NR取10時(shí)，特殊區(qū)域被分為了三部分。由此得出，該方法可以生成連續(xù)的子區(qū)域并保持較少的特殊區(qū)域劃分。

圖8給出了本文方法、GVD方法和BoB方法的f1值的比較結(jié)果?？梢钥闯?，本文方法（藍(lán)色線）的f1值整體穩(wěn)定，最多有兩個(gè)被分割出的特殊區(qū)域，且機(jī)器人的增多不會(huì)造成更多的特殊區(qū)域被分割。而BoB方法（黃色線）存在有3個(gè)分割出的特殊區(qū)域的情況，GVD（紅色線）更會(huì)隨機(jī)器人的增多而產(chǎn)生更多的被分割的特殊區(qū)域。因此，本文方法可以更好地保護(hù)區(qū)域不被分割。

圖9給出了本文方法與GVD方法、BoB方法的f2值比較結(jié)果，用來衡量分配給每個(gè)機(jī)器人的預(yù)期單元格數(shù)和實(shí)際分得的單元格數(shù)之間的差異。本文方法的f2值保持穩(wěn)定且低于另外兩種方法，只隨著機(jī)器人數(shù)量的增多有少量增長。而由于GVD方法并未考慮多機(jī)器人的工作量均衡問題，因此GVD方法會(huì)造成分配給機(jī)器人的工作量不合理。而本文方法和BoB均對(duì)多機(jī)器人可用能量不同的情況采取了措施，因此兩者結(jié)果相近，但本文方法比BoB方法具有更好的工作量均衡的能力。

綜上所述，在場(chǎng)景1中，機(jī)器人數(shù)量取3～10時(shí)本文方法都具有更好的保持特殊區(qū)域完整和合理分配工作量的能力。

3.2 場(chǎng)景2（多個(gè)特殊區(qū)域）

本節(jié)在一個(gè)具有多個(gè)分散特殊區(qū)域的任務(wù)場(chǎng)景中驗(yàn)證算法的性能，并給出了該任務(wù)區(qū)域劃分給不同數(shù)量機(jī)器人的結(jié)果，以及本文方法與GVD方法、BoB方法的性能比較結(jié)果。該任務(wù)場(chǎng)景如圖10所示，包含了4個(gè)隨意設(shè)定的特殊區(qū)域，藍(lán)色虛線表示特殊區(qū)域的邊界。

表2總結(jié)了在場(chǎng)景2中應(yīng)用本文方法的所有數(shù)值結(jié)果，相應(yīng)的區(qū)域劃分結(jié)果如圖11所示，其中特殊區(qū)域中的單元格用黑色五角星標(biāo)記，分配給不同機(jī)器人的單元格用不同顏色表示。從圖11中可以看出，分配給不同機(jī)器人的子區(qū)域是連續(xù)的，并且離起始位置的單元格較近。當(dāng)NR取3～7時(shí)，所有特殊區(qū)域沒有被分割，NR取8～10時(shí)，只有一個(gè)特殊區(qū)域被分割成了兩部分。

圖12給出了本文方法、GVD方法和BoB方法不分割特殊區(qū)域能力比較，即f1的對(duì)比結(jié)果?？梢钥闯?，本文方法相對(duì)穩(wěn)定，大部分情況沒有特殊區(qū)域被分割。而BoB方法和GVD方法則性能較差，被分割的特殊區(qū)域會(huì)隨機(jī)器人個(gè)數(shù)的增多而增加。因此，與其他方法相比，本文方法更有利于保證特殊區(qū)域不被分割。

場(chǎng)景2中，本文方法與GVD方法和BoB方法的f2值的比較如圖13所示。整體來看，所提出的方法的f2值最低且相對(duì)穩(wěn)定，與BoB方法的結(jié)果相差不多，因?yàn)槎叨伎紤]到了工作量均衡的問題。而GVD方法并沒有對(duì)工作量均衡采取措施，因此其f2值偏高且呈上升趨勢(shì)。因此，本文方法在場(chǎng)景2中也可以分配合適的工作量給多機(jī)器人。

通過分析上述結(jié)果，該方法生成的子區(qū)域具有以下特點(diǎn)：① 很少分割特殊區(qū)域;② 分配給每個(gè)機(jī)器人的網(wǎng)格數(shù)量接近預(yù)期數(shù)量;③ 劃分的子區(qū)域是連續(xù)的，接近機(jī)器人起始位置。因此，該方法在避免特殊區(qū)域被分割和保持良好的工作量均衡方面具有優(yōu)勢(shì)，能滿足第2節(jié)中區(qū)域劃分問題的需求。

4 結(jié) 論

針對(duì)多機(jī)器人區(qū)域覆蓋任務(wù)中存在特殊區(qū)域的情景，設(shè)計(jì)了一種區(qū)域劃分方法，將任務(wù)區(qū)域合理分配給多機(jī)器人，并期望使用更少的機(jī)器人覆蓋特殊區(qū)域。不同場(chǎng)景下的仿真結(jié)果表明，該方法可以避免特殊區(qū)域的分割，保持多機(jī)器人的工作量均衡。借助Morse分解的框架，該方法可以擴(kuò)展到多種模式的Morse分解種，最終形成不同的區(qū)域劃分結(jié)果。另外，提出的方法率先將特殊區(qū)域的概念引入?yún)^(qū)域劃分領(lǐng)域，對(duì)于采用多機(jī)器人進(jìn)行對(duì)抗性覆蓋、搜救等含有特殊區(qū)域的區(qū)域覆蓋任務(wù)中具有重要意義。

參考文獻(xiàn)

［1］ 李冠男， 董凌艷， 徐紅麗， 等. 群機(jī)器人區(qū)域覆蓋方法研究［J］. 機(jī)器人， 2017， 39（5）： 670-679.

LI G N， DONG L Y， XU H L， et al. Research on region coverage approach with swarm robots［J］. Robot， 2017， 39（5）： 670-679.

［2］ YAO P， QIU L Y， QI J P， et al. AUV path planning for coverage search of static target in ocean environment［J］. Ocean Engineering， 2021， 241： 110050.

［3］ CHO S W， PARK H J， LEE H， et al. Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations［J］. Computers amp; Industrial Engineering， 2021， 161： 107612.

［4］ AI B， JIA M X， XU H W， et al. Coverage path planning for maritime search and rescue using reinforcement learning［J］. Ocean Engineering， 2021， 241： 110098.

［5］ WU C M， DAI C K， GONG X X， et al. Energy-efficient coverage path planning for general terrain surfaces［J］. IEEE Robotics and Automation Letters， 2019， 4（3）： 2584-2591.

［6］ POPOVICM， VIDAL-CALLEJA T， HITZ G， et al. An informative path planning framework for UAV-based terrain monitoring［J］. Autonomous Robots， 2020， 44（6）： 889-911.

［7］ KRISHNA L A， ELARA M R， RAMALINGAM B， et al. Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robot［J］. Automation in Construction， 2020， 112： 103078.

［8］ VAZQUEZ-CARMONA E V， VASQUEZ-GOMEZ J I， HERRERA-LOZADA J C， et al. Coverage path planning for spraying drones［J］. Computers amp; Industrial Engineering， 2022， 168： 108125.

［9］ 王偉， 張彥斐， 宮金良. 基于蟻群-BFS算法的復(fù)雜環(huán)境下農(nóng)業(yè)機(jī)器人全區(qū)域覆蓋研究［J］. 華南農(nóng)業(yè)大學(xué)學(xué)報(bào)， 2019， 42（3）： 119-125.

WANG W， ZHANG Y F， GONG J L. Study on the whole area coverage of agricultural robot in complex environment based on ant colony-BFS algorithm［J］. Journal of South China Agricultural University， 2019， 42（3）： 119-125.

［10］ NAIR V G， GURUPRASAD K R. MR-SimExCoverage： multi-robot simultaneous exploration and coverage［J］. Computers amp; Electrical Engineering， 2020， 85： 106680.

［11］ ALMADHOUN R， TAHA T， SENEVIRATNE L， et al. A survey on multi-robot coverage path planning for model reconstruction and mapping［J］. SN Applied Sciences， 2019， 1（8）： 847.

［12］ 李娟， 張秉健， 楊莉娟， 等. 未知環(huán)境下基于感知自適應(yīng)的多AUV目標(biāo)搜索算法［J］. 系統(tǒng)工程與電子技術(shù)， 2018， 40（8）： 1839-1845.

LI J， ZHANG B J， YANG L J， et al. Multi-AUV target search algorithm with cognitive-based adaptive optimization in unknown environment［J］. Systems Engineering and Electronics， 2018， 40（8）： 1839-1845.

［13］ HASSAN M， LIU D. Simultaneous area partitioning and allocation for complete coverage by multiple autonomous industrial robots［J］. Autonomous Robots， 2017， 41（8）： 1609-1628.

［14］ NAIR V G， GURUPRASAD K R. GM-VPC： an algorithm for multi-robot coverage of known spaces using generalized voronoi partition［J］. Robotica， 2020， 38（5）： 845-860.

［15］ VIET H H， DANG V， CHOI S， et al. BoB： an online coverage approach for multi-robot systems［J］. Applied Intelligence， 2015， 42（2）： 157-173.

［16］ KAPOUTSIS A C， CHATZICHRISTOFIS S A， KOSMATOPOULOS E B. DARP： divide areas algorithm for optimal multi-robot coverage path planning［J］. Journal of Intelligent amp; Robotic Systems， 2017， 86（3/4）： 663-680.

［17］ BALAMPANIS F， MAZA I， OLLERO A. Area partition for coastal regions with multiple UAS［J］. Journal of Intelligent amp; Robotic Systems， 2017， 88（2/4）： 751-766.

［18］ COOMBES M， FLETCHER T， CHEN W， et al. Optimal polygon decomposition for UAV survey coverage path planning in wind［J］. Sensors， 2018， 18（7）： 2132.

［19］ KIM J. Multi-robot global sonar survey in the presence of strong currents［J］. Ocean Engineering， 2019， 188： 106316.

［20］ DONG W， LIU S S， DING Y， et al. An artificially weighted spanning tree coverage algorithm for decentralized flying robots［J］. IEEE Trans.on Automation Science and Engineering， 2020， 17（4）： 1689-1698.

［21］ GUASTELLA D C， CANTELLI L， GIAMMELLO G， et al. Complete coverage path planning for aerial vehicle flocks deployed in outdoor environments［J］. Computers amp; Electrical Engineering， 2019， 75： 189-201.

［22］ SUN R C， TANG C H， ZHENG J Y， et al. Multi-robot path planning for complete coverage with genetic algorithms［M］. Cham： Springer International Publishing， 2019： 349-361.

［23］ YEHOSHUA R， AGMON N， KAMINKA G A. Robotic adversarial coverage of known environments［J］. The International Journal of Robotics Research， 2016， 35（12）： 1419-1444.

［24］ 魏瀟龍， 姚登凱， 谷志鳴， 等. 基于分割法的無人機(jī)路徑規(guī)劃研究［J］. 計(jì)算機(jī)仿真， 2016， 33（1）： 90-94.

WEI X L， YAO D K， GU Z M， et al. UAV path planning method based on split method［J］. Computer Simulation， 2016， 33（1）： 90-94.

［25］ ACAR E U， CHOSET H， RIZZI A A， et al. Morse decompositions for coverage tasks［J］. The International journal of robotics research， 2002， 21（4）： 331-344.

［26］ CAI C， CHEN J F， YAN Q L， et al. A multi-robot coverage path planning method for maritime search and rescue using multiple AUVs［J］. Remote Sensing， 2023， 15（1）： 93.

［27］ SERKAN G， VERONICA B， SALEH A. N-Queens solving algorithm by sets and backtracking［C］∥Proc.of the Southeast Conference， 2016.

［28］ GLOCK S， MUNHA C D， SUDAKOV B. The N-Queens completion problem［J］. Research in the Mathematical Sciences， 2022， 9： 41.

［29］ 沈夢(mèng)珠. 基于回溯法的掃地機(jī)器人全區(qū)域覆蓋規(guī)劃算法研究［D］. 武漢： 華中科技大學(xué)， 2018.

SHEN M Z. Research on full coverage algorithm of sweeping robot path based on backtracking［D］. Wuhan： Huazhong University of Science amp; Technology， 2018.

作者簡介

蔡 暢（1993—），女，博士研究生，主要研究方向?yàn)锳UV集群、區(qū)域覆蓋、路徑規(guī)劃。

陳建峰（1972—），男，教授，博士，主要研究方向?yàn)锳UV控制、AUV結(jié)構(gòu)。

閆青麗（1990—），女，講師，博士，主要研究方向?yàn)榉植际讲季帧⒙曉炊ㄎ弧?/p>

劉 芬（1982—），女，副教授，博士，主要研究方向?yàn)槿斯ぶ悄堋?/p>