Carnegie Mellon University

The Robotics Institute.

Robotic  Motion Planning, 16735: Homework 6

Voronoi Diagram using iterative technique

Fig. 1– Success

Fig. 2-Success

 

Implementation and Algorithm

 

I used a sensor of infinite range. Using this I kept track of the first three closest points on the boundary and obstacles to the robots.

To start off, the robot initially moves in a direction away from the closest obstacle  until it reaches a double equidistant point. It then finds the direction to drive by taking the normal to the line joining the two closest points to the robots. The robot travels along this direction until it finds a triple equidistant point. It checks for triple equidistance by verifying the 3 three closest points to the robot are infact at the same distance.

On reaching a triple equidistant point it labels the point as a node and defines three direction at the node. Each direction pairs two of the three closest points on the node. Since there is an ambiguity in the direction defined by two points, the robot takes a small step forward and verifies that the value of the third closest distance has increased. If the value decreases the robot decides to move in the opposite direction.

It continues this process until all the directions at each of the node have been explored.

 

 

 

 

 

 

Fig. 3-Success