基于两点法的移动机器人局部路径规划算法

宋 莉，李彩虹,朱宝艳，王小宇

(山东理工大学 计算机科学与技术学院，山东 淄博 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

(编辑：刘宝江)