LIU Ting， WANG Xiaoyan， KANG Zhiqiang
（School of Mechanical and Electrical Engineering, Xi’an University of Architecture and Technology, Xi’an 710055, China）
Abstract： Aiming at the problems of large randomness, long search time and tortuous path in the path planning by means of rapidly-exploring random tree (RRT) in a fusion environment of complex areas with multiple obstacles and open areas with few obstacles, an ant colony optimization target-biased RRT algorithm based on environmental partitions is proposed. Firstly, the random probability sampling based on the environment is combined with the target bias expansion strategy of the artificial potential field to improve the algorithm’s convergence speed and enhance the algorithm’s search ability. Then, in order to solve the problem of tortuous planning path and many redundant points, an improved ant colony optimization path is proposed and combined with jumping point screening strategy and cubic B-spline to eliminate redundant points to smooth the final path. Finally, the improved algorithm is compared and analyzed with the A-star algorithm and the target biased RRT algorithm. The simulation results show that the improved algorithm reduces the node consumption by 54.8% and the time by 75.88% averagely, which verifies the effectiveness of the algorithm.
Key words： path planning； rapidly-exploring random tree (RRT)； target bias； random probability sampling； ant colony system； jump point screening； cubic B-spline
References
［1］DURRANT-WHYTE H. where am I? A tutorial on mobile vehicle localization. Industrial Robot, 1994, 21(2)： 11-16.
［2］WU T. Autonomous Environment Exploration of Mobile Robot Based on Grid-Octree Hybrid Map. Dalian： Dalian Maritime University, 2020.
［3］Wang M C. Path planning of mobile robots based on A* algorithm. Shenyang： Shenyang University of Technology, 2017.
［4］ZHAI H S, WANG J X. Dynamic path planning research for mobile robot based on artificial potential field. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2015, 27(6)： 814-818.
［5］DING J R, DU C P, ZHAO Y, et al. Path planning algorithm for unmanned aerial vehicles based on improved artificial potential field. Journal of Computer Applications, 2016, 36(1)： 287-290.
［6］SUN B, JIANG P, ZHOU G R, et al. AGV optimal path planning based on improved genetic algorithm. Computer Engineering and Design, 2020, 41(2)： 550-556.
［7］BAI J L, CHEN H N, HU Y B, et al. Ant colony algorithm based on negative feedback and its application on robot path planning. Computer Integrated Manufacturing Systems, 2019, 25(7)： 1767-1774.
［8］XIE J H, SU D Y, LU S H, et al. Key technology of transmission line path planning based on improved ant. Electrical Measurement & Instrumentation, 2020, 57(4)： 122-128.
［9］PANG L. Application of fireworks algorithm combined with genetic algorithm in logistics distribution of heterogeneous vehicle path optimization method. Computer Measurement & Control, 2019, 27(8)： 245-248.
［10］WANG S X. Research on improvement and application of fireworks algorithm. Huaibei： Huaibei Normal University, 2019.
［11］PEI Y J， YANG C J， YANG L L. Path planning algorithm for mobile robot based on improved RRT*. Computer Engineering, 2019, 45(5)： 285-290.
［12］WANG K, ZENG G H, LU D K, et al. Path planning of mobile robot based on improved asymptotically-optimal bidirectional rapidly-exploring random tree algorithm. Journal of Computer Applications, 2019, 39(5)： 1312-1317.
［13］ZHU M H. Smart car path planning based on improved RRT. Nanjing： Nanjing University of Science &Technology, 2018.
［14］LIU Z Y, ZHANG J. Path planning using improved RRT algorithm for indoor mobile robot. Computer Engineering and Applications, 2019, 4(5)： 1-11.
［15］ZHAO X, WANG Z, HUANG C K, et al. Mobile robot path planning based on an improved A* algorithm . Robot, 2018, 40(6)： 903-910.
［16］DU M B, MEI T, CHEN J, et al. RRT-based motion planning algorithm for intelligent vehicle in complex environments. Robot, 2015, 37(4)： 443-450.
基于蚁群的环境分区目标偏置RRT算法路径规划
刘挺， 王晓燕， 康智强
（西安建筑科技大学 机电学院， 陕西 西安 710055）
摘要:利用快速扩展随机树算法（(Rapidly-exploring random tree， RRT）进行路径规划时， 在狭窄复杂区域与空旷障碍区域融合环境下， 存在随机性大、 搜索时间长、 路径曲折等问题。 为此， 提出了一种基于蚁群的环境分区目标偏置RRT算法。 首先， 采用分环境的随机概率采样并结合人工势场的目标偏向扩展策略， 以提高算法收敛速度， 增强算法搜索能力。 其次， 为解决规划路径曲折且冗余点多的问题， 提出改进蚁群寻优路径， 并结合跳点筛选策略及三次B样条以消除冗余点平滑最终路径。 最后， 改进后的算法与A*算法、 目标偏向RRT算法进行了对比分析。 仿真结果表明： 改进后的算法节点耗费量降低了54.8%， 时间平均缩短了75.88%， 从而验证了算法的有效性。
关键词:路径规划； 快速扩展随机树； 目标偏向； 随机概率采样 ； 蚁群系统； 跳点筛选； 三次B样条
引用格式：LIU Ting, WANG Xiaoyan, KANG Zhiqiang． Path planning using ant colony based environment partition target-biased RRT algorithm． Journal of Measurement Science and Instrumentation， 2023， 14（1）： 55-65. DOI： 10．3969／j．issn．1674-8042．2023．01．007
[full text view]
