路径规划学习入门
运动规划简介
当虚拟人开始一次漫游时，首先全局规划器根据已有的长期信息进行全局静态规划，确定虚拟人应该经过的最优化路线。然后全局规划器控制执行系统按照该路径运动。在运动过程中，感知系统会持续对周围环境进行感知。当发现动态的物体或未知障碍时，局部规划器根据这些感知到的局部信息，确定短期內的运动。当避障行为的优先级高于沿原路径前进时，局部规划器就能够通过竞争获得执行系统的控制权，使得虚拟人按照局部规划结果运动。完成对当前感知障碍的规避行为后，全局规划器再次取得执行系统的控制权，使得虚拟人重新回到全局规划路径上，继续向目标点运动。参考
Dijkstra和A*算法做的效果演示动画
A算法加入了启发函数，用于引导其搜索方向,A算法会比Dijkstra算法规划速度快不少。
20170913165752985.gif
最佳优先搜索（BFS）算法
BFS按照类似的流程运行，不同的是它能够评估（称为启发式的）任意结点到目标点的代价。与选择离初始结点最近的结点不同的是，它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristic function）快速地导向目标结点。例如，如果目标位于出发点的南方，BFS将趋向于导向南方的路径。在下面的图中，越黄的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。这表明了与Dijkstra 算法相比，BFS运行得更快。
A*算法结合了Dijkstra和BFS的各自的优点，把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。
随机路图法PRM
是基于图搜索的方法，随机路图（Probabilistic Road Maps，PRM）就是在规划空间内随机选取N个节点，之后连接各节点，并去除与障碍物接触的连线，由此得到一个随机路图。
快速扩展随机树法RRT
是基于树状结构的搜索算法，RRT算法是从起始点开始向外拓展一个树状结构，而树状结构的拓展方向是通过在规划空间内随机采点确定的。与PRM类似，该方法是概率完备且不最优的。
20170904092336606.gif
快速扩展随机树法RRT
是基于树状结构的搜索算法，RRT算法是从起始点开始向外拓展一个树状结构，而树状结构的拓展方向是通过在规划空间内随机采点确定的。与PRM类似，该方法是概率完备且不最优的。
虽然基于采样的规划算法（如PRM和RRT）速度很快，但他们也有致命的缺点，那就是由随机采样引入的随机性。利用RRT和PRM算法进行运动规划，用户无法对规划结果进行预判，每次规划的结果都不一样，这就使得自动规划的机器人无法进入工业领域（极端追求稳定性）。
所以目前规划领域也主要集中在对PRM和RRT的改进上，大家都想要尽可能解决这类算法的不确定性，甚至能实现一些优化目标，如RRT，Informed-RRT，SBL等。
Introduction to Autonomous Mobile Robots 中关于路径规划的内容
第一步将可能的连续的环境模型装换成适应于所选路径规划算法的离散图，有三种通用的策略：道路图、单位分解、势场。
道路图
-
可视性图
由连接彼此可见的全部顶点对的连线组成，连接这些无阻挡的顶点即是它们之间 的最短距离。
该方法仅适用于稀疏目标群，而且允许机器人尽可能的接近障碍物。 -
沃罗诺伊图
相对于可视化图，它倾向于使图中机器人与障碍物之间的距离最大化。
它也会使环境中的机器人与物体之间的距离最大化，使得机器人上的短距离传感器检测不到可能存在的危险。
单元分解路径规划
- 主要思想是区分几何区（也叫单元）之间的区别，即把单元区分为自由的和被物体占用的区间。
- 主要分为精确单元分解和
-
精确单元分解：基于以下的思想：在自由空间的各单元中内， 机器人的特殊位置不重要，重要的是机器人从各自由单元走向其相邻自由单元的能力。
在大的稀疏环境中，单元的数目较少，实施效果挺有效。但是一旦单元数目巨大，实现的难度就会剧增。
- 近似单元分解
单元的尺寸不依赖于环境中的特殊物体，路径规划的计算复杂性低。是基于栈格的环境表示的普遍性。
势场路径规划
主要思想：把机器人处理成人工势场影响下的一个点，像球滚下山一样，机器人跟随着场移动。机器人被吸引向目标，同时也被先前已知的障碍物所排斥。
如果障碍物新出现，应该及时更新势场。
扩展势场法
在基本势场上，附加了两个场：转动势场和任务势场。
- 转动势场：当障碍物与机器人行走的方向平行时，减小斥力，因为这样的一个物体不会对机器人的轨迹造成及时的威胁。结果增强了沿墙跟踪能力。
-
任务势场：考虑了当前机器人速度，排除了根据近期势能对机器人速度无影响的障碍物。结果是穿过空间的轨迹更平滑。
