基于凸優化的移動機器人避障路徑規劃

李念

摘 ?要：該文提出一種基于凸優化的移動機器人避障路徑規劃方案，機器人在復雜環境中進行路徑規劃和任務動作規劃是確保機器人避免與障礙物發生碰撞的關鍵。路徑規劃的目標是找到一條從初始狀態到最終狀態的可行路徑，而避免與任何障礙物發生碰撞，目前的規劃方案存在路徑不是最優或者可能出現碰撞的情況。該文的創新點在于提供基于凸優化的導航空間劃分方法，并根據多障礙物環境構建可行的走廊，從而得到一條具有避障保證的路徑。該文的算法可用于任何有障礙物的有限維空間，提供一種通用的路徑生成技術，為機器人路徑規劃技術的發展起到積極作用。

關鍵詞：凸優化；移動機器人；導航空間；避障；空間分區

中圖分類號：TP242 ? ? ?文獻標志碼：A ? ? ? ? ?文章編號：2095-2945（2024）18-0037-04

Abstract： This paper presents a convex optimization-based obstacle avoidance path planning solution for mobile robots. The path planning and task action planning of mobile robot in complex environment is the key to ensure that the robot avoids collision with obstacles. The goal of path planning is to find a feasible path from the initial state to the final state， and to avoid collision with any obstacles. The current planning scheme has the situation that the path is not optimal or may have collision. The innovation of this paper is to provide a navigation space division method based on convex optimization， and to build a feasible corridor according to the multi-obstacle environment， so as to get a path with obstacle avoidance guarantee. The algorithm in this paper can be used in any finite dimensional space with obstacles， provides a general path generation technology， and plays a positive role in the development of robot path planning technology.

Keywords： convex optimization; mobile robot; navigation space; obstacle avoidance; space partition

目前各式各樣的機器人，如機械臂、雙足機器人、四足機器人、無人車、無人機網、水下自治機器人網和智能移動體等，已經成為工業界和學術界的研究熱點。如何在移動機器人所在的位置找到一塊無障礙空間進行路徑規劃和任務動作規劃是控制機器人不與障礙物發生碰撞的關鍵。在此過程中，最核心的問題是機器人的路徑規劃。路徑規劃的目標是找到一條從初始狀態到最終狀態、不與任何障礙物發生碰撞的可行路徑，其主要挑戰源于通常需要探索的巨大搜索空間，特別是對于多障礙環境問題。目前多障礙環境的導航已受到控制和機器人領域的廣泛關注[1]，例如監測或監視[2]。從數學角度來看，主要困難來自運動空間中可行區域的非凸性，從而導致解空間中缺乏連通性。

運動規劃通常分為3個任務，第一個任務是路徑規劃，這是指在導航空間中構建路線，而無需及時進行明確的參數化。接下來，軌跡規劃表示對可行軌跡的搜索，該軌跡尊重生成的路徑以及動態和物理限制給出的約束。最后，低級控制在于制定可靠的反饋控制策略，以便所考慮的代理遵循所獲得的軌跡。現有的方法可以分為2大類。前者是基于優化的策略，例如A*算法[3-4]、勢場法[5-7]、RRT算法[8-9]或凸化技術[10]，合并路徑和軌跡規劃在擁擠的多障礙環境中，任務的代價是更高的計算復雜性。后一類，即基于樣本的方法[11]，依賴于圖的構造，并偏向于運動規劃的第一個任務。無論采用哪種方法，關鍵在于環境建模方式。一種流行的做法是采用凸集，不論是多面體還是橢球體，無論在局部還是全局的可行性，以及在最優性方面都有廣泛應用[12]。

本文側重于解決路徑規劃層面的問題，主要關注全局的可行性。當前存在的問題包括放棄微分約束以及由于有限的轉向或能量而可能出現在運動規劃中的限制，雖然最優性是生成幾何路徑后的次要目標，但其確保避開障礙物，并有可能明確描述可行的走廊，類似于文獻[13]的方法。從數學角度來看，該解決方案將利用凸優化的方法[14]，該凸優化首先用于約束控制和 PWA（分段仿射）控制實現。事實證明，這個方法對于構建分區特別有效，并將在這里用于描述導航空間的特征。這種從障礙物開始構建分區的通用的基于優化的方法可以被理解為用于表征運動空間中的非凸可行區域的凸化過程。本文的主要創新點在于：提供了基于凸優化的導航空間劃分；根據多障礙物環境中的互連圖構建了可行的走廊；提出了一條有避障保證的路徑。本文的算法不限于R2，也不限于R3，并且提供了在任何有障礙物的有限維空間中的通用路徑生成技術。

1整體方案設計

首先，需要考慮有限維輸出空間Ｒd和有限數量的非重疊區域Pj∈Com（Rd），j∈T={1，…，N0}描述障礙物

應用本算法對于路徑軌跡進行生成，其步驟如下：首先要提供工作空間的圖形結構；其次要給出？酌（？茲）、PWA（連續）函數；再者增加一個連續寬度函數？籽（？茲），它保證與標準？酌（？茲）的可接受偏差的度量；最后將可行解？酌（？茲）替換為基于優化的選擇？仔（？茲），而C（？淄）為路徑長度。

為了證明本算法的可行性，在MATLAB2022a中，對圖2障礙物劃分的集合繼續進行目標路徑的優化，運行結果如圖3所示，其中橫、縱坐標表示距離長度，單位為m。首先，要構建關聯圖并找到路徑？酌。接下來，需要指定走廊寬度？籽的近似值（圖3中的深灰色長條區域是走廊）。為了計算走廊寬度，需要對連續參數？茲進行采樣。再通過選擇？仔=？酌來避開本算法的第4步。提供此路徑作為標準路徑跟蹤機制的參考，該機制（帶有菱形標記的淺灰色線）顯示為遵守約束（沒有與障礙物相交并且成功到達目的地）。為了說明最終路徑跟蹤任務，本算法還考慮了標準雙積分器動態并應用了MPC（模型預測控制）策略。

4 ?凸面性的轉換

在整個路徑規劃過程中，本文的基礎是基于障礙物的初始幾何形狀是具有凸面性的。但是在某些情況下，有一些障礙物本身是非凸的，則不滿足本文算法的實施。為此，對于非凸狀態下的復雜環境，這里采用了文獻[19]中所提出的構造方式，其總結如下：對于任何多面體分區，總是存在一個細分，使得該分區的內部邊界被保留，并且新的隔斷是凸狀可升降的。轉置到分區區域中包含的障礙物的當前框架中，可以得出結論，障礙物可以細分為凸子集的集合，從而實現凸優化。在凸優化的可行性研究中是以平面圖中的額外邊為代價的，而只要這些邊與至少一個原始障礙物相交，在后處理階段是可以刪除這些邊的，不會引起結果的失真。非凸障礙物情況下的目標是用凸障礙物的有限并集來表達這些區域。原始設置中缺乏凸度可能會導致結構不可行，用凸形障礙物的方式替換非凸形障礙物可以構建對應隔斷。然而，刪除與原始障礙物相交的邊可能會導致圖表斷開。

5結論

本文提出了一種建設性的解決方案，用于在二維、三維空間中被多個障礙物遮擋的環境中生成兩點之間的最優路徑。有關障礙物幾何形狀的全局信息被視為凸優化過程的入口點，該過程導致凸提升，從而允許對復雜環境進行分區。這種劃分是描述障礙物周圍圖形并最終生成避開障礙物的走廊的關鍵要素。從計算的角度來看，構造的有效性依賴于凸提升的可行性。結果表明，可以通過用有限數量的凸子集重新表述障礙物來提高可行性，此外，該方法還可應用于多個非凸障礙物的情況下的路徑規劃構造。

參考文獻：

[2] KANISTRAS K， MARTINS G， RUTHERFORD M J， et al. A survey of unmanned aerial vehicles （UAVs） for traffic monitoring[C]//2013 international conference on unmanned aircraft systems （ICUAS）. IEEE，2013：221-234.

[3] 孫齊，卞強，童余德.基于地磁匹配輔助導航的改進A*算法路徑規劃[J].江蘇大學學報（自然科學版），2023，44（6）：696-703.

[4] 王洪斌，劉德垚，鄭維，等.異構多目標差分-動態窗口算法及其在移動機器人中的應用[J].控制與決策，2023，38（12）：3390-3398.

[5] 姜文，崔化超，戚志剛，等.基于多目標粒子群-人工勢場法的無人艇局部航路規劃[J].中國電子科學研究院學報，2023，18（9）：814-820.

[6] 高飛翔，郝萬君，吳宇，等.改進人工勢場法機器人避障路徑規劃研究[J].計算機仿真，2023，40（9）：431-436，442.

[7] RIMON E， KODITSCHEK D E. Exact robot navigation using artificial potential functions[J]. IEEE Trans on Robotics & Automation， 1992， 8：501-518.

[8] 劉沖，劉本學，呂桉，等.基于改進RRT算法的室內移動機器人路徑規劃[J].組合機床與自動化加工技術，2023（10）：20-23，29.

[9] 張喜超，尹勇.基于改進RRT*算法的無人船路徑規劃[J].中國航海，2023，46（1）：143-147，154.

[10] SZMUK M， PASCUCCI C A， DUERI D， et al. Convexification and real-time on-board optimization for agile quad-rotor maneuvering and obstacle avoidance[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE， 2017.

[11] KARAMAN S， FRAZZOLI E. Sampling-based Algorithms for Optimal Motion Planning[J]. The International Journal of Robotics Research， 2011， 30（7）：846-894.

[12] 王祝，劉莉，龍騰，等.基于罰函數序列凸規劃的多無人機軌跡規劃[J].航空學報，2016，37（10）：3149-3158.

[13] LIU S， WATTERSON M， MOHTA K， et al. Planning Dynamically Feasible Trajectories for Quadrotors Using Safe Flight Corridors in 3-D Complex Environments[J]. IEEE Robotics & Automation Letters，2017，2（3）：1688-1695.

[14] NGUYEN N A， GULAN M， OLARU S， et al. Convex Liftings： Theory and Control Applications[J]. IEEE Transactions on Automatic Control， 2018， 63（5）：1243-1258.

[15] 吳沛鋒.智能優化算法及其應用[D].沈陽：東北大學，2012.

[16] WANG X， KLOETZER M， MAHULEA C， et al. Collision avoidance of mobile robots by using initial time delays[J].IEEE， 2015.

[17] 江純興，吳鋒.結合維諾區域分割和路徑優化的路徑規劃算法[J].計算機工程與應用，2024，60（10）：311-319.

[18] 張毅，孟啟源，楊秀霞.基于雙旋Lyapunov矢量場的無人機避障算法[J].控制與決策，2018，33（8）：1514-1522.

[19] NGUYEN N A， OLARU S， RODRIGUEZ-AYERBE P， et al. Inverse parametric convex programming problems via convex liftings[J]. IFAC Proceedings Volumes，2014，47（3）：2489-2494.