Large Scale Aerial Multi-Robot Coverage Path Planning 閲讀筆記（一）

Large Scale Aerial Multi-Robot Coverage Path Planning 閲讀筆記（一）

0. 論文説明

這篇論文的英文題目是 Large Scale Aerial Multi-Robot Coverage Path Planning，作者是Kunal Shah，這篇論文利用了一系列的算法解決了多無人機覆蓋的路徑規劃問題，涉及到的知識相對來説比較難，所以寫下了這篇筆記。

1. 論文摘要

這篇論文提供了一種多機器人路徑規劃方法，可以在任意區域內實現覆蓋路徑規劃。通過分而治之的方案擴展了之前提出的方法——用於無人機網絡人口計數的路徑優化（POPCORN），這個方案稱為分割和連接瓦片（SALT），它大大減少了路線規劃所需的時間。這些POPCORN實例可以並行計算，並以可擴展的方式與SALT結合，以在非常大的區域內生成覆蓋路徑。

為了展示這個算法的能力，我們用一組無人機實施了我們的規劃算法，在南極洲羅斯島的科羅齊爾角阿德利企鵝rookery進行了多次航空野生動物攝影調查，這是世界上最大的阿德利企鵝棲息地之一。這個棲息地包含超過30萬對築巢企鵝，跨度超過2公里，大約3小時就完成了調查。相比之下，之前由人類駕駛的單架無人機對同一棲息地的調查需要超過2天才能完成。我們還在加利福尼亞州莫諾湖的幾個小島上部署了我們的調查系統，以調查加利福尼亞海鷗群，以及在加利福尼亞州馬林縣的一個2000英畝的牧場。我們將這個調查路徑規劃工具作為一個名為wadl的開源軟件包提供。同時，作者也爲這篇文章製作了視頻：

2. 前置知識

2.1 覆蓋路徑規劃（CPP）

Survey Region with Grid and Home Sites
覆蓋路徑規劃（Covering Path Planning， CPP）是機器人學和運籌學中的一個重要研究領域，主要探討如何設計一條路徑，使機器人或移動設備能夠完全覆蓋特定區域，同時最小化重複覆蓋和總行走距離。這個問題在諸多實際應用中扮演著關鍵角色，如掃地機器人清潔房間、農業機器人噴灑農藥或收割作物、無人機進行地形測繪或搜索救援，以及自動割草機修剪草坪等。

CPP的核心目標包括確保目標區域的全面覆蓋、最大化效率以減少重複覆蓋、優化路徑以尋找最短覆蓋路徑，以及在存在障礙物的環境中進行有效規劃。為了解決CPP問題，研究人員開發了多種方法，如將複雜區域分解為簡單子區域的分解法、將區域劃分為網格後在網格上規劃路徑的網格法、使用預定義移動模式（如螺旋或之字形）的基於模式的方法，以及在保證完全覆蓋前提下引入隨機性的隨機算法。

值得注意的是，CPP屬於NP難問題，這意味著對於大規模問題，找到最優解在計算上可能是不切實際的。因此，在實際應用中，研究者們經常採用啟發式算法來尋找接近最優的解決方案。這種平衡between理論最優和實際可行的方法，使得CPP在各種場景中都能得到廣泛應用，推動了自動化技術在清潔、農業、測繪等領域的進步。

2.2 旅行商問題（TSP）

Survey Region with Grid and Home Sites
旅行商問題（Traveling Salesman Problem， TSP）是運籌學和理論計算機科學中一個經典的組合優化問題。這個問題的核心在於：一個旅行商需要訪問多個城市，每個城市只訪問一次，最後回到出發的城市，如何找出一條總距離最短的路線。

TSP的描述看似簡單，但實際上是一個極其複雜的數學問題。它屬於NP-難問題，這意味著當城市數量增加時，找到最優解的計算複雜度會呈指數級增長。對於小規模的問題（例如10-15個城市），可以通過暴力搜索所有可能的路徑來找到最優解。但當城市數量增加到更大規模時，精確解法在實際應用中變得不可行。

為了解決大規模TSP，研究者們開發了多種近似算法和啟發式方法。其中包括貪心算法、遺傳算法、蟻群算法、模擬退火等。這些方法雖然不能保證找到最優解，但能在合理的時間內找到較好的近似解。

TSP不僅在理論研究中佔有重要地位，在實際應用中也有廣泛用途。例如在物流配送路線規劃、電路板鑽孔、DNA測序等領域都可以見到TSP的應用。此外，許多其他組合優化問題可以轉化為TSP的變體，使得對TSP的研究具有更廣泛的意義。

儘管經過數十年的研究，TSP仍然是計算機科學和數學領域的一個開放問題。研究者們持續探索新的算法和解決方案，以期在更大規模的問題上取得突破。同時，TSP也常被用作測試新優化算法效能的基準問題。

TSP的研究不僅推動了組合優化領域的發展，也為其他領域如人工智能、運籌學等提供了寶貴的洞見和方法論。它體現了簡單問題描述背後可能隱藏的巨大複雜性，也展示了如何通過創新的思維和算法來應對看似不可能解決的問題。

2.3 布爾可滿足性問題(Boolean Satisfiability Problem, SAT)

布爾可滿足性問題是計算機科學中的一個基本問題。

SAT問題定義

給定一個由布爾變量組成的布爾表達式,判斷是否存在一組變量賦值,使得整個表達式的值為真。其數學表達式如下:

變量

令 X=x1,x2,...,xnX = {x_1, x_2, ..., x_n} 是一組布爾變量,每個 xi∈0,1x_i \in {0, 1}

文字(Literal)

一個文字是一個變量或其否定,例如 xix_i 或 ¬xi\neg x_i

子句(Clause)

子句是文字的析取(OR),表示為:

Cj=(lj1∨lj2∨...∨ljk)C_j = (l_{j1} \vee l_{j2} \vee ... \vee l_{jk})

其中 ljil_{ji} 是一個文字

合取範式(Conjunctive Normal Form, CNF)

SAT問題通常表示為CNF,即子句的合取(AND):

F=C1∧C2∧...∧CmF = C_1 \wedge C_2 \wedge ... \wedge C_m

SAT問題

找到一個賦值 α:X→0,1\alpha: X \rightarrow {0, 1},使得 F(α)=1F(\alpha) = 1

例子

考慮布爾表達式:

(x1∨¬x2)∧(¬x1∨x3)∧(x2∨¬x3)(x_1 \vee \neg x_2) \wedge (\neg x_1 \vee x_3) \wedge (x_2 \vee \neg x_3)

這個表達式有三個子句:

C1=(x1∨¬x2)C_1 = (x_1 \vee \neg x_2)

C2=(¬x1∨x3)C_2 = (\neg x_1 \vee x_3)

C3=(x2∨¬x3)C_3 = (x_2 \vee \neg x_3)

SAT求解器的目標是找到 x1x_1, x2x_2, 和 x3x_3 的值,使得整個表達式為真。

3. 構思

3.1 前置假設

  1. 作者把覆蓋區域映射到一個網格圖 G(V,E)G(V,E)，每個節點v表示物理空間中的一個點，可以映射到二維笛卡爾坐標系。每條邊 e=(vi,vj)e = (v_i, v_j) 表示機器人可以從節點 viv_i 移動到 vjv_j。如下圖所示：
Survey Region with Grid and Home Sites
西克羅齊爾角阿德利企鵝殖民地的衛星圖像，包括調查的地理位置和三個家園(Hi)位置(左圖)。通過覆蓋網格並與地理位置(中心)相交來找到覆蓋網格。在調查過程中拍攝的圖像被拼接在一起，用於種群分析;還可以看到築巢的阿德利企鵝的個體圖像和擴展圖像(右)

  1. 假設所有的覆蓋圖都是網格圖，且是連通圖(但不一定完全連通)。

  2. 規劃算法的主要目標是將節點分配到 KK 個集合 V1,...,VKV_1, ..., V_K，形成K條路徑 p1,...,pKp_1, ..., p_K，使得所有節點至少被訪問一次。

  3. 覆蓋網格的間隔是由其他要求決定的，而本文主要研究的是如何在給定的覆蓋網格上規劃多機器人的路徑。

3.2 模型構思

由於飛機不可能在任意位置起飛，所以作者首先在文中先列出了幾個起飛點（文中稱爲家），并且要求從某一起飛點起飛的飛機在執行完任務以後也要回到它所在的家。每条路径 pkp_k 都可以由一个起始位置 Hk∈HH_k \in H 和一组节点 VkV_k 来描述:

pk=(Hk,Vk={v1k,...,vnk}) 其中 vik∈V 且 (vik,vi+1k)∈Ep_k = (H_k, V_k = \{v^k_1, ..., v^k_n\}) \text{ 其中 } v^k_i \in V \text{ 且 } (v^k_i, v^k_{i+1}) \in E

接著，由於受限于飛行效率和電池容量，要考慮最大化減少飛行時間，所以作者在文中采用了閉環的飛行路徑，即飛機在偵察路徑中的終點就是飛機的起始偵察位置，數學上表達為 v1k=vnkv_1^k=v_n^k，如圖所示：

閉環路圖展示，其中淺藍色為飛機偵察的起點和終點

每條路徑 pkp_k 的長度 sks_k 可以被描述為:

sk=∑i=1n∥L(vi+1)−L(vi)∥s_k = \sum_{i=1}^{n} \|L(v_{i+1}) - L(v_i)\|

其中 nn 是路徑 pkp_k 上節點的數量， L(vi)L(v_i) 表示節點 viv_i 的坐標位置。

由于这些路径形成了一个循环，我们可以移动调查路径的索引，并“附加”主点：

hk=arg⁡min⁡Hk∈Hmin⁡v∈Vk∥Hk−L(v)∥h_k = \arg\min_{H_k \in H} \min_{v \in V_k} \|H_k - L(v)\|

現在，我們可以給出總體的飛行時間公式為

tk=2hkvh+skvs≤Tmax⁡t_k = 2 \frac{h_k}{v_h} + \frac{s_k}{v_s} \leq T_{\max}

其中 hkvh\frac{h_k}{v_h} 為飛機從起飛點到達偵察點所花費的時間，而 skvs\frac{s_k}{v_s} 則表示爲飛機在偵察的時候所花費的時間，其要小於飛機的最大續航時間。

最後給出總體模型：

min⁡∑k=1Ktks.t.tk<Tmax⁡⋃k=1KVk=V\begin{align*} \min \sum_{k=1}^{K} t_k \\ \text{s.t.} \quad t_k &< T_{\max} \\ \bigcup_{k=1}^{K} V_k &= V \end{align*}

如果要考慮達到最經濟的情況，還需要考慮到減少飛機起飛的次數，這樣的話模型可以被描述爲：

min⁡ Ks.t.tk<Tmax⁡⋃k=1KVk=V\begin{align*} \min \ K \\ \text{s.t.} \quad t_k &< T_{\max} \\ \bigcup_{k=1}^{K} V_k &= V \end{align*}

其中KK為飛機的飛行次數。

4. 算法

前人提出的單個智能體和多個智能體規劃方法並沒有總是考慮到航程或電池容量的限制。一些商業方法被設計為可以讓無人機在路線中途返回基地換電池，然後再返回上次停止的位置繼續任務。在这篇文章中，作者設計的規劃器考慮到這些航程限制，並將地理約束直接編碼到規劃過程中。目標是開發一個可以為任意大小的區域和任意數量的智能體生成覆蓋路徑的工具。我們輸出一組路徑，可以由一個智能體依次完成，也可以被多個智能體併行執行。

由於文中的規劃器基於網格，隨著區域規模的增大，網格點數量會成比例增加，導致可能路徑呈指數級增長。故文中採用分治法，將覆蓋圖劃分為一組較小的子圖，類似於許多覆蓋規劃器使用的蜂窩分解方法。作者使用 SAT 方法找到每個子網格的循環路徑，並借鑒圖論中的循環基性質，以保持整體路徑的循環性質，大幅減少了與傳統方法相比的回溯次數。我們提出了兩種啟發式方法來解決最小時間問題，它們都共享相同的初始分割步驟，其中一種專門針對解決時間最小化問題。我們的方法首先在所需的地理圍欄上覆蓋一個網格，然後將其分割為較小的網格區域(“瓦片”)。使用基於 SAT 的方法，我們找到每個瓦片的閉合(循環)路徑。在找到這些路徑後，我們在尊重無人機飛行時間限制的情況下將它們連接起來，找到最終的可行路由。

4.1 分割算法

分而治之: 智能分割策略

這個算法的第一步是「分割」(Split)。想像一下你要測繪一片廣闊的農田或複雜的城市景觀。直接規劃整個區域的路徑會是一個令人生畏的任務。因此,我們採用了一種聰明的方法:將整個區域分割成更小的矩形瓦片。

每個瓦片就像一塊拼圖,包含了原始覆蓋圖的一小部分。這種分割不僅簡化了問題,還為並行處理鋪平了道路。通過調整瓦片的大小,我們可以在計算複雜度和解的質量之間找到完美的平衡點。

精確覆蓋: 從相機到地面

在規劃路徑之前,我們需要確保每張照片都能精確覆蓋地面。算法會考慮無人機的飛行高度和相機參數,精確計算出每張圖片在地面上的覆蓋範圍。通過稍微擴大計劃區域的邊界,我們確保即使是邊緣地帶也不會遺漏。

化繁為簡: SAT問題的魔力

現在到了最激動人心的部分:如何在每個瓦片內規劃路徑?這裡,我們將問題巧妙地轉化為一個SAT(布爾可滿足性)問題。

想像一個巨大的網格,其中每個交叉點代表無人機可能的位置。我們使用布爾變量來表示:「在時刻t,無人機是否在位置v?」通過設置一系列邏輯約束,我們確保:

  • 無人機在每個時刻只能在一個位置。
  • 它只能在相連的點之間移動。
  • 每個點都必須被訪問至少一次。
  • 路徑是一個封閉的回路。

這種方法將複雜的路徑規劃問題轉化為一個可以用高效SAT求解器處理的問題。

優化與效率: 走捷徑

為了進一步提高效率,算法採用了幾個聰明的技巧:

  • 通過逐步增加或減少路徑長度來找到最優解
  • 對於內部結構相似的瓦片,重複使用已經計算出的解
  • 移除不可能出現的狀態,減少計算量

通過這些優化,即使是在普通筆記本電腦上,也能在實地快速生成高質量的飛行路徑。

4.2 鏈接算法

瓦片路径规划

首先，整個測繪區域被分割成多個小瓦片。對每個瓦片，算法都會規劃一條完整的覆蓋路徑，確保瓦片內的每個點都能被訪問到。這是整個過程的基礎，為後續的優化鋪平了道路。

瓦片连接

接下來，算法會嘗試連接相鄰的瓦片。如果兩個相鄰瓦片共享平行邊，它們就可以被巧妙地連接成一個更大的循環路徑。這種連接方法不僅減少了無人機的回溯，還顯著提高了整體效率。

成本计算

為了進行更精確的優化，算法會為每個瓦片計算兩種成本：基本成本(完成瓦片內測繪所需的時間)和轉移成本(從起始點到達瓦片所需的時間)，這些成本將在後續的路徑規劃中起到關鍵作用。

构建Path Graph

算法創建了一個稱為“Path Graph”的加權有向圖，其中包含了所有瓦片和一個代表起始點的抽象節點。通過精心設計邊的權重，這個圖捕捉了整個測繪任務的結構和約束。

路径表示和图分割

有了Path Graph，整個測繪任務就轉化為了一個圖分割問題。算法的目標是將這個圖劃分為多個樹子圖，每個子圖代表一條完整的飛行路徑。

為了解決這個問題，算法提供了兩種方法:一種是快速的廣度優先搜索，另一種是可以得到全局最優解的混合整數線性規劃(MILP)。儘管MILP的計算複雜度較高，但它能夠最小化飛行次數，在某些場景下可能更為理想。

這種方法的優雅之處在於，它不僅能夠在保證完全覆蓋的同時最小化飛行次數和總飛行時間，而且具有良好的可擴展性。由於Path Graph是一個有向無環圖(DAG)，MILP中的約束數量只會隨節點數線性增長，這使得算法能夠處理大規模的測繪任務。

在無人機技術日益普及的今天，這種算法無疑將推動測繪和勘察技術向前邁進一大步。它不僅提高了效率，降低了成本，還為更複雜、更大規模的無人機應用鋪平了道路。

4.3 Breadth-First Partitioning求解方法

Breadth-First Partitioning 是一種生成可行分割的方法。主要步驟如下:

  1. 首先按節點的傳輸成本(transit cost)降序排列路徑圖中的所有節點。
  2. 然後使用算法1來提取路徑。這個算法會選擇最遠的節點，並進行廣度優先搜索(breadth-first expansion)，添加新節點到分割中，並檢查總路徑是否小於指定限制。
  3. cost()方法首先將一個家庭節點附加到最近(最便宜)的節點上，然後使用邊權重計算基於Tree中瓷磚的總路徑成本。

該算法的最壞情況複雜度為 O(nd)O(nd)，其中 nn 是路徑圖中的節點數，dd 是最大邊度。但由於采用了矩形分割，實際中最大邊度大多是4或6。

4.4 Mixed-Integer Linear Programming（MILP）

MILP分區是另一種生成可行分區的方法。它可以為給定的K值產生一組路徑。我們可以迭代地降低K來最小化給定調查所需的總飛行次數。

由於路徑圖 QQ 是一個有向無環圖(DAG)，我們可以找到以家庭節點為根的有向樹子圖。每個子圖都是 QQ 的一個分區，包含一組節點(對應於瓷磚)，使得所有分區的聯集包含所有節點，因此沒有忽略任何瓷磚。

每個子圖被限制為只包含一個家庭邊，可以有任意數量的基本邊。為了進行這種分區，我們可以求解相應的優化問題:

  1. 定義二進制變量 xx 和 zz，分別表示節點和邊的分區分配。
  2. 目標函數是最小化所有邊的總權重(即調查時間)。
  3. 添加一系列約束條件:
    • 每個節點被分配到且只分配到一個分區(除了家庭節點)。
    • 每條邊至少出現在一個分區中。
    • 每個分區恰好有一條來自家庭節點的邊。
    • 每個分區的總邊權重小於無人機的飛行時間限制。
    • 如果一條邊在某個分區，則該分區必須同時包含該邊的起始和終止節點。
    • 每個分區都是一個有向樹。
  4. 通過迭代求解得到最小的飛行次數 KK。

與廣度優先分區方法相比，MILP分區在相同問題實例下產生的飛行次數更少。是此實例可能的最小飛行次數，因為MILP方法能夠迭代地減小允許的路徑數。

5. 算例分析（後面補上）

6. 方法總結

6.1 POPCORN

POPCORN (Path Optimization for Population Counting with Overhead Robotic Networks) 方法的主要流程如下：

問題建模：

  • 將覆蓋區域表示為一個圖 G(V, E),其中節點 V 代表需要覆蓋的點,邊 E 表示可以直接移動的路徑。
  • 定義起始點（家）H,可以有多個起始點。

SAT 問題轉化：

  • 將路徑規劃問題轉化為布爾可滿足性(SAT)問題。
  • 使用一種"one-hot"編碼方式,為每個時間步驟、每個節點創建布爾變量。

變量定義：

對於每個時間步 tt,每個節點 vv,定義布爾變量 xv,tx_{v,t},其中xv,t=1x_{v,t} = 1 表示在時間 tt 訪問節點 vv。

約束條件定義：

  • 覆蓋約束:確保每個節點至少被訪問一次。

⋁t=1Txv,t=1,∀v∈V\bigvee_{t=1}^T x_{v,t} = 1, \forall v \in V

  • 連續性約束:確保路徑是連續的,只能在相鄰節點間移動。

xu,t∧xv,t+1⇒(u,v)∈E,∀tx_{u,t} \wedge x_{v,t+1} \Rightarrow (u,v) \in E, \forall t

  • 起始點約束:路徑必須從指定的起始點開始和結束。

xH,1=1,xH,T=1x_{H,1} = 1, x_{H,T} = 1

  • 其他實際約束:如最大路徑長度（基於電池壽命）等。

目標函數：

  • 最小化總路徑長度或總飛行時間。

SAT 求解：

  • 使用現成的SAT求解器（如Z3）來解決轉化後的SAT問題。

路徑提取：

從SAT求解器的結果中提取實際的路徑。

多機器人擴展：

  • POPCORN可以擴展到多機器人場景,為每個機器人生成單獨的路徑。

迭代優化：

  • 如果需要,可以通過調整約束條件或目標函數進行多次迭代,以獲得更優的結果。

POPCORN方法的一個關鍵特點是允許重複訪問節點,這與傳統的旅行商問題（TSP）解法不同。這種靈活性使得POPCORN能夠處理更廣泛的覆蓋路徑規劃問題。

6.2 SALT

SALT (Split And Link Tiles) 方法是爲了解決POPCORN在大規模問題上的可擴展性問題而提出的。以下是SALT方法的主要流程：

問題分解：

  • 將大的覆蓋區域分割成較小的子區域,稱為"瓦片"(tiles)。
  • 每個瓦片的大小應該適合POPCORN方法能夠在合理時間內求解。

子問題求解：

  • 對每個瓦片使用POPCORN方法獨立求解覆蓋路徑。
  • 這些子問題可以並行計算,大大提高效率。

路徑圖構建：

  • 基於每個瓦片的解,構建一個新的圖,稱為"路徑圖"(pathgraph)。
  • 在路徑圖中,每個節點代表一個瓦片的入口或出口點。

圖分割：

對路徑圖進行分割,使用以下兩種方法之一:

  • 廣度優先搜索(BFS)方法:快速且保證找到解,但可能不是最優的。
  • 混合整數線性規劃(MILP)方法:可以找到最小數量的路徑,但求解速度較慢。

路徑連接：

  • 根據圖分割的結果,將各個瓦片內的路徑連接起來,形成完整的覆蓋路徑。

多機器人任務分配：

  • 如果有多個機器人,將連接後的路徑分配給不同的機器人。

優化調整：

  • 可能需要進行一些局部優化,以消除可能的冗餘或改善路徑質量。

最終路徑生成：

  • 輸出每個機器人的完整覆蓋路徑。

SALT方法的主要優勢在於：

  • 可擴展性: 通過分而治之的策略,可以處理非常大的區域。
  • 計算效率: 子問題可以並行求解,大大減少總計算時間。
  • 靈活性: 可以根據具體需求選擇不同的圖分割方法。
  • 實用性: 能夠快速生成可行的多機器人覆蓋路徑,適合現場實時規劃。

總的來說,SALT方法通過巧妙地結合POPCORN的局部優化能力和分治策略,實現了大規模多機器人覆蓋路徑規劃問題的高效求解。