Michael Edelson
Homework 5
Visibility Graphs:
There are really just a few distinct parts in this problem. First
is creating the configuration-space obstacles. This had to be re-done
from previous labs as previously I was using a pixel-based input
method (took in a jpeg of the world) and now I was using a
vector-based input (vertices of each obstacle and the robot). The
objects were given a buffer zone using the star algorithm from
class:
I assume that the obstacles' vertices are all entered in
the same order, starting from the upper left and going
counter-clockwise (CCW chosen because it makes the normal face
upwards).
Starting at the highest-indexed vertex and proceeding downwards, I check the angle of each edge
(atan2(y1-y2,x1-x2)) (numbered that way since we're decreasing order)
and add a node to a priority queue, sorted by angle, where angle is the given obstacle side's angle -90. (normal facing outwards)
The elements have the relative position of the vertices as well as world coordinates.
Similarly, the queue has the robot's edges added, only with angle+ 90 (normal facing inwards)
Then, while the queue has elements, I pop the queue and draw the line. The first obstacle point is the anchor point to the real world.
The start and goal points were added to the object array as degenerate objects with 1 vertex.
Visibility was easy to solve for since everything was vectorized. First a check of line intersection between the line connecting the possible visibility and every line on every obstacle was made. If, using a parameterized version of the edge of the obstacle yielded a t value outside of the line segment, the obstacle side was deemed to be out of line of sight. This has some problems when obstacles overlap, so I decided this was not allowed. Buffer zones can overlap obstacles, however, since I also check just the obstacle edges in addition to obstacle + buffer edges.
Each obstacle vertex was then tested against every other vertex. When a pair were within line of sight, both obstacles were updated with this knowledge, and thus the opposite direction could be skipped. Adjacent vertices were added separately (if they weren't inside another obstacle) since that way the floating point error wouldn't stop those edges from existing in the graph.
To search through this graph, I used Dijkstra's search (from the lecture slides again). The open set was initialized to the goal. Then I used the graph formed from the visibility tests run on each obstacle.
Pop the lowest costs item off of the open set
Put all of its links into the open set iff they don't exist with a lower cost in in the open set, or exist in the closed set. Each has a back pointer to the popped vertex
Put the popped item in the closed set
Repeat until the goal is popped or the open set is empty
If the goal was never popped, there is no path.
Then the backpointers were followed and the lines changed to green instead of red in the visual. If I were to do this on a robot, I would consider using Dijkstra's backwards (from goal to start) so that the backpointers all point in the direction of travel. This makes following the path a bit easier.
Coloring:
Blue-Obstacle
Magenta-Expanded part of obstacle
Yellow- Robot at start
Red- Vertices within visibility
Green- Chosen shortest path
