Carnegie Mellon University

The Robotics Institute.

Robotic  Motion Planning, 16735: Homework 5

Visibility Graph in R²

 

 Star Algorithm to generate C-space obstacles

 

I implemented the star algorithm to generate c-space obstacle. Note that the workspace is unbounded.

Algorithm details:

 

             -The right most  point on the robot is taken as the reference point.

             -Generates the inward normals of the robot edges and outward normals of the obstacles

             -Stores the angles associated with these normals in an array and sorts them.

             -Picks the first C-space obstacle vertex as the left most obstacle vertex

             -Places the robot reference point at this obstacle vertex and this is the first C-space obstacle vertex

             -To generate the next vertex adds a vector whose direction defined by the (angle - pi/2) of the element in the sorted array                                  associated with the vertex.

             -Continues the above by moving along the sorted list after the initial element until all the elements in the sorted list have been                                        used.

 

 

Visibility Graph

 

The visibility graph is created by checking for every vertex including the start and goal points for the existence of a line of sight to every other vertex. If a vertex of the c-space obstacle happens to be within another obstacle it is not included in the vertex list. The line of sight is decided by checking for intersections with other obstacles along the line segment connecting the two vertices. The obstacles form an open set and the edges are included in the visibility graph if they satisfy the conditions. If a line of sight exists between two vertices (i^th vertex on the j^th obstacle and m verex on n^th obstacle) the elements in the connectivity matrix (V), V_ijmn & V_mnij is assigned a value 1.

 

 

 A* search in the Visibility Graph

All the vertices are first numbered as nodes. The start node is first included in the open list and then popped and put in the closed set. The connected nodes are found using the connectivity matrix, these are included in the open set A* continues as in the previous assignment. The heuristic used is the Euclidean norm between the node and the goal node. The visibility graph guarantees finding paths of minimal length and this can be verified from the examples shown above. A* fails when there is no element in the open set, and this happens when the goal lies in a different connected region in the configuration space as in fig 4 above.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 1– Success

Fig. 2-Success

Fig. 3-Success

Fig. 4-Failure

Note*- The red line indicates the path found using A* in the  visibility graphs