Journal of Frontiers of Computer Science and Technology ›› 2023, Vol. 17 ›› Issue (4): 837-847.DOI: 10.3778/j.issn.1673-9418.2108028

• Theory·Algorithm • Previous Articles     Next Articles

Arbitrary Angle Path Planning Based on Improved LOS Algorithm in Basic Theta*

CHEN Zhengze, PENG Li, DAI Feifei   

  1. 1. Engineering Research Center of Internet of Things Technology Applications, School of Internet of Things Engineering, Jiangnan University (Ministry of Education), Wuxi, Jiangsu 214122, China
    2. Taizhou Institute of Product Quality and Safety Testing, Taizhou, Zhejiang 318000, China
  • Online:2023-04-01 Published:2023-04-01

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

陈正泽,彭力,戴菲菲   

  1. 1. 物联网技术应用教育部工程研究中心(江南大学 物联网工程学院),江苏 无锡 214122
    2. 台州市产品质量安全检测研究院,浙江 台州 318000

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

摘要: 针对传统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