计算机工程 ›› 2007, Vol. 33 ›› Issue (21): 160-162,.doi: 10.3969/j.issn.1000-3428.2007.21.057

• 人工智能及识别技术 • 上一篇    下一篇

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

吕太之1,赵春霞2   

  1. (1. 江苏海事职业技术学院信息工程系,南京 211170;2. 南京理工大学计算机科学与技术学院,南京 210094)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-05 发布日期:2007-11-05

Path Planning Based on Improved Probabilistic Cell Decomposition

LV Tai-zhi1, ZHAO Chun-xia2   

  1. (1. Dept. of Information Engineering, Jiangsu Maritime Institute, Nanjing 211170; 2. School of Computer Science and Technology, Nanjing University of Sciences and Technology, Nanjing 210094)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-11-05 Published:2007-11-05

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

关键词: 概率栅格分解, 路径规划, 移动机器人

Abstract: 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.

Key words: probabilistic cell decomposition, path planning, mobile robot

中图分类号: