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

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

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