Chris Thorne
Programming Assignment 2
The m-file is constructed so the user can dwell at each major result, i.e. it will dwell after calculating and displaying the reflex vertices for each obstacle. The user only needs to click anywhere in the screen to continue on to the next step.
Method
The reflex vertices are calculated using the left-turn predicate. Once the reflex vertices are found, they are used to construct the bitangent edges. To do this, a line is constructed between each pair of reflex vertices and then checked for critical intersection with obstacle boundaries. If there is an intersection with a boundary, the edge is not included in the list of bitangent edges. Due to the general nature of this bitangent edge check, the initial and goal configuration points can be added to the reflex vertex list, automatically constructing mutually visible edges with these points. Lastly, the Dijkstra algorithm is implemented to find the shortest path in the roadmap constructed from the bitangent edges. The cost of each bitangent edge in this case is its length.
Example runs
Here are some example runs:
given geometry and configurations:
trial 1
trial 2
trial 3
trial 4
trial 5
trial 6
Programming assignment 1
To run the m-file, follow the directions on the screen. A typical run of the m-file will proceed as follows:
startup screen
step 1
step 2
step 3
step 4
step 5
step 6
Overview of method
The robot is a nonconvex polygon comprising two convex polygons. The vertices for each convex polygon are stored in a cell array. Each cell pertains to a convex region (2 cells).
The obstacle is created by the user, clicking points to add vertices. The user can enter as many points as they want. The user is then asked to select vertices to create the convex regions of the obstacle. The user clicks outside of the environment every time they wish to start a new convex region, or wish to stop entering regions.
At this point, the randomly configured final robot is constructed. The points of the convex regions of the robot are checked for collision. This is done by constructing the inward facing norms to all of the convex obstacle polygons. The vector from a point on that line to the robot vertex being considered is dotted with the norm. If this dot product is positive, the robot vertex is on the obstacle defined side for that line. If the robot vertex has positive dot products with all the lines for a given convex obstacle region, the vertex is inside that region and a collision has occured. This is done with both convex regions of the robot and all convex regions of the obstacle. This information is used to determine a collision.
The results for runs with convex and non convex obstacles can be seen below:
convex obstacle no collision
nonconvex collision
nonconvex no collision
nonconvex collision2