摘要
在栅格环境建模方法的前提条件下,针对在较大规模、障碍物密集的工作环境中移动机器人难以进行实时路径规划的问题,利用栅格地图的结构特点提出一种松弛的Dijkstra算法。该方法首先采用四邻域搜索在线性时间内构建从源点到全局各点的曼哈顿距离势场,然后从目标点向源点进行八邻域搜索并返回一条无碰撞、近似最优路径。经过Matlab仿真实验证实该方法在计算时间上比采用堆排序实现的Dijksta算法和A-star算法快10倍以上,在路径长度上与最短路径相比误差处于合理范围之内。
Under the premise of using grid method in environment modeling, the problem of real-time path planning for mobile ro- bot in the larger-scale working environment with dense obstacles is difficult to solve. A new method of the global path planning for mobile robot-relaxed Dijkstra algorithm was proposed according to the characteristics of grid-map structure. A potential Manhattan distance filed from the start point to global points was constructed first by four neighborhood searching in linear time. Then, eight neighborhood searching was used to get a collision-free, near-optimal path from the target point to the start point. Last, the results of Matlab simulation experiments proved that the proposed method was ten times faster than the Dijkstra algorithm and A-star algo- rithm that had used heap sort on computing time, and compared with the shortest path, the length of its path had a reasonable error.
出处
《计算机与现代化》
2016年第11期20-24,共5页
Computer and Modernization
基金
国家自然科学基金资助项目(70971046)
