A Short Guide to Robot Path Planning
Editors note: For my Advanced Robot Control midterm, I had to write a report answering four questions related to the class. For your reading pleasure, I now present the fruits of my labor. Note, super technical content to follow. Also note, this post is paginated. You can also download the PDF.
In Chapters 2 through 7, Choset has presented a number of different approaches to path planning. Explain in your own words the progression from Chapter 2 to 7. Include brief (synopsis) explanations of each approach (i.e., the main topic of each chapter).
Chapter 2 covers the two bug algorithms, Bug 1 and Bug 2. The Bug 1 algorithm is perhaps one of the most basic of navigating algorithms. The robot begins at the start and proceeds toward the goal until an obstacle is encountered. Once an obstacle is encountered, the robot will completely circumnavigate the obstacle before proceeding toward from the point on the perimeter that has the shortest distance to the goal.
The Bug 2 algorithm is very similar to the Bug 1 algorithm. The primary difference from Bug 1 is that an imaginary line, the M-line, is draw between the start and goal. When the robot encounters an obstacle, it will circumnavigate the obstacle until it reaches the M-line. Once it reaches the M-line, it will start moving toward the goal again; it does not completely circumnavigate the obstacle.
The primary benefits of Bug 1 and Bug 2 is that very little information is needed: a starting point, goal, and a series of touch sensors to determine when the robot runs into an obstacle.
A more advanced version of Bug 2 is the Tangent Bug. Tangent Bug utilizes a sensor of some range from zero to infinity to detect obstacles. When an obstacle is detected, the robot will start moving around the obstacle. The robot will continue its motion-to-goal routine as soon as it has cleared the obstacle.
In order to describe more complicated path planners, we need to be able to specify the position of the robot and the space it occupies. This is known as the configuration space and is the primary topic of chapter two. We used the new idea of configuration space to develop a set of equations that allow us describe the position of multi-joint planar arms. We extended the equations we used to define the movement of planar arms to define points in both R2 and R3. These equations allow us to define the position and orientation of a single point, as well as one point relative to another.
With our new ability to describe robots in a workspace, we can now begin working with more complicate path planning techniques. Path planning is quite different from the previous navigation algorithms we discussed, such as Bug 1, because path planning requires foreknowledge of the obstacles before the robot begins movement. Chapter four starts with a brief discussion on gradients. Gradients are a well studied mathematical function in undergraduate engineering university, which makes them a great introduction for more complex path planning methods. Gradients work by changing the repulsive potential as a robot gets closer to an obstacle. The start point is given a medium gradient potential, the end point is given a low gradient potential, and the obstacles are given high gradient potentials. All the robot needs to do is “roll down the hill.”
The Brushfire Algorithm is a discrete version of the aforementioned gradient algorithm and involves the use of a grid to determine the potential of cells. A variation on the Brushfire Algorithm is the Wave-Front Planner.
The Wave-Front Planner uses a grid, just like the Brushfire Algorithm, and assigns a “1” to each cell that has an obstacle (or part of an obstacle). The start point is labeled “2” and the “wave” propagates from that point. Each adjacent cell, if empty, is given an incrementally higher number until all the cells have a number. If the goal has a number in its cell, the goal is reachable in that many moves minus one. Adjacency can be computed using either four-point connectivity (where only the north, south, east, and west cells are considered adjacent) or eight-point connectivity (where north, south, east, west, and the diagonal cells are considered adjacent).
Sphere space and Star space are essentially extensions of the generalized potential path planning method with one critical difference: they only have one local minimum. Having one local minimum is a desirable quality as it greatly aids in path planning and avoiding dead ends.
Chapter five introduces roadmaps, which is effectively a way to break up the workspace into distinct stages or paths. The Visibility Graph plots 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. Once constructed, the visibility graph can be searched for the shortest path from the start to the goal.
The Generalized Voronoi Diagram extends the idea of the distinct paths by drawing equidistant “roads” between obstacles and the boundaries of the workspace. A similar technique to the GVD is the Silhouette Method, which works by determining the critical points of obstacles within the workspace. A tangent line extends from each critical point, and around the workspace edge. The path from the start to the goal “snaps” to these paths.
Trapezoidal Decomposition, which is the start of chapter six, extends the concept of the Silhouette Method. However, the obstacles (and workspace) must be represented as trapezoids. A vertical extension marks each vertex, separating the workspace into cells. The cells are mapped from the start to goal using an adjacency graph. The path planner plans a path by connecting the midpoints of the vertical extensions. Morse Cell and Boustrophedon Decomposition follow the same concept as Trapezoidal Decomposition. However, the goal in Morse Cell and Boustrophedon is path coverage rather than path planning.
Path coverage, which seeks to optimize the coverage of the workspace, leads into visibility-based decompositions for pursuit and evasion, which deals with how a pursuer attempts to capture prey and how the prey attempts to evade the predator. Specifically discussing how to clear rooms to make them “uncontaminated” and how to determine the number of predators that are required to check a system based on the number of edges in the workspace.
As this point, the path planning algorithms are becoming fairly complex and computationally intensive. So far, our examples have been using small workspaces with only a handful of obstacles. As the workspace size and number of obstacles increase, the time required to find a solution also increases, usually exponentially. Sampling-based Algorithms work by using a best-guess and check method. A path is calculated and then checked to see if it collides with any obstacles. Specific types of planners include Probabilistic Roadmaps (PRM), Randomized Path Planner (RPP), Expanisve-Spaes Trees (EST), Rapidly-exploring Random Trees (RRT), and Single-query, Bi-directional, Lazy collision-checking (SBL). In all examples of sample-based path planning, the chances of finding a successfully path approach zero as the number of samples increase.
7
