图搜索基础
- 图搜索基础
- 迪杰斯特拉和A星(Dijkstra and A*)
- 点跳转搜索(Jump Point Search)
图搜索基础
配置空间
- 机器人配置：指向机器人所有点的位置的大小
- 机器人*度(DOF)：最少真实坐标n需要的大概机器人配置
- 机器人配置空间：一个未知n大小包含所有机器人能配置的空间，表示为C-space
- 每个机器人都在C-space中变换成一个点
配置空间障碍物
膨胀障碍物大小，将机器人的大小膨胀到障碍物上，来实现将机器人在C-space中变换成一个点
实际空间和配置空间障碍物
- 实际空间中机器人有形状和大小
- 配置空间C-space中机器人是一个点，在运动规划前障碍物就已经在C-space中生成
- 在C-space中模拟障碍物可能比实际障碍物更复杂，这样就可以在实践中使用
图搜索方法
- 首先要创建一棵图搜索树
- 在通过结点之间的关系，来找到目的结点
图遍历
图有两种遍历方法：广度优先遍历（BFS）、深度优先遍历（DFS）
广度优先遍历使用的是队列，深度优先遍历使用的是栈（具体可以在数据结构中了解更详细的内容）
Heuristic Search(启发式搜索)
贪心优先搜索（Greedy Best First Search）
启发式搜索就是一种与目标位置距离远近检测的条件
行动成本（Cost on Actions）
在移动过程中，一个节点到另一个节点有一个成本“C”
Dijkstra and A*(迪杰斯特拉和 A星)
算法流程
Dijkstra’s Algorithm：
代价函数值最小的节点优先遍历
遍历如下路径：
一步步遍历过后如图：
比较关键的点是g(n)的值是叠加的，这样是为了能够当遇到障碍物较多的路径时，能够走出一条更优的路径
在地图的仿真中Dijkstra的效果如图
类似于同心圆的搜索
A*
所以只要时间足够长的情况下，使用Dijkstra就一定能够找出一条最优的路径来。耗时长也是Dijkstra的缺点，在添加了启发式函数之后效果如图
以上效果图都来自于PathFinding.js (qiao.github.io)网站。
可以明显看出，当添加了启发式函数之后，也就是贪心算法，搜索有了更明确的方向性。
Dijkstra的代价函数是到相邻节点的距离，而A*的代价函数则是在Dijkstra之上添加了启发式函数（Heuristic）
从开始状态到目标状态通过节点的最小估计成本f(n) = g(n) + h(n)
启发式函数h(n)常用的是曼哈顿距离、欧氏距离
代码流程：
--维护一个优先级队列来存储所有要扩展的节点（openlist、closelist）
--设置启发式函数h(n)
--初始化起点
--设置g(Xs) = 0,其他节点g(n) = 无穷大
--循环
--如果队列为空，返回false，break
--从openlist里删除f(n) = g(n) + h(n)最小的节点"n"
--把"n"加入closelist
--如果"n"是目标节点，返回true,break
--对于节点"n"不在closelist里的邻居"m"
--如果g(m)无限大
--g(m) = g(n) + Cnm
--将"m"推入队列
--如果g(m) > g(n) + Cnm
g(m) = g(n) + Cnm
--结束循环