The thesis considers the coverage path planning CPP problem. A coverage path of a region O is a path-curve P ⊆ Q, so that for every point x ∈ O the distance between x and P is at most d. We are looking for a coverage path whose length is as small as possible. We focus on polygonal regions and also require that P is a polygonal line. We use a divide-and-conquer approach, we first tesselate our region with smaller tiles, respective coverage paths of individual tiles are later combined in a global coverage path. We limit ourselves to two different tesselations, a tesselation using trapeze tiles and the Boustrophedon tesselation. We optimize the length of the coverage path using different orderings of tiles along a coverage path as well as changing the direction of our tesselation. Considering several families of polygons we can state that choosing Boustrophedon tesselation outperforms the trapeze one, and that the choice of the optimal direction of the tesselation is highly dependent on the ratio between size of O and required resolution d.
|
