diff --git "a/Robots/Fetch\346\234\272\345\231\250\344\272\272\345\271\263\345\217\260.md" "b/Robots/Fetch\346\234\272\345\231\250\344\272\272\345\271\263\345\217\260.md" index 788c4e8..e3ce3f3 100644 --- "a/Robots/Fetch\346\234\272\345\231\250\344\272\272\345\271\263\345\217\260.md" +++ "b/Robots/Fetch\346\234\272\345\231\250\344\272\272\345\271\263\345\217\260.md" @@ -16,7 +16,7 @@ 而我们关心的是其机器人产品:Freight移动机器人和Fetch机械臂。这家公司的独特之处在于拥抱开源和学术界。他们将其中两款产品写了驱动,做了文档,把平台开放出来让大家开发,这就吸引很多公司和实验室用他们的平台来进行机器人算法开发。 -看起来这家公司相当有做硬件的实力,机械底盘谁都能造,但是自己造机械臂还是要勇气的。这家的产品和pr2很类似,而willow garage已经跪了。现在卖机器人是赚不了什么钱的,只能想办法和行业靠拢,做仓储物流平台像是正确的思路,公司能融到25M说明还是有市场可以赚钱。下次可以介绍一下Fetch的竞争对手,从Willow Garage脱离出来的unbounded Robotics,做的产品简直一模一样。 +看起来这家公司相当有做硬件的实力,机械底盘谁都能造,但是自己造机械臂还是要勇气的。这家的产品和pr2很类似,而willow garage已经跪了。现在卖机器人是赚不了什么钱的,只能想办法和行业靠拢,做仓储物流平台像是正确的思路,公司能融到25M说明还是有市场可以赚钱。下次可以介绍一下Fetch的竞争对手,从Willow Garage脱离出来的unbounded Robotics,还有Toyota Human Support Robot,做的产品简直一模一样。 ## 硬件 diff --git a/Software/Algorithms/Motion Planning/Difference of A* & Dijkstra.md b/Software/Algorithms/Motion Planning/Difference of A* & Dijkstra.md new file mode 100644 index 0000000..dc0e028 --- /dev/null +++ b/Software/Algorithms/Motion Planning/Difference of A* & Dijkstra.md @@ -0,0 +1,42 @@ +# Difference of A* & Dijkstra + +tag : *Algorithm* + +author : gzy + +--- + +最短路径搜索,给定了一张地图,已知起始点和目标点,求两点间的最短路径。大家比较常听到的有A*算法和 Dijkstra算法。 + +具体就不用多说,算法比较简单,可以看一下网上的博客(见拓展),30min就可以了解算法是如何运行的。网上也有很多开源代码,ROS也有具体的包实现。 + +## 算法差别 +但是同样是找最短路径,这两种算法有什么不同?这是我主要的疑惑点。我是这么找到答案的。 + +首先,我知道ROS Navigation Stack之前用到了轨迹规划的包叫做Navfn,看网上评论大家似乎用的比较顺手。看了[Navfn的官网](http://wiki.ros.org/navfn),支持Dijkstra但是不支持A* 。我觉得[这个回答](https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=28399#post-id-28399)可以接受,但是具体性能如何,还要根据实际情况判断,比较A*的性能和启发函数相关,不能一概而论。 + +## 被搜索图的差别 +另一个疑惑点是,这两个算法使用的map不太一样。A* 使用的是网格图,每个网格代表一个位置,在简介中,网格不带cost,在网格间移动会产生cost。而Dijkstra使用的是“图”数据结构,每个顶点是一个位置,沿着边移动会产生cost。 + +![A*](../../../meta/pic/A_star.png) + +使用A*搜索的 **网格图** + +![Dijkstra](../../../meta/pic/Dijkstra.png) + +使用Dijkstra搜索的 **图** + +但是仔细一想,这两种地图可以相互转化的。如果要进行图搜索,那A* 用的**网格图**可以转化为**图**,只需要把每个网格变成图的顶点,相邻网格之间连上cost为1的边即可;如果要在**网格图**里进行路径搜索,Dijkstra使用的**图**也可以具体化为**网格图**的,只需要让每个顶点的度变成4,每个边的移动cost变成1就相当于**网格图**了。 + +## 算法和实际ROS实现的差别 +但是再仔细一想,还是有点不太对劲,即使沿路移动的cost被计算进去了,但实际ROS中,对环境感知后得到的cost map却比这个还要多一个东西,就是每一个点上的cost。不仅沿着路移动会有cost,进入下一个点cost也会产生cost。这个是合理的,因为有的点是障碍物,cost极大,虽然向那个点移动可能不花费cost,算是踩到那个点相当于撞墙,所以cost极大,这可以帮助机器人避开不合理的点。 + +所以ROS对上述算法是实现中还做了一个小改动,就是将移动的cost和将要踩到的下一点的cost融合成为一个叫做potential的值,利用这个potential进行排序选择真正的下一点。 + +## 拓展 +[Dijkstra算法详解](https://blog.csdn.net/qq_35644234/article/details/60870719),虽然写的并不太好,不失为快速了解的好方法 + +[A*](https://www.cnblogs.com/zhoug2020/p/3468167.html),一个有趣又简单的举例解释。 + +只有Dijkstra的[navfn](http://wiki.ros.org/navfn)已经不多用了,现在用的更多的是实现了A*和Dijkstra的ROS包[global_planner](http://wiki.ros.org/global_planner) + diff --git a/Software/Algorithms/Motion Planning/GraphSearch.md b/Software/Algorithms/Motion Planning/GraphSearch.md deleted file mode 100644 index 7e8b0e9..0000000 --- a/Software/Algorithms/Motion Planning/GraphSearch.md +++ /dev/null @@ -1 +0,0 @@ -# A_star diff --git a/meta/pic/A_star.png b/meta/pic/A_star.png new file mode 100644 index 0000000..2b27b35 --- /dev/null +++ b/meta/pic/A_star.png Binary files differ diff --git a/meta/pic/Dijkstra.png b/meta/pic/Dijkstra.png new file mode 100644 index 0000000..ae6e4d3 --- /dev/null +++ b/meta/pic/Dijkstra.png Binary files differ