农业采摘机器人路径规划的研究

1.1 路径规划问题描述
       农业采摘机器人路径规划需要机器人根据工作任务、设计需要、执行要求，寻找出一条可以满足以上需求的最优路径并避免对环境障碍物的碰撞。移动机器人通过原有的地图存储信息或者自身的传感器获得实时的环境信息，进而搜索规划出一条可执行操作路径，完成操作要求。
       农业采摘机器人路径规划的研究主要包括两个路径规划方法：全局规划和局部规划。全局路径规划又称静态或离线路径规划，是指轮式移动机器人的路径规划，需要了解地图环境中的所有信息。因为需要掌握环境地图的信息量比较大，所以计算量大，消耗时间多，导致效率低。本地路径规划，即动态或在线路径规划，是一个农业采摘机器人的路径规划和设计，不知道它在哪里或知道它的局部位置。在规划过程中，需要获得来自传感器本身在时间上的环境信息。从实际情况来看，全局规划和地方规划是相辅相成的，没有太大的区别，协同作用。
       在路径规划和设计过程中，农业采摘机器人根据传感器检测到的环境地图信息构建环境模型，通过对具体环境信息的研究以及设计任务的需求选择合适的一种或多种路径规划算法结合或改进，最终设计出最好的农业采摘机器人路径。

2路径规划环境建模
       环境建模首先将环境空间划分并规划提取特征信息，将环境地图信息转化为可存储和利用的计算机数字信息。当地图中出现环境改变时，能及时反馈更新到地图中。因此，农业采摘机器人路径就可以设计规划。接下来，对农业采摘机器人路径规划常用几种环境建模方法进行简单的介绍：
2.1 栅格模型
      栅格模型是较为传统的环境模型，由Moravec和Elfes最早提出，是目前应用最广泛的农业采摘机器人路径规划方法之一。将采摘机器人的环境空间划分为若干区域，形成具有信息量的相互连接、不重叠的单元，即网格。栅格一般包括两种状态：自由栅格，环境内不存在任何障碍物；障碍栅格，环境内部部分或全部填满障碍物。农业采摘机器人路径规划具体步骤：将环境地图栅格化；给栅格编号，根据障碍物分布的情况规划一条可行路径，并用编号表示；将编号转化成实际环境坐标；农业采摘机器人依据环境信息的位置坐标来完成其路径设计。栅格模型引发的问题是：如果提高环境地图和规划路径的精度，物理存储容量的要求就会提高；反之，如果要节约存储空间开销，精准度就会降低。
2.2 几何模型
       几何模型是指利用传感器将环境地图中的障碍物信息转化为几何点、线、面等。环境地图信息通常转化为全局坐标。几何模型不重新规划的路径，由于在出发点和目标点的变化，并具有高度的灵活性；同时，在规划路径时，几何模型对于物理存储空间的要求较小来存储环境地图的信息；几何模型的表示发放也比较紧凑。因为其简便性，得到了广泛应用。几何模型引发的问题是：容易把农业机器人当作质点，这样在规划路径时，障碍物与农业采摘机器人之间没有一个安全距离，容易产生摩擦或碰撞，存在安全隐患。
2.3 拓扑模型
       拓扑模型相对其它模型较为简单；存储空间的需求较小；路径规划效率较高。但有时，拓扑模型可能无法规划出最优路径。拓扑模型的路径规划由传感器系统直接决定，传感器需实时探测反馈环境地图的信息。拓扑模型引发的问题是：如果环境空间划分的不细致，路径规划的精度就会大大降低；反之，数据运算量就会大幅度增加。若障碍物的不具有明显的特征、环境障碍物分布地比较稀疏、不紧密，路径规划时，一般不采取拓扑模型。
2.4 三维模型
       三维模型的研究还不是很成熟，还需更加完善，与二维模型相比，环境地图信息更直观、形象生动，但是存储量、计算量更大，算法也更复杂，所以对于三维模型的研究相对较少。
3 全局路径规划算法
3.1 栅格法
      1968年，W.E.Hovcden提出栅格法。栅格的方法通常是将环境地图分为信息价值的栅格单位，农业采摘机器人的路径规划的性能受划分栅格单元大小的影响比较大。网格单元越小，环境图的分辨率越高，路径规划越精确，但存储空间的要求越高，计算量大、效率和实时性都会降低；栅格单元越大，对存储空间要求就会降低，运算量也会减小，系统的实时性较强，但环境地图的分辨率降低，可能会无法寻找出最优路径。所以，不同环境的选择中，栅格大小的划分是很重要的。A*算法和D*算法是常用的启发式搜索算法。
3.2 可视图法
      可视图法视农业采摘机器人可以被看作为一个点，直线段采用农业采摘机器人的出发点、目标点和环境壁垒都固定组合连接，农业采摘机器人的起点和环境壁垒阻碍关系的每一个顶点，农业采摘机器人的目标点和环境障碍的每个顶点与环境障碍物的顶点之间的无障碍被称为直视，因此生成的图称为可视图最优路径规划问题即为线段之间连接的最短问题。
3.3 链接图法
      链接图法是基于以下两点假设的：在二维模型中，农业采摘机器人的路径规划由点表示；环境障碍物用凸边形的方法表示。用互相不交叉的链接线连接环境障碍物所有的顶点得到环境空间中最大的凸边形；将各连接线的中点作为轮式移动机器人路径规时所要经过的点，由这些路径点组成农业采摘机器人的路径规划。链接图法特点：灵活，环境障碍物的数量影响着链接图法的复杂度，有时并不能获的并不是最短路径。
3.4 概率路径图法
       90年代初，M.H.Overmars、P.Svestka等人提出概率路径图法（简称PRM）。首先，在环境地图中规划设计路线，然后用序列的方式表示农业采摘机器人的路径。采样点碰撞检测的概率路径图算法用于测试环境地图路径连通性。环境空间障碍物的数量、形状、大小对其算法的复杂程度并不产生影响，但农业采摘机器人路径规划的难易程度对其复杂程度有主要影响。
4 局部路径规划算法
4.1 人工势场法
        Khatib博士在1968年最先提出人工势场法（Artifical Potential Field,简称APF）。其原理是，如果现有的农业采摘机器人强环境空间：吸引和排斥，收获的影响，农业机器人斥力的重力和障碍物的运动过程中的两个力，以实现路径规划的效果。
         人工势场法的研究相对成熟，易操作和实现，路径规划时需要的地图信息较少，算法运算量较小，因此在各 大领域都得到了广泛应用。人工势场在路径规划中的缺点，如果目的地存在于周围环境中，当目的地接收到轮式机器人时会吸引接近，不接近目的地，同时也受到障碍物的排斥， 从而完成不了路径规划所要达到的效果。
4.2 RRT算法
        1998年，Steven.M.Lavalle教授提出快速扩展随机树（Rapidly-Exploring Random Tree,简称RRT）算法。它的方法是：在环境地图中，将路径规划起始点作为根节点，随机函数用于展开节点，节点在约束条件下生成，叶节点的常数增加，形成一个随机生成树。最终方案是从起点和目标树节点的路径。
RRT算法在运动力学条件下，通常采用的路径规划问题，不需要对环境空间进行建模，最后的规划路径是合理的。然而，在一般情况下，RRT算法的路径规划是粗糙的，不是最优的，需要改进。
4.3 遗传算法
          在1975，X教授第一次提出了遗传算法（简称GA）。该算法是基于达尔文的进化理论的原则，是一个自然选择的路径搜索算法。遗传算法具体步骤是：初始化路径规划，用染色体编程编码将路径规划个体描述为一系列的路径，然后选择；复制；交叉；变异，不断进化得到最优个体
        遗传算法也有缺点：易早 熟收敛；精度越高，单个代码串越长，算法也就更加的复杂；路 径规划时间较长，不具实时性。
4.4 蚁群算法
       1991年，意大利科学家Dorigo M、Colorni A、Maniezzo V仿生蚂蚁群觅食行为首次提出蚁群算法（Ant Colony Optimization,ACO），其基本原理为:蚁群出去觅食或者搬家时，每一只蚂蚁都会通过释放的方式，作为它的路径参考，其他蚂蚁会知道的分泌物。这种称为费洛蒙信息素的蚂蚁分泌信息，路径选择。蚂蚁会自动走上信息素的路径，这样的路径的分泌物会越来越多，形成越来越集中的信息素。其余部分的信息素浓度的路径逐渐减小，直到没有，最终蚂蚁群将找到一个最佳最合理的路径。
       通常情况下，农业采摘机器人需要从三个方面来考虑路径规划：
1、农业采摘机器人在运动过程中要避开环境障碍物以及农作物枝干；
2、农业采摘机器人从起始点出发，能达到目标点；
3、满足上述两点的最优路径。