本文为美国爱荷华州立大学（作者：Theresa Marie Driscoll）的硕士论文，共71页。

多年来，在一个区域内寻找无碰撞路径的问题得到了大量的研究，其中一个分支是找到一条完全覆盖一个区域的路径问题。全覆盖路径规划问题的解决方案在许多不同领域都有应用，如搜索救援、汽车涂装和农业。在许多情况下，不足以找到完全覆盖现场的规划路线。

我们希望路径是最优的，以最小化某些成本，在农业环境中尤其如此。在精细农业领域，当执行许多不同的操作（如收割、播种、喷洒、施肥和耕作）时，就存在完全覆盖路径规划问题。农民最关心的是降低经营成本。由于大多数农业成本最终取决于农田和覆盖区域的时间，作业效率越高，成本就越低。因此，最优性通常是指通过域找到最短的完全覆盖路径。本文提出了求解n边场边界上最优完全覆盖问题的O（n²）算法，这种多相位算法利用平面扫描算法将场细分为更小的梯形区域，然后计算通过子区域的最佳路径。最后是一个合并阶段，在这个阶段，我们进行如下判决：如果将相邻区域合并在一起，是否比将它们分开能够更有效地覆盖它们。

The problem of finding a collision-freepath through a region has garnered a lot of research over the years. One branchof this is the problem of finding a path that completely covers a region.Solutions to the complete coverage path planning problem have applications inmany different areas, such as search and rescue, automotive painting, andagriculture. In many cases, it is not sufficient to find any route thatcompletely covers the field. It is desired that the path also be optimal so asto minimize certain costs. This is especially true in the agriculturalenvironment. In the area of precision farming alone, the complete coverage pathplanning problem exists while performing many different operations, such asharvesting, seeding, spraying, applying fertilizer, and tillage. Thefundamental concern of farmers is reducing the costs of running the farm. Sincemost farming costs ultimately depend on time in the field and area covered, themore efficient an operation can be completed, the lower the costs. Optimalityis thus typically in terms of finding the shortest complete coverage paththrough the field. In this paper, we present an O(n 2 ) algorithm for solvingthe optimal complete coverage problem on a field boundary with n sides. Thismulti-phase algorithm makes use of a plane-sweep algorithm to subdivide thefield into smaller, trapezoidal regions. The optimal paths through thesubregions are then calculated. Finally there is a merge phase where it isdetermined whether neighboring regions can be more efficiently covered if theywere merged together than if they were left separate.

1. 引言

2. 代价公式

3. 算法设计

4. 实验与结果

5. 结论

更多精彩文章请关注公众号：