Path Planning algorithms for agriculture field machines

零、摘要：

背景： CCPP 条件是全覆盖，目标是尽可能高效。没有普遍的算法可以解决所有问题。
本文：两种解决全覆盖路径规划问题的方法。
第一种 将地块分成若干个相连接的梯形地块；在搜索方法中，找到了每个梯形地块的最适驾驶方向。
第二种算法 路径是基于机器当前的状态。受模型预测控制的影响，所有可能的路线都是在围绕场地的一条路线或一条来回的带状区域的水平面上模拟的。选择最佳的模拟路线，并应用该路线的第一部分，直至下一个转弯。在下一个转弯处，重复该算法。
研究成果一 地块属性的研究，只有少数地块是有单独的矩形或者三角形组成。多数地块形状无法确定。
研究成果二 在调头区，拖挂式拖拉机的轨迹规划。该问题被描述为一个最优控制问题，并使用可用的方法和工具进行求解。使用这种方法，可以求解任何地头宽度和角度的轨迹。

一、
章节2  地块形状分析
章节3  调头区
章节4  自顶至下
章节5  自下到上
1、现在所有的车都是非全向性的，不能完成所有的转向任务。
2、headland 转弯区         tractor-trailer 拖挂式拖拉机
3、非全向性机器的 全覆盖式路径规划 的最优问题很难。
（二）根据6个形状描述指标对地块进行分类
（三）单独掉头的优化可以描述为。轨迹可被视为函数；地块边界可被视为约束；拖拉机运动学约束也要考虑。
（四） 车 自顶至下 复杂形状的地块分解成可驾驶的简单形状地块
（五）在某一预测范围内 模拟若干条路径 选择最优， 然后覆盖整个地块
 注： 解决方案的绝对最优不是目标，因为不能证明路径的最优
原创：

二、地块分析

1、本章目的

更好地理解路径规划问题的需求，尝试将地块分成一些基于形状的集合，找到典型的地块图来测试路径规划算法。

2-4形态指标

2-4-1
本文将地块图作为多边形，运用多边形类型的形状索引算法或者使用位图输入算法。
2-4-2区域的凸性
凸多边形定义：如果把一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，其他各边都在此直线的同旁，那么这个多边形就叫做凸多边形。
凸多边形性质：1、所有内角小于等于180度。2、任意两个顶点间的线段位于多边形的内部或边上。3、多边形内任意两个点，其连线全部在多边形内部或边上。
凸包定义：点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
区域的凸性：区域面积/区域外多边形的凸包的面积。 [0,1]。
2-4-3区域的紧凑性
紧凑性= 4π*A/P  [0,1]   (A:区域面积，P:区域周长)
2-4-4区域的矩形性
最小外接矩形（MBR）：
旋转卡壳法求MBR：https://blog.****.net/clover_hxy/article/details/54024359
原理：外接矩形的某条边上一定包含至少两个凸包上的点，其他边至少包含一个。这样才能确定出一个合法的矩形。

• 枚举凸包上的相邻两点，确定矩形的一条边所在的直线。
• 然后就是要求到该直线最高，最左，最右的点。这些点随着凸包上边的旋转是单调的。
• 最高的点，直接用点到直线的距离。
• 最左最右的话，可以用点积，为什么是点积，因为我们要求的两个点一定在该直线上的投影最长，注意向量的方向。

矩形性= A/S [0,1]   (A:区域面积，S:MBR的面积)
2-4-5区域的特征矩
2-4-6区域的三角性
2-4-7区域的椭圆性
2-4-8区域的主矩比

2-5 结果

凸性的分布不是正态分布，椭圆形也不是正态分布

图3为形状指标的矩阵图：来表示指标的相关性，例如在第四列第二行的地块中，横轴为三角形，纵轴为紧实性。
图4-9为各种地块的指标值

2-6分类