移动机器人路径规划算法的研究

RESEARCH ON PATH PLANNING OF MOBILE ROBOT

路径规划技术作为机器人研究领域中的一个重要分支,是依据某些优化准则,在其工作空间中找到一条从起始状态到目标状态的最优无碰路径。本文针对机器人路径规划技术进行了深入地研究,阐述了机器人路径规划问题的三个子问题等内容,讨论了传统路径规划方法和基于智能算法的路径规划方法。本文运用传统Dijkstra算法的贪心策略,针对静态环境下移动机器人路径规划的寻路径子问题,提出了一种改进的Dijkstra路径规划算法。该算法借助具有"先进先出"特点的队列,采用广度优先遍历二维网络结点。该算法在选择邻接结点进行遍历的时候,采用的禁忌策略是禁止访问已经访问的结点,以及被标识为障碍物的结点。实验及分析表明,该算法能准确并快速地寻找到最优路径,且时间复杂度为O(4*n)。

Path planning, an important branch of the robotics research, generates a collision-free path in workspace with respect to some criterion. We study on the path planning techniques of mobile robot, describe three sub-problems of path planning and discuss the traditional path planning algorithm and intelligent path planning algorithm. According to the greedy strategy of Dijkstra algorithm, we propose the Improved Dijkstra algorithm （ID algorithm） in view of path planning in a static environment. The ID algorithm traverses the two-dimensional grid in breadth-first strategy by means of the FIFO queue. In the choice of adjacent grid node, the ID algorithm adopts the tabu search strategy whose tabu restriction is to forbid visiting tabu or traversed nodes. The experimental evaluations on four different grids and analysis show that the ID algorithm produces the shortest path very quickly and its time complexity is O（4＊n）.