The times they are a-changin’.
This post seems to be older than 14 years—a long time on the internet. It might be outdated.
Pick your favorite path planning approach and explain why you prefer it. Give an example of how it works. Identify its strengths and weaknesses, compared to other methods. Describe how you might apply it.
My favorite path planning approach is the visibility graph. I enjoy the visibility graph because it is one the primary methods I use to when performing my own human version of “path planning.” Last summer, I worked in a cubicle office space. There were two doors leading into the office space and the door to the restroom was more or less situated between the two doors. I was constantly trying to figure out which door required the least amount of steps. Although I didn’t know it at the time, I was basically creating a visibility graph and attempting to determine the shortest path, all in my head.
The Visibility Graph works by plotting straight line paths between the start, goal, and all the vertices of the all the objects in the workspace. The paths may cross over each other; however they may not intersect an object. There are several methods to actually calculate the visibility graph; however the most common method is the rotational plane sweep algorithm. Once constructed, the visibility graph can be searched for the shortest path from the start to the goal. Searching for a path usually requires weighting each segment of the line. Typically, the weight would just be its distance. However, other factors such as quality of terrain or amount of energy needed could also be taken into account.
One of the most obvious weaknesses of the visibility graph is that its complexity greatly increases as the number of objects increases. Additionally, many of the edges in the visibility graph are unneeded, such as when a vertex occurs in a convex area. There are methods to remove these additional edges; however, they will require additional computation efforts. If a workspace is expected to have many objects with convex vertices, it would probably be more efficient to use trapezoidal decomposition.
One of the benefits of the visibility graph, especially when compared to trapezoidal decomposition, is that the path planner does not care about the boundaries of the workspace. This could be especially helpful in situations where the edges of the workspace are complex. And let’s face it, looking at the visibility graph is pretty cool in and of itself.
7