基于改进概率栅格分解的路径规划算法

Path Planning Based on Improved Probabilistic Cell Decomposition

栅格分解法是目前研究最广泛的路径规划方法之一,但随着机器人自由度增加会出现"维数灾难"问题,不太适合于解决高自由度机器人在复杂环境中的路径规划。该文提出了基于改进概率栅格分解的路径规划算法,将随机采样应用到栅格分解算法中,虽然不能保证算法的最优性,却极大地提高了算法的效率,使其适合于解决高自由度机器人在复杂环境下的路径规划问题。仿真试验表明该算法可以在较短时间内获得可通行的路径。

The path planning based on cell decomposition is one of the most popularly studied methods. There is a problem called dimension curse with the dimension of robot freedom increasing, so it disagrees with solving the problem of path planning for high-dimensional robot in complex environment. Therefore, this paper presents an algorithm of path planning based on improved probabilistic cell decomposition. The path constructed by this algorithm is not the best, because probabilistic sampling is introduced in the algorithm. But the efficiency of the algorithm is improved owing to probabilistic sampling, so it is adapted to solve the problem of path planning for the complex environment. Simulation shows improved that this algorithm can quickly find a feasible path.