引入必经点约束的路径规划算法研究

doi:10.3778/j.issn.1002-8331.2004-0423

计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (21): 25-29.DOI: 10.3778/j.issn.1002-8331.2004-0423

引入必经点约束的路径规划算法研究

王磊，孙力帆

1.河南科技大学国际教育学院，河南洛阳 471023
2.河南科技大学信息工程学院，河南洛阳 471023

出版日期:2020-11-01 发布日期:2020-11-03

Research on Path Planning Algorithm with Obligatory Node Constraint

WANG Lei, SUN Lifan

1.School of International Education, Henan University of Science and Technology, Luoyang, Henan 471023, China
2.School of Information Engineering, Henan University of Science and Technology, Luoyang, Henan 471023, China

Online:2020-11-01 Published:2020-11-03

摘要/Abstract

摘要：

针对传统A*算法存在搜索范围广、运行效率低的问题，提出了一种引入必经点约束的路径规划算法。该算法结合障碍物分布特点，通过寻找最短路径必经点，实现对A*搜索方向的约束，再对最短路径段进行拼接得到最短路径。最后，在100×100网格地图中进行对比实验，结果表明，引入必经点约束的改进算法比传统A*算法的结点访问量大幅降低，运行效率得到显著提高。

关键词: A*算法, 障碍物块, 登陆点, 模拟路径, 必经点, 路径规划

Abstract:

As for the problems of searching too many nodes and running inefficiently on traditional A-Star algorithm, this paper proposes a path planning algorithm with obligatory node constraint. Considering the layout of obstacles, this algorithm limites searching directions of A* by finding out an obligatory node of shortest path. And then it connects both shortest path segments to form the shortest path. An experiment is performed between traditional A-Star algorithm and improved algorithm in maps of 100×100 grids. It shows that the operation efficiency of A-Star algorithm has been significantly improved.

Key words: A-Star algorithm, obstacle block, landing point, simulate path, obligatory node, path planning

王磊，孙力帆. 引入必经点约束的路径规划算法研究[J]. 计算机工程与应用, 2020, 56(21): 25-29.

WANG Lei, SUN Lifan. Research on Path Planning Algorithm with Obligatory Node Constraint[J]. Computer Engineering and Applications, 2020, 56(21): 25-29.

[1]	孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.
[2]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[3]	廖列法，李浩瀚，李帅，朱合隆，李志军. 结合Winner-Take-All的足球机器人控制策略研究[J]. 计算机工程与应用, 2021, 57(7): 136-143.
[4]	韩晓微，韩震，岳高峰，崔建江. 救灾无人机的优化A*航迹规划算法[J]. 计算机工程与应用, 2021, 57(6): 232-238.
[5]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[6]	刘建宇，范平清. 基于改进的RRT*-connect算法机械臂路径规划[J]. 计算机工程与应用, 2021, 57(6): 274-278.
[7]	王迪，李彩虹，郭娜，刘国名，高腾腾. 基于模糊势场法的移动机器人局部路径规划[J]. 计算机工程与应用, 2021, 57(6): 212-218.
[8]	蒋林，方东君，雷斌，李维刚. 单目视觉移动机器人导航算法研究现状及趋势[J]. 计算机工程与应用, 2021, 57(5): 1-9.
[9]	马向华，张谦. 改进蚁群算法在机器人路径规划上的研究[J]. 计算机工程与应用, 2021, 57(5): 210-215.
[10]	杨凌耀，张爱华，张洁，宋季强. 栅格地图环境下机器人速度势实时路径规划[J]. 计算机工程与应用, 2021, 57(24): 290-295.
[11]	王琛，茅健. 基于时间窗模型的双向机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(23): 287-294.
[12]	赵伟，吴子英. 双层优化A*算法与动态窗口法的动态路径规划[J]. 计算机工程与应用, 2021, 57(22): 295-303.
[13]	成怡，郝密密. 改进深度强化学习的室内移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(21): 256-262.
[14]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[15]	涂睿，王文格，卢成阳. 移动机器人实时采样路径重规划[J]. 计算机工程与应用, 2021, 57(20): 157-163.

引入必经点约束的路径规划算法研究

Research on Path Planning Algorithm with Obligatory Node Constraint

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics