基于極值法的靜態(tài)路徑規(guī)劃算法

楊晶所 劉子龍

摘要：針對傳統(tǒng)路徑規(guī)劃算法在求解靜態(tài)已知環(huán)境下的最優(yōu)或次優(yōu)路徑時存在轉(zhuǎn)折次數(shù)過多、路徑復(fù)雜等問題，提出一種基于極值法的移動機(jī)器人靜態(tài)路徑規(guī)劃算法。在對環(huán)境建模時，采用邊界點(diǎn)集描述障礙物不可行區(qū)域的輪廓信息；在路徑規(guī)劃過程中，首先判斷當(dāng)前出發(fā)點(diǎn)到目的點(diǎn)之間是否有障礙物，然后利用極值法獲得轉(zhuǎn)折點(diǎn)，進(jìn)而得到初步路徑，同時為后續(xù)利用極值法獲取新的轉(zhuǎn)折點(diǎn)提供計算與判斷依據(jù)。仿真結(jié)果證明了該算法的有效性。

關(guān)鍵詞：移動機(jī)器人；環(huán)境建模；靜態(tài)路徑規(guī)劃；極值法

DOIDOI：10.11907/rjdk.181772

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）010-0072-04

英文摘要Abstract：In order to solve the problem that the traditional path planning algorithm has many shortcomings such as too many turning times and complex path in solving the optimal or suboptimal path in the static known environment， a static path planning algorithm for mobile robot based on extreme value method is proposed. In the environment modeling， the boundary point set is used to describe the contour information of the unfeasible area of the obstacle. In the process of path planning， it is firstly to judge whether there is an obstacle between the current starting point and the destination point， the turning point is obtained by using the extreme value method， and then the initial path is obtained， and the new rotation is obtained by using the extreme value method in the same time. The folding point provides the basis for calculation and the basis of judgment. The simulation results show the effectiveness of the algorithm.

英文關(guān)鍵詞Key Words：mobile robot；environment modeling；static path planning；extreme value method

0 引言

路徑規(guī)劃是移動機(jī)器人系統(tǒng)的重要組成部分， 根據(jù)對環(huán)境信息掌握程度可將其劃分為兩大類[1]：①基于環(huán)境先驗完全信息的靜態(tài)路徑規(guī)劃，又稱全局路徑規(guī)劃；②基于傳感器檢測信息的動態(tài)路徑規(guī)劃，又稱局部路徑規(guī)劃。靜態(tài)路徑規(guī)劃過程是根據(jù)先驗環(huán)境信息找出從出發(fā)點(diǎn)到目的點(diǎn)中滿足一定要求的最優(yōu)或次優(yōu)可行路徑，它涉及的基本問題是環(huán)境建模[2]和路徑搜索[3]。

廣泛應(yīng)用于機(jī)器人路徑規(guī)劃的柵格法[4]，通過將移動機(jī)器人工作的物理空間抽象成以柵格為最小單位的環(huán)境地圖，將機(jī)器人的路徑搜索以此為最小移動單位進(jìn)行路徑規(guī)劃，而路徑的變化方向根據(jù)柵格位置的不同最多確定8個，即東、南、西、北、東北、西北、東南、 西南[5]方向，因此得到的路徑會出現(xiàn)折線多、轉(zhuǎn)折次數(shù)多、路徑復(fù)雜等問題[6]。

本文提出一種基于極值法的路徑規(guī)劃算法。該算法將當(dāng)前出發(fā)點(diǎn)和目的點(diǎn)范圍內(nèi)所有的障礙物邊界點(diǎn)距出發(fā)點(diǎn)和目的點(diǎn)連線“最遠(yuǎn)”的點(diǎn)視為極值點(diǎn)，再據(jù)此搜索下一個極值點(diǎn)直至無法搜索出符合條件的極值點(diǎn)時，完成路徑規(guī)劃。本文算法給出了一個新的處理路徑規(guī)劃過程思路，即當(dāng)前的出發(fā)點(diǎn)、目的點(diǎn)不一定是原始的出發(fā)點(diǎn)、目的點(diǎn)，而是在路徑規(guī)劃過程中一個求解極值點(diǎn)的“分支”上的出發(fā)點(diǎn)、目的點(diǎn)，即通過以上一級出發(fā)點(diǎn)為出發(fā)點(diǎn)、極值點(diǎn)為目的點(diǎn)，或上一級的目的點(diǎn)為目的點(diǎn)、極值點(diǎn)為出發(fā)點(diǎn)，不斷地更新當(dāng)前的出發(fā)點(diǎn)、目的點(diǎn)。

1 極值法設(shè)計思路

在考慮距離最優(yōu)的前提下，已知靜態(tài)環(huán)境信息，由出發(fā)點(diǎn)到目的點(diǎn)的最優(yōu)可行路徑必定是轉(zhuǎn)折次數(shù)最少、路程最短的一條路徑[7]。在不穿過障礙物及保留安全間距的前提下，上述最優(yōu)路徑必定存在至少一個“緊靠”障礙物的不可行區(qū)域邊界線的轉(zhuǎn)折點(diǎn)[8]。上述轉(zhuǎn)折點(diǎn)從出發(fā)點(diǎn)與目的點(diǎn)構(gòu)成的直線，本質(zhì)上是障礙物的不可行區(qū)域邊界線的點(diǎn)集在該直線上的極值點(diǎn)[9]。將上述極值點(diǎn)作為新的出發(fā)點(diǎn)或目的點(diǎn)，與原來的目的點(diǎn)及出發(fā)點(diǎn)構(gòu)成新的出發(fā)點(diǎn)、目的點(diǎn)組合。若該起止點(diǎn)組合構(gòu)成的直線穿過障礙物（即起止點(diǎn)之間有障礙物），則重復(fù)上述過程以獲得下一個轉(zhuǎn)折點(diǎn)，直至所有線段均符合“避開障礙物”這一條件[10]。如圖1所示，出發(fā)點(diǎn)A、目的點(diǎn)B、障礙物O以及留有間距d的不可行區(qū)域的邊界點(diǎn)集S，構(gòu)成環(huán)境模型基本信息。

3 路徑規(guī)劃仿真

基于python仿真語言環(huán)境，利用上述算法實現(xiàn)路徑規(guī)劃仿真實驗，仿真結(jié)果如圖11（a）～圖11（d）所示。在仿真環(huán)境中，機(jī)器人的每次路徑規(guī)劃都是基于不同的出發(fā)點(diǎn)與目的點(diǎn)（分別用及表示），障礙物的位置、形狀也是隨機(jī)的。

仿真結(jié)果表明，對于能大致描述出清晰輪廓特征的環(huán)境模型，基于極值法的路徑規(guī)劃算法不依賴于障礙物的具體外形，且規(guī)劃出的路徑能以較少的轉(zhuǎn)折點(diǎn)、簡單的路徑滿足最優(yōu)或次優(yōu)路徑要求。

4 結(jié)語

本文提出基于極值法的移動機(jī)器人靜態(tài)路徑規(guī)劃算法并對其進(jìn)行了仿真。研究分析表明，該算法優(yōu)化了求解靜態(tài)環(huán)境下最優(yōu)或次優(yōu)路徑時轉(zhuǎn)折次數(shù)過多、路徑復(fù)雜等問題。此外，在以邊界點(diǎn)集進(jìn)行環(huán)境建模時，其邊界點(diǎn)集的密集程度決定環(huán)境模型的精度，直接影響到算法的計算時間和最終路徑生成結(jié)果，即邊界點(diǎn)集越密集，環(huán)境模型的精度越高，算法計算時間越長，路徑規(guī)劃結(jié)果也越接近最優(yōu)解。

參考文獻(xiàn)：

[1] VASUDEVAN C， GANESAN K. Case-based path planning for autonomous underwater vehicles[C]. IEEE Int Symposium on Intelligent Control. Columbus， 1994：160-165.

[2] 時丕芳，趙永瑞.移動機(jī)器人行走路徑環(huán)境建模方法綜述與解析[J].現(xiàn)代制造技術(shù)與裝備，2010（1）：1-2.

[3] 李曉敏.智能移動機(jī)器人全局路徑規(guī)劃及仿真[D].南京：南京理工大學(xué)，2004.

[4] 劉曉磊，蔣林，金祖飛，等.非結(jié)構(gòu)化環(huán)境中基于柵格法環(huán)境建模的移動機(jī)器人路徑規(guī)劃[J].機(jī)床與液壓，2016，44（17）：1-2.

[5] 王娟娟，曹凱.基于柵格法的機(jī)器人路徑規(guī)劃[J].農(nóng)業(yè)裝備與車輛工程，2009（4）：15-16.

[6] 王紅衛(wèi)，馬勇，謝勇，等.基于平滑A*算法的移動機(jī)器人路徑規(guī)劃[J].同濟(jì)大學(xué)學(xué)報：自然科學(xué)版，2010，38（11）：1647-1650.

[7] 禹建麗，李曉燕，王躍明，等.一種基于神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃算法[J].洛陽工學(xué)院學(xué)報，2001，22（1）：31-34.

[8] 陳衛(wèi)忠，王慶.基于機(jī)器人避障問題的數(shù)學(xué)模型[J].長春大學(xué)學(xué)報，2013，23（6）：689-692.

[9] 陳英俏.改進(jìn)蟻群算法及其在移動機(jī)器人路徑規(guī)劃中的研究[D].沈陽：東北大學(xué)，2010.

[10] 韋如明.基于強(qiáng)化學(xué)習(xí)的移動機(jī)器人路徑規(guī)劃研究與實現(xiàn)[D].廣州：華南理工大學(xué)，2015.

[11] 禹建麗，程思雅，孫增圻，等.一種移動機(jī)器人三維路徑規(guī)劃優(yōu)化算法[J].中南大學(xué)學(xué)報：自然科學(xué)版，2009，40（2）：471-477.

[12] 化建寧，趙憶文，王越超.一種新的移動機(jī)器人全局路徑規(guī)劃算法[J].機(jī)器人，2006，28（6）：593-597.

[13] 王愛民，史慶國，呂晨亮.關(guān)于移動機(jī)器人路徑最優(yōu)化問題[J].中國機(jī)械工程，2001，12（6）：685-687.

[14] SUGIHARA K， SMITH J. Genetic algorithms for adaptive motion planning of an autonomous mobile robot[C]. IEEE International Symposium on Computational Intelligence in Robotics and Automation，2002：138-143.

[15] LIN Y H， LIU Y S， GAO G， et al. The IFC-based path planning for 3D indoor spaces[J]. Advanced Engineering Informatics， 2013，27（2）：189-205.

[16] 韓雪.多目標(biāo)遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué)，2011.

[17] 步立新，羅文鈺，馮允成.隨機(jī)遞歸算法求解車輛路徑問題[J].系統(tǒng)工程理論與實踐，2008，28（11）：142-148.

[18] LI A H， LIU X H， ZHANG Y J. Based on completely two forks trees concept algorithm design and analysis[J]. Journal of Shandong University of Technology， 2006（9）：146-4-149.

[19] RIVES P， BORRELLY J J， CORRêAVICTORINO A， et al. Mobile robot navigation and guidance[EB/OL]. http：//spie.org/Publications/Proceedings/Volume/7129 SSO=1 2003.

[20] PORTA J M， JAILLET L， ONARD， et al. Randomized path planning on manifolds based on higher-dimensional continuation[J]. International Journal of Robotics Research， 2012，31（2）：201-215.

[21] 趙先章，常紅星，曾雋芳，等.一種基于粒子群算法的移動機(jī)器人路徑規(guī)劃方法[J].計算機(jī)應(yīng)用研究，2007，24（3）：181-183.

（責(zé)任編輯：杜能鋼）