基于凸優(yōu)化的移動(dòng)機(jī)器人避障路徑規(guī)劃

李念

摘 ?要：該文提出一種基于凸優(yōu)化的移動(dòng)機(jī)器人避障路徑規(guī)劃方案，機(jī)器人在復(fù)雜環(huán)境中進(jìn)行路徑規(guī)劃和任務(wù)動(dòng)作規(guī)劃是確保機(jī)器人避免與障礙物發(fā)生碰撞的關(guān)鍵。路徑規(guī)劃的目標(biāo)是找到一條從初始狀態(tài)到最終狀態(tài)的可行路徑，而避免與任何障礙物發(fā)生碰撞，目前的規(guī)劃方案存在路徑不是最優(yōu)或者可能出現(xiàn)碰撞的情況。該文的創(chuàng)新點(diǎn)在于提供基于凸優(yōu)化的導(dǎo)航空間劃分方法，并根據(jù)多障礙物環(huán)境構(gòu)建可行的走廊，從而得到一條具有避障保證的路徑。該文的算法可用于任何有障礙物的有限維空間，提供一種通用的路徑生成技術(shù)，為機(jī)器人路徑規(guī)劃技術(shù)的發(fā)展起到積極作用。

關(guān)鍵詞：凸優(yōu)化；移動(dòng)機(jī)器人；導(dǎo)航空間；避障；空間分區(qū)

中圖分類號(hào)：TP242 ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? ? ? ?文章編號(hào)：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

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

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

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

1整體方案設(shè)計(jì)

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

應(yīng)用本算法對(duì)于路徑軌跡進(jìn)行生成，其步驟如下：首先要提供工作空間的圖形結(jié)構(gòu)；其次要給出？酌（？茲）、PWA（連續(xù)）函數(shù)；再者增加一個(gè)連續(xù)寬度函數(shù)？籽（？茲），它保證與標(biāo)準(zhǔn)？酌（？茲）的可接受偏差的度量；最后將可行解？酌（？茲）替換為基于優(yōu)化的選擇？仔（？茲），而C（？淄）為路徑長(zhǎng)度。

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

4 ?凸面性的轉(zhuǎn)換

在整個(gè)路徑規(guī)劃過程中，本文的基礎(chǔ)是基于障礙物的初始幾何形狀是具有凸面性的。但是在某些情況下，有一些障礙物本身是非凸的，則不滿足本文算法的實(shí)施。為此，對(duì)于非凸?fàn)顟B(tài)下的復(fù)雜環(huán)境，這里采用了文獻(xiàn)[19]中所提出的構(gòu)造方式，其總結(jié)如下：對(duì)于任何多面體分區(qū)，總是存在一個(gè)細(xì)分，使得該分區(qū)的內(nèi)部邊界被保留，并且新的隔斷是凸?fàn)羁缮档?。轉(zhuǎn)置到分區(qū)區(qū)域中包含的障礙物的當(dāng)前框架中，可以得出結(jié)論，障礙物可以細(xì)分為凸子集的集合，從而實(shí)現(xiàn)凸優(yōu)化。在凸優(yōu)化的可行性研究中是以平面圖中的額外邊為代價(jià)的，而只要這些邊與至少一個(gè)原始障礙物相交，在后處理階段是可以刪除這些邊的，不會(huì)引起結(jié)果的失真。非凸障礙物情況下的目標(biāo)是用凸障礙物的有限并集來表達(dá)這些區(qū)域。原始設(shè)置中缺乏凸度可能會(huì)導(dǎo)致結(jié)構(gòu)不可行，用凸形障礙物的方式替換非凸形障礙物可以構(gòu)建對(duì)應(yīng)隔斷。然而，刪除與原始障礙物相交的邊可能會(huì)導(dǎo)致圖表斷開。

5結(jié)論

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

參考文獻(xiàn)：

[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] 孫齊，卞強(qiáng)，童余德.基于地磁匹配輔助導(dǎo)航的改進(jìn)A*算法路徑規(guī)劃[J].江蘇大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，44（6）：696-703.

[4] 王洪斌，劉德垚，鄭維，等.異構(gòu)多目標(biāo)差分-動(dòng)態(tài)窗口算法及其在移動(dòng)機(jī)器人中的應(yīng)用[J].控制與決策，2023，38（12）：3390-3398.

[5] 姜文，崔化超，戚志剛，等.基于多目標(biāo)粒子群-人工勢(shì)場(chǎng)法的無人艇局部航路規(guī)劃[J].中國電子科學(xué)研究院學(xué)報(bào)，2023，18（9）：814-820.

[6] 高飛翔，郝萬君，吳宇，等.改進(jìn)人工勢(shì)場(chǎng)法機(jī)器人避障路徑規(guī)劃研究[J].計(jì)算機(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] 劉沖，劉本學(xué)，呂桉，等.基于改進(jìn)RRT算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2023（10）：20-23，29.

[9] 張喜超，尹勇.基于改進(jìn)RRT*算法的無人船路徑規(guī)劃[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] 王祝，劉莉，龍騰，等.基于罰函數(shù)序列凸規(guī)劃的多無人機(jī)軌跡規(guī)劃[J].航空學(xué)報(bào)，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] 吳沛鋒.智能優(yōu)化算法及其應(yīng)用[D].沈陽：東北大學(xué)，2012.

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

[17] 江純興，吳鋒.結(jié)合維諾區(qū)域分割和路徑優(yōu)化的路徑規(guī)劃算法[J].計(jì)算機(jī)工程與應(yīng)用，2024，60（10）：311-319.

[18] 張毅，孟啟源，楊秀霞.基于雙旋Lyapunov矢量場(chǎng)的無人機(jī)避障算法[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.