基于BUG理论的平行主线改进算法

马晓辉，丁洪伟，王梦瑶，赵一帆

(1.中国人民武装警察部队昆明市支队，昆明　650220；2.云南大学　信息学院，昆明　650091)



·实 验 技 术·

基于BUG理论的平行主线改进算法

马晓辉1，丁洪伟2，王梦瑶2，赵一帆2

(1.中国人民武装警察部队昆明市支队，昆明650220；2.云南大学信息学院，昆明650091)

基于Pioneer3机器人平台提出一种未知环境中的机器人路径规划的改进算法。在BUG理论的基础上，通过先锋机器人实时读取机器人角度偏差的能力，即时重新规划机器人到达目标点的路线。改进算法缩短了BUG理论中的运动路径，提高了机器人避障的效率。

先锋3；BUG理论；平行主线；算法

机器人路径规划是移动机器人研究的一个重要课题[1]，根据工作环境的不同大致可以分为两种：一种是基于模型的路径规划，其作业环境的全部信息是预知的；另一种是基于传感器的路径规划，作业环境的信息是全部未知或部分未知的[2-3]。基于未知环境的算法有BUG算法、HGVG方法等，但此类算法都存在着一定的不足[4]。本文主要是在BUG理论的基础上，利用先锋3机器人的特点提出了改进算法并进行了仿真实验，以证明改进算法的可行性和有效性。

1　Pioneer3机器人简介

MobileRobots公司常年致力于大学及研究机构的智能机器人系统的研制与开发，先后开发出先锋系列3代(Pioneer3)机器人及面向研究的软件平台系统，如图1所示。Pioneer3机器人具有16个声呐环，有物体检测、距离检测、自动避障、面貌识别、定位以及导航等功能，声呐灵敏度可调，可以为机器人提供360°无缝检测。Pioneer3机器人还为用户提供了丰富的软件系统，包括机器人控制器软件系统和机器人客户端软件系统。在使用系统软件时可以结合机器人的声呐实时读取机器人的方向角度。这也是本文提出的平行主线改进算法得以实现的重要基础和保障。

图1　Pioneer3机器人平台

2　BUG理论

BUG理论[5]是在移动机器人路径规划研究中较早被提出的理论，其主要思想类似于现代定向运动理论中绕过障碍物的方法[6]，即：将起始点与目标点的连接线作为机器人运动的主线(M-line)，开始移动时机器人沿M-line运动，当遇到障碍物时，机器人改变移动策略，沿着障碍物的边缘运动，直至再次回到主线，并且其与终点的距离较前一次离开主线时有所减少时，机器人继续沿主线前进，直至到达终点。

BUG算法简单地将机器人在未知环境中的运动分为“沿墙走”和“沿主线走”两种模式，简单实用，可有效地在二维环境中找到到达目标点的路径。但这种算法会存在冗余，尤其在障碍物不是规则物体的情况下，往往会造成机器人路径的较多冗余[7]。如图2所示，障碍物边缘较为复杂时，障碍物的边缘较为冗长，这样机器人“沿墙走”的路径也会变得很冗长，比直线到达目标点会形成许多不必要的浪费，移动的效率也较低[8]。

图2　BUG理论造成的路径冗余

3　BUG算法的改进和实验仿真

基于BUG算法会在复杂未知环境中造成的路线冗余和Pioneer3机器人自身的特点，本文提出了“平行主线”的改进算法。其基本思想为：机器人开始按照BUG理论的方式产生起点到目标点的主线，并沿主线行走，遇到障碍物后进入“沿墙走”模式，并在沿墙走中实时读取自己的位置角度，当自己的位置与主线平行时，退出“沿墙走”模式，并以此点为起点重新生成主线，并沿新的主线行走直至达到目标点。

如图3所示，Pioneer3机器人在得到目标点位置信息后，先将自己所在坐标设为起点坐标A(XA，YA，θA)，其中XA，YA为二维坐标值，θA为机器人的角度，机器人能够随着移动实时读取偏转的角度。机器人得到指定的目标点B(XB，YB，θB)后，生成一条连接A、B两点的主线(M-line)并计算出主线的斜率k，而后机器人沿主线向目标点移动。当达到点P时，检测到前方有障碍物，机器人按照BUG算法进入“沿墙走”模式，并实时检测自身的方向偏差率k′，k′=tanθ。当机器人移动到点R时，k′和主线斜率k相等，此时，机器人退出“沿墙走”模式，并以点R为新的起点生成新的主线，沿新主线移动至终点B，完成点A到点B的移动。

图3　改进算法原理图

根据几何知识容易得知：在图3中，当构建三角形△QRB时，QR与QB之和明显大于RB，即QR+QB>RB，又因为曲线RQ的长度会大于直线RQ的长度，所以机器人在与主线平行的点退出“沿墙走”模式并重新设定主线的路径会大大缩短，从而提高了机器人运动的效率。由此可以简单判断出，改进算法可以提高机器人移动的效率，达到减少路径的冗余度的目的。

图4　二次遇到障碍物

另外，在复杂环境中运动时机器人可能会二次遇到障碍物[9]，此时只需要再次使用“平行主线策略”，即可以使机器人在顺利到达目标点的同时又缩短移动的距离，减少路径的冗余，达到提高机器人移动效率的目的。如图4所示，当机器人遇到障碍物时执行“平行主线策略”，在斜率与主线相同的点重新规划路径，生成“主线2”并沿其运动，在沿“主线2”运动的过程中再次遇到障碍物，此时机器人调用“沿墙走”模式，直至运动路径平行于“主线2”时，再次执行“平行主线策略”，重新规划直线路径并运动到目标点B，完成既定目标。

为了验证算法的可行性，本文在Matlab平台上进行了实验仿真，仿真结果如图5所示：粗线为机器人的运动轨迹，细线为BUG算法中的主线(M-line)。通过仿真结果可以看出，利用改进算法后机器人少走了部分弯路，并且能够直接到达目标点。表1为在仿真实验中不同障碍物的情况下两种算法的路径长度比较，通过数据也可以明显看到，随着障碍物的增大和复杂性的增加，改进算法能够更有效地减少路径长度，提高机器人的效率。

图5　仿真实验结果

障碍物BUG算法改进算法157.87854.405260.12254.736365.09155.128

4　结束语

本文在先锋3机器人的运行环境中提出了一种基于BUG理论的、在未知环境中的移动机器人路径

规划算法。改进算法根据机器人能实时读取自身运动角度的特性，提前退出BUG算法中的“沿墙走”模式，及时重新规划路径，在能准确到达目标位置的基础上，大大减少了路径的冗余，提高了机器人运动的效率。

[1]都志辉，陈谕，刘鹏.网格计算[M].北京：清华大学出版社，2002.

[2]付岩.智能水下机器人全局及局部路径规划技术研究[D].哈尔滨：哈尔滨工业大学，2004.

[3]李彩虹，李贻斌，范晨.移动机器人动态避障算法[J].山东大学学报：工学版，2007，37(5)： 60-64.

[4] 蔡自兴，贺汉根，陈虹. 未知环境中移动机器人导航控制研究的若干问题[J]. 控制与决策，2002，30(7)：385-390.

[5] LUMDSKY V，STEPANOV A.Path-planning stralegles for a point mobile automation moving amidst unknown obstacles of arbitrary shape[J].Algorithmica，1987，11(2)：403-430.

[6]康亮，赵春霞，郭剑辉.未知环境下基于三次螺线Bug算法的移动机器人路径规划[J].工程图学学报，2010，23(1)：30-38.

[7]KAMON I，RIVLIN E.Sensory based motion planning with global proofs[C]//HIROS’95.Pittsburgh，PA，USA:[s.n.]，1995：435-440.

[8] 禹建丽，ROUMOV V，孙增圻.一种不确定环境下移动机器人避障规划算法[J].机器人，2007，23(3)：201-205.

[9] 席裕庚.动态不确定环境下广义控制问题的预测控制[J].控制理论与应用，2007，17(5)：665-670.

Improved Algorithm Based on the Parallel Main Line of BUG Theory

MA Xiaohui1，DING Hongwei2，WANG Mengyao2，ZHAO Yifan2

(1.Kunming Detachment of Chinese Armed Police Force，Kunming 650220,China;2.School of Information，Yunnan University，Kunming 650091，China)

One of the improved algorithms for robot path planning in an unknown environment is proposed in this paper under the background in Pioneer3 robot platform. Based on the BUG theory and using the ability to read real time deviation of robot angle by pioneer robot，the robot plans a rode to reach the goal point immediately. The improved algorithm reduces the motion path in the BUG theory and improves the efficiency of the robot obstacle avoidance.

Pioneer 3;BUG theory;parallel main line;algorithm

2014-10-12；修改日期: 2014-11-13

国家自然科学基金(6146105)。

马晓辉(1987-)，男，硕士生，主要从事无线传感器网络、移动机器人控制方面的研究。

TP242.6

A

10.3969/j.issn.1672-4550.2016.01.001