基于角度搜索的移动机器人路径规划方法

doi:10.16182/j.issn1004731x.joss.23-0407

摘要/Abstract

摘要：

为提升路径搜索速度，优化路径长度，提出一种用角度控制机器人的寻路算法—角度搜索算法。该算法根据机器人位置与目标点位置进行一定维度的高效搜索，从而实现在静态环境中有效寻路。根据所用栅格地图的环境特点，提前设定搜索角；计算机器人周围栅格的预估角；将预估角与搜索角进行比较选出新的扩展点，在扩展过程中排除重复路径的扩展和搜索角范围内无可行点的情况，直到找到目标点生成最终路径。通过仿真测试，将提出算法与Dijkstra、A*两种算法在复杂程度不同的两种地图上进行比较，所提算法寻路时间分别最大减少了19.44%和12.23%，转折次数分别最大减少了28.6%和54.5%，路径长度较A*算法在两种地图上分别减少了9.28%和6.53%，且在简单场景中实现了对局部障碍物的动态规避。将所提算法应用到基于ROS的移动机器人Turtlebot2上，实验结果表明，在相同地图环境中，所提算法较A*算法路径更加平滑稳定，验证了所提算法的有效性和可行性。

关键词: 路径规划, 预估角, 移动机器人, 搜索角, ROS

Abstract:

The angle search algorithm for angle-controlled robots is proposed to increase the path search speed and optimize the path length. The algorithm effectively finds a path in static surroundings by performing an efficient search in a specific dimensional range based on the position of the robot and the target point. Firstly, search angles are predetermined according to the characteristics of the environment in the grid map. Then, the estimated angle of the robot's surrounding grid is computed. Finally, a new extension point is chosen by comparing the estimated angle to the search angle, demonstrating the usefulness and viability of the suggested algorithm. The proposed algorithm is compared with the Dijkstra and A* algorithms on two types of maps with different levels of complexity. The path finding time of the proposed algorithm is reduced by 19.44% and 12.23% respectively, and the number of turns is reduced by 28.6% and 54.5% respectively. The path length is reduced by 9.28% and 6.53% respectively compared with the A* algorithm on the two maps, and the dynamic avoidance of local obstacles is realized in simple scenes. The proposed algorithm is then applied to the ROS-based Turtlebot2 mobile robot, and the experimental results reveal that it is smoother and more stable than the A* algorithm in the same map environment, proving its viability and effectiveness.

Key words: path planning, estimated angle, mobile robot, search angle, ROS

中图分类号:

TP391.9

王雅如,姚得鑫,刘增力等 . 基于角度搜索的移动机器人路径规划方法[J]. 系统仿真学报, 2024, 36(7): 1643-1654.

Wang Yaru,Yao Dexin,Liu Zengli,et al . Path Planning for Mobile Robot Based on Angle Search[J]. Journal of System Simulation, 2024, 36(7): 1643-1654.

图/表 21

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表1

图11

图12

图13

表2

图14

图15

图16

图17

图18

图19

参考文献 24

1	Wu Lei, Huang Xiaodong, Cui Junguo, et al. Modified Adaptive Ant Colony Optimization Algorithm and Its Application for Solving Path Planning of Mobile Robot[J]. Expert Systems with Applications, 2023, 215: 119410.
2	Fragapane Giuseppe, René de Koster, Sgarbossa Fabio, et al. Planning and Control of Autonomous Mobile Robots for Intralogistics: Literature Review and Research Agenda[J]. European Journal of Operational Research, 2021, 294(2): 405-426.
3	Wu Xiaojing, Xu Lei, Zhen Ran, et al. Biased Sampling Potentially Guided Intelligent Bidirectional RRT^* Algorithm for UAV Path Planning in 3D Environment[J]. Mathematical Problems in Engineering, 2019, 2019: 5157403.
4	曲道奎, 杜振军, 徐殿国, 等. 移动机器人路径规划方法研究[J]. 机器人, 2008, 30(2): 97-101, 106.
	Qu Daokui, Du Zhenjun, Xu Dianguo, et al. Research on Path Planning for a Mobile Robot[J]. Robot, 2008, 30(2): 97-101, 106.
5	王殿君. 基于改进A^*算法的室内移动机器人路径规划[J]. 清华大学学报(自然科学版), 2012, 52(8): 1085-1089.
	Wang Dianjun. Indoor Mobile-robot Path Planning Based on an Improved A^* Algorithm[J]. Journal of Tsinghua University(Science and Technology), 2012, 52(8): 1085-1089.
6	Jeddisaravi Kossar, Reza Javanmard Alitappeh, C A Pimenta Luciano, et al. Multi-objective Approach for Robot Motion Planning in Search Tasks[J]. Applied Intelligence, 2016, 45(2): 305-321.
7	Fu Bing, Chen Lin, Zhou Yuntao, et al. An Improved A^* Algorithm for the Industrial Robot Path Planning with High Success Rate and Short Length[J]. Robotics and Autonomous Systems, 2018, 106: 26-37.
8	Zhao Tao, Li Haodong, Songyi Dian. Multi-robot Path Planning Based on Improved Artificial Potential Field and Fuzzy Inference System[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39(5): 7621-7637.
9	Bakdi Azzeddine, Hentout Abdelfetah, Boutami Hakim, et al. Optimal Path Planning and Execution for Mobile Robots Using Genetic Algorithm and Adaptive Fuzzy-logic Control[J]. Robotics and Autonomous Systems, 2017, 89: 95-109.
10	朱庆保, 张玉兰. 基于栅格法的机器人路径规划蚁群算法[J]. 机器人, 2005, 27(2): 132-136.
	Zhu Qingbao, Zhang Yulan. An Ant Colony Algorithm Based on Grid Method for Mobile Robot Path Planning[J]. Robot, 2005, 27(2): 132-136.
11	Conn R A, Kam M. Robot Motion Planning on N-dimensional Star Worlds Among Moving Obstacles[J]. IEEE Transactions on Robotics and Automation, 1998, 14(2): 320-325.
12	朱毅, 张涛, 宋靖雁. 未知环境下势场法路径规划的局部极小问题研究[J]. 自动化学报, 2010, 36(8): 1122-1130.
	Zhu Yi, Zhang Tao, Song Jingyan. Study on the Local Minima Problem of Path Planning Using Potential Field Method in Unknown Environments[J]. Acta Automatica Sinica, 2010, 36(8): 1122-1130.
13	Tang Gang, Tang Congqiang, Claramunt Christophe, et al. Geometric A-star Algorithm: An Improved A-star Algorithm for AGV Path Planning in a Port Environment[J]. IEEE Access, 2021, 9: 59196-59210.
14	Chen Jiqing, Li Mingyu, Su Yousheng, et al. Direction Constraints Adaptive Extended Bidirectional A^* Algorithm Based on Random Two-dimensional Map Environments[J]. Robotics and Autonomous Systems, 2023, 165: 104430.
15	魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711.
	Wei Tong, Long Chen. Path Planning for Mobile Robot Based on Improved Genetic Algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 703-711.
16	陈凯, 解印山, 李彦明, 等. 多约束情形下的农机全覆盖路径规划方法[J]. 农业机械学报, 2022, 53(5): 17-26, 43.
	Chen Kai, Xie Yinshan, Li Yanming, et al. Full Coverage Path Planning Method of Agricultural Machinery under Multiple Constraints[J]. Transactions of the Chinese Society for Agricultural Machinery, 2022, 53(5): 17-26, 43.
17	Fatin Hassan Ajeil, Ibraheem Kasim Ibraheem, Ahmad Taher Azar, et al. Grid-based Mobile Robot Path Planning Using Aging-based Ant Colony Optimization Algorithm in Static and Dynamic Environments[J]. Sensors, 2020, 20(7): 1880.
18	Xu Lin, Cao Maoyong, Song Baoye. A New Approach to Smooth Path Planning of Mobile Robot Based on Quartic Bezier Transition Curve and Improved PSO Algorithm[J]. Neurocomputing, 2022, 473: 98-106.
19	乔乔, 王艳, 纪志成. 基于冲突搜索算法的多机器人路径规划[J]. 系统仿真学报, 2022, 34(12): 2659-2669.
	Qiao Qiao, Wang Yan, Ji Zhicheng. Multi-robot Path Planning Based on CBS Algorithm[J]. Journal of System Simulation, 2022, 34(12): 2659-2669.
20	Wu Zhengtian, Hamid Reza Karimi, Dang Chuangyin. A Deterministic Annealing Neural Network Algorithm for the Minimum Concave Cost Transportation Problem[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(10): 4354-4366.
21	Luo Min, Hou Xiaorong, Yang Jing. Surface Optimal Path Planning Using an Extended Dijkstra Algorithm[J]. IEEE Access, 2020, 8: 147827-147838.
22	Li Zhe, Li Yibin, Rong Xuewen, et al. Grid Map Construction and Terrain Prediction for Quadruped Robot Based on C-Terrain Path[J]. IEEE Access, 2020, 8: 56572-56580.
23	朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25(7): 961-967.
	Zhu Daqi, Yan Mingzhong. Survey on Technology of Mobile Robot Path Planning[J]. Control and Decision, 2010, 25(7): 961-967.
24	Akka Khaled, Khaber Farid. Mobile Robot Path Planning Using an Improved Ant Colony Optimization[J]. International Journal of Advanced Robotic Systems, 2018, 15(3): 1729881418774673.

[1]	黄志锋, 刘媛华. 基于改进哈里斯鹰和B-spline曲线的无人机路径规划研究[J]. 系统仿真学报, 2024, 36(7): 1509-1524.
[2]	朱子璐, 刘永奎, 张霖, 王力翚, 林廷宇. 基于深度强化学习的机器人轴孔装配策略仿真研究[J]. 系统仿真学报, 2024, 36(6): 1414-1424.
[3]	刘金辉, 陈孟元, 韩朋朋, 陈何宝, 张玉坤. 面向移动机器人大视角运动的图神经网络视觉SLAM算法[J]. 系统仿真学报, 2024, 36(5): 1043-1060.
[4]	雷旭, 陈静夷, 陈潇阳. 改进哈里斯鹰算法的仓储机器人路径规划研究[J]. 系统仿真学报, 2024, 36(5): 1081-1092.
[5]	刘泽森, 毕盛, 郭传鈜, 王延葵, 董敏. 基于深度学习的机器人局部路径规划方法[J]. 系统仿真学报, 2024, 36(5): 1199-1210.
[6]	王小康, 冀杰, 刘洋, 贺庆. 基于改进Q学习算法的无人物流配送车路径规划[J]. 系统仿真学报, 2024, 36(5): 1211-1221.
[7]	姜兆祯, 王文龙, 孙文祺. 基于改进RRT^*算法的无人艇路径规划快速求解算法[J]. 系统仿真学报, 2024, 36(4): 888-900.
[8]	张瑞, 周丽, 刘正洋. 融合RRT*与DWA算法的移动机器人动态路径规划[J]. 系统仿真学报, 2024, 36(4): 957-968.
[9]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[10]	闫星宇, 李大焱, 王妮娅, 张凯翔, 毛剑琳. 带障碍物惩罚因子的多机器人路径规划[J]. 系统仿真学报, 2024, 36(3): 673-685.
[11]	刘福琳, 李庆鑫. 多移动机器人混合避障算法的编队策略[J]. 系统仿真学报, 2024, 36(3): 726-734.
[12]	余翔, 姜陈, 段思睿, 邓千锐. 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.
[13]	庄鹤林, 夏小云, 李康顺, 陈泽丰, 张先超. 电动汽车路径规划模型与算法研究进展[J]. 系统仿真学报, 2024, 36(2): 320-337.
[14]	唐昀超, 祁少军, 朱立学, 卓献荣, 张芸齐, 孟繁. 移动机器人避障运动研究[J]. 系统仿真学报, 2024, 36(1): 1-26.
[15]	陈德峻, 方子豪, 曾云秀, 许凯. 战场迷雾中的欺骗路径规划[J]. 系统仿真学报, 2023, 35(9): 1895-1908.