幾種較為常見的安全通道的生成方法介紹

安全通道是什么呢？安全通道是指在無人機軌跡生成時，為了避免碰撞而設(shè)定的無人機可以飛行的通道。它連通了起點與終點，并且在安全通道內(nèi)生成的任意軌跡都是安全無碰撞的。安全通道是軌跡生成中用于避免碰撞的重要技術(shù)，關(guān)于安全通道的生成目前已經(jīng)有了許多的方法。一般來說，安全通道都是用多個連通在一起的多面體進行表示。這樣安全通道的生成問題，可以轉(zhuǎn)化為多個多面體生成。下面針對幾種較為常見的安全通道的生成方法進行介紹。

1. 半定規(guī)劃的迭代區(qū)域膨脹

為了獲取多面體，這個方法首先構(gòu)造一個初始橢球，由一個以選定點為中心的單位球組成。然后，遍歷障礙物，為每個障礙物生成一個超平面，該超平面與障礙物相切并將其與橢球分開。再次，這些超平面定義了一組線性約束，它們的交集是一個多面體。然后，可以在那個多面體中找到一個最大的橢球，使用這個橢球來定義一組新的分離超平面，從而定義一個新的多面體。

選擇生成分離超平面的方法，這樣橢圓體的體積在迭代之間永遠不會減少。可以重復(fù)這個過程，直到橢圓體的增長率低于某個閾值，此時我們返回多面體和內(nèi)接橢圓體。這個方法具有迭代的思想，并且具有收斂判斷的標準，算法的收斂快慢和初始橢球具有很大的關(guān)系。



圖 1 半定規(guī)劃的迭代區(qū)域膨脹。每一行即為一次迭代操作，直到橢圓體的增長率低于閾值。

2. 基于凸分解的安全通道生成

基于凸分解的安全通道生成方法由四個步驟完成安全通道的生成，分別為：找到橢球、找到多面體、邊界框、收縮。這四個步驟的具體介紹如下：

1）生成橢球

先形成一個球體，球的半徑為兩個路徑點的距離，然后再進行收縮其中的兩個長軸，以保證該橢球為最大橢球，最后再拉伸第三個軸（連接路徑點的軸）以保證這個橢球是最大的。

橢球的計算是基于路徑點進行的，路徑點的疏密程度，將會影響橢球的個數(shù)，因此在使用時最好能夠利用計算的橢球融合其包含的路徑點，這樣來減少計算路徑點的個數(shù)。



圖 2生成橢球。粗線段為 L，灰色區(qū)域表示障礙物，白色區(qū)域為自由空間。左：從一個球體開始，我們找到離 L 中心最近的點 p*，并調(diào)整短軸的長度，使虛線橢球接觸這個 p*。中：重復(fù)相同的過程，找到一個新的最近點 p* 和新的橢球。右：橢球內(nèi)沒有障礙物，當(dāng)前橢球是最大橢球。需要多次迭代以確保最終的球體排除所有障礙。

2）找到多面體

找到多面體。不斷擴張橢球直到和障礙物相切，保存切線。重復(fù)上面的操作，獲得更多的切線，直到當(dāng)前地圖都和其相交為止。這個過程的主要計算量都在障礙物的判斷中，因此計算很快。



圖 3生成多面體。左：找到橢球和超平面的第一個交點（紅線），相應(yīng)的半空間之外的障礙點被移除（陰影）。中：找到下一個交點（虛線橢球表示原始橢球，實線橢球表示新橢球），繼續(xù)從地圖中移除新半空間之外的障礙點。右：繼續(xù)擴張直到當(dāng)前地圖中沒有障礙物，凸空間 （藍色區(qū)域）由半平面的交點定義。

3）邊界框

邊界框的作用是分割地圖，將附近的local障礙物地圖從全局地圖中提取出來，也就是獲得local障礙物地圖。其主要原因是上面的操作不能對整個地圖執(zhí)行，因為那樣的計算量太大了，因此可以在路徑點附近打上邊框，這樣就能降低計算量了。邊框大小的選擇就非常具有經(jīng)驗性質(zhì)了，最好能夠涵蓋所需要的信息。

4）收縮


對安全通道進行收縮，收縮的尺度由無人機的尺寸決定，這樣的處理可以讓無人機變成一個質(zhì)點。收縮是對生成的多面體進行的，這樣的好處是不會造成兩個多面體出現(xiàn)不相交的情況。

3. 平行凸簇膨脹方法

上述的兩種方法都是從點云地圖出發(fā)，并且都是基于橢圓完成凸多面體的生成。而平行凸簇膨脹方法，與上面的方法不同，該方法是從柵格地圖出發(fā)，利用最小凸集生成算法，完成凸多面體的生成。

其算法的思想是首先獲得一個凸集，再沿著凸集的表面進行擴張，擴張之后再進行凸集檢測，判斷新擴張的集合是否保持為凸。一直擴張到不能再擴張為止，再提取凸集的邊緣點，利用快速凸集生成算法，生成凸多面體。該算法的好處在于可以利用這種擴張的思路，將安全的多面體的體積盡可能的充滿整個空間，因此獲得的安全通道更大。

但其也具有一定的缺點，就是計算量比較大，計算所需要的時間比較長，為了解決這個問題，在該文章中，又提出了采用GPU加速的方法，來加速計算。



圖 4 平行凸簇膨脹方法。在 (a) 和 (b) 中，所有合格的相鄰單元格都被添加到凸簇中。在 (c) 和 (d) 中，由于進行邊緣單元格凸集檢測時，射線經(jīng)過了不在凸簇的單元格，該單元格被排除在凸簇中。[3]

總結(jié)

安全通道的生成雖然是一個比較小的問題，但是因為它直接影響了最終生成軌跡的質(zhì)量，因此也非常重要。安全通道能夠直接轉(zhuǎn)化為優(yōu)化問題中的凸約束，這種特性應(yīng)該也可以利用在其他的領(lǐng)域內(nèi)。




審核編輯：劉清