解决问题
解决机器人如何去到目标点的问题。
常用算法
A*（A Star）
原理
测试
animation
说明：使用A星算法进行基于二维网格的最短路径规划，动画中青色点为搜索过的节点，启发算法为二维欧几里得距离。
animation_two_side
批量Informed RRT*（Batch Informed RRTStar）
原理
测试
说明：这是使用批量Informed RRT*的路径规划代码。
贝塞尔曲线法（Bezier Path）
原理
【路径规划】局部路径规划算法——贝塞尔曲线法（含python实现 | c++实现）
测试
双向A*（Bidirectional AStar）
原理
测试
双向广度优先搜索（Bidirectional Breadth First Search）
原理
测试
广度优先搜索（Breadth First Search）
原理
测试
B-spline曲线（B Spline Path）
原理
测试
说明：这是段使用B样条曲线进行规划的例子，输入路点，它会利用B样条生成光滑的路径，第一个和最后一个路点位于最后的路径上。
（Bug Planning）
原理
自动驾驶决策规划算法 - Bug Algorithms Bug算法
测试
闭环RRT*（Closed Loop RRT Star）
原理
测试
说明：使用闭合回路RRT*（Closed loop RRT*）实现的基于车辆模型的路径规划，这段代码里，转向控制用的是纯追迹算法（pure-pursuit algorithm），速度控制采用了PID。
回旋曲线（Clothoid Path）
原理
[Python|Clothoid]Clothoid曲线（回旋曲线）与直角坐标求解的python实现
测试
三次样条插值（Cubic Spline）
原理
测试
说明：这是段三次路径规划的示例代码，这段代码根据x-y的路点，利用三次样条生成一段曲率连续的路径。
每个点的指向角度也可以用解析的方式计算。
深度优先搜索（Depth First Search）
原理
DFS——深度优先算法（Depth First Search）
测试
迪杰斯特拉（Dijkstra）
原理
测试
说明：这是利用迪杰斯特拉（Dijkstra）算法实现的基于二维网格的最短路径规划，动画中青色点为搜索过的节点。
D*（D Star）
原理
测试
D * Lite（D Star Lite）
原理
测试
杜宾斯路径（Dubins Path）
原理
APA(自动泊车辅助系统)-第三讲 路径规划算法(Dubins算法)
测试
动态运动基元（Dynamic Movement Primitives）
原理
DMP(Dynamic Movement Primitives)算法简介
Dynamic Movement Primitives介绍及Python实现与UR5机械臂仿真
测试
动态窗口法(Dynamic Window Approach)
原理
测试
- 原理
动态窗口法在一定程度上采用了粒子滤波的思想，在速度空间（v,w）中采样多组速度，并模拟出这些速度在一定时间内的运动轨迹，并通过评价函数对这些轨迹进行评价，选取最优轨迹对应的速度驱动机器人运动。
2.基本思想：
（1）在机器人的控制空间中离散采样 (dx,dy,dtheta)；
（2）对于每个采样速度，从机器人的当前状态执行前向模拟，以预测如果采样速度应用于某个（短）时间段会发生什么；
（3）使用包含以下特征的度量来评估前向模拟产生的每个轨迹：与障碍物的距离、与目标的距离、与全局路径的距离和速度，排除非法轨迹（与障碍物相撞的轨迹）；
（4）选择得分最高的轨迹并将相关的速度发送到移动基地；
（5）重复执行上述步骤。
3.优点
（1）计算简单
（2）适用于差分和全向车模
4.缺点
（1）前瞻性不足
（2）动态效果差
（3）不适用于阿克曼模型车模
（Eta3 Spline Path）
原理
测试
（Eta3 Spline Trajectory）
原理
测试
（Flow Field）
原理
测试
（Frenet Optimal Trajectory）
原理
测试
（Greedy Best First Search）
原理
测试
（Grid Based Sweep CPP）
原理
测试
（Hybrid AStar）
原理
测试
（Informed RRT Star）
原理
测试
说明：青色椭圆为Informed RRT*的启发采样域。
（ LQR Planner）
原理
测试
（LQR RRT Star）
原理
测试
说明：这是个使用LQR-RRT*的路径规划模拟，LQR局部规划采用了双重积分运动模型。
模型预测路径生成（Model Predictive Trajectory Generator）
原理
测试
路径优化示例：
势场算法（Potential Field Planning）
原理
测试
说明：动画中蓝色的热区图显示了每个格子的势能。
随机路径图（Probabilistic Road Map）
原理
测试
说明：在图搜索上采用了迪杰斯特拉方法，动画中的蓝点为采样点，青色叉为迪杰斯特拉方法搜索过的点，红线为PRM的最终路径。
（Quintic Polynomials Planner）
原理
测试
（Reeds Shepp Path）
原理
测试
快速搜索随机树（RRT）
原理
测试
说明：黑色圆为障碍物，绿线为搜索树，红叉为开始位置和目标位置。
（RRT Dubins）
原理
测试
RRT*（RRT Star）
原理
测试
说明：黑色圆为障碍物，绿线为搜索树，红叉为开始位置和目标位置。
基于Dubins路径的RRT*（RRT Star Dubins）
原理
测试
说明：为汽车形机器人提供的使用RRT*和dubins路径规划的路径规划算法。
基于reeds-shepp路径的RRT*（RRT Star Reeds Shepp）
原理
测试
说明：为汽车形机器人提供的使用RRT*和reeds shepp路径规划的路径规划算法。
（Spiral Spanning Tree CPP）
原理
测试
状态晶格规划（State Lattice Planner）
原理
测试
均匀极性采样UniformPolarSampling
路线采样LaneSampling
偏差极性采样BiasedPolarSampling
时间弹性带(Time Elastic Band)
原理
测试
时间弹性带(TEB)简而言之，就是连接起始、目标点，并让这个路径可以变形，变形的条件就是将所有约束当做橡皮筋的外力。起始点、目标点状态由用户/全局规划器指定，中间插入N个控制橡皮筋形状的控制点（机器人姿态），当然，为了显示轨迹的运动学信息，我们在点与点之间定义运动时间Time：
time+elasticband=timedelaticsband
其目标函数的定义：
虽然待优化的橡皮筋有不少状态点与时间段，目标函数也好像很多。但是，每个目标函数只与橡皮筋中的某几个状态有关，而非整条橡皮筋。将它描述成图，然后用图优化。
1.优点
（1）前瞻性好
（2）适用于各种车模
2.缺点
（1）计算复杂
（2）速度和角速度波动大，控制不稳定
（Visibility Road Map）
原理
测试
Voronoi路径图（Voronoi Road Map）
原理
测试
说明：在图搜索上采用了迪杰斯特拉方法，动画中的蓝点为Voronoi点，青色叉为迪杰斯特拉方法搜索过的点，红线为Voronoi路径图的最终路径。
（Wavefront CPP）
原理
测试
模型预测控制(MPC)
原理
测试
MPC其实是一种基于对受控对象进行预测的控制方法。MPC最大的特点在于，相对于LQR控制而言，MPC可以考虑空间状态变量的各种约束，而LQR，PID等控制只能够考虑输入输出变量的各种约束。
MPC的作用机理可以表述为：在每一个采样时刻，根据当前的测量信息，在线求解一个有限时间开环优化问题，并将得到的控制序列的第一个元素用于被控对象；在下一个采样时刻，用新的测量值作为此时预测系统未来动态的初试条件，刷新优化问题求解。应用于机器人的典型的模型预测控制方法：
问题模型
参数空间
传统MPC控制流程为：
（1）设置优化问题
（2）使用测量模块告诉我们当前的initial state
（3）求解优化问题得到参数，这些参数构成系统的最优输入 u*
（4）使用 u驱动系统，由于系统受到干扰无法保证求解得到的 u我们想要的，仅此旨在很小一段时间中使用，然后利用观测的状态重新求解问题，转回步骤(2)
评论区