diff --git a/Software/Algorithms/Aerial Robotics/Control.md b/Software/Algorithms/Aerial Robotics/Control.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Aerial Robotics/Control.md +++ /dev/null diff --git a/Software/Algorithms/Aerial Robotics/Geometry.md b/Software/Algorithms/Aerial Robotics/Geometry.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Aerial Robotics/Geometry.md +++ /dev/null diff --git a/Software/Algorithms/Aerial Robotics/Mechanics.md b/Software/Algorithms/Aerial Robotics/Mechanics.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Aerial Robotics/Mechanics.md +++ /dev/null diff --git a/Software/Algorithms/Aerial Robotics/PX4.md b/Software/Algorithms/Aerial Robotics/PX4.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Aerial Robotics/PX4.md +++ /dev/null diff --git a/Software/Algorithms/Aerial Robotics/Planning.md b/Software/Algorithms/Aerial Robotics/Planning.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Aerial Robotics/Planning.md +++ /dev/null diff --git a/Software/Algorithms/Estimation/KalmanFilter.md b/Software/Algorithms/Estimation/KalmanFilter.md deleted file mode 100644 index 8f0506a..0000000 --- a/Software/Algorithms/Estimation/KalmanFilter.md +++ /dev/null @@ -1,274 +0,0 @@ -#Kalman Filter - - -卡尔曼滤波是基于传感器对动态系统当前状态的观测,结合动态系统运动的规律,对其未来时刻的运动状态进行预测。首先需要跟踪预测的对象建立一个动力学模型,用微分方程描述。然后对观测和运动引入高斯噪声,然后用概率学的公式和优化理论,给出一个表征系统未来时刻运动状态的极大似然估计。 - -一篇写得很好的[外文博客](http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/)及其[中文翻译](https://blog.csdn.net/u010720661/article/details/63253509) - - -## 导论 - -卡尔曼滤波本质上是一个数据融合算法,将具有同样测量目的、来自不同传感器、(可能) 具有不同单位 (unit) 的数据融合在一起,得到一个更精确的目的测量值。 - -卡尔曼滤波的局限性在于其只能拟合线性高斯系统。但其最大的优点在于计算量小,能够利用前一时刻的状态(和可能的测量值)来得到当前时刻下的状态的最优估计。 - -本文虽然是小白教程,但还是需要各位至少知道高斯分布,一点点线性代数,还有状态向量这样的名词。 - - -## 简述 - -考虑一个SLAM 问题,它由一个运动方程: -![](../../../meta/pic/kalmanFilter/640.png) - -和一个观测方程组成: - -![](../../../meta/pic/kalmanFilter/640-1.png) - -就把它当作一个线性系统吧(非线性系统请看下一讲扩展卡尔曼滤波),并且为了简化推导,忽略路标的下标j,并把路标y 并入到状态向量一起优化,那么运动方程就可以写为: -![](../../../meta/pic/kalmanFilter/640-2.png) - -其中: - -![](../../../meta/pic/kalmanFilter/640-3.png)为t 时刻的状态向量,包括了相机位姿、路标坐标等信息,也可能有速度、朝向等信息; - -![](../../../meta/pic/kalmanFilter/640-4.png)为运动测量值,如加速度,转向等等; - -![](../../../meta/pic/kalmanFilter/640-5.png)为状态转换方程,将t-1 时刻的状态转换至t 时刻的状态 - -![](../../../meta/pic/kalmanFilter/640-6.png)是控制输入矩阵,将运动测量值![](../../../meta/pic/kalmanFilter/640-4.png)的作用映射到状态向量上; -![](../../../meta/pic/kalmanFilter/640-7.png)是预测的高斯噪声,其均值为0,协方差矩阵为![](../../../meta/pic/kalmanFilter/640-8.png) 。 - -这一步在卡尔曼滤波中也称为预测 (predict)。 - -类似,测量方程可以写为: - -![](../../../meta/pic/kalmanFilter/640-9.png) - -其中: - -![](../../../meta/pic/kalmanFilter/640-10.png)为传感器的测量值; - -![](../../../meta/pic/kalmanFilter/640-11.png)为转换矩阵,它将状态向量映射到测量值所在的空间中; - -![](../../../meta/pic/kalmanFilter/640-12.png)为测量的高斯噪声,其均值为0,协方差矩阵为 。 - -而卡尔曼滤波就是预测 - 测量之间不断循环迭代。当然,对于某些情况,如GPS + IMU,由于IMU 测量频率远比GPS 高,在只有IMU 测量值时,只执行运动更新,在有GPS 测量值时再进行测量更新。 - - -▌一个小例子 - -用一个在解释卡尔曼滤波时最常用的一维例子:小车追踪。如下图所示: -![](../../../meta/pic/kalmanFilter/640.jpeg) - -状态向量为小车的位置和速度: - -![](../../../meta/pic/kalmanFilter/640-13.png) - -而司机要是踩了刹车或者油门,小车就会具有一个加速度,![](../../../meta/pic/kalmanFilter/640-14.png)。 - -假设t 和t-1 时刻之间的时间差为 -![](../../../meta/pic/kalmanFilter/640-15.png) 。根据物理知识,有: -![](../../../meta/pic/kalmanFilter/640-16.png) - -写成矩阵形式就有: - -![](../../../meta/pic/kalmanFilter/640-17.png) - -跟之前的运动方程对比,就知道 - -![](../../../meta/pic/kalmanFilter/640-18.png) - -上式就写为: - -![](../../../meta/pic/kalmanFilter/640-19.png) - - -![](../../../meta/pic/kalmanFilter/640-20.png)表示t-1 时刻卡尔曼滤波的状态估计; -![](../../../meta/pic/kalmanFilter/640-21.png)则表示中t-1 到t 时刻,预测更新所得的预测值。 - -再利用运动模型对状态向量进行更新后,还要继续更新状态向量的协方差矩阵P,公式为: - -![](../../../meta/pic/kalmanFilter/640-22.png) - -假设 -![](../../../meta/pic/kalmanFilter/640-3.png) 为t 时刻下状态向量的真值(自然是永远未知的),由之前的现形运动方程(式(3))给出,将式(3) 与式(9) 相减可得: -![](../../../meta/pic/kalmanFilter/640-23.png) - -而: -![](../../../meta/pic/kalmanFilter/640-24.png) - -考虑到状态向量和噪声是不相关的,则![](../../../meta/pic/kalmanFilter/640-25.png),上式就可以简化为: -![](../../../meta/pic/kalmanFilter/640-26.png) - -**推导完毕。** - -可以看到,经过预测更新,协方差矩阵P 变大了。这是因为状态转换并不完美,而且运动测量值含有噪声,具有较大的不确定性。 - -预测更新实际上相当于“加法”:将当前状态转换到下一时刻(并增加一定不确定性),再把外界的干扰(运动测量值)叠加上去(又增加了一点不确定性) - -![](../../../meta/pic/kalmanFilter/640-1.jpeg) - -上面即为卡尔曼滤波中预测这一步。这一步相对比较直观,推导也较测量更新简单,就只在这里详细给出了。 - -如果得到了测量值,那么我们就可以对状态向量进行测量更新了,对应的公式为: - -![](../../../meta/pic/kalmanFilter/640-27.png) - - -其中: - -![](../../../meta/pic/kalmanFilter/640-3.jpeg) - -为卡尔曼增益。 - -从这里就可以看到,测量更新显然比预测更新复杂,难点也集中在这里。下面就给出测量更性的详细推导。 - - -▌推导 - -一些CASE - -从t-1 时刻起,小车运动后,经过前面所述的预测更新后,我们就得到了t 时刻的小车位置的估计,由于在卡尔曼滤波中,我们使用高斯概率分布来表示小车的位置,因此这个预测的位置可以写为: - -![](../../../meta/pic/kalmanFilter/640-30.png) - -为了与前面的通用的推导区别开来,在这个一维的例子中我们使用了新的符号。不过熟悉高斯概率分布的话应该可以马上看出来, -![](../../../meta/pic/kalmanFilter/640-31.png)为这个高斯分布的均值, -![](../../../meta/pic/kalmanFilter/640-32.png)为方差,而r 为小车的可能位置, -![](../../../meta/pic/kalmanFilter/640-33.png)为某个可能位置 (r) 的概率分布。 - -假设在t 时刻,我们通过某测距仪测得小车距离原点的距离r,由于测量包含噪声(且在面前我们假设了其为高斯噪声),因此该测量值也可以利用高斯概率分布来表示: - -![](../../../meta/pic/kalmanFilter/640-34.png) - -除了下标外,其余的字母的含义都和上面的式子一样。 - -![](../../../meta/pic/kalmanFilter/640-4.jpeg) - - -如上图琐事,现在在t 时刻,我们有了两个关于小车位置的估计。而我们所能得到的关于小测位置的最佳估计就是将预测更新和测量更新所得的数据融合起来,得到一个新的估计。而这个融合,就是一个简单的“乘法”,并利用了一个性质:两个高斯分布的乘积仍然是高斯分布。 - -![](../../../meta/pic/kalmanFilter/640-35.png) - -将上式化简一下: - -![](../../../meta/pic/kalmanFilter/640-36.png) - -其中, -![](../../../meta/pic/kalmanFilter/640-37.png)为 -![](../../../meta/pic/kalmanFilter/640-38.png)和 -![](../../../meta/pic/kalmanFilter/640-39.png)的加权平均, -![](../../../meta/pic/kalmanFilter/640-40.png)则是 -![](../../../meta/pic/kalmanFilter/640-41.png)和 -![](../../../meta/pic/kalmanFilter/640-42.png)的调和平均的二分一: - -![](../../../meta/pic/kalmanFilter/640-43.png) -![](../../../meta/pic/kalmanFilter/640-6.jpeg) - - - -最右边的式子是为了后面的计算而准备的。 - -本质上,这(高斯分布相乘)就是卡尔曼滤波中测量更新的全部了。 - -那么, 怎么由上面两个简单的一维的式子得到前一节 -![](../../../meta/pic/kalmanFilter/640-44.png)和 -![](../../../meta/pic/kalmanFilter/640-45.png)呢?一步一步来。 - - -▌转换矩阵H的引入 - -在刚刚的一维情况的小例子中,我们其实做了一个隐式的假设,即有预测更新得到的位置的概率分布和测距仪所得的测量值具有相同的单位 (unit),如米 (m)。 - -但实际情况往往不是这样的,比如,测距仪给出的可能不是距离,而是信号的飞行时间(由仪器至小车的光的传播时间),单位为秒 (s)。这样的话,我们就无法直接如上面一般直接将两个高斯分布相乘了。 - -此时,就该转换矩阵 -![](../../../meta/pic/kalmanFilter/640-46.png)闪亮登场了。由于 -![](../../../meta/pic/kalmanFilter/640-47.png),c为光速。所以此时 -![](../../../meta/pic/kalmanFilter/640-48.png)(测量方程为 -![](../../../meta/pic/kalmanFilter/640-49.png),可以回去参考一下式(4))。 - -预测值就要写为: - -![](../../../meta/pic/kalmanFilter/640-50.png) - -而测量值保持不变: - -![](../../../meta/pic/kalmanFilter/640-51.png) - -这样,两个高斯概率分布在转换矩阵H 的作用下又在同一个空间下了。根据前面 -![](../../../meta/pic/kalmanFilter/640-52.png)和![](../../../meta/pic/kalmanFilter/640-53.png)的公式 (式(27) 和式(28)),可得: -![](../../../meta/pic/kalmanFilter/640-54.png) - -将上式两端都乘以c 则可得: -![](../../../meta/pic/kalmanFilter/640-55.png) - -由于![](../../../meta/pic/kalmanFilter/640-56.png)(这里转换矩阵H 不随时间变化而变化,所以把下标t 略去),并记![](../../../meta/pic/kalmanFilter/640-57.png),则上式可以写为: -![](../../../meta/pic/kalmanFilter/640-58.png) - -类似的有: - -![](../../../meta/pic/kalmanFilter/640-59.png) - - -两边乘以![](../../../meta/pic/kalmanFilter/640-60.png)有: -![](../../../meta/pic/kalmanFilter/640-61.png) - - -▌小结一下 - -通过这个一维情况的推导,希望能说明卡尔曼滤波就是在给定初始值的情况下,由预测和测量不断迭代、更新状态向量。而预测就是一个“加法”:状态转换和运动预测叠加;测量则是简单的高斯分布相乘,中间引入了一个转换矩阵将测量值和状态向量映射在同一个代数空间中。 - - -▌讨论 - -至此,相信你已经明白了卡尔曼滤波的推导过程。而具体的问题就取决于你的建模了。如在上面的小车的例子中,各个参数如下: - -![](../../../meta/pic/kalmanFilter/640-62.png) - -假设该时刻下运动测量值为加速度![](../../../meta/pic/kalmanFilter/640-63.png),为均值为0标准差为![](../../../meta/pic/kalmanFilter/640-64.png) 的高斯分布(标准差可以为经验值或仪器精度。![](../../../meta/pic/kalmanFilter/640-65.png) : - -![](../../../meta/pic/kalmanFilter/640-66.png) - -对于测量值,同样可以假设![](../../../meta/pic/kalmanFilter/640-67.png),那么![](../../../meta/pic/kalmanFilter/640-68.png)。 - - -▌多问个为什么 - -如果只关心卡尔曼滤波的推导和结果,到这里就可以停止啦。 - -但推完卡尔曼滤波,我还有几个个为什么。知其然更要知其所以然。下面是我对于自己的疑惑学习、思考得到的解答,而且碍于表达能力,不敢说百分百正确。 - -首先是对于预测更新。前面也说到了,预测更新相当于“加法”。这相对好理解一些。在t-1 时刻我们有了对于小车位置的一个估计,根据对小车速度(状态向量之一)、小车的加速度(运动测量值)的建模,在辅以时间间隔,自然可以计算出小车在该时间间隔内的位移和速度增量,再将之叠加到原有的状态向量上即可。由于建模和测量的过程带有噪声,所以此时小车的位置估计的精度是下降的(方差增大)。 - -那么为什么测量更新就是乘法而非加法呢? - -因为测量更新的依据是**贝叶斯法则**。在有了测量值之后,我们求小车位置的概率分布其实就是在求![](../../../meta/pic/kalmanFilter/640-69.png)。根据贝叶斯法则有: -![](../../../meta/pic/kalmanFilter/640-70.png) - -![](../../../meta/pic/kalmanFilter/640-69.png)是**后验概率**。直接求后验概率比较困难(为什么?)。假设就在这个一维的小车例子中,当我们得到一个距离测量值z,那么小车的位置可能是距离原点的-z 或z 的两个点上。对于二维就可能是一个圆,三维则是一个球。此时要精确地知道小车的位置(消除歧义点),一则我们可以继续测量,二则需要额外的信息。这就使得求后验概率比较费时费力。 - -反观贝叶斯法则的右侧,此时我们已经有了**先验概率**![](../../../meta/pic/kalmanFilter/640-71.png),这是上一时刻的状态向量的概率分布,并且我们也有了![](../../../meta/pic/kalmanFilter/640-69.png),因为所得的测量值![](../../../meta/pic/kalmanFilter/640-72.png)表达的就是在当前位置下,我们能得到的测量值,亦即贝叶斯中的**似然**。在![](../../../meta/pic/kalmanFilter/640-73.png)为一个常数的情况下,最大化![](../../../meta/pic/kalmanFilter/640-74.png)就得到了最优的 。 - -既然测量更新是以贝叶斯公式为基础,那么反观预测更新,除了前面那个直观的“加法”解释之外,是不是也有一个概率上的解释呢? - -连续的高斯分布所表示的小车位置的预测更新我没找到(不好意思),但就**离散情况**的话还是有的,就是**全概率公式**。以下图为例,假设t-1 时刻,小车的位置分布概率如图所示,到了t 时刻,预测小车向前运动了3米(3个格子),但由于模型的不确定性和噪音,我们不能保证小车精确地向前走了3米,根据概率分布,我们可以假设小车有80%的概率往前走了3米,10%的概率往前走了两米,而另有10%的概率往前走了4米。 - -![](../../../meta/pic/kalmanFilter/640-7.jpeg) - -那么,在t 时刻,若小车真的运动到了这个位置,其概率分布是怎样的呢?它既有可能是在距离该位置3米远的地方以0.8的概率运动到现在这个位置的,也有可能是以0.1 的概率从2或4米远的地方为初始位置运动到这的,根据全概率公式,可以表达为: - -![](../../../meta/pic/kalmanFilter/640-8.jpeg) - -![](../../../meta/pic/kalmanFilter/640-75.png) - -类似地,t时刻下,小车运动后在其他位置上的概率分布也可以用全概率公式表达出来。当然,最后的计算结果还需要进行**归一化处理**。 - -如果我们不断地减小每个方格的分辨率,并按照高斯分布给予每个方格一个概率值,并对小车运动也做如此的离散化处理,应该也是可以不断逼近连续的情况(个人猜想)。 - -至此,关于卡尔曼滤波的个人浅见就到此为止了。精通还需要不断地实践,但希望读完本文,能让你对卡尔曼滤波有全面的了解。 - -参考文献 -Ramsey Faragher 的 understanding the basis of the kalman filter. -维基百科 Kalman filter -高翔的《视觉SLAM十四讲》 \ No newline at end of file diff --git a/Software/Algorithms/Estimation/MaximumLikelihoodEstimate/1546196212158.png b/Software/Algorithms/Estimation/MaximumLikelihoodEstimate/1546196212158.png deleted file mode 100644 index 06d20c4..0000000 --- a/Software/Algorithms/Estimation/MaximumLikelihoodEstimate/1546196212158.png +++ /dev/null Binary files differ diff --git a/Software/Algorithms/Estimation/MaximumLikelihoodEstimate/MaximumLikelihoodEstimate.md b/Software/Algorithms/Estimation/MaximumLikelihoodEstimate/MaximumLikelihoodEstimate.md deleted file mode 100644 index bea9663..0000000 --- a/Software/Algorithms/Estimation/MaximumLikelihoodEstimate/MaximumLikelihoodEstimate.md +++ /dev/null @@ -1,14 +0,0 @@ -# 极大似然估计 -## Maximum Likelihood Estimate - -极大似然估计 MaximumLikelihoodEstimate, 在感知算法中很常用于分类问题,以及在直接法视觉里程计中用于相邻帧配准的问题。 - -想法是将需要根据参数进行估计的问题,转化成一个概率论中的随机变量,如果该变量的分布是单峰的,则用一个多维高斯分布去逼近、拟合这个变量的分布(问题中要估计的量由几个参数决定,就用几维的高斯分布),在极大似然的意义下,可得到闭式的全局最优解。对于单峰的随机变量而言,是很高效的方法,除了预测、分类外,还可以用极大似然估计达到压缩信息的目的——本来为了保存该变量的分布,在不知道其模型的情况下只能把每一个样本的数据都存下来,用高斯分布拟合逼近之后,就只有均值和方差两个数(或向量)需要存了,大大节省空间。 - -[多维高斯分布公式1] - -而如果要逼近的随机变量有多个峰,那么需要用高斯混合模型,并通过最大化期望法(Expectation-Maximization,EM算法)来逼近拟合,此方法无法得到闭式的全局最优解,但可以确保收敛至一个局部最优解。 - -[高斯混合模型公式2] - -![EM算法流程图|center|](./1546196212158.png) diff --git a/Software/Algorithms/Estimation/ParticleFilters.md b/Software/Algorithms/Estimation/ParticleFilters.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Estimation/ParticleFilters.md +++ /dev/null diff --git a/Software/Algorithms/Estimation/TargetTracking.md b/Software/Algorithms/Estimation/TargetTracking.md deleted file mode 100644 index e69de29..0000000 --- a/Software/Algorithms/Estimation/TargetTracking.md +++ /dev/null diff --git a/Software/Algorithms/Learning/Estimation/KalmanFilter.md b/Software/Algorithms/Learning/Estimation/KalmanFilter.md new file mode 100644 index 0000000..8f0506a --- /dev/null +++ b/Software/Algorithms/Learning/Estimation/KalmanFilter.md @@ -0,0 +1,274 @@ +#Kalman Filter + + +卡尔曼滤波是基于传感器对动态系统当前状态的观测,结合动态系统运动的规律,对其未来时刻的运动状态进行预测。首先需要跟踪预测的对象建立一个动力学模型,用微分方程描述。然后对观测和运动引入高斯噪声,然后用概率学的公式和优化理论,给出一个表征系统未来时刻运动状态的极大似然估计。 + +一篇写得很好的[外文博客](http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/)及其[中文翻译](https://blog.csdn.net/u010720661/article/details/63253509) + + +## 导论 + +卡尔曼滤波本质上是一个数据融合算法,将具有同样测量目的、来自不同传感器、(可能) 具有不同单位 (unit) 的数据融合在一起,得到一个更精确的目的测量值。 + +卡尔曼滤波的局限性在于其只能拟合线性高斯系统。但其最大的优点在于计算量小,能够利用前一时刻的状态(和可能的测量值)来得到当前时刻下的状态的最优估计。 + +本文虽然是小白教程,但还是需要各位至少知道高斯分布,一点点线性代数,还有状态向量这样的名词。 + + +## 简述 + +考虑一个SLAM 问题,它由一个运动方程: +![](../../../meta/pic/kalmanFilter/640.png) + +和一个观测方程组成: + +![](../../../meta/pic/kalmanFilter/640-1.png) + +就把它当作一个线性系统吧(非线性系统请看下一讲扩展卡尔曼滤波),并且为了简化推导,忽略路标的下标j,并把路标y 并入到状态向量一起优化,那么运动方程就可以写为: +![](../../../meta/pic/kalmanFilter/640-2.png) + +其中: + +![](../../../meta/pic/kalmanFilter/640-3.png)为t 时刻的状态向量,包括了相机位姿、路标坐标等信息,也可能有速度、朝向等信息; + +![](../../../meta/pic/kalmanFilter/640-4.png)为运动测量值,如加速度,转向等等; + +![](../../../meta/pic/kalmanFilter/640-5.png)为状态转换方程,将t-1 时刻的状态转换至t 时刻的状态 + +![](../../../meta/pic/kalmanFilter/640-6.png)是控制输入矩阵,将运动测量值![](../../../meta/pic/kalmanFilter/640-4.png)的作用映射到状态向量上; +![](../../../meta/pic/kalmanFilter/640-7.png)是预测的高斯噪声,其均值为0,协方差矩阵为![](../../../meta/pic/kalmanFilter/640-8.png) 。 + +这一步在卡尔曼滤波中也称为预测 (predict)。 + +类似,测量方程可以写为: + +![](../../../meta/pic/kalmanFilter/640-9.png) + +其中: + +![](../../../meta/pic/kalmanFilter/640-10.png)为传感器的测量值; + +![](../../../meta/pic/kalmanFilter/640-11.png)为转换矩阵,它将状态向量映射到测量值所在的空间中; + +![](../../../meta/pic/kalmanFilter/640-12.png)为测量的高斯噪声,其均值为0,协方差矩阵为 。 + +而卡尔曼滤波就是预测 - 测量之间不断循环迭代。当然,对于某些情况,如GPS + IMU,由于IMU 测量频率远比GPS 高,在只有IMU 测量值时,只执行运动更新,在有GPS 测量值时再进行测量更新。 + + +▌一个小例子 + +用一个在解释卡尔曼滤波时最常用的一维例子:小车追踪。如下图所示: +![](../../../meta/pic/kalmanFilter/640.jpeg) + +状态向量为小车的位置和速度: + +![](../../../meta/pic/kalmanFilter/640-13.png) + +而司机要是踩了刹车或者油门,小车就会具有一个加速度,![](../../../meta/pic/kalmanFilter/640-14.png)。 + +假设t 和t-1 时刻之间的时间差为 +![](../../../meta/pic/kalmanFilter/640-15.png) 。根据物理知识,有: +![](../../../meta/pic/kalmanFilter/640-16.png) + +写成矩阵形式就有: + +![](../../../meta/pic/kalmanFilter/640-17.png) + +跟之前的运动方程对比,就知道 + +![](../../../meta/pic/kalmanFilter/640-18.png) + +上式就写为: + +![](../../../meta/pic/kalmanFilter/640-19.png) + + +![](../../../meta/pic/kalmanFilter/640-20.png)表示t-1 时刻卡尔曼滤波的状态估计; +![](../../../meta/pic/kalmanFilter/640-21.png)则表示中t-1 到t 时刻,预测更新所得的预测值。 + +再利用运动模型对状态向量进行更新后,还要继续更新状态向量的协方差矩阵P,公式为: + +![](../../../meta/pic/kalmanFilter/640-22.png) + +假设 +![](../../../meta/pic/kalmanFilter/640-3.png) 为t 时刻下状态向量的真值(自然是永远未知的),由之前的现形运动方程(式(3))给出,将式(3) 与式(9) 相减可得: +![](../../../meta/pic/kalmanFilter/640-23.png) + +而: +![](../../../meta/pic/kalmanFilter/640-24.png) + +考虑到状态向量和噪声是不相关的,则![](../../../meta/pic/kalmanFilter/640-25.png),上式就可以简化为: +![](../../../meta/pic/kalmanFilter/640-26.png) + +**推导完毕。** + +可以看到,经过预测更新,协方差矩阵P 变大了。这是因为状态转换并不完美,而且运动测量值含有噪声,具有较大的不确定性。 + +预测更新实际上相当于“加法”:将当前状态转换到下一时刻(并增加一定不确定性),再把外界的干扰(运动测量值)叠加上去(又增加了一点不确定性) + +![](../../../meta/pic/kalmanFilter/640-1.jpeg) + +上面即为卡尔曼滤波中预测这一步。这一步相对比较直观,推导也较测量更新简单,就只在这里详细给出了。 + +如果得到了测量值,那么我们就可以对状态向量进行测量更新了,对应的公式为: + +![](../../../meta/pic/kalmanFilter/640-27.png) + + +其中: + +![](../../../meta/pic/kalmanFilter/640-3.jpeg) + +为卡尔曼增益。 + +从这里就可以看到,测量更新显然比预测更新复杂,难点也集中在这里。下面就给出测量更性的详细推导。 + + +▌推导 + +一些CASE + +从t-1 时刻起,小车运动后,经过前面所述的预测更新后,我们就得到了t 时刻的小车位置的估计,由于在卡尔曼滤波中,我们使用高斯概率分布来表示小车的位置,因此这个预测的位置可以写为: + +![](../../../meta/pic/kalmanFilter/640-30.png) + +为了与前面的通用的推导区别开来,在这个一维的例子中我们使用了新的符号。不过熟悉高斯概率分布的话应该可以马上看出来, +![](../../../meta/pic/kalmanFilter/640-31.png)为这个高斯分布的均值, +![](../../../meta/pic/kalmanFilter/640-32.png)为方差,而r 为小车的可能位置, +![](../../../meta/pic/kalmanFilter/640-33.png)为某个可能位置 (r) 的概率分布。 + +假设在t 时刻,我们通过某测距仪测得小车距离原点的距离r,由于测量包含噪声(且在面前我们假设了其为高斯噪声),因此该测量值也可以利用高斯概率分布来表示: + +![](../../../meta/pic/kalmanFilter/640-34.png) + +除了下标外,其余的字母的含义都和上面的式子一样。 + +![](../../../meta/pic/kalmanFilter/640-4.jpeg) + + +如上图琐事,现在在t 时刻,我们有了两个关于小车位置的估计。而我们所能得到的关于小测位置的最佳估计就是将预测更新和测量更新所得的数据融合起来,得到一个新的估计。而这个融合,就是一个简单的“乘法”,并利用了一个性质:两个高斯分布的乘积仍然是高斯分布。 + +![](../../../meta/pic/kalmanFilter/640-35.png) + +将上式化简一下: + +![](../../../meta/pic/kalmanFilter/640-36.png) + +其中, +![](../../../meta/pic/kalmanFilter/640-37.png)为 +![](../../../meta/pic/kalmanFilter/640-38.png)和 +![](../../../meta/pic/kalmanFilter/640-39.png)的加权平均, +![](../../../meta/pic/kalmanFilter/640-40.png)则是 +![](../../../meta/pic/kalmanFilter/640-41.png)和 +![](../../../meta/pic/kalmanFilter/640-42.png)的调和平均的二分一: + +![](../../../meta/pic/kalmanFilter/640-43.png) +![](../../../meta/pic/kalmanFilter/640-6.jpeg) + + + +最右边的式子是为了后面的计算而准备的。 + +本质上,这(高斯分布相乘)就是卡尔曼滤波中测量更新的全部了。 + +那么, 怎么由上面两个简单的一维的式子得到前一节 +![](../../../meta/pic/kalmanFilter/640-44.png)和 +![](../../../meta/pic/kalmanFilter/640-45.png)呢?一步一步来。 + + +▌转换矩阵H的引入 + +在刚刚的一维情况的小例子中,我们其实做了一个隐式的假设,即有预测更新得到的位置的概率分布和测距仪所得的测量值具有相同的单位 (unit),如米 (m)。 + +但实际情况往往不是这样的,比如,测距仪给出的可能不是距离,而是信号的飞行时间(由仪器至小车的光的传播时间),单位为秒 (s)。这样的话,我们就无法直接如上面一般直接将两个高斯分布相乘了。 + +此时,就该转换矩阵 +![](../../../meta/pic/kalmanFilter/640-46.png)闪亮登场了。由于 +![](../../../meta/pic/kalmanFilter/640-47.png),c为光速。所以此时 +![](../../../meta/pic/kalmanFilter/640-48.png)(测量方程为 +![](../../../meta/pic/kalmanFilter/640-49.png),可以回去参考一下式(4))。 + +预测值就要写为: + +![](../../../meta/pic/kalmanFilter/640-50.png) + +而测量值保持不变: + +![](../../../meta/pic/kalmanFilter/640-51.png) + +这样,两个高斯概率分布在转换矩阵H 的作用下又在同一个空间下了。根据前面 +![](../../../meta/pic/kalmanFilter/640-52.png)和![](../../../meta/pic/kalmanFilter/640-53.png)的公式 (式(27) 和式(28)),可得: +![](../../../meta/pic/kalmanFilter/640-54.png) + +将上式两端都乘以c 则可得: +![](../../../meta/pic/kalmanFilter/640-55.png) + +由于![](../../../meta/pic/kalmanFilter/640-56.png)(这里转换矩阵H 不随时间变化而变化,所以把下标t 略去),并记![](../../../meta/pic/kalmanFilter/640-57.png),则上式可以写为: +![](../../../meta/pic/kalmanFilter/640-58.png) + +类似的有: + +![](../../../meta/pic/kalmanFilter/640-59.png) + + +两边乘以![](../../../meta/pic/kalmanFilter/640-60.png)有: +![](../../../meta/pic/kalmanFilter/640-61.png) + + +▌小结一下 + +通过这个一维情况的推导,希望能说明卡尔曼滤波就是在给定初始值的情况下,由预测和测量不断迭代、更新状态向量。而预测就是一个“加法”:状态转换和运动预测叠加;测量则是简单的高斯分布相乘,中间引入了一个转换矩阵将测量值和状态向量映射在同一个代数空间中。 + + +▌讨论 + +至此,相信你已经明白了卡尔曼滤波的推导过程。而具体的问题就取决于你的建模了。如在上面的小车的例子中,各个参数如下: + +![](../../../meta/pic/kalmanFilter/640-62.png) + +假设该时刻下运动测量值为加速度![](../../../meta/pic/kalmanFilter/640-63.png),为均值为0标准差为![](../../../meta/pic/kalmanFilter/640-64.png) 的高斯分布(标准差可以为经验值或仪器精度。![](../../../meta/pic/kalmanFilter/640-65.png) : + +![](../../../meta/pic/kalmanFilter/640-66.png) + +对于测量值,同样可以假设![](../../../meta/pic/kalmanFilter/640-67.png),那么![](../../../meta/pic/kalmanFilter/640-68.png)。 + + +▌多问个为什么 + +如果只关心卡尔曼滤波的推导和结果,到这里就可以停止啦。 + +但推完卡尔曼滤波,我还有几个个为什么。知其然更要知其所以然。下面是我对于自己的疑惑学习、思考得到的解答,而且碍于表达能力,不敢说百分百正确。 + +首先是对于预测更新。前面也说到了,预测更新相当于“加法”。这相对好理解一些。在t-1 时刻我们有了对于小车位置的一个估计,根据对小车速度(状态向量之一)、小车的加速度(运动测量值)的建模,在辅以时间间隔,自然可以计算出小车在该时间间隔内的位移和速度增量,再将之叠加到原有的状态向量上即可。由于建模和测量的过程带有噪声,所以此时小车的位置估计的精度是下降的(方差增大)。 + +那么为什么测量更新就是乘法而非加法呢? + +因为测量更新的依据是**贝叶斯法则**。在有了测量值之后,我们求小车位置的概率分布其实就是在求![](../../../meta/pic/kalmanFilter/640-69.png)。根据贝叶斯法则有: +![](../../../meta/pic/kalmanFilter/640-70.png) + +![](../../../meta/pic/kalmanFilter/640-69.png)是**后验概率**。直接求后验概率比较困难(为什么?)。假设就在这个一维的小车例子中,当我们得到一个距离测量值z,那么小车的位置可能是距离原点的-z 或z 的两个点上。对于二维就可能是一个圆,三维则是一个球。此时要精确地知道小车的位置(消除歧义点),一则我们可以继续测量,二则需要额外的信息。这就使得求后验概率比较费时费力。 + +反观贝叶斯法则的右侧,此时我们已经有了**先验概率**![](../../../meta/pic/kalmanFilter/640-71.png),这是上一时刻的状态向量的概率分布,并且我们也有了![](../../../meta/pic/kalmanFilter/640-69.png),因为所得的测量值![](../../../meta/pic/kalmanFilter/640-72.png)表达的就是在当前位置下,我们能得到的测量值,亦即贝叶斯中的**似然**。在![](../../../meta/pic/kalmanFilter/640-73.png)为一个常数的情况下,最大化![](../../../meta/pic/kalmanFilter/640-74.png)就得到了最优的 。 + +既然测量更新是以贝叶斯公式为基础,那么反观预测更新,除了前面那个直观的“加法”解释之外,是不是也有一个概率上的解释呢? + +连续的高斯分布所表示的小车位置的预测更新我没找到(不好意思),但就**离散情况**的话还是有的,就是**全概率公式**。以下图为例,假设t-1 时刻,小车的位置分布概率如图所示,到了t 时刻,预测小车向前运动了3米(3个格子),但由于模型的不确定性和噪音,我们不能保证小车精确地向前走了3米,根据概率分布,我们可以假设小车有80%的概率往前走了3米,10%的概率往前走了两米,而另有10%的概率往前走了4米。 + +![](../../../meta/pic/kalmanFilter/640-7.jpeg) + +那么,在t 时刻,若小车真的运动到了这个位置,其概率分布是怎样的呢?它既有可能是在距离该位置3米远的地方以0.8的概率运动到现在这个位置的,也有可能是以0.1 的概率从2或4米远的地方为初始位置运动到这的,根据全概率公式,可以表达为: + +![](../../../meta/pic/kalmanFilter/640-8.jpeg) + +![](../../../meta/pic/kalmanFilter/640-75.png) + +类似地,t时刻下,小车运动后在其他位置上的概率分布也可以用全概率公式表达出来。当然,最后的计算结果还需要进行**归一化处理**。 + +如果我们不断地减小每个方格的分辨率,并按照高斯分布给予每个方格一个概率值,并对小车运动也做如此的离散化处理,应该也是可以不断逼近连续的情况(个人猜想)。 + +至此,关于卡尔曼滤波的个人浅见就到此为止了。精通还需要不断地实践,但希望读完本文,能让你对卡尔曼滤波有全面的了解。 + +参考文献 +Ramsey Faragher 的 understanding the basis of the kalman filter. +维基百科 Kalman filter +高翔的《视觉SLAM十四讲》 \ No newline at end of file diff --git a/Software/Algorithms/Learning/Estimation/MaximumLikelihoodEstimate/1546196212158.png b/Software/Algorithms/Learning/Estimation/MaximumLikelihoodEstimate/1546196212158.png new file mode 100644 index 0000000..06d20c4 --- /dev/null +++ b/Software/Algorithms/Learning/Estimation/MaximumLikelihoodEstimate/1546196212158.png Binary files differ diff --git a/Software/Algorithms/Learning/Estimation/MaximumLikelihoodEstimate/MaximumLikelihoodEstimate.md b/Software/Algorithms/Learning/Estimation/MaximumLikelihoodEstimate/MaximumLikelihoodEstimate.md new file mode 100644 index 0000000..bea9663 --- /dev/null +++ b/Software/Algorithms/Learning/Estimation/MaximumLikelihoodEstimate/MaximumLikelihoodEstimate.md @@ -0,0 +1,14 @@ +# 极大似然估计 +## Maximum Likelihood Estimate + +极大似然估计 MaximumLikelihoodEstimate, 在感知算法中很常用于分类问题,以及在直接法视觉里程计中用于相邻帧配准的问题。 + +想法是将需要根据参数进行估计的问题,转化成一个概率论中的随机变量,如果该变量的分布是单峰的,则用一个多维高斯分布去逼近、拟合这个变量的分布(问题中要估计的量由几个参数决定,就用几维的高斯分布),在极大似然的意义下,可得到闭式的全局最优解。对于单峰的随机变量而言,是很高效的方法,除了预测、分类外,还可以用极大似然估计达到压缩信息的目的——本来为了保存该变量的分布,在不知道其模型的情况下只能把每一个样本的数据都存下来,用高斯分布拟合逼近之后,就只有均值和方差两个数(或向量)需要存了,大大节省空间。 + +[多维高斯分布公式1] + +而如果要逼近的随机变量有多个峰,那么需要用高斯混合模型,并通过最大化期望法(Expectation-Maximization,EM算法)来逼近拟合,此方法无法得到闭式的全局最优解,但可以确保收敛至一个局部最优解。 + +[高斯混合模型公式2] + +![EM算法流程图|center|](./1546196212158.png) diff --git a/Software/Algorithms/Learning/Estimation/ParticleFilters.md b/Software/Algorithms/Learning/Estimation/ParticleFilters.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Learning/Estimation/ParticleFilters.md diff --git a/Software/Algorithms/Learning/Estimation/TargetTracking.md b/Software/Algorithms/Learning/Estimation/TargetTracking.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Learning/Estimation/TargetTracking.md diff --git a/Software/Algorithms/Mobility/Aerial Robotics/Control.md b/Software/Algorithms/Mobility/Aerial Robotics/Control.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Mobility/Aerial Robotics/Control.md diff --git a/Software/Algorithms/Mobility/Aerial Robotics/Geometry.md b/Software/Algorithms/Mobility/Aerial Robotics/Geometry.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Mobility/Aerial Robotics/Geometry.md diff --git a/Software/Algorithms/Mobility/Aerial Robotics/Mechanics.md b/Software/Algorithms/Mobility/Aerial Robotics/Mechanics.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Mobility/Aerial Robotics/Mechanics.md diff --git a/Software/Algorithms/Mobility/Aerial Robotics/PX4.md b/Software/Algorithms/Mobility/Aerial Robotics/PX4.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Mobility/Aerial Robotics/PX4.md diff --git a/Software/Algorithms/Mobility/Aerial Robotics/Planning.md b/Software/Algorithms/Mobility/Aerial Robotics/Planning.md new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Software/Algorithms/Mobility/Aerial Robotics/Planning.md diff --git a/Software/Algorithms/Motion Planning/ConfigurationSpace.md b/Software/Algorithms/Motion Planning/ConfigurationSpace.md deleted file mode 100644 index c69589f..0000000 --- a/Software/Algorithms/Motion Planning/ConfigurationSpace.md +++ /dev/null @@ -1 +0,0 @@ -#Configuration Space diff --git a/Software/Algorithms/Motion Planning/GradientBasedPlanner.md b/Software/Algorithms/Motion Planning/GradientBasedPlanner.md deleted file mode 100644 index 701dbde..0000000 --- a/Software/Algorithms/Motion Planning/GradientBasedPlanner.md +++ /dev/null @@ -1 +0,0 @@ -#Gradient Based Planner diff --git a/Software/Algorithms/Motion Planning/ProbabilisticRoadmap.md b/Software/Algorithms/Motion Planning/ProbabilisticRoadmap.md deleted file mode 100644 index 87c74a7..0000000 --- a/Software/Algorithms/Motion Planning/ProbabilisticRoadmap.md +++ /dev/null @@ -1 +0,0 @@ -#Probabilistic Roadmap diff --git a/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200547561.png b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200547561.png new file mode 100644 index 0000000..bd731da --- /dev/null +++ b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200547561.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200571261.png b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200571261.png new file mode 100644 index 0000000..d9b2c85 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200571261.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200603529.png b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200603529.png new file mode 100644 index 0000000..ea23830 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200603529.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200682136.png b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200682136.png new file mode 100644 index 0000000..cf7e560 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Probablistic Road Map/1546200682136.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Probablistic Road Map/Probablistic Road Map.md b/Software/Algorithms/Motion Planning/Probablistic Road Map/Probablistic Road Map.md new file mode 100644 index 0000000..b6bbe7e --- /dev/null +++ b/Software/Algorithms/Motion Planning/Probablistic Road Map/Probablistic Road Map.md @@ -0,0 +1,10 @@ +#Probablistic Road Map + +伪代码: +![Alt text](./1546200547561.png) + +1. 生成随机图: +![Alt text](./1546200571261.png) +2. 碰撞检测![Alt text](./1546200603529.png) +3. 用图规划问题的算法求解 +![Alt text](./1546200682136.png) diff --git a/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/1546201707049.png b/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/1546201707049.png new file mode 100644 index 0000000..739e194 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/1546201707049.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/1546201717793.png b/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/1546201717793.png new file mode 100644 index 0000000..74b9cbe --- /dev/null +++ b/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/1546201717793.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/Rapid Exploring Random Trees.md b/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/Rapid Exploring Random Trees.md new file mode 100644 index 0000000..072910c --- /dev/null +++ b/Software/Algorithms/Motion Planning/Rapid Exploring Random Trees/Rapid Exploring Random Trees.md @@ -0,0 +1,25 @@ +# Rapid Exploring Random Trees + +- Add start node to tree +- Repeat n times + - Generate a random configuration, x + - If x is in freespace using the CollisionCheck function + - Find y, the closest node in the tree to the random configuration + - If (Dist (x, y) > delta) – Check if x is too far from y + - Find a configuration, z, that is along the path from x to y such that Dist(z,y) <= delta + - x = z; + - If (LocalPlanner (x,y)) – Check if you can get from x to y Add x to the tree with y as its parent + +![Alt text](./1546201707049.png) + + +- While not done + - Extend Tree A by adding a new node, x + - Find the closest node in Tree B to x, y + - If (LocalPlanner(x,y)) – Check if you can bridge the 2 trees + - Add edge between x and y. + - This completes a route between the root of Tree A and the root of Tree B. Return this route - -- + - Else + - Swap Tree A and Tree B + - +![Alt text](./1546201717793.png) diff --git a/Software/Algorithms/Motion Planning/Sample Based Planners/1546201453749.png b/Software/Algorithms/Motion Planning/Sample Based Planners/1546201453749.png new file mode 100644 index 0000000..47eac1c --- /dev/null +++ b/Software/Algorithms/Motion Planning/Sample Based Planners/1546201453749.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Sample Based Planners/1546201460892.png b/Software/Algorithms/Motion Planning/Sample Based Planners/1546201460892.png new file mode 100644 index 0000000..bcb89ee --- /dev/null +++ b/Software/Algorithms/Motion Planning/Sample Based Planners/1546201460892.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Sample Based Planners/Characteristics of Sample Based Planners.md b/Software/Algorithms/Motion Planning/Sample Based Planners/Characteristics of Sample Based Planners.md new file mode 100644 index 0000000..3b3a0d7 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Sample Based Planners/Characteristics of Sample Based Planners.md @@ -0,0 +1,19 @@ +#Characteristics of Sample Based Planners +There are a couple of characteristics of Random Sampling Based approaches that are worth noting. + +•  First of all, while these methods work very well in practice they are not strictly speaking complete. + +•  A complete path planning algorithm would find a path if one existed and report failure if it didn’t. + +With the PRM procedure it is possible to have a situation where the algorithm would fail to find a path even when one exists if the sampling procedure fails to generate an appropriate set of samples. + +![Alt text](./1546201453749.png) +![Alt text](./1546201460892.png) + +What we can say is that if there is a route and the planner keeps adding random samples it will, eventually find a solution. + +•  However it may take a long time to generate a sufficient number of samples. + +•  A real advantage of these PRM based planners is that they can be applied to systems with lots of degrees of freedom as opposed to grid based sampling schemes which are typically restricted to problems in 2 or 3 dimensions. + +•  In conclusion by relaxing the notion of completeness a bit and embracing the power of randomization these probablistic road map algorithms provide effective methods for planning routes that can be applied to a wide range of robotic systems including systems with many degrees of freedom. \ No newline at end of file diff --git a/Software/Algorithms/Motion Planning/Trapezoidal Decomposition/1546201910730.png b/Software/Algorithms/Motion Planning/Trapezoidal Decomposition/1546201910730.png new file mode 100644 index 0000000..55afeae --- /dev/null +++ b/Software/Algorithms/Motion Planning/Trapezoidal Decomposition/1546201910730.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Trapezoidal Decomposition/Trapezoidal Decomposition.md b/Software/Algorithms/Motion Planning/Trapezoidal Decomposition/Trapezoidal Decomposition.md new file mode 100644 index 0000000..81839c4 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Trapezoidal Decomposition/Trapezoidal Decomposition.md @@ -0,0 +1,4 @@ +#Trapezoidal Decomposition +处理Configuration Space的一种方法,将多边形图切割成一个个梯形 + +![Alt text](./1546201910730.png) diff --git a/Software/Algorithms/Motion Planning/Visibility Graph/1546200410450.png b/Software/Algorithms/Motion Planning/Visibility Graph/1546200410450.png new file mode 100644 index 0000000..c3e0a3c --- /dev/null +++ b/Software/Algorithms/Motion Planning/Visibility Graph/1546200410450.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Visibility Graph/1546200430877.png b/Software/Algorithms/Motion Planning/Visibility Graph/1546200430877.png new file mode 100644 index 0000000..29f454e --- /dev/null +++ b/Software/Algorithms/Motion Planning/Visibility Graph/1546200430877.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Visibility Graph/1546200467850.png b/Software/Algorithms/Motion Planning/Visibility Graph/1546200467850.png new file mode 100644 index 0000000..818539a --- /dev/null +++ b/Software/Algorithms/Motion Planning/Visibility Graph/1546200467850.png Binary files differ diff --git a/Software/Algorithms/Motion Planning/Visibility Graph/Visibility Graph.md b/Software/Algorithms/Motion Planning/Visibility Graph/Visibility Graph.md new file mode 100644 index 0000000..8522802 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Visibility Graph/Visibility Graph.md @@ -0,0 +1,9 @@ +#Configuration Space +首先构建Visibility Graph: +![Alt text](./1546200430877.png) +然后随机取点并进行碰撞检测得到边: +![Alt text](./1546200410450.png) +最后规划出路径: +![Alt text](./1546200467850.png) + + diff --git a/Software/Algorithms/Robotics Algorithms.xmind b/Software/Algorithms/Robotics Algorithms.xmind index 5dcba3d..6a5421c 100644 --- a/Software/Algorithms/Robotics Algorithms.xmind +++ b/Software/Algorithms/Robotics Algorithms.xmind Binary files differ