Table of Contents
Robotino Voronoi Navigation
This tutorial is developed from the Robotino Navigation Series, an extension of the Robotino Operation series. It is recommended the reader familiarize themselves with that series before continuing
The completed project can be downloaded here robotino_control_voronoi.zip
Videos
The completed project in action.
Program Design
This program generates a Vornoi diagram using Fortune's algorithm. O'Sullivan encapsulated this algorithm in a c++ class and it can be downloaded here. This class returns the edges of the Voronoi diagram. In order to effectively navigate the diagram it was decided to represent the Voronoi diagram in the form of a linked tree. Pointers were used to point to each node (intersection) on the Voronoi diagram. A hashing table called a voroMap was designed to store each node. This way it is possible to link the nodes together efficiently. A goal and start node are found by searching for the voronoi node closest to the the goal or start.
A “weighted” breadth first search was used in order to find an optimal path through these nodes. We add each adjacent, non visited, node from our current working node to a queue. The queue consists of both the node to jump to and the total cost to jump to that node and is ordered by the cost of each jump. So, the jump that is the closest to the start (where distance is measured over the voronoi edges). Once we have added all adjacent nodes to the queue we change our current working node to the last node on the queue (the closest one) and repeat the process until the goal is found. We must also set the node we jumped from to the working nodes paren't node.
Once we have found a goal node we can jump across each parent node until we reach the start node. The start node is identifiable because it's parent node vector is of length 0. Each time we jump up a parent node we add it's location to an output vector that we can use as a list of waypoints later on.
Below is an example of the path found by the algorithm.
Now in order to have the robot navigate the Voronoi diagram all we need to do is have it traverse a vector of waypoints to the goal point.