A Continuous Path Planning and Updating Algorithm Based on Voronoi Diagrams

Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Graduate School of Natural and Applied Sciences, Turkey

Approval Date: 2020

Thesis Language: English


Consultant: Ulaş Yaman


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 a highly flexible algorithm that can be used for coverage and graph traversal. In addition to being applicable to diverse types of engineering problems, proposed method is advantageous to other algorithms, as it never turns around and traverses the edge it recently traversed. Although the method takes 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. Furthermore, path planning algorithm can update the path to deal with changes in the graph. In some applications, like 3D printing, path planning must be done for many instances. However, our algorithm calculates the path at the first layer, and performs only necessary changes at the subsequent layers, instead of calculating the whole path from scratch. This update mechanism makes the method very efficient as it is demonstrated with several test cases. In addition to the path planning algorithm, a G-code file encryption method is introduced, size of G-code files can be greatly reduced. As automation and robotics integrate into numerous areas everyday, proposed methods can be useful for many applications.