CN110865642A - A Path Planning Method Based on Mobile Robot - Google Patents

Abstract

The invention discloses a path planning method based on a mobile robot, which comprises the following steps: based on a polygonal obstacle plane model, utilizing Q-IGA to search the most appropriate control point P in a collaborative mode to serve as a control point of a Bezier curve, and utilizing the control point to generate an optimal path; calculating the difference between different paths in the population at each iteration, and adding a judgment criterion for operator selection for optimization to ensure the diversity of feasible solutions in the population; and constructing a fitness function considering the distance of the obstacle, the turning angle and the size of the robot, wherein the optimization target is the maximum fitness function value. The method avoids the problem of complicated steps caused by the fact that the optimal path is obtained by utilizing the Bezier curve to directly fit and search in the robot path planning, ensures that the path planning process is efficiently completed, and has short time and higher path planning efficiency.

Description

Translated fromChinese

一种基于移动机器人的路径规划方法A Path Planning Method Based on Mobile Robot

技术领域technical field

本发明涉及人工智能领域，尤其涉及一种基于移动机器人的路径规划方法。The invention relates to the field of artificial intelligence, in particular to a path planning method based on a mobile robot.

背景技术Background technique

随着计算机技术、控制理论、传感器技术和人工智能等众多交叉学科的发展成熟，自导航机器人技术得到快速发展，各式各样的机器人被应用于科学研究、工业生产、家居生活等众多领域^[1]。自导航机器人技术不仅是移动机器人完成高难度任务的基石，也是机器人智能化成熟的重要标志^[2]。控制自导航机器人运动的算法^[3]主要由定位算法、导航控制算法及路径规划算法三部分组成。在路径搜索过程中安全避障是机器人顺利完成任务的前提，因此路径规划方法的优劣对机器人作业具有重要影响。路径规划的目的是寻找一条从起始点到目标点的无碰撞最优路径。目前，路径规划技术的主要研究成果包括：传统方法，智能仿生学方法以及基于搜索的方法。With the development and maturity of many interdisciplinary subjects such as computer technology, control theory, sensor technology and artificial intelligence, self-navigation robot technology has developed rapidly, and various robots have been used in scientific research, industrial production, home life and many other fields^{[ 1]} . Self-navigation robot technology is not only the cornerstone of mobile robots to complete difficult tasks, but also an important symbol of intelligent and mature robots^[2] . The algorithm for controlling the motion of self-navigating robot^[3] is mainly composed of three parts: positioning algorithm, navigation control algorithm and path planning algorithm. In the process of path search, safe obstacle avoidance is the premise for the robot to successfully complete the task, so the pros and cons of the path planning method have an important impact on the robot operation. The purpose of path planning is to find a collision-free optimal path from the starting point to the target point. At present, the main research results of path planning technology include: traditional methods, intelligent bionic methods and search-based methods.

传统的路径规划方法已被广泛研究。许斯军等人将可视图法^[4-5]用于机器人路径规划，把机器人当作一个质点，将起始点、终点以及障碍物的所有顶点用直线相连，然后采用特定的搜索方法寻找起始点之间的最优路径。这种技术虽然实现简单，但是不够灵活，一旦机器人行进的实际环境发生变化，则需要重新构造可视图；如果环境中障碍物数量较多，则其相应点间的连线就会过多，将导致路径搜索时间较长。栅格法^[6-7]用于机器人路径规划时将环境空间划分为大小相等的连续栅格，然后采用优化算法进行搜索，即可获得一条由一系列栅格组成的路径。栅格法对于障碍物的处理较为简单，并且便于计算机存储、处理与分析。由于该方法将机器人的环境信息用栅格来表达，因此，在路径规划时，栅格的大小将直接影响环境信息存储量、环境分辨率以及规划时间。利用人工势场法^[8]进行路径规划时，障碍物与目标点分别对机器人产生斥力和引力，通过两者的合力来指导机器人的运动，使路径规划过程高效完成。但这种方法存在一定局限性，如存在局部极小点、目标不可到达以及易发生震荡等缺点，使路径规划过程无法稳步进行。Traditional path planning methods have been extensively studied. Xu Sijun et al. used the visual view method^[4-5] for robot path planning, taking the robot as a particle, connecting the starting point, the ending point and all the vertices of the obstacle with a straight line, and then using a specific search method to find the starting point. the optimal path between. Although this technology is simple to implement, it is not flexible enough. Once the actual environment in which the robot travels changes, the visible view needs to be reconstructed; if there are a large number of obstacles in the environment, there will be too many connections between the corresponding points. This results in a longer path search time. The grid method^[6-7] is used for robot path planning to divide the environment space into continuous grids of equal size, and then use the optimization algorithm to search to obtain a path composed of a series of grids. The grid method is relatively simple to deal with obstacles, and is convenient for computer storage, processing and analysis. Since this method expresses the environmental information of the robot with grids, the size of the grid will directly affect the storage capacity of environmental information, the environmental resolution and the planning time during path planning. When using the artificial potential field method^[8] for path planning, obstacles and target points have repulsion and gravitational forces on the robot respectively, and the combined force of the two guides the robot's movement, so that the path planning process can be completed efficiently. However, this method has certain limitations, such as the existence of local minimum points, unreachable targets, and easy oscillations, which make the path planning process unable to proceed steadily.

参考文献references

[1]CaiP,CaiY,Chandrasekaran,I&Zheng,Parallel genetic algorithm basedautomatic path planning for crane lifting in complex environments[J].Automation in Construction,2016,62(1):133-147.[1]CaiP,CaiY,Chandrasekaran,I&Zheng,Parallel genetic algorithm basedautomatic path planning for crane lifting in complex environments[J].Automation in Construction,2016,62(1):133-147.

[2]G.A.Mohammed,M.Hou.Optimization ofactive muscle force-lengthmodels using least squares curve fitting[J].IEEE Trans.Biomed.Eng,2016,63(3):630–635.[2] G.A.Mohammed, M.Hou.Optimization of active muscle force-length models using least squares curve fitting[J].IEEE Trans.Biomed.Eng,2016,63(3):630–635.

[3]R.Cimurs,J.Hwang,I.H.Suh.Bezier curve-based smoothing for pathplanner with curvature constraint[C].IEEE International Conference on RoboticComputing(IRC),2017,pp.241–248.[3]R.Cimurs,J.Hwang,I.H.Suh.Bezier curve-based smoothing for pathplanner with curvature constraint[C].IEEE International Conference on RoboticComputing(IRC),2017,pp.241–248.

[4]许斯军，曹奇英.基于可视图的移动机器人路径规划[J].计算机应用与软件，2011,28(3):220-223.[4] Xu Sijun, Cao Qiying. Path Planning of Mobile Robots Based on Visualization [J]. Computer Applications and Software, 2011, 28(3): 220-223.

[5]黎萍，朱军燕，彭芳.基于可视图与A＊算法的路径规划[J].计算机工程，2014,40(3):193-196.[5] Li Ping, Zhu Junyan, Peng Fang. Path Planning Based on Visual View and A* Algorithm [J]. Computer Engineering, 2014, 40(3): 193-196.

[6]梁嘉俊，曾碧，何元烈.基于改进势场栅格法的清洁机器人路径规划算法研究[J].广东工业大学学报，2016,33(4):30-34.[6] Liang Jiajun, Zeng Bi, He Yuanlie. Research on path planning algorithm of cleaning robot based on improved potential field grid method [J]. Journal of Guangdong University of Technology, 2016,33(4):30-34.

[7]刘晓磊，蒋林，金祖飞.非结构化环境中基于栅格法环境建模的移动机器人路径规划[J].机床与液压，2016，44(17)：1-7.[7] Liu Xiaolei, Jiang Lin, Jin Zufei. Path planning of mobile robots based on grid method environment modeling in unstructured environments [J]. Machine Tools and Hydraulics, 2016, 44(17): 1-7.

[8]Chia-Chia Kao,Chin-Min Lin.Application ofPotential Filed Methodand Optimal Path Planning to Mobile Robot Control[C].2015IEEE InternationalConference on Automation Science and Engineering(CASE),2015:1552-1554.[8] Chia-Chia Kao, Chin-Min Lin. Application of Potential Filed Method and Optimal Path Planning to Mobile Robot Control [C]. 2015 IEEE International Conference on Automation Science and Engineering (CASE), 2015: 1552-1554.

[9]刘晓锋，彭仲仁，张立业，等.面向交通信息采集的无人飞机路径规划[J].交通运输系统工程与信息，2012，12(1):91－97.[9] Liu Xiaofeng, Peng Zhongren, Zhang Liye, et al. Unmanned Aircraft Path Planning for Traffic Information Collection [J]. Transportation System Engineering and Information, 2012, 12(1): 91-97.

[10]Yupei Yan,Yangnin Li.Mobile Robot Autonomous Path Planning Basedon Fuzzy Logic and Filter Smoothing in Dynamic Environment[C]201612WorldCongress on Intelligent Control and Automation(WCICA),2016:1479-1484.[10] Yupei Yan, Yangnin Li.Mobile Robot Autonomous Path Planning Basedon Fuzzy Logic and Filter Smoothing in Dynamic Environment[C]201612WorldCongress on Intelligent Control and Automation(WCICA), 2016:1479-1484.

[11]颜雪松,胡成玉,姚宏等.精英粒子群优化算法及其在机器人路径规划中的应用[J].光学精密工程,2013,21(12):3160-3168.[11] Yan Xuesong, Hu Chengyu, Yao Hong, etc. Elite particle swarm optimization algorithm and its application in robot path planning [J]. Optical Precision Engineering, 2013, 21(12): 3160-3168.

[12]R.Cimurs,J.Hwang,I.H.Suh.Bezier curve-based smoothing for pathplannerwith curvature constraint[C].in:IEEE International Conference onRobotic Computing(IRC),IEEE,2017,pp.241–248.[12]R.Cimurs,J.Hwang,I.H.Suh.Bezier curve-based smoothing for pathplannerwith curvature constraint[C].in:IEEE International Conference onRobotic Computing(IRC),IEEE,2017,pp.241–248.

发明内容SUMMARY OF THE INVENTION

本发明提供了一种基于移动机器人的路径规划方法，本发明避免了利用在机器人路径规划中利用贝塞尔曲线直接拟合搜索得到的最优路径造成步骤繁琐，保证路径规划过程高效完成，详见下文描述：The invention provides a path planning method based on a mobile robot. The invention avoids the cumbersome steps caused by the optimal path obtained by directly fitting and searching by using the Bezier curve in the path planning of the robot, and ensures the efficient completion of the path planning process. See description below:

一种基于移动机器人的路径规划方法，所述方法包括：A path planning method based on a mobile robot, the method comprising:

基于多边形障碍物平面模型，利用Q-IGA协同搜索最合适的控制点P作为贝塞尔曲线的控制点，利用控制点生成最佳路径；Based on the polygonal obstacle plane model, Q-IGA is used to search for the most suitable control point P as the control point of the Bezier curve, and the optimal path is generated by using the control point;

计算每次迭代种群内不同路径之间的差异度，为选择算子增加一个判断准则进行优化，保证种群内可行解的多样性；Calculate the degree of difference between different paths in the population in each iteration, add a judgment criterion to the selection operator for optimization, and ensure the diversity of feasible solutions in the population;

构建考虑障碍物距离、转弯角度、机器人体积的适应度函数，优化目标为适应度函数值最大。Build a fitness function that considers obstacle distance, turning angle, and robot volume. The optimization goal is to maximize the fitness function.

其中，所述利用Q-IGA协同搜索最合适的控制点P作为贝塞尔曲线的控制点具体为：Wherein, the use of Q-IGA to search for the most suitable control point P as the control point of the Bezier curve is specifically:

对多边形障碍物平面模型进行二值化处理，使其相当于具有多个像素点的网格地图；Binarize the polygonal obstacle plane model to make it equivalent to a grid map with multiple pixels;

每一个网格相当于一个基因，其值为0或1，当该网格是贝塞尔曲线的控制点时，其值取为1，否则取为0；Each grid is equivalent to a gene, and its value is 0 or 1. When the grid is the control point of the Bezier curve, its value is 1, otherwise it is 0;

若该网格被障碍物覆盖，则其值设为-1，不可作为控制点。If the grid is covered by obstacles, its value is set to -1 and cannot be used as a control point.

进一步地，所述利用控制点生成最佳路径具体为：Further, the generation of the optimal path using the control points is specifically:

1)连接起始点的一条线段具有0阶连续性；1) A line segment connecting the starting points has 0-order continuity;

2)在两条线段的连接处，用等效切线保证一阶连续性；2) At the junction of the two line segments, use the equivalent tangent to ensure first-order continuity;

3)三阶以上贝塞尔曲线由曲率连续性保证其连续性；3) Bezier curves above the third order are guaranteed by the continuity of curvature;

在满足连续性的条件下，采用三阶贝塞尔曲线生成平滑路径。Under the condition of continuity, a third-order Bezier curve is used to generate a smooth path.

其中，所述为选择算子增加一个判断准则进行优化具体为：Wherein, adding a judgment criterion to the selection operator for optimization is specifically:

在每次迭代中，只有种群的相似性指标低于阈值η时，这些路径保留进入下一次迭代。In each iteration, these paths are reserved for the next iteration only if the similarity index of the population is lower than the threshold η.

本发明提供的技术方案的有益效果是：The beneficial effects of the technical scheme provided by the present invention are:

当机器人执行本方法后，可以得到一条与障碍物保持安全距离且非常平滑的路径，满足对路径合理性的要求；并且所用时间较短，路径规划效率更高，满足实际应用中的多种需要。After the robot executes the method, it can obtain a very smooth path that maintains a safe distance from the obstacle and meets the requirements for the rationality of the path; and the time required is shorter, the path planning efficiency is higher, and it meets various needs in practical applications. .

附图说明Description of drawings

图1为满足连续性的一组三阶贝塞尔曲线的示意图；Fig. 1 is the schematic diagram of a group of third-order Bezier curves satisfying continuity;

图2为转弯角度优化效果图；Figure 2 is the effect diagram of turning angle optimization;

图3为Q-IGA算法流程图；Fig. 3 is the flow chart of Q-IGA algorithm;

图4为参数性能图；Figure 4 is a parameter performance diagram;

其中，(a)为种群规模与路径长度；(b)为种群规模与计算时间；(c)为迭代次数与路径长度；Among them, (a) is the population size and path length; (b) is the population size and calculation time; (c) is the number of iterations and path length;

(d)为迭代次数与计算时间。(d) is the number of iterations and computation time.

图5为不同环境下的仿真结果图。Figure 5 shows the simulation results in different environments.

其中，(a)为不规则障碍物地图；(b)为窄带障碍物地图；(c)为复杂迷宫地图。Among them, (a) is a map of irregular obstacles; (b) is a map of narrow-band obstacles; (c) is a map of complex mazes.

具体实施方式Detailed ways

为使本发明的目的、技术方案和优点更加清楚，下面对本发明实施方式作进一步地详细描述。In order to make the objectives, technical solutions and advantages of the present invention clearer, the embodiments of the present invention are further described in detail below.

传统的路径规划方法或是受到复杂程度的影响，或是受性能的制约，都无法在实际的机器人路径规划中普及使用。目前普遍使用的是基于智能仿生学原理的路径规划方法，并已有很多研究成果证明相较于传统方法，其具有很强的自组织、自学习能力并且具有一定的容错能力。文献^[9]提出一种基于滚动窗口的改进蚁群算法，增强了死角分析和处理能力，克服路径搜索易早熟的问题；文献^[10]利用模糊逻辑算法基于机器人本身配备的传感器实时测量到环境信息，通过预先建立的规则做出决策来完成路径规划。该方法可以避免人工势场法易陷入局部最优的问题，特别是易于处理实时路径规划。颜雪松等^[11]设计了一个更新函数和精英选择机制，使得粒子群算法在减少收敛到局部最优解的可能性的同时，加快了算法收敛速度，并将该改进算法运用到了机器人路径规划中，该改进算法能够获得更优的路径。而遗传算法由于其进化算子具有各态历经性，使其能够有效处理具有概率意义的全局搜索，并且搜索过程不需要限制问题的内在性质，因而在解决路径规划问题方面脱颖而出。并且由于一般方法求解得到的路径多为折线路径，因此利用贝塞尔曲线，B样条曲线进行路径平滑的方法也开始被广泛使用^[12]。The traditional path planning method is either affected by the complexity or restricted by the performance, so it cannot be widely used in the actual robot path planning. At present, the path planning method based on the principle of intelligent bionics is widely used, and many research results have proved that compared with the traditional method, it has strong self-organization, self-learning ability and certain fault tolerance ability. Reference^[9] proposes an improved ant colony algorithm based on rolling windows, which enhances the analysis and processing capabilities of dead spots, and overcomes the problem of premature path search. Reference^[10] uses fuzzy logic algorithm to measure the environment in real time based on the sensors equipped with the robot itself. information, and make decisions through pre-established rules to complete path planning. This method can avoid the problem that artificial potential field method is easy to fall into local optimum, especially it is easy to deal with real-time path planning. Yan Xuesong et al.^[11] designed an update function and an elite selection mechanism, which made the particle swarm algorithm reduce the possibility of converging to a local optimal solution while speeding up the algorithm convergence speed, and applied the improved algorithm to robot path planning. , the improved algorithm can obtain a better path. The genetic algorithm, because its evolution operator is ergodic, can effectively deal with the global search with probabilistic significance, and the search process does not need to limit the intrinsic nature of the problem, so it stands out in solving the path planning problem. And because the path obtained by the general method is mostly a polyline path, the method of using Bezier curve and B-spline curve to smooth the path has also begun to be widely used^[12] .

虽然目前各种优化方法克服了遗传算法用于路径规划时固有的一些缺点，例如：提升了其对新空间的探索能力以防止其过早收敛到局部最优解；降低复杂度以防止其在个体数量较多时计算效率过低。然而，对于应用在实际生产生活环境中的机器人路径导航系统，很多时候不一定希望最优结果是上述方法中所描述的最短路径。相对地，更希望得到一条“合理”的路径。在这里，合理的路径被定义为这样一条路径：它既没有穿过障碍物，也不会紧紧贴着障碍物行进，并且尽可能少的做出大角度的转弯，在满足上述条件的前提下，使路程尽可能最短。Although various optimization methods have overcome some inherent shortcomings of genetic algorithms for path planning, such as: improving their ability to explore new spaces to prevent them from prematurely converging to local optimal solutions; reducing complexity to prevent them from When the number of individuals is large, the computational efficiency is too low. However, for the robot path navigation system applied in the actual production and living environment, it is not always expected that the optimal result is the shortest path described in the above method. On the contrary, it is more desirable to obtain a "reasonable" path. Here, a reasonable path is defined as a path that neither passes through obstacles nor travels closely to obstacles, and makes as few large-angle turns as possible, on the premise that the above conditions are met to make the distance as short as possible.

因此，针对上述问题与需求，本发明提出一种利用Q-IGA动态拟合贝塞尔曲线的路径规划方法，该方法避免了在机器人路径规划中利用贝塞尔曲线直接拟合搜索得到的最优路径造成步骤繁琐，保证路径规划过程高效完成。并且通过在遗传算法的选择算子中利用Q值检验法的思想判断种群内解方案的多样性，去掉相似度较高的解，增强其勘探能力，使路径搜索效率提高。Therefore, in view of the above problems and requirements, the present invention proposes a path planning method using Q-IGA to dynamically fit Bezier curves. The optimal path causes cumbersome steps to ensure the efficient completion of the path planning process. And by using the Q-value test method in the selection operator of the genetic algorithm to judge the diversity of the solutions within the population, remove the solutions with higher similarity, enhance its exploration ability, and improve the efficiency of path search.

同时本发明通过修正适应度函数公式，加入除路径长度外的其他代价因素，使生成的路径满足前文所述对路径合理性的要求。仿真结果证明Q-IGA算法相较于改进人工势场法和混合遗传算法可以得到与障碍物保持一定安全距离的平滑路径且计算效率更高。在机器人应用中，该方法为避免能量耗竭提供了一种有效的途径，特别是在动态资源有限的机器人应用中。At the same time, the present invention modifies the fitness function formula and adds other cost factors except the path length, so that the generated path satisfies the above-mentioned requirements on the rationality of the path. The simulation results show that the Q-IGA algorithm can obtain a smooth path that maintains a certain safe distance from obstacles and has higher computational efficiency than the improved artificial potential field method and the hybrid genetic algorithm. In robotic applications, this method provides an efficient way to avoid energy exhaustion, especially in robotic applications with limited dynamic resources.

实施例1Example 1

1、环境建模1. Environment modeling

机器人行进的环境为一个二维平面空间，平面中的障碍物设置为静态、随机和已知的任意不规则多边形，其顶点(x,y)由环形列表表示。与栅格法相比，该方法易于解决复杂的环境信息问题，且占用的资源较少。The environment in which the robot travels is a two-dimensional plane space, and the obstacles in the plane are set as static, random and known arbitrary irregular polygons, and its vertices (x, y) are represented by a circular list. Compared with the grid method, this method is easy to solve complex environmental information problems and takes up less resources.

2、动态并行拟合策略2. Dynamic parallel fitting strategy

在以往的研究中，利用贝塞尔曲线平滑路径的过程是一个独立的过程，即在产生最优路径后再用贝塞尔曲线进行静态拟合，这样会增加计算步骤使算法繁琐。因此利用Q-IGA协同搜索最合适的控制点P作为贝塞尔曲线的控制点，利用选出的控制点可生成较短的最佳路径。In previous research, the process of smoothing the path using Bezier curve is an independent process, that is, after generating the optimal path, use Bezier curve to perform static fitting, which will increase the calculation steps and make the algorithm cumbersome. Therefore, Q-IGA is used to search for the most suitable control point P as the control point of the Bezier curve, and the selected control point can be used to generate a shorter optimal path.

本发明方法中建立的环境模型为多边形障碍物平面模型，所以首先对其进行二值化处理，使其相当于具有多个像素点的网格地图。每一个网格相当于一个基因，其值可以为0或1，当该网格是贝塞尔曲线的控制点时，其值取为1，当该网格不是贝塞尔曲线的控制点时，其值取为0。若该网格被障碍物覆盖，则其值设为-1，不可作为控制点。The environment model established in the method of the present invention is a polygonal obstacle plane model, so it is first subjected to binarization processing to make it equivalent to a grid map with a plurality of pixel points. Each grid is equivalent to a gene, and its value can be 0 or 1. When the grid is a control point of a Bezier curve, its value is 1, and when the grid is not a control point of a Bezier curve , and its value is set to 0. If the grid is covered by obstacles, its value is set to -1 and cannot be used as a control point.

因此遗传算法初始种群内的每个染色体编码方式为二进制编码，基因值为0或1即代表路径点是不是待选控制点。若路径穿过障碍物，即穿过值为-1的网格点，则此路径点会在后续的遗传操作中通过避障操作被移除。在路径规划过程中保证路径的连续性十分重要，在此定义低阶连续性准则如下：Therefore, the coding method of each chromosome in the initial population of the genetic algorithm is binary coding, and the gene value is 0 or 1, which means whether the path point is a control point to be selected. If the path passes through an obstacle, that is, through a grid point with a value of -1, this waypoint will be removed by the obstacle avoidance operation in the subsequent genetic operation. It is very important to ensure the continuity of the path in the path planning process. Here, the low-order continuity criterion is defined as follows:

1)连接起始点的一条线段具有0阶连续性。1) A line segment connecting the starting points has 0-order continuity.

2)在两条线段的连接处，用等效切线保证一阶连续性。2) At the junction of two line segments, use the equivalent tangent to ensure first-order continuity.

3)三阶以上贝塞尔曲线由曲率连续性保证其连续性。3) Bezier curves above the third order are guaranteed by the curvature continuity.

考虑到计算复杂度，在满足连续性的条件下，贝塞尔曲线的阶次越低越好。本发明采用三阶贝塞尔曲线生成平滑路径，三阶贝塞尔曲线定义如下：Considering the computational complexity, under the condition of continuity, the lower the order of the Bezier curve, the better. The present invention uses a third-order Bezier curve to generate a smooth path, and the third-order Bezier curve is defined as follows:

Q(t)＝B₀(1-t)³+3B₁(1-t)²t+3B₂(1-t)²+B₃t³Q(t)=B₀ (1-t)³ +3B₁ (1-t)² t+3B₂ (1-t)² +B₃ t³

其中，B₀等为得到三阶贝塞尔曲线所需的4个控制点坐标。Among them, B₀ and so on are the coordinates of the four control points required to obtain the third-order Bezier curve.

3、优化选择算子增加种群适应性3. Optimize selection operator to increase population adaptability

在Q-IGA中，依据遗传算法基本步骤，首先随机产生一个种群，它包含S条染色体，每条染色体为一个路径规划方案，染色体的结构可以表示为x_s＝{u₁，u₂，....，u_P}。优化算法的问题之一是求解过程具有很强的随机性，这导致迭代结果易损失多样性。In Q-IGA, according to the basic steps of the genetic algorithm, a population is randomly generated, which contains S chromosomes, each chromosome is a path planning scheme, and the structure of chromosomes can be expressed as x_s = {u₁ , u₂ , . ..., u_P }. One of the problems of optimization algorithms is that the solution process has strong randomness, which leads to the easy loss of diversity in the iterative results.

为提高遗传算法生成解的多样性，本发明对选择算子进行优化。通过计算每次迭代种群内不同路径方案之间的差异度，为选择算子增加一个判断准则，保证种群内可行解的多样性。算法设置的判断准则为：In order to improve the diversity of solutions generated by the genetic algorithm, the present invention optimizes the selection operator. By calculating the degree of difference between different path schemes in the population in each iteration, a judgment criterion is added to the selection operator to ensure the diversity of feasible solutions in the population. The judgment criteria set by the algorithm are:

在每次迭代中，只有种群的相似性指标低于阈值η时，这些方案才可保留进入下一次迭代。η的初始值为(0,1)中的一个随机值。在迭代过程中，η的值从初始值线性下降到0。在算法模型中，使用衰减因子w＝0.99代表衰减率，即η的衰减公式为：In each iteration, these schemes can be retained for the next iteration only if the similarity index of the population is lower than the threshold η. The initial value of η is a random value in (0,1). During the iteration, the value of η decreases linearly from the initial value to 0. In the algorithm model, the decay factor w=0.99 is used to represent the decay rate, that is, the decay formula of η is:

η_t+1＝ωη_tη_t+1 =ωη_t

当t趋近于无穷时，η趋近于0。As t approaches infinity, η approaches 0.

因此，优化的选择过程拒绝相同和过于相近的解决方案同时存在，有助于遗传算法避免局部最优问题，增强其勘探能力。在每一次迭代中，η都会减小，这意味着在搜索后期趋近于最优解时迭代得到的路径方案越来越相似，即在搜索开始和结束之间得到了平衡。Therefore, the optimized selection process rejects the coexistence of the same and too close solutions, which helps the genetic algorithm to avoid the local optimum problem and enhance its exploration ability. In each iteration, η decreases, which means that the iteratively obtained path schemes are more and more similar when approaching the optimal solution in the later stage of the search, that is, a balance is obtained between the beginning and the end of the search.

本发明方法借鉴Q值检验法思想判断种群的多样性。根据路径模型，定义两个解决方案x1，x2之间的q值为：

The method of the invention judges the diversity of the population by drawing on the idea of the Q value test method. According to the path model, the q value between two solutions x1, x2 is defined as:

其中，N¹¹代表两染色体中对应位置基因值都为1的数量，N⁰⁰代表两染色体中对应位置基因值都为0的数量；N⁰¹代表x₁染色体基因值为0的位置对应x₂基因值为1的数量；N¹⁰代表x₁染色体基因值为1的位置对应x₂基因值为0的数量。Among them, N¹¹ represents the number of genes whose corresponding positions in the two chromosomes are both 1, N⁰⁰ represents the number of genes whose corresponding positions in the two chromosomes are both 0; N⁰¹ represents the position of the x₁ chromosome whose gene value is 0 corresponds to the x₂ gene The number of values of 1; N¹⁰ represents the number of positions where the x₁ chromosome has a gene value of 1 corresponding to the number of x₂ genes with a value of 0.

若两个染色体x₁＝[1 1 0 0 1 1 0 0 1 0]，x₂＝[1 0 1 0 1 0 1 0 1 1]，则：If two chromosomes x₁ =[1 1 0 0 1 1 0 0 1 0], x₂ =[1 0 1 0 1 0 1 0 1 1], then:

则种群相似性Q为计算得到的所有个体两两之间q值的平均值，即：Then the population similarity Q is the average of the calculated q values between all individuals, namely:

4、优化适应度函数4. Optimize the fitness function

遗传算法的另一重要步骤是计算个体适应度值。从常识可以得知，在相似的运动环境中，机器人的运动能耗与运动距离成正相关，即运动距离越长，耗能越多。传统的遗传算法通过适应度函数判断路径长短，可以保证机器人在完成运动目标的前提下尽可能缩短机器人的运动距离。然而这样得到的路径有可能与障碍物距离过近、或出现耗能较大的大角度转弯。因此在本发明方法中，适应度函数将转弯角度、机器人体积也作为评价因素，优化目标为使重新定义的适应度函数值最大。Another important step of the genetic algorithm is to calculate the individual fitness value. It can be known from common sense that in a similar motion environment, the motion energy consumption of the robot is positively correlated with the motion distance, that is, the longer the motion distance, the more energy consumption. The traditional genetic algorithm judges the length of the path through the fitness function, which can ensure that the robot's movement distance can be shortened as much as possible on the premise of completing the movement target. However, the path obtained in this way may be too close to the obstacle, or there may be a large-angle turn that consumes a lot of energy. Therefore, in the method of the present invention, the fitness function takes the turning angle and the robot volume as evaluation factors, and the optimization goal is to maximize the value of the redefined fitness function.

(1)距离因素(1) Distance factor

在遗传算法完成控制点搜索后，路径长度D即可表示为：After the genetic algorithm completes the control point search, the path length D can be expressed as:

其中，n为控制点的数量，d(p_i,p_i+1)为相邻两个控制点之间的距离。Among them,_n is the number of control points, and d(pi,pi₊₁ ) is the distance between two adjacent control points.

路径长度可以由贝塞尔曲线的积分来计算：The path length can be calculated by integrating the Bezier curve:

(2)机器人的体积：(2) The volume of the robot:

在理想环境中，移动机器人被视为一个粒子，并不考虑其体积对行进过程的影响。然而，在实际应用中，机器人在运动过程中不仅要避开障碍物，而且应与障碍物保持一定的安全距离。在经典的路径规划算法中，为保证最优路径为最短路径，常常会导致机器人紧靠障碍物或墙壁等限制情况出现。In an ideal environment, the mobile robot is treated as a particle, and the effect of its volume on the traveling process is not considered. However, in practical applications, the robot should not only avoid obstacles, but also keep a certain safe distance from the obstacles during the movement. In the classical path planning algorithm, in order to ensure that the optimal path is the shortest path, it often causes the robot to be close to obstacles or walls and other constraints.

因此本发明方法对经典适应度函数计算方法做出优化。对于无法穿过的障碍物，用+∞来描述其代价。这样，障碍物附近某个点对于机器人运动的代价定义为：Therefore, the method of the present invention optimizes the classical fitness function calculation method. For impenetrable obstacles, use +∞ to describe the cost. In this way, the cost of a point near the obstacle for the robot motion is defined as:

其中，k₁为归一化系数，d是机器人中心与障碍物之间的距离，d₀是机器人的外形尺寸，σ为高斯函数的宽度。Among them, k₁ is the normalization coefficient, d is the distance between the robot center and the obstacle, d₀ is the outer dimension of the robot, and σ is the width of the Gaussian function.

可以看出，在与障碍物之间的距离小于机器人的尺寸时，其代价为+∞，此时适应度函数值为0，即认为机器人在这种条件下会与障碍物发生碰撞；在与障碍物的距离大于机器人的尺寸时，其代价值呈高斯函数衰减，使其在一定范围内保证机器人尽可能远离障碍物。It can be seen that when the distance to the obstacle is less than the size of the robot, the cost is +∞, and the fitness function value is 0 at this time, that is, it is considered that the robot will collide with the obstacle under this condition; When the distance of the obstacle is greater than the size of the robot, its cost value is attenuated by a Gaussian function, making it possible to keep the robot as far away from the obstacle as possible within a certain range.

(3)机器人的转弯角度(3) The turning angle of the robot

路径转角过大或过于频繁不仅影响机器人的工作效率，在运动距离同等的条件下，还会消耗更多的能量。虽然随着锂电池等可充电电池技术近年来的快速发展和成熟，机器人的续航时间越来越长，但是充电时间长等缺点仍然限制着机器人的循环使用效率。因此，本发明将转弯角度因素引入适应度函数，每个拐点因转弯所带来的代价定义为：Too large or frequent path rotation not only affects the work efficiency of the robot, but also consumes more energy under the condition of the same moving distance. Although with the rapid development and maturity of rechargeable battery technologies such as lithium batteries in recent years, the battery life of robots is getting longer and longer, but the shortcomings of long charging time still limit the recycling efficiency of robots. Therefore, the present invention introduces the turning angle factor into the fitness function, and the cost of each turning point due to turning is defined as:

其中，α为转弯角度，k₂为归一化系数，优化后的路径拐弯次数更少，且转角更加平滑。Among them, α is the turning angle, and k₂ is the normalization coefficient. The optimized path has fewer turns and smoother turning angles.

综合路径长度因素、机器人自身体积和机器人转弯角度带来的代价，适应度函数最终被修正为：

Considering the path length factor, the robot's own volume and the cost of the robot's turning angle, the fitness function is finally revised as:

其中，D为路径长度，R₁(n)为机器人体积代价，R₂(n)为机器人转弯角度代价，算法的迭代目标即使新定义的适应度函数值达到最大。Among them, D is the path length, R₁ (n) is the robot volume cost, and R₂ (n) is the robot turning angle cost. The iterative goal of the algorithm is even if the newly defined fitness function value reaches the maximum value.

5、路径搜索5. Path search

完成对遗传算法选择算子和适应度函数的改进之后，即可利用上述优化后的Q-IGA算法搜索路径点并动态搜索确定贝塞尔曲线的控制点，使路径搜索与路径平滑过程并行执行。After completing the improvement of the selection operator and fitness function of the genetic algorithm, the above optimized Q-IGA algorithm can be used to search for path points and dynamically search to determine the control points of the Bezier curve, so that the path search and path smoothing process are executed in parallel. .

实施例2Example 2

在进行仿真实验前，首先需要设置合理的参数使算法得到最优解。图4中(a)，(b)，(c)，(d)分别为种群规模与路径长度、计算时间，迭代次数与路径长度、计算时间的关系。综合4个性能图可知，随着种群规模和迭代次数的增加，算法的执行时间不断增加，基本呈现线性上涨的趋势，符合运行时间与算法复杂度成正比的关系；而随着种群规模和迭代次数的增加，路径长度下降一段时间之后，在某个节点以后趋于平稳基本不变。由图(a)和图(c)可知，当种群规模在110，迭代次数在150次以后路径长度达到稳定，因此对于第一幅地图，在尽量保持路径长度较短且计算时间也较短的条件下，设置种群规模为110，迭代次数为160。其余两幅地图的参数选择方法与第一幅地图原理相同，在此不做赘述。Before the simulation experiment, it is necessary to set reasonable parameters to get the optimal solution of the algorithm. (a), (b), (c), and (d) in Figure 4 are the relationship between population size, path length, and computation time, and the number of iterations, path length, and computation time, respectively. Based on the four performance graphs, it can be seen that with the increase of the population size and the number of iterations, the execution time of the algorithm continues to increase, basically showing a linear upward trend, which is in line with the relationship between the running time and the algorithm complexity; As the number of times increases, the length of the path decreases for a period of time, and tends to be stable and basically unchanged after a certain node. As can be seen from Figures (a) and (c), when the population size is 110 and the number of iterations is 150, the path length becomes stable. Therefore, for the first map, try to keep the path length as short as possible and the calculation time as short as possible. Under the conditions, set the population size to 110 and the number of iterations to 160. The parameter selection method of the other two maps is the same as that of the first map, and will not be repeated here.

本发明设置了三种地图环境进行仿真实验，分别为不规则障碍物环境(大小为20*20)，窄带障碍物环境(大小为30*30)和复杂迷宫图环境(大小为45*45)。初始环境由一个环形坐标系表示，阴影部分为障碍物。将改进人工势场法和混合遗传算法作为对比算法，每种地图环境下都验证了三种算法的性能。如图5展示了三种算法产生的路径效果，它们均能得到一条从起始点到目标点可以避开障碍物的路径，且改进工势场法和混合遗传算法产生的路径在某些环境下是最短的，但是均有较大的转角，某些路径点由于没有考虑机器人自身体积带来的影响，因此距离障碍物过近，增加了机器人与障碍物发生摩擦的风险。本发明方法产生的路径虽然不是最短路径，但达到了对机器人路径规划合理性的要求，它可以完成避障并根据机器人的体积与障碍物保持一定的距离，同时路径更加平滑，更符合机器人在实际工程应用中对路径的要求。The present invention sets up three map environments for simulation experiments, namely irregular obstacle environment (size is 20*20), narrow-band obstacle environment (size is 30*30) and complex maze map environment (size is 45*45) . The initial environment is represented by a circular coordinate system, shaded by obstacles. The improved artificial potential field method and the hybrid genetic algorithm are used as comparison algorithms, and the performance of the three algorithms is verified in each map environment. Figure 5 shows the path effects generated by the three algorithms, all of which can obtain a path from the starting point to the target point that can avoid obstacles, and the paths generated by the improved potential field method and the hybrid genetic algorithm are in some environments. It is the shortest, but both have large turning angles. Some path points are too close to obstacles because they do not consider the influence of the robot's own volume, which increases the risk of friction between the robot and obstacles. Although the path generated by the method of the invention is not the shortest path, it meets the requirements for the rationality of the robot path planning. It can complete obstacle avoidance and maintain a certain distance from the obstacle according to the volume of the robot. Requirements for paths in practical engineering applications.

本发明所提出方法旨在得到合理路径的同时提高算法的搜索效率，因此对混合遗传算法和Q-IGA(本方法)两种算法的时间性能进行了考察。从表1中可以看出，Q-IGA算法在时间上比混合遗传算法短，在获得最优路径的同时有效提高了算法的时间效率。The method proposed in the present invention aims to obtain a reasonable path and at the same time improve the search efficiency of the algorithm. Therefore, the time performance of the hybrid genetic algorithm and the Q-IGA (this method) algorithm is investigated. It can be seen from Table 1 that the Q-IGA algorithm is shorter in time than the hybrid genetic algorithm, which effectively improves the time efficiency of the algorithm while obtaining the optimal path.

表1各算法时间性能Table 1 Time performance of each algorithm

本发明实施例对各器件的型号除做特殊说明的以外，其他器件的型号不做限制，只要能完成上述功能的器件均可。In the embodiment of the present invention, the models of each device are not limited unless otherwise specified, as long as the device can perform the above functions.

本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。Those skilled in the art can understand that the accompanying drawing is only a schematic diagram of a preferred embodiment, and the above-mentioned serial numbers of the embodiments of the present invention are only for description, and do not represent the advantages or disadvantages of the embodiments.

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。The above are only preferred embodiments of the present invention and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within the range.

Claims (4)

Translated fromChinese

1.一种基于移动机器人的路径规划方法，其特征在于，所述方法包括：1. A path planning method based on a mobile robot, wherein the method comprises:基于多边形障碍物平面模型，利用Q-IGA协同搜索最合适的控制点P作为贝塞尔曲线的控制点，利用控制点生成最佳路径；Based on the polygonal obstacle plane model, Q-IGA is used to search for the most suitable control point P as the control point of the Bezier curve, and the optimal path is generated by using the control point;计算每次迭代种群内不同路径之间的差异度，为选择算子增加一个判断准则进行优化，保证种群内可行解的多样性；Calculate the degree of difference between different paths in the population in each iteration, add a judgment criterion to the selection operator for optimization, and ensure the diversity of feasible solutions in the population;构建考虑障碍物距离、转弯角度、机器人体积的适应度函数，优化目标为适应度函数值最大。Build a fitness function that considers obstacle distance, turning angle, and robot volume. The optimization goal is to maximize the fitness function.2.根据权利要求1所述的一种基于移动机器人的路径规划方法，其特征在于，所述利用Q-IGA协同搜索最合适的控制点P作为贝塞尔曲线的控制点具体为：2. a kind of path planning method based on mobile robot according to claim 1, is characterized in that, described utilizing Q-IGA to search for the most suitable control point P as the control point of Bezier curve is specifically:对多边形障碍物平面模型进行二值化处理，使其相当于具有多个像素点的网格地图；Binarize the polygonal obstacle plane model to make it equivalent to a grid map with multiple pixels;每一个网格相当于一个基因，其值为0或1，当该网格是贝塞尔曲线的控制点时，其值取为1，否则取为0；Each grid is equivalent to a gene, and its value is 0 or 1. When the grid is the control point of the Bezier curve, its value is 1, otherwise it is 0;若该网格被障碍物覆盖，则其值设为-1，不可作为控制点。If the grid is covered by obstacles, its value is set to -1 and cannot be used as a control point.3.根据权利要求1所述的一种基于移动机器人的路径规划方法，其特征在于，所述利用控制点生成最佳路径具体为：3. a kind of path planning method based on mobile robot according to claim 1, is characterized in that, described utilizing control point to generate optimal path is specifically:1)连接起始点的一条线段具有0阶连续性；1) A line segment connecting the starting points has 0-order continuity;2)在两条线段的连接处，用等效切线保证一阶连续性；2) At the junction of the two line segments, use the equivalent tangent to ensure first-order continuity;3)三阶以上贝塞尔曲线由曲率连续性保证其连续性；3) Bezier curves above the third order are guaranteed by the continuity of curvature;在满足连续性的条件下，采用三阶贝塞尔曲线生成平滑路径。Under the condition of continuity, a third-order Bezier curve is used to generate a smooth path.4.根据权利要求1所述的一种基于移动机器人的路径规划方法，其特征在于，所述为选择算子增加一个判断准则进行优化具体为：4. a kind of path planning method based on mobile robot according to claim 1, is characterized in that, described is that selecting operator adds a judgment criterion and optimizes specifically:在每次迭代中，只有种群的相似性指标低于阈值η时，这些路径保留进入下一次迭代。In each iteration, these paths are reserved for the next iteration only if the similarity index of the population is lower than the threshold η.

Images