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

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

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

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

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



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

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

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

1）生成橢球

先形成一個(gè)球體，球的半徑為兩個(gè)路徑點(diǎn)的距離，然后再進(jìn)行收縮其中的兩個(gè)長(zhǎng)軸，以保證該橢球?yàn)樽畲髾E球，最后再拉伸第三個(gè)軸（連接路徑點(diǎn)的軸）以保證這個(gè)橢球是最大的。

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



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

2）找到多面體

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



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

3）邊界框

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

4）收縮


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

3. 平行凸簇膨脹方法

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

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

但其也具有一定的缺點(diǎn)，就是計(jì)算量比較大，計(jì)算所需要的時(shí)間比較長(zhǎng)，為了解決這個(gè)問題，在該文章中，又提出了采用GPU加速的方法，來加速計(jì)算。



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

總結(jié)

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




審核編輯：劉清