机器人路径规划、轨迹优化系列课程
路径规划
一、基于搜索的路径规划
- Dijkstra
栅格地图：对障碍物进行膨胀处理，对机器人看作质点。
https://github.com/AtsushiSakai/PythonRobotics
代码解读：建立栅格地图、障碍物、起终点、画图；栅格大小、转弯半径、障碍物位置；
初始化地图、初始化障碍物grip、膨胀障碍物；机器人运动方式motion，节点node，open_set、close_set、calc_index、
算法复杂度：哈希表、优先级队列；
- A*
算法和dijkstra差不多，加上启发式算法，直接导向终点，无需搜索更大的范围，比dikstra算法更优
二、基于采样的路径规划
- RRT
原理：快速扩展随机树算法（Rapidly Exploring Random Tree）
代码讲解：设计障碍物、采样距离、采样步长、迭代次数、判断是否碰撞、是否靠近终点
总结：找到路径快、路径较差
- RRT*
目标：找到一条更优的路径
方法：找出更短的父节点
总结：速度慢
- Inform RRT*
目标：速度更快
方法：椭圆在不断缩小，限制采样范围
代码：
- 概率路线图算法PRM（Probabilistic Roadmap）
构建概率路线图
在图上寻找路径
总结：两阶段，速度慢，不能找到最优路径，
三、基于智能算法的路径规划
- 遗传算法
原理：选择、交叉、变异
种群初始化
选择：适应度函数（距离的倒数、角度函数）、概率轮盘赌、
交叉：交换交叉点路径
变异：随机选择路径两个栅格
代码：matlab
main
产生种群
遗传变异
generate_continuous_path
cal_path_value计算距离，适应度函数一部分
cal_path_smooth计算角度，适应度函数一部分
selection轮盘赌选择
crossover交叉
mutation变异
- 蚁群算法
和遗传算法差不多
轨迹优化
一、轨迹表示方法
- 多项式曲线（论文）
上述公式很重要
优化目标：上述最小，论文提出该观点
公式推导：
建立约束s.t.：位置约束、速度约束、加速度约束、连续性约束；二次规划问题；
代码讲解：等式构建
不等式构建：安全飞行走廊
闭式求解（论文）
总结：可以平滑曲线、但不会考虑障碍物信息；
无约束优化问题、
- 贝塞尔曲线
二、轨迹优化目标
- mininum snap
- 轨迹长度
三、轨迹约束方法
- 软约束
论文: 梯度下降、目标函数求取最小值
代码：ros仿真代码学习
github.com/HKUST.Aerial.Robotics/grad_traj_optimization
总结：基于软约束的轨迹优化方法，当目标函数比较复杂时，可能会导致轨迹和障碍物产生碰撞
- 硬约束
贝塞尔曲线
