[發(fā)明專利]一種多智能優(yōu)化并行算法的機器人路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110578408.7
• 申請日: 2021-05-26
• 公開（公告）號: CN113110520B
• 公開（公告）日: 2022-08-09
• 發(fā)明（設(shè)計）人: 黃超;張毅;鄭凱
• 申請（專利權(quán)）人: 重慶郵智機器人研究院有限公司
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京同恒源知識產(chǎn)權(quán)代理有限公司 11275
• 代理人: 楊柳岸

1.一種多智能優(yōu)化并行算法的機器人路徑規(guī)劃方法，其特征在于：該方法包括以下步驟：

S1：建立環(huán)境柵格地圖，利用環(huán)境模型來對路徑規(guī)劃算法進行評估；

S2：為解決粒子群優(yōu)化算法應(yīng)用于路徑規(guī)劃時存在易陷入局部極值的問題，提出多智能優(yōu)化并行算法的機器人路徑規(guī)劃方法，利用若干算法互補獲取路徑；

S3：為解決多智能優(yōu)化并行算法單純堆疊存在的時間消耗較大的問題，提出并行策略，通過嵌入并行的遺傳算法中的選擇、交叉、變異算子以及細菌覓食算法中的趨化操作加強局部搜索能力；

S4：將粒子分為兩類，分別進行局部搜索，增強局部搜索能力的同時，縮短時間；

S5：在柵格地圖上測試多智能優(yōu)化并行算法，并以不同的測試結(jié)果作為對照；

所述S1具體為：

通過RGB-D傳感器獲取環(huán)境信息，降維處理為柵格地圖，柵格地圖就是將實際工作環(huán)境等價為由相同大小格子構(gòu)成的一個柵格矩陣，對每個柵格以0-1進行編碼，將實際障礙物對應(yīng)的柵格以1填充，在地圖中以黑色表示，對可行區(qū)域以0填充，白色表示；根據(jù)柵格法，將機器人的工作環(huán)境映射到平面上，便于路徑的規(guī)劃；

在所述S2中，在柵格地圖中使用多智能優(yōu)化并行算法進行路徑規(guī)劃得到路線，由連續(xù)的小柵格組成，在規(guī)劃路徑的過程中，智能算法根據(jù)設(shè)定的搜索維度空間會得到組成路徑的多個柵格點，將點與點之間通過線段連接構(gòu)成規(guī)劃路徑；在構(gòu)建路徑時需要求解線段經(jīng)過的柵格，實現(xiàn)直線的柵格化，用于判斷是否經(jīng)過障礙，以此更新算法的適應(yīng)度函數(shù)；直線柵格化的步驟如下：

S21：獲取線段兩端頂點坐標，計算兩點的縱向距離和橫向距離；

S22：比較橫向距離和縱向距離的大小；

1)若橫向距離較大，則按照橫向柵格的列循環(huán)，求出線段與橫向柵格列中心線的交點對應(yīng)的柵格；

2)若縱向距離較大，則按照縱向柵格的行循環(huán)，求出線段與縱向柵格行中心線的交點對應(yīng)的柵格；

3)若線段之間不存在斜率，則按照柵格行循環(huán)；

S23：輸出直線柵格化的柵格點；

所述S4具體為：

S41：采用實數(shù)編碼，對粒子群進行初始化；

定義n個粒子組成粒子群對柵格地圖進行空間搜索，粒子具備位置屬性x和速度屬性v，以及定義適應(yīng)度函數(shù)，作為路徑規(guī)劃的優(yōu)化目標；

第i個粒子在t時刻的位置表示為：

第i個粒子在t時刻的速度表示為：

式中t指代當前迭代次數(shù)，D表示搜索關(guān)鍵點個數(shù)；

選用歐式距離作為算法的適應(yīng)度函數(shù)：

其中x，y是關(guān)鍵點實數(shù)編碼對應(yīng)的柵格位置，λ代表懲罰因子，T指代當前路徑穿過的障礙數(shù)量；

S42：將現(xiàn)有粒子群復(fù)制成兩份，一份嵌入遺傳算法的選擇、交叉、變異操作，另一份嵌入細菌覓食算法的趨化操作，并行訓(xùn)練綜合加強粒子群尋優(yōu)能力，保持粒子搜索速度；經(jīng)過選擇、交叉、變異操作產(chǎn)生新的粒子：

經(jīng)過細菌覓食算法的趨化操作，產(chǎn)生的新粒子為：

其中C(i)0表示向前粒子游動的步長，Φ(i)表示旋轉(zhuǎn)后隨機選擇的單位方向向量；在細菌覓食算法中存在群聚效應(yīng)，更新粒子的適應(yīng)度函數(shù)值加上粒子之間的相互作用力；令J_cc(x，i，t)表示同時考慮粒子間吸引力和排斥力的目標函數(shù)，其計算公式如下：

d_atact,d_repellant,w_atact,w_repellant四個參數(shù)表示粒子之間的受力因子，是第i個粒子位置屬性的第m個元素；

S43：將兩個分支的粒子群進行融合，獲取最優(yōu)粒子群；判斷新的粒子群的最優(yōu)解是否滿足設(shè)定的目標閾值，若不滿足，則執(zhí)行粒子群算法的更新公式；位置和速度屬性更新公式如下：

式中ω是慣性權(quán)重，決定歷史速度對當前速度的影響；c₁,c₂為學(xué)習(xí)因子，r₁,r₂為隨機因子，P_best是單個粒子在搜索過程中的歷史最優(yōu)值，G_best是粒子群在搜索過程中的歷史最優(yōu)值；

S44：執(zhí)行粒子群更新之后，再次判斷粒子群最優(yōu)適應(yīng)度函數(shù)值是否滿足設(shè)定目標閾值，若滿足，則結(jié)束算法，否則再次執(zhí)行S41～S44。