Michael Edelson
Homework7
For my PRM planner, I used the simplest local planner I could think of. This was linear interpolation of both angles and locations between two states. Fifty states (including start and end) were taken into consideration and checked for obstacle collision.
Obstacle collision was performed by checking if a point was above or below a line (or, for vertical lines, left vs right). Obstacles are defined in a clockwise manner, so the inside is easily figured out for any line on the obstacle. By comparing the starting and ending x and y coordinates, it is simple to see which side of the line is a collision.
Connecting neighbors is done based on the local planner. Two robot states which are close both in x,y coordinates and joint angles are tested to see if a path exists between them. At each sample between two robot states, it is checked for obstacle collisions. If for all the samples it is obstacle-free, the two neighbors are connected in the graph.
For following the roadmap, a simple depth-first search is done from start to end, and the first path to the end is chosen. My A* didn’t quite work on the path, so I just let it be horribly inefficient for now. Therefore, as shown in both examples, the robot does not even almost follow the most direct path there, even though there are enough intermediate states to do so.
If no path is found, more states are thrown on to the world and then they are also connected to the roadmap.
In the pictures and videos, the obstacles are outlined in blue, the robot states that do not intersect obstacles are in green, and the robot states chosen for the path are in red. The videos show the motion of the robot between these red states.
One Obstacle:
Three Obstacles:
Video of Two Obstacles (Three obstacles – one obstacle):