机器人路径规划算法初步了解

一． Astar算法

Aster算法是在Dijkstra算法基础上发展出来的，是在静态路径中用于求解最优路径有效的直接搜索算法，比dikstra算法多了一个启发式的搜索函数，也就是通过一个代价函数来确定搜索方向(从起点开始向周围扩张，通过代价函数，计算得到周围每个节点的代价值，选出最小代价节点作为下一个扩展点，重复这个过程直到到达目标点。)。

二． RRT算法

RRT是一种在多维空间中基于采样的规划方法。该方法通过随机探索自由空间，并构建一棵从初始状态开始寻找朝向目标状态的可行路径的树T=(V,E)。在迭代的过程中，创建随机点并搜索距离该点最近的顶点，然后以固定步长得到该方向上的新节点，并检查其是否属于自由空间，直至达到目标。在未占用空间中均匀扩展的属性，使得其在复杂的高维环境、动态环境以及非完整和运动约束环境中依旧有效。

三． Fuzzy

基于模糊的导航是一种反应式规划技术，其中考虑障碍物的当前位置和距离来计算即时移动，而无需考虑未来。以这种方式，即时动作会导致机器人的运动，最终达到目标。为了使用模糊逻辑解决这个问题，我们首先需要选择几个最能代表机器人当前所处位置的输入。运动决策完全基于这些输入，而不是实际情况。对于此问题，选择了6个输入。它们是与前方障碍物的距离、与左前对角线处障碍物的距离、与右前对角线处障碍物的距离、机器人前进方向与目标之间的角度、机器人的距离、从目标和首选转向。最后一个输入，首选旋转指示顺时针或逆时针旋转是否有益，所有其他忽略输入。使用简单规则设置参数。如果前方障碍物距离较远，则转向以面向更多的面目标。如果前方障碍物靠近，并且遇到新的前方障碍物，则使用目标一侧转弯首选。如果前面的障碍物很近，并且发现与上一步中遇到的障碍物相同，则重复先前的转向。模糊系统产生一个单一输出，即转向或即时角速度。模糊的规则的编写应确保机器人能够避开障碍物，并将自身对准目标。模糊系统是在各种情况下，对规则和成员函数进行大量手动调整的结果。

四． GA算法

GA将用作标准优化算法。作为一种优化算法，GA不会要求提供有关衍生工具的任何信息，以便发挥作用。要将问题建模为优化问题，我们需要一个目标函数和变量规格目标函数（及其边界）。设一条路径的特征为机器人地图。为了从这组点创建一些路径，我们从源开始，并将其连接到第一个点用直线指向。第一个点通过直线连接到第二个点，依此类推。最后最后一点与目标相连。目标函数是该路径的长度。如果有，将处以重罚部分路径位于障碍物内，而惩罚与障碍物内路径的长度成比例。每个固定数量点的位置（X轴和Y轴位置）都是优化变量。变量边界使点位于贴图内部（下限为1，上限为长度/宽度X/Y轴的贴图）。所有点（X轴和Y轴值）逐个放置，使遗传个体使用用于优化。路径中的每个点都标记一个转弯点。总点数是一个算法参数，应为等于机器人在机器人地图中预期的最大转动次数。将此数字设置得太高将导致非常大的计算需求。如果算法不允许有大量的计算时间，输出可能是随机结果。在简单场景中设置一个较大的值将导致无用的转弯，因此高路径长度。参数值太小可能无法为算法提供足够的灵活性来建模最佳路径，从而产生容易发生碰撞的路径。

四． PRM

PRM算法分为两个阶段：离线路线图（图）构建阶段和在线规划/查询阶段阶段离线路线图（graph）构建阶段的目的是在图形的所有顶点和边都应无碰撞，以便机器人可以使用相同的图形进行运动规划。PRM在工作空间中选择多个随机点（状态）作为顶点。整齐若要限定为顶点，随机选择的点（状态）不得位于某个障碍物内。设k数作为算法参数的状态数。顶点数或k越大，使用计算时间损失。然后，该算法尝试连接所有随机选择的顶点对。如果有的话两个顶点可以通过一条直线连接，该直线作为边添加。由于图是已知的，所以可以使用任何图搜索算法。代码使用算法来实现相同的功能。边的权重作为连接点之间的欧几里德距离和启发式函数（表示点与目标）作为到目标的欧几里得距离。

五． RRT算法

RRT算法生长并维护一棵树，其中树的每个节点都是工作区。该算法所探索的区域就是树所占据的区域。最初，算法从将源作为唯一节点的树。在每次迭代中，通过选择随机状态和将树扩展到该状态。通过将树中最近的节点向通过小步选择随机状态。该算法一直运行到某种扩展使树离目标足够近。步长的大小是一个算法参数。较小的值会导致缓慢扩展，但更精细的路径或可以很好地转弯。通过选择目标作为具有一定概率的随机状态。

六．人工势场法

基于人工势场的导航是一种反应式规划技术，其中障碍物被认为是计算即时移动的工具，而不必担心未来。在这样的情况下立即采取行动的方式引导机器人运动，最终实现目标。所有障碍物都会排斥机器人大小与距离成反比。目标吸引了机器人。合成电势，测量吸引和排斥组件，并将其用于移动机器人。方向表示势向量的方向。测量障碍物在各个角度与机器人之间的距离。在本教程中，在特定位置仅5个距离测量角度以计算排斥势。这些是向前、左侧、右侧、向前左对角线和向前右对角线。