A continuous path planning approach on Voronoi diagrams for robotics and manufacturing applications

摘要

Coverage of an area is required for a large variety of robotics and manufacturing applications, such as environment monitoring, home cleaning, search and rescue operations, machining, delivery, additive manufacturing and even for 3D terrain reconstruction. In this work, we present highly flexible algorithms that can be used for coverage and graph traversal. Although our methods take advantage of variable-sized Voronoi cells, by which regular, irregular and complex geometries can be easily composed, it is not limited to Voronoi diagrams and can be applied for any connected graph. After the construction of the Voronoi diagram, an Eulerian graph is generated. Then, three algorithms are elaborated for the traversal of it. Two of those algorithms traverse the graph continuously, leading to Eulerian cycles. On the other hand, one algorithm requires switching positions from time to time, which we callfast travel. Additionally, we describe the phenomenon of traversing the same edge twice in a row, i.e.,uturn, and draw a conclusion to emphasize the importance of this specific problem.