1）摘要

????????自主探索是無人機 （UAV） 各種應用的基本問題。最近，基于 LiDAR 的探索因其能夠生成大規模環境的高精度點云地圖而受到廣泛關注。雖然點云本身就為導航提供了信息，但許多現有的勘探方法仍然依賴于額外的（通常是昂貴的）環境表示。這種依賴源于兩個主要原因：需要邊界檢測或信息增益計算，這通常取決于內存密集型占用網格地圖，以及直接在點云上進行路徑規劃的高計算復雜性，主要是由于昂貴的碰撞檢查。為了解決這些限制，我們提出了 EPIC，這是一個基于 LiDAR 的輕量級無人機探索框架，可直接利用點云數據來探索大規模環境。EPIC 引入了一種直接源自點云質量的新型觀測地圖，無需全局占用網格圖，同時保留了全面的探索功能。我們還提出了一種直接在點云上運行的增量拓撲圖構建方法，可以在大規模環境中進行實時路徑規劃。利用這些組件，我們構建了一個分層規劃框架，該框架可生成敏捷且節能的軌跡，與大多數現有方法相比，顯著降低了內存消耗和計算時間。廣泛的模擬和實際實驗表明，與最先進的方法相比，EPIC 實現了更快的探索，同時顯著降低了內存消耗。

2）創新點

①一種直接利用點云數據進行大規模探索的新型框架，無需額外的昂貴環境表示，同時確保高效和全局的勘探。

②直接來自點云的觀測圖，有效指導勘探。

③增量構建的拓撲圖，支持直接在點云上進行實時路徑規劃，有助于在大規模環境中進行高效探索。

④廣泛的仿真和實際測試驗證了所提出的方法，在內存消耗、探索效率和計算速度方面表現出卓越的性能。

3）算法結構

????????這篇文章中解決的問題是使用自主飛行器 （UAV） ∈ R 3 探索大規模、未知、有界的 3D 空間來生成密集的點云地圖。

????????提出的探索框架由基于觀察地圖的環境表示和實時分層規劃框架組成。在收到新的 LiDAR 點云掃描后，記錄表面觀測質量的觀測地圖會逐漸更新。基于觀測地圖檢測前沿 并對其進行聚類。為了實現大范圍環境中的高效路徑規劃，在點云上逐步構建拓撲圖 G。視點是根據拓撲可達性戰略性選擇的。隨后，計算從當前位置開始并穿過所有視點的全局引導路徑。基于全局路徑，生成搞笑、敏捷的局部軌跡，引導無人機按順序 （V-C） 訪問這些視點。如果不存在邊界，則認為探索已完成。

A 基于觀測地圖探索的環境表達

????????在本節中，我們提出了一種新的基于觀測的無人機探索環境表示方法，該方法包括兩個關鍵組成部分：觀測地圖Mobs 和前沿集群列表Lclusters。前者記錄表面觀測的質量，該質量由 LiDAR 的觀察距離和視圖方向決定。根據質量評估，觀察到的表面被標記為觀察良好或觀察不佳。前沿定義為觀察良好的表面和觀察不佳的表面之間的邊界，被聚類并存儲在 前沿集群列表中。當收到新的點云幀時，Mobs 和 Lclusters 都會以增量方式更新。

a1 觀測地圖構建

????????為了方便對地表觀測質量的高效查詢，避免過多的內存消耗，我們采用了空間哈希映射來存儲地表觀測的質量。將其定義為觀測地圖 Mobs，內部的每個元素都是表示小表面斑塊的體素，并根據觀測質量標記為觀察良好或觀察不佳。與內存密集型占用網格地圖不同，這種選擇性存儲確保只關注地表周圍的區域，從而減少內存消耗，同時保留足夠的信息進行邊界檢測。

????????每個表面面片的觀測質量由距離約束和視點方向約束決定。考慮一個以 ps 為中心的表面貼片，并且 LiDAR 位于 pl ，如果滿足以下條件，則認為滿足距離約束：

????????如上圖（a） 所示，鑒于隨著 LiDAR 光束變得更加垂直于表面貼片，觀察質量會提高，對于 2D 情況，視向質量與 |90? ? θ|呈負相關。假設 l2 ≥ l1，θ 可以通過以下方式計算：

其中 δ 表示兩個相鄰 LiDAR 光束之間的恒定角度間隔，該值由 LiDAR 的機械配置決定。根據方程，|90? ? θ|和 L1/L2 呈負相關。因此，我們可以使用 l1/l2 來評估視圖方向的質量。我們認為當 l1/l2 超過閾值 T 時，視圖方向約束得到滿足。

????????對于 3D 情況，如上圖（b） 所示，LiDAR 的感應區域由許多小的金字塔形體積組成。考慮一個以 pi 為中心的表面patch，落在金字塔形的體積 fi 內。如果組成 fi 的四條光線都滿足上述條件，則我們認為滿足視圖方向約束。當收到新的點云幀時，與點云相交的生物體素將被識別并附加到更新隊列 Q 中。我們隨后迭代隊列。對于每個未標記或之前標記為觀察不佳的體素，如果它同時滿足距離和方向約束，我們會將其分類更新為觀察良好。否則，我們會將其標記為觀察不佳。

a2 前沿檢測和聚類

????????為了實現實時前沿邊界更新，我們提出了一種增量前沿檢測和聚類方法。我們首先迭代所有在 Q 中標記為觀察不佳的體素，如果體素有一個標記為觀察良好的相鄰體素，則將其分類更新為 frontier。請注意，frontier 集合是 poorly集合的子集。

在迭代過程中，同時計算從 frontier 變為 well-observed 的體素以及從 Poorly-observed 過渡到 frontier 的體素的軸對齊邊界框 （AABB） Bupdate。除了更新 Mob 之外，當前幀中新生成的 frontier 也會被附加到一個集合的 Fcurrent 中。

????????對于點云數據的第一幀，我們基于歐幾里得距離和表面法線對 Fcurrent 應用聚類方法。考慮兩個邊界體素 fi ， fj 分別具有中心位置 pi 、 pj 和法線向量 ni 、 nj 。如果滿足以下條件，我們將這兩個體素視為相鄰體素：

????????聚類過程首先從 Fcurrent 中選擇第一個元素。從體素開始，我們采用 Breadth First Search （BFS） 算法來擴展集群，識別并合滿足指定距離和法線相似性標準的相鄰體素。如果 BFS 自然完成或集群的 AABB 大小超過預定義的閾值，則擴展將終止。在此過程中，添加到集群的體素會同時從 Fcurrent 中刪除。集群擴展結束后，該過程將使用更新的 Fcurrent 的第一個元素重新初始化。迭代將繼續，直到 Fcurrent 為空。之后，每個集群的 AABB、前沿體素及其相應的法線向量都存儲在 Lclusters 中以供進一步處理。

????????對于點云的第二幀或后續幀，我們首先識別所有與 Bupdate 相交的集群，將它們從 Lclusters 中刪除，并將它們的邊界體素添加到 Fcurrent 中。然后，我們在 Fcurrent 上執行新的聚類過程，并根據聚類結果更新 Lclusters。

B 分層探索規劃

????????分層探索規劃模塊由三個關鍵組件組成：增量構建的拓撲圖 G、全局引導路徑規劃器和局部軌跡規劃器。

????????為了在大規模環境中實現高效的路徑搜索，我們提出了一種直接在點云上構建的增量拓撲圖。利用拓撲圖 G，Global Planner 計算引導路徑。隨后，當地規劃者根據這些引導路徑生成安全、平穩和可行的軌跡，然后無人機可以有效地覆蓋邊境。

b1 增量拓撲圖構建

????????拓撲圖廣泛用于大規模環境探索，以實現更快的路徑搜索。但是，大多數現有方法都基于內存密集型的全局占用網格圖構建拓撲圖。為了解決這個問題，我們提出了一種直接在點云上運行的增量拓撲圖構建方法。在我們的方法中，拓撲圖表示為 G = （V， E），其中 V 表示獨立自由空間中的代表性頂點，E 表示顯示這些自由空間之間連通性的邊。E 中的每條邊都與無碰撞路徑相關聯。

????????我們將整個探索空間分解為長方體區域 R，這些區域由空間哈希映射管理。拓撲圖 G 的頂點 V 存儲在其相應的區域內。在收到新的區域中心無碰撞球體區域子區域代表頂點障礙物觀測面 （a） （b） （c） （d） 點云幀后，與激光雷達當前觀測區域相交的區域被添加到更新列表 Lregion 中。此外，對于在整個探索過程中首次添加到 Lregion 的區域，其相應的頂點集將初始化為 ?。

（區域中拓撲圖頂點更新過程的圖示。（a） 和 （b）：使用無碰撞球體的自由空間覆蓋。（c）：基于連通性的聚類球體。（d）：選擇代表性頂點。）

????????1） 頂點更新：對于 Lregion 中的每個區域 ri，我們使用多個無碰撞球體來覆蓋其自由空間。如圖（a） 和圖（b） 所示，初始無碰撞球體以 ri 為中心，其半徑由到點云圖中最近點的距離決定。如果此球體完全包含該區域，則 ri 的覆蓋操作結束。否則，該過程將根據球體的半徑繼續。如果半徑超過預定義的安全距離，則該區域將由對應于球體內切立方體的六個面的平面細分為更小的子區域。否則，球體將被丟棄，然后該區域被三個正交平面通過球體的中心分成八個子區域，平行于 xy、yz 和 zx 平面。

????????對于每個子區域，以遞歸方式重復球體生成和區域細分的過程，直到它完全被無碰撞的球體覆蓋或其大小小于安全半徑。隨后，我們采用聯合查找算法，根據它們的連通性對這些球體進行聚類，如圖（c） 所示。如果兩個球體的交集大小大于安全半徑，則這兩個球體被視為同一群集的一部分。

????????對于每個生成的群集，將選擇一個代表性頂點。頂點的位置設置為簇內最靠近區域中心的球體中心，如圖（d） 所示。此外，我們在進程開始之前將存儲在 Lregion 中的所有頂點記錄為 Vpre，并在 Lregion 更新后記錄為 Vnew。這兩個集合都保留用于后續算法步驟。

????????2） Edge Updating：邊集 E 初始化為 ?。隨著 G 頂點的更新，連接它們的邊將從通過 A* 搜索算法獲得的路徑派生。如上圖所示，基于 Vpre 和 Vnew，我們將頂點分為三個不同的集合：

其中 Vremove 表示 Vpre 中存在但在 Vnew 中不存在的頂點，Vremain 表示在 Vpre 和 Vnew 之間保持不變的頂點，Vinsert 表示出現在 Vnew 中但不在 Vpre 中的新頂點。

????????首先，我們遍歷 Vremove，從 G 中消除所有相關的邊。接下來，對于 Vremain 中的頂點，我們檢查與連接到它們的邊對應的所有無碰撞路徑。對于每個路徑，我們驗證它在更新的點云地圖中是否保持無碰撞。如果路徑不再無沖突，我們將其相應的頂點對添加到隊列 Qedge 中，并從 G 中刪除關聯的邊。然后，對于每個 v ∈ Vinsert，我們在 v 和相鄰區域中的節點之間構造頂點對，并將這些對添加到 Qedge。

????????隨后，對 Qedge 中的每個頂點對執行 A* 搜索算法。如果找到無碰撞路徑，則將相應的邊添加到 G 中，并存儲無碰撞路徑。此外，為了加速搜索過程并避免冗余邊緣，我們將 A* 算法的搜索范圍限制在一個小區域。此區域定義為軸對齊邊界框 （AABB），它緊緊地包圍了起點和目標點，并帶有等于一個區域大小的附加填充。最后，我們更新 vodom，即代表無人機當前位置的頂點，調整其位置，刪除以前的邊緣，并建立新的連接。

b2 全局路徑規劃

????????該模塊旨在確定 Lclusters 中前沿集群的有效訪問序列，然后為本地軌跡規劃器生成引導路徑。

????????鑒于全局最優訪問序列通常優先考慮附近的集群，而不是遠處的集群，并且考慮到飛行過程中的高頻重新規劃，在下一個重新規劃周期之前只執行一小部分引導路徑。所以，遠程集群排序的影響會減小。因此，我們最初使用粗略距離估計對 Lclusters 中的所有前沿集群進行排名，從而產生粗略的初步訪問序列。然后，我們對該序列的前 K 個元素進行更精細的調整，相應地生成全局引導路徑。這種兩階段策略將計算資源集中在近端集群上，有效地平衡了路徑最優性和計算效率，使其特別適合大規模場景下的實時探索。

????????1） 前沿集群排序：在探索過程中，不斷生成前沿，每個前沿都可以在生成時通過無人機位置的直線路徑到達，因為它們當時從無人機上可以看到。受這一觀察結果的啟發，我們引入了一個回溯距離指標來確定 Frontier 集群的優先級。對于以 ci 為中心的集群，讓 pi 表示無人機在集群產生時的位置，回溯距離可以定義為：

????????回溯距離 di 通過追溯其歷史路徑來量化無人機到達 ci 的總距離。通過維護無人機在每個集群生成時的飛行距離及其總飛行距離的記錄，我們可以計算 O（1） 時間復雜度的 di。這種高效的計算使我們能夠在 Lclusters 中快速對集群進行排名，從而產生一個粗略的全局訪問序列。

????????2） 引導路徑規劃：對于序列中的前 K 個集群，我們根據后續3）中描述的方法為每個集群生成一個視點，并將這些視點作為頂點連接到圖 G。然后，我們對 G 執行 A* 搜索以計算視點對之間的距離。隨后，我們將其表述為非對稱旅行推銷員問題 （ATSP） 并解決它。該解決方案產生從當前車輛位置開始并穿越所有選定視點的最短路徑，作為我們的全局引導路徑。

????????3） 視點生成：對于前沿集群 Cf，候選視點集合是在以集群中心為中心的圓柱坐標系中均勻采樣得到，如下圖（a） 所示。然后，我們計算從每個候選視點到點云地圖中最近點的距離。距離低于安全閾值的視點將被消除。其余候選視點每個對應于一個無碰撞球體。然后，我們根據它們相關球體的連通性將它們聚類到幾個視點集群 Ccv 中。這個過程如下圖（b） 所示，其中候選視點被分為兩個視點集群。

????????對于 Ccv 中的每個集群，其中的所有元素都可以相互訪問。所以我們選擇一個代表元素，并將其作為頂點 vrepresent 添加到 G 中，以檢查它是否可以從 vodom 到達。如果是這樣，則集群中的所有元素都被視為可訪問。在此評估之后，將從 G 中刪除 vrepresent 及其關聯的邊緣，以確保圖形在未來的規劃周期中保持高效和清晰。然后，我們從 Cf 的可訪問候選項中選擇覆蓋率得分最高的視點。視點的覆蓋率分數定義為 Cf 中可以很好地觀察到的邊界數量。如果到視點的距離小于 D，將邊界體素連接到視點 lvf 的線暢通無阻，并且 lvf 與邊界的法線向量之間的角度低于閾值，則認為邊界體素觀察良好。對于每個可到達的視點，候選偏航角在 360 度上均勻采樣，對于每個采樣的偏航角，評估 LiDAR 視場 （FOV） 內觀察到的邊界數量。選擇最大化觀察良好邊界數量的偏航角，此計數將記錄為相應視點的覆蓋分數。然后，選擇得分最高的視點并將其連接到拓撲圖。

b3 局部軌跡生成

????????獲得全局引導路徑后，我們直接在點云地圖上生成平滑的局部軌跡。采用分段多項式 MINCO 分別表示位置軌跡 p（t） = [x（t）， y（t）， z（t）]T 和偏航軌跡 ψ（t）。為了構建安全懲罰，我們使用 FIRI 沿引導路徑生成多面體安全飛行走廊。為了主動觀察未知空間，偏航被限制在查看未來的航路點。此外，我們對最大速度、傾斜角度、推力和本體速施加約束，以確保動力學的可行性。還納入了最低時間懲罰以實現敏捷飛行。利用 MINCO 的特性，我們通過聯合時空優化生成高效且敏捷的本地軌跡。

4）實驗

A 實驗設置

a1 對比方法： FUEL, ERRT, and M3 using the MARSIM simulator。

a2 大場景：a cave [224×330×41]m3 , a garage [192×156×4]m3 , and a campus [160×128×40]m3

a3 測試方法：每種方法每個場景執行四次，最大速度為 4.0m/s，地圖分辨率為 0.4m（M3 除外），時間限制為 1500 秒。

B 實驗結果

????????從上圖可是，在以垂直落差、狹窄隧道和死胡同為特征的洞穴場景中，以及以不同的建筑高度和廣闊的開放區域為特色的校園場景中，我們的方法是唯一實現完整探索的方法。隨著勘探區域的擴大，路徑搜索的計算負擔增加，FUEL 超時，ERRT 因信息獲取不足而提前終止，M3 由于其粗略的前沿更新策略而提前結束勘探。在車庫場景中，一個更結構化的環境，我們的方法和 FUEL 都完成了探索，盡管 FUEL 需要兩倍的時間。ERRT 和 M3 實現了相對較高的表面覆蓋率，但沒有完成任務。

????????如上表所示，每種方法都表現出不同的權衡： M3 和 ERRT 都采用貪婪策略來實現穩定的響應時間，但犧牲了全局規劃最優性。請注意，盡管 M3 在大多數場景中實現了最低的平均計算時間，但由于表示過于簡化，它無法完成探索。另一方面，FUEL 優先考慮全局規劃最優性，導致高計算負擔（在校園場景中高達 16.72 秒）。我們的算法平衡了這些方法，具有有競爭力的計算時間（平均 0.05 ? 0.09 秒），實現了完整的探索和近乎最優的路徑規劃（甚至比車庫場景中的 FUEL 還要短）。這導致更高的平均速度（平均 2.5 ? 3.1m/s）和更快的整體探索。

????????如上表所示，我們的環境表示方法在所有測試場景中實現了最低的內存開銷。

????????此外，進行了各種真實世界的實驗以進一步驗證我們的方法。我們利用了一個基于 LiDAR 的四旋翼平臺，配備了 Intel NUC 機載計算機、NxtPx4 自動駕駛儀 [22] 和安裝在 40? 俯仰角的 Livox MID360 LiDAR。FAST-LIO2 [23] 的修改版本被改編用于定位和映射。為確保安全，最高速度限制為 3.5m/s。首先，我們探索了一個大型校園建筑場景。勘探覆蓋了 [77 × 74 × 3]m3 的區域，耗時 181 秒，穿越了 530.4m。圖 1 顯示了示例點云圖和飛行軌跡。其次，為了在自然環境中驗證我們的方法，我們在 [50 × 84 × 3] m3 雜亂的森林場景中進行了勘探測試，耗時 152.6 秒，穿越 328.5 米。點云地圖和軌跡如圖 9 所示。最后，我們在 [77 × 24 × 3] m3 室內走廊場景中測試了我們的方法，飛行時間為 94.7 秒，飛行長度為 194.8m。補充視頻中提供了更詳細的實驗結果和所有場景的可視化。

5）結論

????????在這封信中，我們介紹了 EPIC，這是一種基于輕量級 LiDAR 的無人機探索框架，適用于大規模環境。它使用直接源自點云的基于觀測的環境表示，消除了內存密集型全局占用網格地圖，同時保留了足夠的信息以進行全面探索。我們還開發了一種直接在點云上運行的增量拓撲圖構建方法，從而實現高效的路徑規劃。利用這些組件，我們構建了一個分層規劃框架，與現有方法相比，顯著降低了內存消耗和計算時間。