Abstract: Path planning is one of the key technologies for robot navigation. An excellent path planning algorithm can quickly find the best collision-free path and improve operational efficiency. Most existing classification methods have difficulty in expressing the differences and connections between algorithms. To distinguish different path planning algorithms more clearly, they are divided into graph-based search, bionic-based, potential field-based, velocity space-based and sampling-based algorithms based on their principle and nature. This paper introduces the concept, characteristics, and development status of each type of algorithm, analyzes the more widely used sample-based algorithms from the perspective of single-query and multi-query algorithms, and the advantages and problems of different types of path planning algorithms are compared and summarized. Finally, the future development trend of robot path planning algorithms in terms of multi-robot collaboration, multi-algorithm fusion and adaptive planning is prospected.

Key words: robot, path planning, heuristic algorithms, obstacle avoidance algorithms, sampling-based algorithms

摘要： 路径规划算法是机器人导航的关键技术之一，优良的路径规划算法能够快速找出最佳无碰撞行走路径，提高运行效率。大多数现有的分类方法难以表述清楚算法间的区别与联系，根据机器人路径规划算法的设计原理，将其分为基于图搜索、基于仿生、基于势场、基于速度空间和基于采样的规划算法以更清晰地区分不同的路径规划算法。阐述了每类算法的概念、特点和发展现状，并从单查询算法和多查询算法的角度重点分析了应用更为广泛的基于采样的算法，对比总结了不同类型路径规划算法的优缺点，从多机器人协作、多算法融合和自适应规划等方面展望了机器人路径规划算法的未来发展趋势。

关键词: 机器人, 路径规划, 启发式算法, 避障算法, 采样算法