基于兩點法的移動機器人局部路徑規劃算法

宋 莉，李彩虹,朱寶艷，王小宇

(山東理工大學 計算機科學與技術學院，山東 淄博 255049)

基于兩點法的移動機器人局部路徑規劃算法

宋 莉，李彩虹,朱寶艷，王小宇

(山東理工大學 計算機科學與技術學院，山東 淄博 255049)

針對傳統移動機器人局部路徑規劃存在死區或陷阱區域等問題，提出了一種新的兩點法算法.在路徑規劃過程中，首先利用兩點法確定機器人面向目標的旋轉角度，進而判斷出在前進路徑中遇到障礙物后的路徑，并推導出在不同環境信息下最優或次優的規劃算法.在前進過程中機器人只需要處理當前狀態下的傳感器數據，不需要處理全局的復雜環境信息，節省了機器人存儲空間，提高了規劃效率.最后用RobotBasic仿真平臺對所推導的算法進行仿真.結果驗證了算法的有效性和可靠性.

移動機器人；局部路徑規劃；兩點法；RobotBasic

機器人局部路徑規劃[1-2]具有魯棒性明顯、實時性顯著，能靈敏地處理外部信息隨時變化的狀態，應用范圍較為廣泛.其缺點是只能依靠局部信息，容易出現局部極值點和震蕩，以至機器人無法順利到達目標點，故需要合適的算法來解決這些問題.局部路徑方法主要有神經網絡算法[3]、模糊邏輯算法[4]、人工勢場法[5]、遺傳算法[6]等.

利用機器人本體上配備的緩沖器、紅外傳感器感知周圍障礙物信息，利用GPS和指南針分析機器人在所處環境中的位置.在算法推導中首先確定機器人面向目標點的旋轉角度，然后在前進路徑中獲取實時環境信息，判斷在遇到障礙物后的最優或次優路徑，并利用攝像頭尋找目標點，提出了改進后的兩點法算法.該算法的數學方法簡單，計算量小，解決了移動機器人陷入死區、停滯不前和只能找到可行性局部路徑的問題.

1 移動機器人傳感器

本文移動機器人配備有緩沖器、紅外傳感器、攝像頭、GPS和指南針4種類型的傳感器[6].

機器人本體前后的緩沖器分別形成130°弧，兩側緩沖器形成50°弧.緩沖器安裝在簡單的折疊開關上，當機器人撞上一個物體時，壓力使得一個或多個開關關閉.緩沖器系統將每個傳感器的邏輯“1”(探測到障礙物)或“0”(無障礙)發送至計算機的對應位.四個緩沖器狀態分別用二進制表示如圖1所示.紅外傳感器使用紅外LED(發光二極管)，機器人向周圍發送紅光線.如果紅光線被反射回機器人，則晶體管電路可檢測到，推測附近有物體.5個紅外傳感器分別相隔45°度裝在機器人前面，如圖2所示.編碼的數字用來表示紅外傳感器的狀況.機器人右邊的傳感器是二進制數字中最小的.每個傳感器按順時針旋轉進行配位.攝像頭可用于探測機器人與物體之間的距離，為機器人提供圖像以供分析.GPS用來確定機器人和目標點的位置，指南針確定機器人的當前方向.

2 局部路徑規劃算法設計

2.1 基本兩點法的設計思路

兩點法的基本思想是在全局路徑規劃的基礎上，機器人首先通過衛星定位確定機器人的當前位置.假設A點為機器人的出發點，B點為終點.然后利用裝在機器人周圍的傳感器感知障礙物和目標點的位置信息.在沒有檢測到障礙物存在時，機器人沿著起點和終點的直線前進.在檢測到障礙存在時，機器人會確定子目標點C的位置，然后沿直線朝著C點運動.到達C點后再將C點當作機器人的新的起點，檢測到CB之間有障礙物，再確定子目標點D的位置.到達D點后再將D點當作機器人的新的起點，尋找直線DB之間的無障礙路徑，以此類推，直到機器人到達最終需要到達的點[7]，如圖1所示.

圖1 基本的兩點法示意圖Fig.1 A schematic diagram of the basic two-point method

2.2 改進后的兩點法的設計思路

該算法首先利用GPS和指南針獲取移動機器人當前位置(Rx,Ry)、機器人當前方向CH和目標點的位置(Tx,Ty)，建立坐標系如圖2所示.

圖2 機器人面向信標旋轉角度Fig.2 The rotation angle of robot oriented beacon

則機器人橫坐標與目標之差為

dX=Tx-Rx

(1)

機器人縱坐標與目標之差為

dY=Ty-Ry

(2)

機器人和目標之間的距離R為

(3)

水平軸和機器人中心與目標中心連線之間所形成的角度為

TA=π-arctan(dX/dY)

(4)

此角度用于計算需要旋轉的方向和度數dA，可使機器人朝向目標.指南針的基準方向為北，是360°角，以東向為基準測量的機器人角度值TA是±360°角，機器人通常認為東向為0°，為使機器人上的指南針能被機器人識別，故將TA轉換為以北為基準，再加上90°，使TA準換為指南針指向.再減去機器人上指南針指向的角度，就是機器人朝向目標需要旋轉的角度dA，該角度為

dA=SA×180/π+90-CH

(5)

改進后的兩點法的原理是首先利用GPS確定機器人和目標點的當前位置，分析機器人面向目標點應旋轉的角度，然后用傳感器確定機器人前進路徑上是否有障礙物的存在.機器人在未遇到障礙物之前沿出發點與目標點之間的直線向目標點前進[8]，檢測到障礙物之后，先確定此時機器人的方向，機器人在此方向的基礎上再通過向順時針和逆時針旋轉一定角度，判斷沿障礙物左側還是右側前進的路徑更優，然后沿確定好的最優路徑前進，邊行駛邊檢測是否有障礙物，調整機器人前進方向.若檢測到機器人左邊有障礙物，則向右隨機旋轉0°～135°；若檢測到機器人右邊有障礙物，則向左隨機旋轉0°～135°，防止機器人陷入死區.在單個障礙物環境中，前進路徑中當機器人上的攝像頭看到目標點時，機器人沿直線行駛向目標點.在離散障礙物群中，機器人將恰好感知到第二個障礙物的點看做起點，在起點和目標點之間用兩點法重新進行路徑規劃，依次類推直到安裝在機器人上的攝像頭看到目標點，則機器人沿直線行駛向目標點.機器人在每個障礙區存在的局部環境中找到局部最優路徑，綜合起來即可以找到局部最優路徑.

如圖3所示，為機器人遇到某個不規則障礙物局部最優路徑選擇的算法分析.X為起點，Y為目標點，假設起始點與目標點之間的連線XY與水平線之間的夾角為α.若XY上有障礙物存在，沿逆時針方向旋轉角度θ，得到XY1.若XY1上也有障礙物，由線段XY1沿順時針方向旋轉2θ，得到XY2，以此類推.最先得到的無障礙物的直線，說明那個方向的障礙物繞行路徑最短.故機器人返回到與水平線之間的夾角為α的朝向，用緩沖器和紅外傳感器感應障礙物繞其確定好的方向前進.在前進過程中用攝像頭隨時感應判斷目標點，一旦緩沖器和紅外傳感器未感應到障礙物存在，并且攝像頭看到目標點，則沿障礙物前進沿用兩點法確定好的直線駛向目標點，在距目標點較近處停下來，防止機器人與目標點相撞.改進后的兩點法算法適合起始點和目標點相距相對較遠，且障礙物邊長在機器人傳感器都能檢測到的范圍內.

圖3 機器人路徑規劃圖Fig.3 The map of robot path planning

2.3 出現的問題及解決方案

表1 最優局部路徑可行性分析
Tab.1 The feasibility analysis of the optimal local path

機器人位置目標位置理論局部路徑實際局部路徑最優局部路徑可行性可得到的局部路徑編號上部上部順時針順時針可行①中部順時針或逆時針逆時針可行②下部逆時針逆時針可行③中部上部順時針順時針可行④中部順時針逆時針不可行⑤下部逆時針逆時針可行⑥下部上部順時針順時針可行⑦中部逆時針順時針不可行⑧下部逆時針逆時針可行⑨

由表1中可得局部路徑編號為①②③④⑥⑦⑨的最優局部路徑可行，利用新的兩點法算法能找到最優路徑，局部路徑編號為⑤⑧的最優局部路徑不可行，說明新的兩點法算法在⑤⑧這種特殊環境下只能找到可行性路徑，因此在上述分析的基礎上對可行路徑進行改進，力求規劃出最優局部路徑.

對⑤⑧兩種特殊環境下的機器人規劃出的可行性局部路徑進行分析，如圖4中(a)(b)所示.利用新的兩點法算法，機器人在圖(a)中，根據理論性分析，機器人距離障礙物上端的距離較長，因此最優路徑是沿順時針方向駛向中間目標點，但是利用新的兩點法算法得出的最優路徑是沿順時針方向前進，因此利用上述算法得出的是可行性局部路徑；圖(b)中利用新的兩點法算法沿順時針方向規劃路徑，根據理論性分析機器人的最優路徑是沿逆時針方向駛向中間目標點，因此規劃出的路徑也是可行性路徑.

(a) (b) (c)圖4 機器人與目標點的位置分布示意圖Fig.4 A schematic diagram of the position distribution of robot and target point

(a)一般環境 (b)特殊環境圖5 兩點法算法流程圖Fig.5 The low chart of two-points method

針對上述環境信息中出現的問題，利用幾何知識進行分析，如圖4(c)所示，虛線圖形為機器人未檢測到障礙物的位置，實線為障礙物恰好被機器人傳感器檢測到的位置，當機器人和目標點位于的障礙物的兩端時，即當直線AC與障礙物的端點相切于M點時，機器人能夠檢測到的障礙物的邊長最長為MNmax.

(6)

在三角形ANM中，

(7)

MN=AN×tanα

(8)

在三角形ABC和ANM中，利用三角形相似定理，

(9)

(10)

根據以上分析過程，針對不同環境信息所設計的算法流程圖如圖5所示.

3 路徑規劃的仿真與實驗

仿真結果表明改進后的兩點法算法算法簡單、可行，充分利用多傳感器融合技術，減小了計算量，能成功規劃出機器人的較優或次優路徑.

(a) 順時針繞行復雜障礙物 (b) 逆時針繞行復雜障礙物 (c) 順時針繞行凹形障礙物

(d) 逆時針繞行凹形障礙物 (e) 順時針繞行復雜障礙物 (f) 順時針繞行復雜障礙物圖6 移動機器人路徑仿真結果Fig.6 The simulation results of mobile robot path

4 結束語

本文利用改進后的兩點法對機器人進行了局部路徑規劃.基于RobotBasic仿真平臺，對所設計的規劃算法進行了仿真.在一般的復雜環境中，能規劃出相對較優的路徑，尤其適合當起始點和目標點距離相對較遠、障礙物較小和數量較多的情景.針對在特殊環境信息下只能規劃出可行性路徑的問題，利用幾何知識對該算法進行了改進.該方法簡單易懂，計算量少，解決了機器人在路徑規劃中存在的死區、在陷阱區容易左右徘徊以及在特殊環境信息只能規劃出可行性路徑的問題.仿真結果表明，改進后的兩點法算法能有效規劃出不同環境下機器人躲避障礙的局部最優路徑.

[1] PARK J H,HUH U Y.Local path planning for mobile robot using artificial neural network-Potential field algorithm[J].Transactions of the Korean Institute of Electrical Engineer,2015,64(10):1 479-1 485.

[2] YU J J, DU H W,WANG G W,ed al. Research about local path planning of moving robot based on improved artificial potential field[C]//2013 25th Chinese Control and Decision Conference.Beijing:IEEE Computer Society,2013:2 861-2 865.

[3]蔡曉慧，李艷君，吳鐵軍.基于智能算法的移動機器人路徑規劃研究[D].杭州：浙江大學，2007.

[4]林正鵬，關新平.多移動機器人路徑規劃算法及實驗研究[D].秦皇島：燕山大學，2013.

[5]WANG M, LIU J N K.Fuzzy logic based robot path planning in unknown environment[C]//International Conference on Machine Learnning and Cybernetics.Hong Kong: Institute of Electrical and ElectronicsEngineers Computer Society,2005:813-818.

[6] BLANKENSHIP J,MISHAL S.機器人編程設計與實現[M].卜遲武，唐慶菊,譯.北京：科學出版社，2010:23-124.

[7]李彩虹，張子間.基于兩點法的機器人路徑規劃[J].山東理工大學學報(自然科學版)，2005,19(1):17-20.

[8]康亮，趙春霞，郭劍輝.未知環境下改進的基于BUG算法的移動機器人路徑規劃[J].系統仿真學報，2009,21(17):5 414-5 422.

[9]顧德祥.ZKRT-300型機器人的RobotBasic編程與控制[J].電子世界，2013(24):242-243.

[10]朱映輝.RobotBasic應用于人工智能課程的實踐教學研究[J].現代計算機(專業版)，2012(3):23-25.

[11] UEYAMA T, FUKUDA T. Cooperative search using genetic algorithm based on local information - path planning for structure configuration of cellular robot[C]//1993 International Conference on Intelligent Robots and Systems. Japan:Publ by IEEE,1993:1 110-1 118.

Researchonlocalpathplanningalgorithmforthemobilerobotbasedontwo-dotmethod

SONG Li , LI Cai-hong, ZHU Bao-yan, WANG Xiao-yu

(School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, China)

This paper proposed an improved two-point method for the local path planning of the mobile robot for solving the tradition problems in unknown environment, such as dead zone or trap area. In the path planning process, the rotation angle of the robot target oriented is firstly determined by two-point method, then the path after encountering obstacles is judged in the forward path,and finally the optimal or sub-optimal planning path is derived in different environmental information. In the process of moving forward, the robot only needs to deal with the sensor data in the current state instead of the whole complex environmental information, which saves the storage space of the robot and improves the efficiency of the planning. Finally, the RobotBasic simulation platform is used to simulate the derived algorithm.The simulation results show that the algorithm is effective and reliable, and can adapt to the unknown local environment information.

mobile robot; local path planning; two-dot method; RobotBasic

2016-12-04

國家自然科學基金項目(61473179)；山東省自然科學基金項目(ZR2014FM007)

宋莉, 女, 18369905833@163.com;

李彩虹, 女, lich@sdut.edu.cn

1672-6197(2018)01-0010-05

TP242

A

(編輯：劉寶江)