Research on Map partitioning and Preprocessing Algorithms for Global Path Planning

摘要

Indoor mobile robots utilize SLAM technology to acquire indoor maps and rely on these maps to accomplish navigation tasks. In this paper, a new indoor partitioning algorithm is proposed to process indoor maps and enable it to perform in-door map partitioning tasks. Compared with the neural network partitioning algorithm, which requires large scale map data set, and the bullock cell decomposition method, which is susceptible to obstacles. The algorithm proposed in the article has the advantages of not requiring datasets to pretrain the algorithm and the indoor partitioning effect is less likely to be affected by obstacles compared to the boustrophedon cellular decomposition. Subsequently, a global path planning preprocessing algorithm based on indoor map partitioning is proposed in this paper. The essence of the algorithm is to reduce the computational effort of the global path planning algorithm by using the elimination of non-relevant regions of the indoor map. In this paper, the sampling-based global path planning algorithms RRT and PRM, and the graph search-based global path planning algorithms A* and Dijkstra are selected for testing. Finally, the average time consumed by the six groups of preprocessing algorithms based on indoor partitioning is 9. 2333ms, taking the hospital scene graph as an example. In the comparison of the three sets of global path planning tasks, the global path planning task using preprocessing showed a significant reduction in computation time compared to the global path planning task without preprocessing. the computation time of the A* algorithm was reduced by 15.69%, the computation time of the Dijkstra algorithm was reduced by 37.6%, the computation time of the RRT algorithm was reduced by 44.21%, and the computation time of the PRM algorithm was reduced by 61.28%.