路径规划算法1.1图搜索算法——可视图法

前言

机器人自主运动三巨头：感知，规划，控制。规划又包括运动规划、路径规划。路径规划又包括全局规划，局部规划。

路径规划，就是在给定的地图，找出一条从起点和终点的轨迹，随着任务逐渐复杂，这条线必须满足一些要求：路径最好短一些（最优路径），规划速度快一些（时间复杂度），不能碰到障碍物（避障），有解时一定能找到解（完备性），等等。

图搜索算法

机器人地图多使用图结构储存，因此许多经典的图搜索算法都适用于路径规划。另外，路径规划还有一个重要的方向，就是地图表示，不过这里只研究规划算法，地图有空再研究。

图结构可以分为有无向图，有无权图，排列组合就有四种有向有权图，无向无权图balabala。

对于无权图有两种基本图搜索算法：广度优先搜索BFS，深度优先搜索DFS

在BFS中加入贪心：Dijkstra算法

在BFS中加入启发式搜索：贪婪最佳优先搜索GBFS

在Dijkstra中加入启发式搜索：A*算法

可视图法

原论文：An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles.

可视图法将机器人描述为点，障碍物为多边形，然后将起点S、终点G、多边形顶点V连接，并且任何连线都不能穿透障碍物，可以将直线的距离作为连线的权值。这样就建立了一个可视图，可以通过优化算法对{S,G,V}进行求解获得最优路径。

VG法在建图时，由于没有考虑到机器人、障碍物的尺寸，机器人在生成轨迹上运动时会擦着障碍物的边走，因此会发生碰撞。后续的改进算法在建图前，先将障碍物边界扩展一个机器人的尺寸，生成的轨迹就使得机器人能刚好贴着障碍物运动。

此外，原始的VG法也无法对圆弧边界障碍物建图，因此在后续改进中将圆弧边界用切线包围，就退化为多边形障碍物问题了。

实际上，可视图法就是一种通过可视地图构建算法。