<< Chapter < Page Chapter >> Page >

In the above figures, the configuration space is two dimensional because the robot has two degrees of freedom. If the heading of the robot mattered (i.e., if the robot were not circular), then a configuration would consist of a position and an orientation. The configuration space would therefore be three dimensional. If the robot had a rotatable joint, this would add another degree of freedom and another dimension to the C-space.

The path planning problem

The robotic path planning problem is, given a robot, a work space, and starting and goal configurations for the robot in the work space, find a collision-free path for the robot from the starting configuration to the goal, if one exists. Otherwise determine that no such path exists. An extensive introduction to the path planning problem and existing solutions may be found in .

Early approaches to path planning included:

  • Construction of visibility graphs between the vertices of C-space obstacles.
  • Decomposition of the C-space, effectively into subproblems.
  • Potential field methods, in which the goal exerts an attractive force on the robot, and the obstacles exert repulsive forces.
The first two methods scale poorly with the dimensionality of the C-space, since the complexity of the C-space affects their run time. Potential fields are subject to local minima. A robot moving down the potential gradient might get stuck in a potential well before it reaches the global potential minimum at the goal.

Sampling-based path planning

One solution to the scalability problem was to find methods whose run time does not depend on the dimensionality of the C-space, but on some other factor. This led to sampling-based path planning. Rather than making some explicit analysis of the whole C-space, sampling based planners built their representation of C-space by sampling random configurations and using a fast collision checker to determine whether they are in collision.

The basis of many modern sampling-based planners is the Probabilistic Roadmap Method (PRM) . Although the implementation details can become complicated, the basic algorithmic framework is quite straightforward and easy to understand.

    The prm algorithmic framework:

  • Randomly sample a large number of points in C-space, keeping any that are not in collision. This creates a point set in C-space.
  • Using a local planner , attempt to connect pairs of samples that are relatively close to each other by thoroughly sampling and collision checking configurations between them. This creates a graph data structure called a roadmap.
  • To query the roadmap, first attempt to connect the start and goal configurations to the existing graph. If that is successful, search the graph for a path from start to goal using any standard graph search method (often A*).
PRM implementations vary in terms of how the points are sampled--remember that random does not mean uniformly at random--as well as in how the local planner attempts to connect nearby configurations.

Configuration space for path planning

A configuration space in which we wish to build a Probabilistic Roadmap.

Sampling

Random points in the configuration space are tested for collision with obstacles. Collision-free points are kept.

Connection

The roadmap is constructed by connecting nearby samples. Many collision checks are made along each edge to ensure that the connection is legitimate.

Query

The start and goal configurations are connected to their nearest neighbors in the roadmap. A graph search is then made to find the shortest path in the roadmap from start to goal.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Geometric methods in structural computational biology. OpenStax CNX. Jun 11, 2007 Download for free at http://cnx.org/content/col10344/1.6
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Geometric methods in structural computational biology' conversation and receive update notifications?

Ask