运动规划之搜索算法：前端规划、后端轨迹生成到状态求解 _算法

背景：16-18年做过一阵子无人驾驶，那时候痴迷于移动规划；然而当时可学习的资料非常少，网上的论文也不算太多。基本就是Darpa的几十篇无人越野几次比赛的文章，基本没有成系统的文章和代码讲解实现。所以对移动规划的认识不算全面，这几年随着自动驾驶、无人机的研究和应用的增多，很多的论文课程成体系的开始介绍这方面的内容。对于一个理工男来说机器人并且是能自动的、智能规划的，相信没有多少理工男是可以抗拒不想去做进一步了解的。所以一直在收集资料，筹划这哪一天可以出一个这方面系列，然后在code一个项目出来在机器人上捣腾各种实现。再一次加速本人对这一想法落实是两年前看到fast-lab高飞团队出的一系列飞行走廊解决无人机路径规划的工作视频。第一次看到视频时候真被震惊到，移动规划原来还可以这么玩，如此优美的数学框架。讲了这么多只是想致敬过去的经历，开启这个专题第一讲。这个系列主线就是围绕高飞老师《移动机器人动态规划》课程讲稿，里面会补充一些算法细节和自己的思考。这个课程对移动规划体系框架构建非常棒，内容排布的也非常好，唯一缺憾就是对于动态不确定障碍物的规划会少一些，因为课程本来就是针对无人机设计的。
正文：现代机器人学和自动驾驶等领域，路径规划是一个重要的主题. 它涉及到在给定的环境中找到从起点到终点的最优路径. 这个过程通常分为两个部分：前端路径搜索和后端轨迹规划. 前端路径搜索在地图中搜索出一条避开障碍物的轨迹，而后端轨迹规划则对搜索到的轨迹进行优化，使其符合机器人的运动学和动力学约束.
实环境中的机器人运动规划是一个比较复杂的问题，对于复杂的问题人类的解法一般都是分步求解：先做个大概、然后在大概轮廓上逐步的复杂精细。机器人运动规划的学院派解法也是如此：
1.前端：路径规划

基于搜索的方法
通用图搜索：深度优先搜索（DFS），广度优先搜索（BFS）
Dijkstra 和 A* 搜索
跳点搜索
基于采样的方法
概率路线图（PRM）
快速探索随机树（RRT）
RRT，有信息的 RRT
带动力学约束路径规划
状态-状态边界值最优控制问题
状态栅格搜索
动力学RRT*
混合A*

2.后端：轨迹生成

最小抖动轨迹生成
微分平坦性
最小抖动优化
最小抖动的闭式解
时间分配
实际应用
软硬约束轨迹优化
软约束轨迹优化
硬约束轨迹优化

3.不确定性状态求解：移动障碍物、突变环境、设备建模变化

基于马尔可夫决策过程的规划（MDP）
规划中的不确定性和马尔可夫决策过程
最小最大成本规划和期望成本最小规划
值迭代和实时动态规划
机器人规划的模型预测控制（MPC）
线性模型预测控制
非线性模型预测控制

前端——搜索路径规划在开始这部分内容介绍前，需要介绍几个概念。介绍这几个概念的目的在于更贴近实际的去理解搜索在业务中应用。搜索路径规划中是把机器人当成一个质点来考虑的，然而实际的机器人是有一定形状和占用空间的，如果把机器人当成质点来考虑很可能是会搜索出一条实际上不可行的（会碰到障碍物的）路径的。为了解决这个问题呢，我们可以简单的物体的形状转移到地图（让地图障碍物区域加上物体占用空间）。在这样的地图里把机器人当成质点来搜索可行路径。