移动机器人路径规划综述

传播知识是一项伟大的使命。

路径规划（Path Planning）是移动机器人最重要的任务之一，担负着移动机器人改变自身位置的重大使命。我对移动机器人的路径规划充满兴趣，并一直希望能够对这一领域有一个全面而深入地理解。在了解了一些路径规划算法之后，找了几篇关于路径规划方面的综述性文章，做了一些笔记，整理在此，大家相互学习。
目前对路径规划算法的分类标准比较多样，但是大致上可以分为以下几类：

依据信息的多寡

• 全局路径规划算法：从整体环境出发，依据整幅地图的全部信息（比如障碍物的形状、位置、是否运动等信息），规划出一条从起点到目标位置安全无碰撞路径。比如A*、Dijkstra算法、RRT系列算法等。
• 局部路径规划算法：仅仅依据机器人周边的环境信息来进行路径规划，信息不够全面，但是对动态的障碍物有很好的表现，多用于避障。比如VFH系列算法。

环境动态与否

• 静态路径规划算法：该类算法假设环境是静态的，规划出的路径对环境中运动的障碍物应对能力较差。所有算法都可以当做静态路径规划算法。
• 动态路径规划算法：该类算法考虑到了环境中运动的障碍物，比如人活着其他机器人，应对不虞之境的能力比较好。比如势场法。

方法思路

• 经典路径规划算法：顾名思义就是那些传统的、经典的路径规划算法。比如visibility graph、voronoi diagram等。
• 启发式路径规划算法：与经典算法相区别，这一类算法加入了启发性信息，最典型的比如**A***算法。
• 人工智能路径规划算法：随着人工智能的兴起而出现的一系列算法，比如遗传算法GA、粒子群优化算法PSO、蚁群算法ACO等。

看起来，好像依据第三种分类方法更加容易把各个算法区别开来。但是有些启发式搜索和经典算法并不是特别容易区分，因此，本文只按照经典/启发式算法和人工智能算法两大类来介绍。力图把当前移动机器人路径规划的研究现状厘清。
因此本文计划介绍以下这些算法：

1、经典路径规划算法

• Cell Decomposition算法：Exact CD、Approximate CD、Probability CD
• roadmap算法：visibility graph 、voronoi diagram、PRM
• 图搜索算法：BFS、Dijkstra、A*、Hybrid A*
• RRT系列：RRT、RRT*、Informed RRT*
• 势场法PF
• VFH系列：VFH、VFH+、VFH*

2、人工智能路径规划算法

• 遗传算法GA
• 差异进化DE
• 蚁群优化算法ACO
• 粒子群优化算法PSO
• 人工蜂群算法ABC
• 蝙蝠算法BAT
• 爬山法、
• 模拟退火AS
• 人工免疫算法AIA
• 模糊系统Fuzzy System
• 神经网络NN