Motion planning
autonomous robot
总结一下什么是自主机器人：
首先我们需要状态估计（定位）；
基于此，利用传感器融合人建立一个周围环境的三维地图；
基于状态估计和感知，运动规划模块被要求在复杂、未知的环境下能够生成安全且动力学可行的移动机器人运动轨迹；
最后交给控制器实现所生成的轨迹；
T(what）
basic requirements
- safety: collision avoidance
- smoothness: energy saving, comfort,stable
- kinodynamic feasibility: executable , controllable
本门课程运动规划的风格，是把整个规划问题分为前端（路径发现/路径搜索）和后端（轨迹生成/轨迹优化）。在前端，要在一个相对低维的状态空间（通常是离散的），去找一个初始的、安全的、让机器人课通行的一个初始值，解的质量可能不是很好，我们称之为Path，这个路径通常是没有时间信息的并且只局限在低维的信息。之后我们再通过后端的轨迹优化，把这样一个低维的Path转变为可执行的高维的轨迹，会用到很多优化的技巧。
w(How)
首先要有一个对规划的总体认知，针对不同的场景不同的需求选择合适的算法，并且常常需要设计一些自定义的策略；第二点就是要勇于去做，去调试；最后，因为规划属于一个相对顶层的位置，下面有感知定位控制机械设计等内容，所以要知道整个系统的运作才能真正的知道规划的算法是否是有效的。不需要真的去参与到那些部分的开发，但至少要熟悉，达到能够去维护的要求。
相关领域的课题组推荐
front-end path finding
- search for an initial safe path
- low dimensional
- discrete space
e.g search-basic ,sample-basic, kinodynmic path
⚫ SEARCH-BASED PATH FINDING
➢ Graph Search Basis
➢ Dijkstra and A*
➢ Jump Point Search
⚫ SAMPLING-BASED PATH FINDING
➢ Probabilistic Road Map
➢ Rapidly-exploring Random Tree (RRT)
➢ Optimal Sampling-based Methods
➢ Advanced Sampling-based Methods
⚫ KINODYNAMIC PATH FINDING
➢ Introduction
➢ State-state Boundary Value Optimal Control Problem
➢ State Lattice Search
➢ Kinodynamic RRT*
➢ Hybrid A*（在无人驾驶中应用广泛）
对于每个基于图搜索的路径规划问题，都有一个相应的状态空间图,图中节点之间的连通性用(有向或无向)边表示
PRM
RRTvs RRT
informed RRTz
在椭圆内采样，收敛时间快 - kinematic dynamic path finding
- state lattice search
Hybrid A*
与lattice grid相似，只会在一个栅格里保留一个点
Kinodynamic RRT*
需要转化为两点边界值最优问题进行求解
back-end trajectory generation (后端）
- search for an executable trajectory
- high dimensional
- continuous space
e.g minimum snap trajectory generation, soft and hard constrained trajectory optimization
MDP(markov decision process-based planning)&MPC(model predictive control for robotics planning)
⚫ MINIMUM SNAP TRAJECTORY GENERATION
➢ Differential Flatness
➢ Minimum Snap Optimization
➢ Closed-form Solution to Minimum Snap
➢ Time Allocation
➢ Implementation in Practice
⚫ SOFT AND HARD CONSTRAINED TRAJECTORY OPTIMIZATION
➢ Soft Constrained Trajectory Optimization
➢ Hard Constrained Trajectory Optimization
⚫ MARKOV DECISION PROCESS-BASED PLANNING
➢ Uncertainties in Planning and MDP
➢ Minimax Cost Planning and Expected Cost Minimal Planning
➢ Value Iteration and Real-Time Dynamic Programming
⚫ MODEL PREDICTIVE CONTROL FOR ROBOTICS PLANNING
➢ Introduction
➢ Linear MPC
➢ Non-linear MPC
- find problem
- find actual problem
- engineer first
- solve
- simple but effective solution is always preferable
- no just simulation
for different scenarios, suitable methods
don’t wait ,move
Type
basic minimum-snap
hard constrained Minimum-snap
将安全空间表示为凸的解空间-
soft constrained Minimum-snap
Map
数据结构和用什么方法做数据融合
最简单 occupancy grid map
2.5D地图，在空间上堆方块
- 特点
密集切分
结构化
直接索引
但实际上障碍物不需那么多,链接
最常用的是栅格地图表示，具有以下几个特点：最稠密；结构化；直接进行坐标索引查询：复杂度为O ( 1 )
octo-map
递归8切分地图
八叉树结构：没有障碍物的用一个大的空白方块表示，有障碍物的地方递归切分，直到找到包含障碍物的小方块 ，将其存储到内存中。
特点：稀疏；结构化；非直接的坐标索引查询(树查询)。
- 特点
非直接查询，需要根据树结构来查询，
结构化
voxel hashing
体素哈希
离散结构，使用哈希表访问,分成两级
坐标->block->hash table ->精确查询
- 特点
特别稀疏（适合于视觉地图重建）
结构化 ,非直接的坐标索引查询
point cloud map
PCL 点云数据,文档非常全，这个库可以看看
不过是无序的；无法进行坐标索引查询
TSDF map(truncated signed distance function
按距离进行截断
截断的有符号距离函数
应用案例
如果不截断,则为ESDF
ESDF map
欧式带符号的距离函数。
应用案例
VoxBlox
FIESTA 高飞博士和同学写的
TRR’s Local Map
Free-space Roadmap
凸的多面体有助于路径规划
Voronoi Diagram Map
拓扑地图
路径搜索节省很多资源
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
