一文洞悉Python必备50种算法!资深大牛至少得掌握25种!
一、环境需求
二、怎样使用
三、本地化
3.1扩展卡尔曼滤波本地化
3.2无损卡尔曼滤波本地化
3.3粒子滤波本地化
3.4直方图滤波本地化
四、映射
4.1高斯网格映射
4.2光线投射网格映射
4.3k均值物体聚类
4.4圆形拟合物体形状识别
五、slam
5.1迭代最近点匹配
5.2ekf slam
5.3fastslam 1.0
5.4fastslam 2.0
5.5基于图的slam
六、路径规划
6.1动态窗口方式
6.2基于网格的搜索
迪杰斯特拉算法
a*算法
势场算法
6.3模型预测路径生成
路径优化示例
查找表生成示例
6.4状态晶格规划
均匀极性采样(uniform polar sampling)
偏差极性采样(biased polar sampling)
路线采样(lane sampling)
6.5随机路径图(prm)规划
6.6voronoi路径图规划
6.7快速搜索随机树(rrt)
基本rrt
rrt*
基于dubins路径的rrt
基于dubins路径的rrt*
基于reeds-shepp路径的rrt*
informed rrt*
批量informed rrt*
闭合回路rrt*
lqr-rrt*
6.8三次样条规划
6.9b样条规划
6.10eta^3样条路径规划
6.11贝济埃路径规划
6.12五次多项式规划
6.13dubins路径规划
6.14reeds shepp路径规划
6.15基于lqr的路径规划
6.16frenet frame中的最优路径
七、路径跟踪
7.1姿势控制跟踪
7.2纯追迹跟踪
7.3史坦利控制
7.4后轮反馈控制
7.5线性二次regulator(lqr)转向控制
7.6线性二次regulator(lqr)转向和速度控制
7.7模型预测速度和转向控制
八、项目支持
一、环境需求
python 3.6.x
numpy
scipy
matplotlib
pandas
cvxpy 0.4.x
二、怎样使用
安装必要的库;
克隆本代码仓库;
执行每个目录下的python脚本;
如果你喜欢,则收藏本代码库:)
三、本地化
3.1 扩展卡尔曼滤波本地化
私信小编001 获取源文件以及pdf!
该算法利用扩展卡尔曼滤波器(extended kalman filter, ekf)实现传感器混合本地化。
蓝线为真实路径,黑线为导航推测路径(dead reckoning trajectory),绿点为位置观测(如gps),红线为ekf估算的路径。
红色椭圆为ekf估算的协方差。
相关阅读:
概率机器人学
http://www.probabilistic-robotics.org/
3.2 无损卡尔曼滤波本地化
该算法利用无损卡尔曼滤波器(unscented kalman filter, ukf)实现传感器混合本地化。
线和点的含义与ekf模拟的例子相同。
相关阅读:
利用无差别训练过的无损卡尔曼滤波进行机器人移动本地化
https://www.researchgate.net/publication/267963417_discriminatively_trained_unscented_kalman_filter_for_mobile_robot_localization
3.3 粒子滤波本地化
该算法利用粒子滤波器(particle filter, pf)实现传感器混合本地化。
蓝线为真实路径,黑线为导航推测路径(dead reckoning trajectory),绿点为位置观测(如gps),红线为pf估算的路径。
该算法假设机器人能够测量与地标(rfid)之间的距离。
pf本地化会用到该测量结果。
相关阅读:
概率机器人学
http://www.probabilistic-robotics.org/
3.4 直方图滤波本地化
该算法是利用直方图滤波器(histogram filter)实现二维本地化的例子。
红十字是实际位置,黑点是rfid的位置。
蓝色格子是直方图滤波器的概率位置。
在该模拟中,x,y是未知数,yaw已知。
滤波器整合了速度输入和从rfid获得距离观测数据进行本地化。
不需要初始位置。
相关阅读:
概率机器人学
http://www.probabilistic-robotics.org/
四、映射
4.1 高斯网格映射
本算法是二维高斯网格映射(gaussian grid mapping)的例子。
4.2 光线投射网格映射
本算法是二维光线投射网格映射(ray casting grid map)的例子。
4.3 k均值物体聚类
本算法是使用k均值算法进行二维物体聚类的例子。
4.4 圆形拟合物体形状识别
本算法是使用圆形拟合进行物体形状识别的例子。
蓝圈是实际的物体形状。
红叉是通过距离传感器观测到的点。
红圈是使用圆形拟合估计的物体形状。
五、slam
同时本地化和映射(simultaneous localization and mapping,slam)的例子。
5.1 迭代最近点匹配
本算法是使用单值解构进行二维迭代最近点(iterative closest point,icp)匹配的例子。
它能计算从一些点到另一些点的旋转矩阵和平移矩阵。相关阅读:
机器人运动介绍:迭代最近点算法
https://cs.gmu.edu/~kosecka/cs685/cs685-icp.pdf
5.2 ekf slam
这是基于扩展卡尔曼滤波的slam示例。
蓝线是真实路径,黑线是导航推测路径,红线是ekf slam估计的路径。
绿叉是估计的地标。
相关阅读:
概率机器人学
http://www.probabilistic-robotics.org/
5.3 fastslam 1.0
这是用fastslam 1.0进行基于特征的slam的示例。
蓝线是实际路径,黑线是导航推测,红线是fastslam的推测路径。
红点是fastslam中的粒子。
黑点是地标,蓝叉是fastlsam估算的地标位置。
相关阅读:
概率机器人学
http://www.probabilistic-robotics.org/
5.4 fastslam 2.0
这是用fastslam 2.0进行基于特征的slam的示例。
动画的含义与fastslam 1.0的情况相同。
相关阅读:
概率机器人学
http://www.probabilistic-robotics.org/
tim bailey的slam模拟
http://www-personal.acfr.usyd.edu.au/tbailey/software/slam_simulations.htm
5.5 基于图的slam
这是基于图的slam的示例。
蓝线是实际路径。
黑线是导航推测路径。
红线是基于图的slam估算的路径。
黑星是地标,用于生成图的边。
相关阅读:
基于图的slam入门
http://www2.informatik.uni-freiburg.de/~stachnis/pdf/grisetti10titsmag.pdf
六、路径规划
6.1 动态窗口方式
这是使用动态窗口方式(dynamic window approach)进行二维导航的示例代码。
相关阅读:
用动态窗口方式避免碰撞
https://www.ri.cmu.edu/pub_files/pub1/fox_dieter_1997_1/fox_dieter_1997_1.pdf
6.2 基于网格的搜索
迪杰斯特拉算法
这是利用迪杰斯特拉(dijkstra)算法实现的基于二维网格的最短路径规划。
动画中青色点为搜索过的节点。
a*算法
下面是使用a星算法进行基于二维网格的最短路径规划。
动画中青色点为搜索过的节点。
启发算法为二维欧几里得距离。
势场算法
下面是使用势场算法进行基于二维网格的路径规划。
动画中蓝色的热区图显示了每个格子的势能。