Using Voronoi Tessellations to Find Safe Paths in Autonomous Robot Navigation
Title: Using Voronoi Tessellations to Find Safe Paths in Autonomous Robot Navigation
Student: Vanessa Moreno
Advisor: Dr. Hoa Nguyen
Abstract: Autonomous robots often have to navigate through environments containing obstacles. Mathematics can be used to find a safe path from a starting point to the desired destination. Voronoi tessellations provide one way of partitioning the robot’s environment into regions. The Voronoi tessellation gives us information about the neighborhood of the current robot position, such as whether an obstacle is present, and how far it is to the destination. Each obstacle is represented by a rectangle that bounds the obstacle. Using the set of bounding rectangles, the initial location, the destination, and a set of underlying grid points, we construct a standard Euclidian Voronoi tessellation. To decide how to move from the current point to the desired neighbor we utilize the scoring function from the A* algorithm which is widely used in path planning. Given two complicated scenarios we are able to find safe and feasible paths for the robot. More benchmark problems will be explored as we refine our algorithm.