Automatic path planning of robot for integrated installation of large laser device
-
摘要: 针对大型激光装置集成安装过程中的机器人路径规划问题，提出一种简单有效的改进A*算法。该算法较传统A*算法进行了三步改进，第一步是限制可行走方向，避免出现传统A*算法发生穿越障碍物情况；二是将其启发函数优化为加权曼哈顿距离函数，加速向x方向或者y方向扩展节点，改善限制可行走方向带来的遍历节点数激增现象，三是引入转弯惩罚项，减少路径规划过程中的转弯次数，提高路径规划搜索效率和质量。在不同大小的栅格地图中验证三步改进A*算法的性能，并与传统A*算法进行比较。实验结果表明，简单地图中，三步改进A*算法遍历节点数略高于传统A*算法，转弯次数与传统A*算法相当，但路径避障性能明显优于传统A*算法，更有利于机器人安全行走。复杂地图中，综合考虑遍历节点数、转弯次数和路径长度的优先关系后，可以实现调节三步改进A*算法参数至路径规划结果最优。Abstract: A simple and effective improved A* algorithm is proposed to solve the problem of robot path planning in the integrated installation of large-scale laser devices. Compared with the traditional A* algorithm, the algorithm has been improved in three steps. Firstly, the walking direction is limited, which avoids the phenomenon of crossing obstacles occurred in the traditional A* algorithm; Secondly, the heuristic function is optimized as a weighted Manhattan distance function, which accelerates the expansion of nodes to X direction or Y direction, and reduces the surge of traversal nodes caused by limiting the walking direction. Thirdly, the turning penalty term is introduced to reduce the turning times in the path planning process, and improve the search efficiency and quality. The performance of the three-step improved A* algorithm is verified in different size raster maps, and compared with the traditional A* algorithm. Experimental results show that in simple maps, the number of nodes traversed by the three-step improved A* algorithm is slightly higher than that of the traditional A* algorithm, and the number of turns is equivalent to that of the traditional A* algorithm, but the obstacle avoidance performance is obviously better than that of the traditional A* algorithm, which is more conducive to the safe walking of robots. In complex maps, considering the priority relationship of traversal nodes, turn times and path length, the parameters of the three-step improved A* algorithm can be adjusted to obtain the optimal path planning result.
-
图 3 限制可行走方向A*算法搜索路径
Figure 3. Search path based on A* algorithm with limited walking direction
图 4 基于加权曼哈顿距离A*算法搜索路径
Figure 4. Search path based on A* algorithm of weighted Manhattan distance
图 5 移动机器人直行和转弯示意图
Figure 5. Schematic diagram of mobile robot going straight and turning
图 6 路径规划结果(
${\lambda _1}$ =2，${\lambda _2}$ =1，m=5)Figure 6. Path planning result (
${\lambda _1}$ =2，${\lambda _2}$ =1，m=5)
图 9 不同调节参数下的三步改进A*算法在复杂地图中的路径规划结果
Figure 9. Path planning results of quadratic optimization A* algorithm under different adjustment parameters in complex maps
表 1 改进 A*算法和传统 A*算法在简单地图中的性能比较
Table 1. Performance comparison between improved A* algorithm and traditional A* algorithm in simple map
experimental group number algorithm traversed nodes turn times path length 1 traditional A* algorithm 64 8 27.21 2 A*-1 algorithm（${\lambda _1}$=${\lambda _2}$=1，m=0） 175 13 34 3 A*-1* algorithm（${\lambda _1}$=${\lambda _2}$ =1，m=1） 199 6 36 4 A*-2 algorithm（${\lambda _1}$=2，${\lambda _2}$=1，m=0） 96 11 34 5 A*-2* algorithm（${\lambda _1}$=2，${\lambda _2}$=1，m=2） 122 6 36 
下载: 导出CSV
表 2 不同调节参数下的三步改进A*算法在复杂地图中的路径规划结果统计
Table 2. Statistics of path planning results of quadratic optimization A* algorithm under different adjustment parameters in complex map
experimental group number algorithm traversed nodes turn times path length 1-1 A*-1 algorithm（${\lambda _1}$=${\lambda _2}$=1，m=0） 1279 29 98 1-2 A*-1* algorithm（${\lambda _1}$=${\lambda _2}$=1，m=1） 1217 16 98 2-1 A*-2 algorithm（${\lambda _1}$=1，${\lambda _2}$=2，m=0） 336 33 106 2-2 A*-2 algorithm（${\lambda _1}$=1，${\lambda _2}$ =5，m=0） 245 33 106 2-3 A*-2* algorithm（${\lambda _1}$=1，${\lambda _2}$=2，m=2） 367 27 104 2-4 A*-2* algorithm（${\lambda _1}$=1，${\lambda _2}$=5，m=5） 310 31 106 2-5 A*-2* algorithm（${\lambda _1}$=1，${\lambda _2}$=2，m=5） 376 27 104 3-1 A*-2 algorithm（${\lambda _1}$=5，${\lambda _2}$= 1，m=0） 272 29 110 3-2 A*-2* algorithm（${\lambda _1}$=5，${\lambda _2}$=1，m=5） 339 27 114
下载: 导出CSV
-
[1] 郑万国, 邓颖, 周维, 等. 激光聚变研究中心激光技术研究进展[J]. 强激光与粒子束, 2013, 25(12):3082-3090 doi: 10.3788/HPLPB20132512.3082Zheng Wanguo, Deng Ying, Zhou Wei, et al. Development of laser technology in research center of laser fusion[J]. High Power Laser and Particle Beams, 2013, 25(12): 3082-3090 doi: 10.3788/HPLPB20132512.3082 [2] 熊召, 尹灵钰, 裴国庆, 等. 面向大型激光装置的智能装配调度[J]. 强激光与粒子束, 2023, 35:092002 doi: 10.11884/HPLPB202335.230170Xiong Zhao, Yin Lingyu, Pei Guoqing, et al. Intelligent assembly scheduling for large laser devices[J]. High Power Laser and Particle Beams, 2023, 35: 092002 doi: 10.11884/HPLPB202335.230170 [3] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271. doi: 10.1007/BF01386390 [4] 李鼎鑫. 复杂环境下移动机器人路径规划方法研究与应用[D]. 北京: 北京工业大学, 2021: 1-5Li Dingxin. Research and application of path planning method for mobile robot in complex environment[D]. Beijing: Beijing University of Technology, 2021: 1-5 [5] Guruji A K, Agarwal H, Parsediya D K. Time-efficient A* algorithm for robot path planning[J]. Procedia Technology, 2016, 23: 144-149. doi: 10.1016/j.protcy.2016.03.010 [6] Qi Jie, Yang Hui, Sun Haixin. MOD-RRT*: a sampling-based algorithm for robot path planning in dynamic environment[J]. IEEE Transactions on Industrial Electronics, 2021, 68(8): 7244-7251. doi: 10.1109/TIE.2020.2998740 [7] Luo Qiang, Wang Haibao, Zheng Yan, et al. Research on path planning of mobile robot based on improved ant colony algorithm[J]. Neural Computing and Applications, 2020, 32(6): 1555-1566. doi: 10.1007/s00521-019-04172-2 [8] Ajeil F H, Ibraheem I K, Azar A T, et al. Grid-based mobile robot path planning using aging-based ant colony optimization algorithm in static and dynamic environments[J]. Sensors, 2020, 20: 1880. doi: 10.3390/s20071880 [9] Xin Junfeng, Zhong Jiabao, Yang Fengru, et al. An improved genetic algorithm for path-planning of unmanned surface vehicle[J]. Sensors, 2019, 19: 2640. doi: 10.3390/s19112640 [10] 吕太之, 赵春霞, 夏平平. 基于同步可视图构造和A*算法的全局路径规划[J]. 南京理工大学学报, 2017, 41(3):313-321Lv Taizhi, Zhao Chunxia, Xia Pingping. Global path planning based on simultaneous visibility graph construction and A* algorithm[J]. Journal of Nanjing University of Science and Technology, 2017, 41(3): 313-321 [11] 孔继利, 张鹏坤, 刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8):231-237 doi: 10.3778/j.issn.1002-8331.2002-0016Kong Jili, Zhang Pengkun, Liu Xiaoping. Research on improved A* algorithm of bidirectional search mechanism[J]. Computer Engineering and Applications, 2021, 57(8): 231-237 doi: 10.3778/j.issn.1002-8331.2002-0016 [12] 郭晓静, 杨卓橙. 基于邻域拓展的静态路径规划A*算法研究[J]. 计算机工程与应用, 2022, 58(8):168-174 doi: 10.3778/j.issn.1002-8331.2010-0222Guo Xiaojing, Yang Zhuocheng. Improved A* algorithm based on neighbor extension in static environment[J]. Computer Engineering and Applications, 2022, 58(8): 168-174 doi: 10.3778/j.issn.1002-8331.2010-0222 [13] 胡蔚旻, 靳文舟. 改进平滑A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(16):204-210 doi: 10.3778/j.issn.1002-8331.2001-0090Hu Weimin, Jin Wenzhou. Multi-AGV path planning based on improved smooth A* algorithm[J]. Computer Engineering and Applications, 2020, 56(16): 204-210 doi: 10.3778/j.issn.1002-8331.2001-0090 -
点击查看大图
计量
- 文章访问数: 22
- HTML全文浏览量: 15
- PDF下载量: 2
- 被引次数: 0
