计算机与现代化

• 算法设计与分析 • 上一篇    下一篇

基于松弛Dijkstra算法的移动机器人路径规划

  

  1. 中北大学经济与管理学院,山西太原030051
  • 收稿日期:2016-03-28 出版日期:2016-11-15 发布日期:2016-11-23
  • 作者简介:潘成浩(1990-),男,山东费县人,中北大学经济与管理学院硕士研究生,研究方向:物流机器人路径规划与调度;郭敏(1969-),男,山西太原人,教授,博士,研究方向:系统建模与仿真,证据推理理论,供应链管理。
  • 基金资助:
    国家自然科学基金资助项目(70971046)

Path Planning for Mobile Robot Based on Relaxed Dijkstra Algorithm

  1. College of Economics and Management, North University of China, Taiyuan 030051, China
  • Received:2016-03-28 Online:2016-11-15 Published:2016-11-23

摘要: 在栅格环境建模方法的前提条件下,针对在较大规模、障碍物密集的工作环境中移动机器人难以进行实时路径规划的问题,利用栅格地图的结构特点提出一种松弛的Dijkstra算法。该方法首先采用四邻域搜索在线性时间内构建从源点到全局各点的曼哈顿距离势场,然后从目标点向源点进行八邻域搜索并返回一条无碰撞、近似最优路径。经过Matlab仿真实验证实该方法在计算时间上比采用堆排序实现的Dijksta算法和A-star算法快10倍以上,在路径长度上与最短路径相比误差处于合理范围之内。

关键词: 栅格法, 移动机器人, 路径规划, 松弛Dijkstra算法

Abstract: Under the premise of using grid method in environment modeling, the problem of real-time path planning for mobile robot 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 〖JP2〗algorithm that had used heap sort on computing time, and compared with the shortest path, the length of its path had a reasonable error.〖JP〗

Key words: grid method, mobile robot, path planning, relaxed Dijkstra algorithm

中图分类号: