CN113219986A - 基于遗传算法和三次样条插值的机器人全局路径规划方法 - Google Patents
基于遗传算法和三次样条插值的机器人全局路径规划方法 Download PDFInfo
- Publication number
- CN113219986A CN113219986A CN202110589621.8A CN202110589621A CN113219986A CN 113219986 A CN113219986 A CN 113219986A CN 202110589621 A CN202110589621 A CN 202110589621A CN 113219986 A CN113219986 A CN 113219986A
- Authority
- CN
- China
- Prior art keywords
- path
- robot
- cubic spline
- path planning
- point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 55
- 230000002068 genetic effect Effects 0.000 title claims abstract description 32
- 238000004422 calculation algorithm Methods 0.000 title claims abstract description 29
- 238000010187 selection method Methods 0.000 claims abstract description 5
- 230000035772 mutation Effects 0.000 claims description 12
- 238000005457 optimization Methods 0.000 claims description 9
- 230000003068 static effect Effects 0.000 claims description 5
- 238000003780 insertion Methods 0.000 claims description 3
- 230000037431 insertion Effects 0.000 claims description 3
- 230000001788 irregular Effects 0.000 claims description 3
- 230000009191 jumping Effects 0.000 claims description 2
- 230000001172 regenerating effect Effects 0.000 claims description 2
- 238000004364 calculation method Methods 0.000 claims 1
- 238000001514 detection method Methods 0.000 abstract description 5
- 230000004888 barrier function Effects 0.000 abstract description 4
- 238000004088 simulation Methods 0.000 abstract description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000013461 design Methods 0.000 description 2
- 230000007613 environmental effect Effects 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 238000005094 computer simulation Methods 0.000 description 1
- 238000009795 derivation Methods 0.000 description 1
- 238000012938 design process Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000005265 energy consumption Methods 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 230000008303 genetic mechanism Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
- G05D1/0214—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with safety or protection criteria, e.g. avoiding hazardous areas
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
- G05D1/0221—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving a learning process
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0276—Control of position or course in two dimensions specially adapted to land vehicles using signals provided by a source external to the vehicle
Landscapes
- Engineering & Computer Science (AREA)
- Aviation & Aerospace Engineering (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Automation & Control Theory (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
- Manipulator (AREA)
Abstract
基于遗传算法和三次样条插值的机器人全局路径规划方法,采用多面模型表示法来表示机器人所处的环境空间;使用二维坐标表示机器人行驶的路径;采用随机和定向两种搜索策略产生初始路径集,从而保证了初始化种群的多样性;根据环境地图信息和障碍物的特点等先验知识,采用了一种合适的碰撞检测方法;使用了一种带有惩罚的适应度函数;采用轮盘赌选择法、单点交叉、随机变异等方式对初始化种群进行遗传操作;仿真实验表明本发明对于求解机器人全局路径规划问题具有较好的可行性和有效性。本发明为解决移动机器人全局路径规划问题提供了新的思路。
Description
技术领域
本发明属于机器人领域,涉及一种基于遗传算法和三次样条插值的机器人全局路径规划方法。
背景技术
机器人技术是现代科学理论与实践综合交叉的成果。20世纪60年代末,斯坦福研究院研制了自主移动机器人,路径规划方法是其关键核心技术。移动机器人路径规划技术,就是机器人在遵循一些优化指标(比如时间最短、路程最优和能耗最低等)前提下,在运行环境中规划出从起始点到目标点不发生碰撞的最优路径。
移动机器人路径规划实质上是满足一定约束条件的优化问题,其算法设计过程具有复杂性、随机性、多目标性和多约束性等特点。根据机器人关于环境的认识,路径规划可分为两类:第一类机器人具有被建模为地图的环境的先验知识,因此可以基于可用地图计划路径,此类路径称为全局路径规划,全局路径规划属于静态规划;第二类路径规划假设机器人没有环境的先验信息,因此它必须感测障碍物位置并在搜索过程中实时构建预估的环境地图,以避开障碍物并获取朝向目标位置的合适路径。此类路径称为局部路径规划,局部路径规划属于动态规划。根据研究环境的信息特点,路径规划还可以分为离散域范围内的路径规划和连续域范围内的路径规划,离散域范围内的路径规划属于一维静态优化问题,即环境信息简化后的路线优化问题,而连续范围内的路径规划问题则是连续性多维动态环境下的问题。
遗传算法(Genetic Algorithm,GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。遗传算法具有很强的全局寻优能力和适应性,被广泛地应用于路径规划问题,或者用来对原有路径规划方法进行改进。
发明内容
一种基于遗传算法和三次样条插值的机器人全局路径规划方法,包括采用多面模型表示法来表示机器人所处的环境空间;使用二维坐标表示机器人行驶的路径;采用随机和定向两种搜索策略产生初始路径集,从而保证了初始化种群的多样性;根据环境地图信息和障碍物的特点等先验知识,采用了一种合适的碰撞检测方法;使用了一种带有惩罚的适应度函数;采用轮盘赌选择法、单点交叉、随机变异等方式对初始化种群进行遗传操作;仿真实验表明本发明对于求解机器人全局路径规划问题具有较好的可行性和有效性。本发明为解决移动机器人全局路径规划问题提供了新的思路。
本发明采用的技术方案是:一种基于改进遗传算法的移动机器人路径规划方法,其特征在于,包括以下步骤:
S1:使用多面模型表示法对移动机器人的工作环境建模;
S2:编码;
设置初始化参数,包括路径起点、路径终点、种群数量、迭代次数、交叉率和变异率;
S4:生成初始化种群;
S5:利用三次样条插值方法在节点之间插入节点;
S6:判断路径中每个路径节点是否与障碍物发生碰撞,如果路径节点与障碍物发生碰撞,则在适应度函数中添加惩罚;
S7:根据适应度函数,计算初始化种群中每个个体的适应度值;
S8:执行选择操作,对初始化种群生成的路径进行更新;
S9:执行交叉操作,对选择操作生成的路径进行更新;
S10:执行变异操作,对交叉操作生成的路径进行更新;
判断是否达到最大迭代次数,若达到最大迭代次数,则停止搜索,输出最优路径,否则跳转至S5进行下一次迭代寻优。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S1的栅格法建模具体为:
使用多面模型表示法对移动机器人的工作环境建模。移动机器人的运动空间用二维平面图形表示,障碍物的顶点用(x,y)记录。障碍物被设置为静态的、随机的、已知的任意不规则多边形。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S2中编码操作具体为:
使用二维坐标表示机器人行驶的路径。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S4中初始化种群具体为:
采用了随机和定向两种搜索策略来生成遗传算法的初始化种群集,从而保证了初始化种群的多样性。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S5中插入节点的方法具体为:
本发明利用三次样条插值方法在路径起点、三个中间节点、路径终点之间插入三次样条插入点。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S6中碰撞检测的方法具体为:
本发明涉及的碰撞检测只需要判断点是否位于圆形障碍物内部,换句话说,只需判断点到圆心的距离是否小于圆的半径即可。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S7中适应度函数具体为:
其中,P表示惩罚系数,用来淘汰生成的较差路径;C表示生成的路径与障碍物发生碰撞的次数,L表示机器人的路径长度,可根据公式(4)进行计算。
其中,(xi,yi)和(xi+1,yi+1)分别为路径中第i和i+1个点的坐标。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S8中选择操作具体为:
采用轮盘赌选择法作为选择操作。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S9中交叉操作具体为:
本发明采用单点交叉作为交叉操作。当交叉条件满足时,随机选择两个个体中除起点和终点外的一个位置作为交叉点,然后这两个个体在交叉点进行交叉操作。例如,假设参与交叉操作的两个个体分别为p={s,p1,…,pi,…,pnum,e}和q={s,q1,…,qi,…,qnum,e},pi和qi是交叉点,在pi和qi交叉点处进行交叉操作,则产生的两个新个体分别为 pnew={s,p1,…,qi,…,qnum,e}和qnew={s,q1,…,pi,…,pnum,e}。
根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S10中变异操作具体为:
本发明采用随机交叉作为变异操作。当变异条件满足时,随机选取除路径起点和路径终点外的两个节点作为变异点,按照初始化种群中随机搜索策略在变异点处重新生成一个新的个体,从而完成变异操作。例如,假设参与变异操作的个体为t={s,t1,…,ti,…,tnum,e}, ti是变异点,利用随机搜索策略生成的新个体为u={s,u1,…,ui,…,unum,e},将新个体u中ui的替换参与变异操作个体t中的ti,从而生成新的个体tnew={s,t1,…,ui,…,tnum,e}。
附图说明
图1为本发明基于改进遗传算法的移动机器人路径规划的总体流程图;
图2为本发明实施例中给定环境下路径规划示意图;
图3为本发明实施例中给定环境下平均适应度函数曲线图;
具体实施方式
为了便于理解下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅是本发明的一部分实施例。
如图1所示,一种基于改进遗传算法的移动机器人路径规划方法,主要包括以下步骤:
S1:使用多面模型表示法对移动机器人的工作环境建模;
使用多面模型表示法对移动机器人的工作环境建模。移动机器人的运动空间用二维平面图形表示,障碍物的顶点用(x,y)记录。障碍物被设置为静态的、随机的、已知的任意不规则多边形。
S2:编码;
使用二维坐标表示机器人行驶的路径。
S4:生成初始化种群;
采用了随机和定向两种搜索策略来生成遗传算法的初始化种群集,从而保证了初始化种群的多样性。
S5:利用三次样条插值方法在节点之间插入节点;
利用三次样条插值方法在路径起点、三个中间节点、路径终点之间插入三次样条插入点。
S6:判断路径中每个路径节点是否与障碍物发生碰撞,如果路径节点与障碍物发生碰撞,则在适应度函数中添加惩罚;
本发明涉及的碰撞检测只需要判断点是否位于圆形障碍物内部,换句话说,只需判断点到圆心的距离是否小于圆的半径即可。
S7:根据适应度函数,计算初始化种群中每个个体的适应度值;
其中,P表示惩罚系数,用来淘汰生成的较差路径;C表示生成的路径与障碍物发生碰撞的次数,L表示机器人的路径长度,可根据公式(6)进行计算。
其中,(xi,yi)和(xi+1,yi+1)分别为路径中第和个点的坐标。
S8:执行选择操作,对初始化种群生成的路径进行更新;
采用轮盘赌选择法作为选择操作。
S9:执行交叉操作,对选择操作生成的路径进行更新;
本发明采用单点交叉作为交叉操作。当交叉条件满足时,随机选择两个个体中除起点和终点外的一个位置作为交叉点,然后这两个个体在交叉点进行交叉操作。例如,假设参与交叉操作的两个个体分别为p={s,p1,…,pi,…,pnum,e}和q={s,q1,…,qi,…,qnum,e},pi和qi是交叉点,在pi和qi交叉点处进行交叉操作,则产生的两个新个体分别为 pnew={s,p1,…,qi,…,qnum,e}和qnew={s,q1,…,pi,…,pnum,e}。
S10:执行变异操作,对交叉操作生成的路径进行更新;
本发明采用随机交叉作为变异操作。当变异条件满足时,随机选取除路径起点和路径终点外的两个节点作为变异点,按照初始化种群中随机搜索策略在变异点处重新生成一个新的个体,从而完成变异操作。例如,假设参与变异操作的个体为t={s,t1,…,ti,…,tnum,e}, ti是变异点,利用随机搜索策略生成的新个体为u={s,u1,…,ui,…,unum,e},将新个体u中的ui替换参与变异操作个体t中的ti,从而生成新的个体tnew={s,t1,…,ui,…,tnum,e}。
图2表示本发明在给定环境下一次实验结果的路径规划。其中,四边形表示起点,五角星表示终点。图3表示本发明在给定环境下的迭代曲线。其中,横坐标表示迭代次数,纵坐标表示适应度值。从图2和图3可以看出,本发明能够在125代左右跳出局部最优,达到全局最优解,从而可以找到机器人从起点到终点的一条安全的无碰撞最优路径。仿真实验表明本发明对于求解机器人全局路径规划问题具有较好的可行性和有效性。
Claims (9)
1.基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,包括以下步骤:
S1:使用多面模型表示法对移动机器人的工作环境建模;
S2:编码;
S3:设置初始化参数,包括路径起点、路径终点、种群数量、迭代次数、交叉率和变异率;
S4:生成初始化种群;
S5:利用三次样条插值方法在节点之间插入节点;
S6:判断路径中每个路径节点是否与障碍物发生碰撞,如果路径节点与障碍物发生碰撞,则在适应度函数中添加惩罚;
S7:根据适应度函数,计算初始化种群中每个个体的适应度值;
S8:执行选择操作,对初始化种群生成的路径进行更新;
S9:执行交叉操作,对选择操作生成的路径进行更新;
S10:执行变异操作,对交叉操作生成的路径进行更新;
S11:判断是否达到最大迭代次数,若达到最大迭代次数,则停止搜索,输出最优路径,否则跳转至S5进行下一次迭代寻优。
2.根据权利要求1所述的方法,其特征在于,所述步骤S1的栅格法建模具体为:
使用多面模型表示法对移动机器人的工作环境建模;移动机器人的运动空间用二维平面图形表示,障碍物的顶点用(x,y)记录;障碍物被设置为静态的、随机的、已知的任意不规则多边形。
3.根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S2中编码操作具体为:
使用二维坐标表示机器人行驶的路径。
4.根据权利要求1所述的方法,其特征在于,所述步骤S4中初始化种群具体为:
采用随机和定向两种搜索策略来生成遗传算法的初始化种群集以保证初始化种群的多样性。
5.根据权利要求1所述的方法,其特征在于,所述步骤S5中插入节点的方法具体为:
利用三次样条插值方法在路径起点、三个中间节点、路径终点之间插入三次样条插入点。
7.根据权利要求1所述的方法,其特征在于,所述步骤S8中选择操作具体为:
采用轮盘赌选择法作为选择操作。
8.根据权利要求1所述的方法,其特征在于,所述步骤S9中交叉操作具体为:
采用单点交叉作为交叉操作:
当交叉条件满足时,随机选择两个个体中除起点和终点外的一个位置作为交叉点,然后这两个个体在交叉点进行交叉操作。
9.根据权利要求1所述的一种基于遗传算法和三次样条插值的机器人全局路径规划方法,其特征在于,所述步骤S10中变异操作具体为:
采用随机交叉作为变异操作:
当变异条件满足时,随机选取除路径起点和路径终点外的两个节点作为变异点,按照初始化种群中随机搜索策略在变异点处重新生成一个新的个体,从而完成变异操作。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202110589621.8A CN113219986A (zh) | 2021-05-28 | 2021-05-28 | 基于遗传算法和三次样条插值的机器人全局路径规划方法 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202110589621.8A CN113219986A (zh) | 2021-05-28 | 2021-05-28 | 基于遗传算法和三次样条插值的机器人全局路径规划方法 |
Publications (1)
Publication Number | Publication Date |
---|---|
CN113219986A true CN113219986A (zh) | 2021-08-06 |
Family
ID=77098967
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN202110589621.8A Pending CN113219986A (zh) | 2021-05-28 | 2021-05-28 | 基于遗传算法和三次样条插值的机器人全局路径规划方法 |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN113219986A (zh) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN115079693A (zh) * | 2022-06-08 | 2022-09-20 | 江苏师范大学 | 基于改进遗传算法和b样条拟合的无人车路径规划方法 |
Citations (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN105988468A (zh) * | 2015-01-28 | 2016-10-05 | 中国人民公安大学 | 一种基于改进遗传算法的移动机器人路径规划方法 |
CN112686429A (zh) * | 2020-12-16 | 2021-04-20 | 天津城建大学 | 移动机器人及其基于自适应遗传算法的路径规划方法 |
-
2021
- 2021-05-28 CN CN202110589621.8A patent/CN113219986A/zh active Pending
Patent Citations (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN105988468A (zh) * | 2015-01-28 | 2016-10-05 | 中国人民公安大学 | 一种基于改进遗传算法的移动机器人路径规划方法 |
CN112686429A (zh) * | 2020-12-16 | 2021-04-20 | 天津城建大学 | 移动机器人及其基于自适应遗传算法的路径规划方法 |
Non-Patent Citations (3)
Title |
---|
刘志海等: "基于遗传算法的机器人路径规划的种群初始化改进", 《机床与液压》 * |
宋宇等: "基于改进遗传算法的移动机器人路径规划", 《现代电子技术》 * |
魏彤等: "基于改进遗传算法的移动机器人路径规划", 《北京航空航天大学学报》 * |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN115079693A (zh) * | 2022-06-08 | 2022-09-20 | 江苏师范大学 | 基于改进遗传算法和b样条拟合的无人车路径规划方法 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN110083165B (zh) | 一种机器人在复杂狭窄环境下路径规划方法 | |
CN109540150B (zh) | 一种应用于危化品环境下多机器人路径规划方法 | |
CN113159432B (zh) | 一种基于深度强化学习的多智能体路径规划方法 | |
CN107607120B (zh) | 基于改进修复式Anytime稀疏A*算法的无人机动态航迹规划方法 | |
WO2018176596A1 (zh) | 基于权重改进粒子群算法的无人自行车路径规划方法 | |
CN102722749B (zh) | 一种基于粒子群算法的自适应三维空间路径规划方法 | |
CN107992040B (zh) | 基于地图栅格与qpso算法结合的机器人路径规划方法 | |
CN113848919A (zh) | 一种基于蚁群算法的室内agv路径规划方法 | |
Wang et al. | Scene mover: Automatic move planning for scene arrangement by deep reinforcement learning | |
CN109799820A (zh) | 基于比较式随机路标图法的无人船舶局部路径规划方法 | |
CN108413963A (zh) | 基于自学习蚁群算法的条形机器人路径规划方法 | |
CN112947480B (zh) | 一种移动机器人路径规划方法、存储介质及系统 | |
Yan et al. | Learning topological motion primitives for knot planning | |
CN115829179B (zh) | 一种舰船路径规划方法及装置 | |
CN113219986A (zh) | 基于遗传算法和三次样条插值的机器人全局路径规划方法 | |
Dey | Applied Genetic Algorithm and Its Variants: Case Studies and New Developments | |
CN112613608A (zh) | 一种强化学习方法及相关装置 | |
Gu et al. | Robot path planning of improved adaptive Ant Colony System Algorithm based on Dijkstra | |
CN115933669A (zh) | 基于改进蝴蝶优化算法的移动机器人路径规划方法 | |
CN101996516A (zh) | 基于矢量法的路径规划预处理方法 | |
CN112504274A (zh) | 一种基于Dsl_GA算法的移动机器人路径规划方法 | |
Hosseinzadeh et al. | Evolutionary approach for mobile robot path planning in complex environment | |
Bhaduri | A mobile robot path planning using genetic artificial immune network algorithm | |
CN117420832A (zh) | 一种基于改进gto的机器人路径规划方法 | |
CN116430891A (zh) | 一种面向多智能体路径规划环境的深度强化学习方法 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
RJ01 | Rejection of invention patent application after publication | ||
RJ01 | Rejection of invention patent application after publication |
Application publication date: 20210806 |