结合维诺区域分割和路径优化的路径规划算法

doi:10.3778/j.issn.1002-8331.2302-0168

摘要/Abstract

摘要： 在一些较大面积的建筑物内，移动机器人的路径规划算法的效率仍然面临着较大的挑战。针对这类工作场景，提出了一种结合维诺区域分割和路径优化的路径规划算法（Voronoi region segmentation and path optimization，VSO），实现在大规模室内场景下的快速路径规划。该算法使用广义维诺图（generalized Voronoi graph，GVG）从地图中构建拓扑图，在拓扑图上可以快速获得初始启发式路径。通过将采样过程约束在初始路径周围的区域，减少了对工作空间的过度探索。在此基础上，选择路径点将采样区域划分为多个子区域，之后在子区域中并行搜索路径来减少搜索空间并提升搜索速度。最后将连接各个子区域内的路径作为结果路径，并使用优化算法来平滑最终路径。仿真实验与机器人实验验证了该算法的实用性与有效性。

关键词: 移动机器人, 路径规划, 路径优化, 多线程

Abstract: In some large buildings, the efficiency of path planning algorithms for mobile robots still faces great challenges. To deal with this problem, a path planning algorithm combining Voronoi region segmentation and path optimization (VSO) is proposed to achieve fast path planning in large-scale indoor scenario. The algorithm uses the generalized Voronoi graph (GVG) to construct the topological map from the environmental map, and then the initial heuristic path can be obtained quickly on the topological map. By sampling in the area around the initial path, the over-exploration of the workspace can be reduced. What’s more, the algorithm selects waypoints to divide the sampling area into multiple sub-regions, and search paths in the sub-regions in parallel to further reduce the search space and improve the search efficiency. Finally, the path obtained from each sub-region is connected as the solution of the overall problem, and the optimization algorithm is used to smooth the final path. Simulation and robot experiments are conducted to verify the practicability and effectiveness of the proposed algorithm.

Key words: mobile robot, path planning, path optimization, multithreading

江纯兴, 吴锋. 结合维诺区域分割和路径优化的路径规划算法[J]. 计算机工程与应用, 2024, 60(10): 311-319.

JIANG Chunxing, WU Feng. Path Planning with Voronoi Region Segmentation and Path Optimization[J]. Computer Engineering and Applications, 2024, 60(10): 311-319.

参考文献

[1] 王鹤静, 王丽娜.机器人路径规划算法综述[J].桂林理工大学学报, 2023, 43(1): 137-147.
WANG H J, WANG L N. Review of path planning for robots[J]. Journal of Guilin University of Technology, 2023, 43(1): 137-147.
[2] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[3] BREMERMANN H J. The evolution of intelligence: the nervous system as a model of its environment[D]. Washington: University of Washington. Department of Mathematics, 1958.
[4] 张硕航, 郭改枝.多旅行商模型及其应用研究综述[J].计算机科学与探索, 2022, 16(7): 1516-1528.
ZHANG S H, GUO G Z. Review of multiple traveling salesman model and its application[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1516-1528.
[5] 李珺, 段钰蓉, 郝丽艳, 等.混合优化算法求解同时送取货车辆路径问题[J].计算机科学与探索, 2022, 16(7): 1623-1632.
LI J, DUAN Y R, HAO L Y, et al. Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery-pickup[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1623-1632.
[6] 肖金壮, 余雪乐, 周刚, 等.一种面向室内AGV路径规划的改进蚁群算法[J].仪器仪表学报, 2022, 43(3): 277-285.
XIAO J Z, YU X L, ZHOU G, et al. An improved ant colony algorithm for indoor AGV path planning[J]. Chinese Journal of Scientific Instrument, 2022, 43(3): 277-285.
[7] HART P E, NILSSON N J, RAPHAE B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science & Cybernetics, 1972, 4(2): 28-29.
[8] STENTZ A. Optimal and efficient path planning for partially known environments[M]//Intelligent unmanned ground vehicles. Boston: Springer, 1997: 203-220.
[9] LAVALLE S. Rapidly-exploring random trees: a new tool for path planning[R]. Iowa State University, 1998.
[10] KAVRAKI L E, SVESTKA P, LATOMBE J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1996, 12(4): 566-580.
[11] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
[12] SALZMAN O, HALPERIN D. Asymptotically near-optimal RRT for fast, high-quality motion planning[J]. IEEE Transactions on Robotics, 2016, 32(3): 473-483.
[13] KUFFNER J J, LAVALLE S M. RRT-connect: an efficient approach to single-query path planning[C]//Proceedings of the 2002 IEEE International Conference on Robotics and Automation, 2002: 995-1001.
[14] 刘奥博, 袁杰.目标偏置双向RRT*算法的机器人路径规划[J].计算机工程与应用, 2022, 58(6): 234-240.
LIU A B, YUAN J. Robot path planning based on goal biased bidirectional RRT* algorithm[J]. Computer Engineering and Applications, 2022, 58(6): 234-240.
[15] JANSON L, SCHMERLING E, CLARK A, et al. Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions[J]. The International Journal of Robotics Research, 2015, 34(7): 883-921.
[16] GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014: 2997-3004.