移动机器人规划 - 概述

文章旨在对深蓝学院移动机器人规划系列课程学习记录，方便日后回顾今日所学

1 移动机器人概述

本课程期望：实用第一

自动驾驶机器人：具有高度自动化（不受外部影响）的机器人

所属领域：计算机科学、自动化、机械、电子。。。

自动驾驶机器人各个模块的一般要求：
（1）估计：低延迟、高准确性和一致性
（2）感知：3D感知或密集感知、用于规划的地图融合和集成
（3）规划：复杂或者未知的环境、安全和动态可行性、有限的感知和计算
（4）控制：迅速的执行、平滑轨迹跟踪

1.1 什么是运动规划

基本要求：
（1）安全：无碰撞
（2）平滑：节省能源、舒适
（3）动态可行性：控制器可执行

学院派的思路：

前端路径搜索：在离散低维空间下搜索出一条安全的路径

后端轨迹生成：搜索可执行的轨迹（高维、连续空间）

1.2 如何做机器人相关的研究

重要！！！！

发现问题
（1）如果一个问题在想象中出现，那根本不是一个问题。对于机器人领域来说，一定要解决实际真实存在的问题，否则方法和算法是没有多大意义的，因为并不确定这个问题在真实的机器人系统中是否真的存在。
（2）每个机器人学家是一个出色的工程师，需要知道这些算法在机器人里是怎么运转的
（3）不要盲目的跟从热点话题
（4）诚实，想象中存在的问题根本就不是一个实际的问题

解决问题
（1）不要故意地让问题变得复杂
（2）简单但有效的方案在机器人领域中一定是最受欢迎的
（3）仿真能说明的问题很小，一定要在真实的机器人上进行展示
（4）解决真实存在的问题，并彻底解决它

1.3 如何做运动规划相关的研究

全面了解规划
（1）针对不同的场景选择合适的方略
（2）自定义制定策略
勇于动手
不要等着做事情，不要只读论文。自己去做大量的编码工作，实地工作

了解整个系统
关心机器人中的每一个部分

2 课程大纲

前端：路径搜索
（1）基于搜索的路径查找

• 图搜索基础
• Dijstra和A*
• JPS
• 作业

（2）基于采样的路径查找

• PRM
• RRT
• 基于优化采样的方法
• 基于采样的更一步的方法
• 作业

（3）基于动力学约束的路径搜索

• 介绍
• 状态 - 状态边界值最优控制问题
• State Lattice Search
• Kinodynamic RRT*
• 混合A*
• 作业

后端：轨迹生成
（1）Minimum snap轨迹生成

• 微分平坦
• Minimum Snap的优化
• Minimum Snap的闭式解
• 时间分配
• 实践应用
• 作业

（2）软硬约束轨迹优化

• 软约束轨迹优化
• 硬约束轨迹优化
• 作业

MDP & MPC
（1）基于马尔可夫决策树的规划

• 不确定性规划和MDP
• Minimax Cost Planning and Expected Cost Minimal Planning
• 值迭代和实时动态规划
• 作业

（2）机器人规划的模型预测控制

• Introduction
• 线性MPC
• 非线性MPC
• 作业

2.1 前端：路径搜索

对于每个搜索问题，都有一个对应的状态空间图。图中节点的连通性由有向边或者无向边来表示。
栅格地图：

拓扑地图：

基于搜索：
（1）一般图搜索方法：DFS、BFS
（2）Dijstra和A*搜索
（3）JPS

基于采样：
（1）PRM

（2）RRT
（3）RRT*，启发式RRT*

Kinodynamic Path Finding：
（1）State Lattice Search
建立一个移动机器人的动力学模型，将它的控制量进行一个离散化，对于一个简单的汽车模型或者自行车模型，在不同的方向上打方向盘，并且按照固定的大小去踩油门，可以产生汽车往前行进的路径。在一个固定的时间里把路径都连接起来，获得图，在一个高维的空间里搜索出一条最短路径。但是这种图搜索代价必定十分高昂的，为了让这种算法真正有效地应用在移动机器人上，下面地混合A* 算法应运而生。

（2）混合A*

• 遵循A* 算法
• 正向模拟不同离散控制输入的状态
• 每个栅格中仅保留一个状态

（3）Kinodynamic RRT*

• 遵循RRT*算法
• 采样一个随机状态
• 解决两个边界状态的最优控制问题

2.2 后端：轨迹优化

（1）Basic Minimum-snap

用基于采样的路径规划算法在复杂环境中找到一条几何无碰撞安全的路径，沿着这个Path，把这里Path的分段点作为Minimum-snap轨迹生成的路标点，显然折线不会碰到障碍物，但是生成的轨迹有可能碰到障碍物。应对措施：假设生成的轨迹在某个地方碰到了障碍物，在两个RRT* 路径的两个路标点之间的中点取一个新的路标点。也就是说在轨迹会发生碰撞的地方，让他尽可能逼近前端路径的直线从而规避碰撞。

（2）硬约束下的Minimum-snap

（3）软约束下的Minimum-snap

3 地图表示

Map：数据结构 + 融合方法
（1）占用的栅格地图

• 最密集
• 结构化
• 直接索引查询
  

https://github.com/ANYbotics/grid_map

（2）八叉树地图
环境真正包含障碍物的地方比较少，对于这些地方，不一定需要把它进行密集的切分，占用内存

• 稀疏
• 结构化
• 间接索引查询

https://octomap.github.io/

（3）Voxel hashing 哈希表

• 最稀疏
• 结构化
• 间接索引查询
  

https://github.com/niessner/VoxelHashing

（4）点云地图

• 无序
• 无法查询
  

（5）TSDF地图
截断符号距离函数
假设一个相机对环境进行了观测，曲面假设为障碍物，曲面有距离场，场内表示正值，场外不知道外面是什么表示为负值。截断的意思就是不需要维护整个地图里所有点的距离值，只关心扇形这样的锥形区域，然后按照距离截断

https://github.com/personalrobotics/OpenChisel

（6）ESDF地图
欧式符号距离函数增量式地图，全局地图

Distance Transforms of Sampled Functions, PF Felzenszwalb

（1）https://github.com/ethz-asl/voxblox
（2）https://github.com/HKUST-Aerial-Robotics/FIESTA
（3）https://github.com/HKUST-Aerial-Robotics/Teach-Repeat-Replan

（7）自由空间路线图

https://github.com/HKUST-Aerial-Robotics/Teach-Repeat-Replan

（8）Voronoi图

https://github.com/ethz-asl/mav_voxblox_planning

---

加油😀😀😀