改进Basic Theta*中LOS算法的任意角度路径规划

doi:10.3778/j.issn.1673-9418.2108028

摘要/Abstract

摘要： 针对传统A*算法在进行机器人路径规划时，生成的路径只能沿网格方向进行，带来冗余路径的产生，导致规划的路径非最优路径等问题，提出了一种对A*算法的改进策略。首先，设计Basic Theta*算法，改进A*算法的搜索方式，通过引入视线算法（LOS），增加搜索过程中非网格方向路径的选择，实现任意角度的路径规划；其次，对Basic Theta*算法中的LOS进行改进，提出一种基于网格中心点的视线检测算法，提高Basic Theta*算法规划路径的可实现性。为了验证改进A*算法和改进Basic Theta*算法的效果，在五种不同尺寸的栅格地图中进行仿真测试，仿真结果表明，改进后的A*算法能够在运行时间基本不变的情况下实现路径沿任意角度进行，打破网格的限制，剔除冗余路径，降低路径长度，路径长度的缩减率可达到8%；改进的Basic Theta*算法在保证路径长度基本不变的情况下，能够有效优化传统Basic Theta*算法路径中存在的不符合机器人运动学的路径，同时缩短Basic Theta*算法的运行时间，提高算法的运行效率，规划的路径能够满足机器人运动的实际要求。

关键词: 路径规划, Basic Theta*算法, 任意角度路径, 改进LOS

Abstract: When the traditional A* algorithm is used for robot path planning, the generated path can only be carried out along the grid direction, which leads to the generation of redundant paths and leads to non optimal path of the planned path. An improved strategy for the A* algorithm is proposed. Firstly, the Basic Theta* algorithm is designed to improve the search mode of A* algorithm. By using the line of sight (LOS) algorithm, the selection of non grid path in the search process is increased to realize path planning from any angle. Secondly, the line of sight algorithm in Basic Theta* algorithm is improved, and a line of sight detection algorithm based on grid center point is proposed to improve the realizability of Basic Theta* algorithm. In order to verify the effect of the improved A* algorithm and the improved Basic Theta* algorithm, simulation test is carried out in five grid maps of different sizes. Simulation results show that the improved A* algorithm can realize the path along any angle under the condition of basically unchanged running time, break the limitation of the grid, eliminate redundant paths, reduce the path length, and the reduction rate of path length can reach 8%. At the same time, the improved Basic Theta* algorithm can effectively optimize the path that does not conform to the robot kinematics in the path of the traditional Basic Theta* algorithm, shorten the running time of the Basic Theta* algorithm, improve the operation of the algorithm, and the planned path can meet the actual requirements of robot motion.

Key words: path planning, Basic Theta* algorithm, any angle path, improved LOS

陈正泽, 彭力, 戴菲菲. 改进Basic Theta*中LOS算法的任意角度路径规划[J]. 计算机科学与探索, 2023, 17(4): 837-847.

CHEN Zhengze, PENG Li, DAI Feifei. Arbitrary Angle Path Planning Based on Improved LOS Algorithm in Basic Theta*[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(4): 837-847.

参考文献

[1] 赵晓, 王铮, 黄程侃,等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.
ZHAO X, WANG Z, HUANG C K, et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot, 2018, 40(6): 903-910.
[2] 王洪斌, 尹鹏衡, 郑维, 等. 基于改进的A*算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42(3): 92-99.
WANG H B, YI P H, ZHENG W, et al. Mobile robot path planning based on improved A* algorithm and dynamic window method[J]. Robot, 2020, 42(3): 92-99.
[3] TAO Y, GAO H, REN F, et al. A mobile service robot global path planning method based on ant colony optimiza-tion and fuzzy control[J]. Applied Sciences, 2021, 11(8): 3605.
[4] ZHAO H R, ZHOU H, YANG G Q. Research on global path planning of artificial intelligence robot based on improved ant colony algorithm[J]. Journal of Physics: Conference Series, 2021, 1744(2): 022032.
[5] GUO X H, JI M J, ZHAO Z W, et al. Global path planning and multi-objective path control for unmanned surface vehicle based on modified particle swarm optimization (PSO) algorithm[J]. Ocean Engineering, 2020, 216: 107693.
[6] LONG Y, ZUO Z M, SU Y X, et al. An A*-based bacterial foraging optimisation algorithm for global path planning of unmanned surface vehicles[J]. Journal of Navigation, 2020, 73(6): 1247-1262.
[7] CHENG Z, ZHANG C, AO L, et al. An improved A* algori-thm applying to path planning of games[J]. Journal of Physics: Conference Series, 2020, 1631(1): 012068.
[8] TIAN L. A path planning method for mobile robot based on A* and ant-colony algorithms[J]. Journal of Innovation and Social Science Research, 2020, 7(1).
[9] JI X Y, FENG S. Improvement and fusion of A* algorithm and dynamic window approach considering complex environ-mental information[J]. Arabian Journal for Science and Engi-neering, 2021, 46(8): 1-15.
[10] XIE L, XUE S F, ZHANG J F, et al. A path planning app-roach based on multi-direction A* algorithm for ships navi-gating within wind farm waters[J]. Ocean Engineering, 2019, 184: 311-322.
[11] DAI X L, LONG S, ZHANG Z W, et al. Mobile robot path planning based on ant colony algorithm with A* heuristic method[J]. Frontiers in Neurorobotics, 2019, 13: 15.
[12] FERGUSON D, STENTZ A. Using interpolation to improve path planning: the field D* algorithm[J]. Journal of Field Robotics, 2006, 23(2): 79-101.
[13] PERKINS S, MARAIS P, GAIN J, et al. Field D* path-finding on weighted triangulated and tetrahedral meshes[J]. Autonomous Agents and Multi-agent Systems, 2013, 26(3): 354-388.
[14] GAO B, XU D M, ZHANG F B. The algorithm for the dynamic object based on Field D algorithm and the method of path extraction[J]. Fire Control & Command Control, 2010, 35(8): 98-102.
[15] 王琼, 于登云, 贾阳. 一种基于地形方向通行性的改进Theta*算法[J]. 空间科学学报, 2016, 36(3): 401-406.
WANG Q, YU D Y, JIA Y. An improved Theta* algorithm based on terrain directional traversability[J]. Chinese Journal of Space Science, 2016, 36(3):?401-406.
[16] DANIEL K, NASH A, KOENIG S, et al. Theta*: any-angle path planning on grids[J]. Journal of Artificial Intelligence Research, 2010, 39(1): 533-579.
[17] 王琼, 于登云, 贾阳. Risk Theta*: 一种基于地形危险度的任意航向路径规划算法[J]. 深空探测学报, 2014, 1(4): 269-274.
WANG Q, YU D Y, JIA Y. Risk Theta*: an any angle path planning algorithm based on terrain risk[J]. Journal of Deep Space Exploration, 2014, 1(4): 269-274.
[18] 肖国宝, 严宣辉. 一种基于改进Theta*的机器人路径规划算法[J]. 智能系统学报, 2013, 8(1): 58-65.
XIAO G B, YAN X H. A path planning algorithm based on improved Theta* for mobile robot[J]. CAAI Transactions on Intelligent Systems, 2013, 8(1): 58-65.
[19] 毛杰, 张昊, 李海燕. 基于Lazy Theta*算法的反潜巡逻飞机航路规划研究[J]. 舰船电子工程, 2020, 40(12): 40-43.
MAO J, ZHANG H, LI H Y. Research of anti-submarine patrol aircraft route planning based on Lazy Theta* alogri-thm[J]. Ship Electronic Engineering, 2020, 40(12): 40-43.
[20] FARIA M, MARíN R, POPOVI? M, et al. Efficient lazy Theta* path planning over a sparse grid to explore large 3D volumes with a multirotor UAV[J]. Sensors, 2019, 19(1): 174.
[21] DERGACHEV S, YAKOVLEV K, PRAKAPOVICH R. A combination of Theta*, ORCA and push and rotate for multi-agent navigation[C]//LNCS 12336: Proceedings of the 5th International Conference on Interactive Collaborative Robo-tics, St Petersburg, Oct 7-9, 2020. Cham: Springer, 2020: 55-66.