基于极值法的静态路径规划算法

杨晶所 刘子龙

摘要：针对传统路径规划算法在求解静态已知环境下的最优或次优路径时存在转折次数过多、路径复杂等问题，提出一种基于极值法的移动机器人静态路径规划算法。在对环境建模时，采用边界点集描述障碍物不可行区域的轮廓信息；在路径规划过程中，首先判断当前出发点到目的点之间是否有障碍物，然后利用极值法获得转折点，进而得到初步路径，同时为后续利用极值法获取新的转折点提供计算与判断依据。仿真结果证明了该算法的有效性。

关键词：移动机器人；环境建模；静态路径规划；极值法

DOIDOI：10.11907/rjdk.181772

中图分类号：TP312

文献标识码：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.

英文關键词Key Words：mobile robot；environment modeling；static path planning；extreme value method

0 引言

路径规划是移动机器人系统的重要组成部分， 根据对环境信息掌握程度可将其划分为两大类[1]：①基于环境先验完全信息的静态路径规划，又称全局路径规划；②基于传感器检测信息的动态路径规划，又称局部路径规划。静态路径规划过程是根据先验环境信息找出从出发点到目的点中满足一定要求的最优或次优可行路径，它涉及的基本问题是环境建模[2]和路径搜索[3]。

广泛应用于机器人路径规划的栅格法[4]，通过将移动机器人工作的物理空间抽象成以栅格为最小单位的环境地图，将机器人的路径搜索以此为最小移动单位进行路径规划，而路径的变化方向根据栅格位置的不同最多确定8个，即东、南、西、北、东北、西北、东南、 西南[5]方向，因此得到的路径会出现折线多、转折次数多、路径复杂等问题[6]。

本文提出一种基于极值法的路径规划算法。该算法将当前出发点和目的点范围内所有的障碍物边界点距出发点和目的点连线“最远”的点视为极值点，再据此搜索下一个极值点直至无法搜索出符合条件的极值点时，完成路径规划。本文算法给出了一个新的处理路径规划过程思路，即当前的出发点、目的点不一定是原始的出发点、目的点，而是在路径规划过程中一个求解极值点的“分支”上的出发点、目的点，即通过以上一级出发点为出发点、极值点为目的点，或上一级的目的点为目的点、极值点为出发点，不断地更新当前的出发点、目的点。

1 极值法设计思路

在考虑距离最优的前提下，已知静态环境信息，由出发点到目的点的最优可行路径必定是转折次数最少、路程最短的一条路径[7]。在不穿过障碍物及保留安全间距的前提下，上述最优路径必定存在至少一个“紧靠”障碍物的不可行区域边界线的转折点[8]。上述转折点从出发点与目的点构成的直线，本质上是障碍物的不可行区域边界线的点集在该直线上的极值点[9]。将上述极值点作为新的出发点或目的点，与原来的目的点及出发点构成新的出发点、目的点组合。若该起止点组合构成的直线穿过障碍物（即起止点之间有障碍物），则重复上述过程以获得下一个转折点，直至所有线段均符合“避开障碍物”这一条件[10]。如图1所示，出发点A、目的点B、障碍物O以及留有间距d的不可行区域的边界点集S，构成环境模型基本信息。

3 路径规划仿真

基于python仿真语言环境，利用上述算法实现路径规划仿真实验，仿真结果如图11（a）～图11（d）所示。在仿真环境中，机器人的每次路径规划都是基于不同的出发点与目的点（分别用及表示），障碍物的位置、形状也是随机的。

仿真结果表明，对于能大致描述出清晰轮廓特征的环境模型，基于极值法的路径规划算法不依赖于障碍物的具体外形，且规划出的路径能以较少的转折点、简单的路径满足最优或次优路径要求。

4 结语

本文提出基于极值法的移动机器人静态路径规划算法并对其进行了仿真。研究分析表明，该算法优化了求解静态环境下最优或次优路径时转折次数过多、路径复杂等问题。此外，在以边界点集进行环境建模时，其边界点集的密集程度决定环境模型的精度，直接影响到算法的计算时间和最终路径生成结果，即边界点集越密集，环境模型的精度越高，算法计算时间越长，路径规划结果也越接近最优解。

参考文献：

[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].现代制造技术与装备，2010（1）：1-2.

[3] 李晓敏.智能移动机器人全局路径规划及仿真[D].南京：南京理工大学，2004.

[4] 刘晓磊，蒋林，金祖飞，等.非结构化环境中基于栅格法环境建模的移動机器人路径规划[J].机床与液压，2016，44（17）：1-2.

[5] 王娟娟，曹凯.基于栅格法的机器人路径规划[J].农业装备与车辆工程，2009（4）：15-16.

[6] 王红卫，马勇，谢勇，等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报：自然科学版，2010，38（11）：1647-1650.

[7] 禹建丽，李晓燕，王跃明，等.一种基于神经网络的机器人路径规划算法[J].洛阳工学院学报，2001，22（1）：31-34.

[8] 陈卫忠，王庆.基于机器人避障问题的数学模型[J].长春大学学报，2013，23（6）：689-692.

[9] 陈英俏.改进蚁群算法及其在移动机器人路径规划中的研究[D].沈阳：东北大学，2010.

[10] 韦如明.基于强化学习的移动机器人路径规划研究与实现[D].广州：华南理工大学，2015.

[11] 禹建丽，程思雅，孙增圻，等.一种移动机器人三维路径规划优化算法[J].中南大学学报：自然科学版，2009，40（2）：471-477.

[12] 化建宁，赵忆文，王越超.一种新的移动机器人全局路径规划算法[J].机器人，2006，28（6）：593-597.

[13] 王爱民，史庆国，吕晨亮.关于移动机器人路径最优化问题[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] 韩雪.多目标遗传算法在机器人路径规划中的应用[D].哈尔滨：哈尔滨工程大学，2011.

[17] 步立新，罗文钰，冯允成.随机递归算法求解车辆路径问题[J].系统工程理论与实践，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].计算机应用研究，2007，24（3）：181-183.

（责任编辑：杜能钢）