3. Different Approaches

There are several approaches to the problem of motion planning most of which fall into one of the following categories (hybrid approaches also exist):

cell decomposition

The configuration space is split into disjoint subsets (cells) which are represented in a graph. Nodes correspond to cells and edges connect nodes if the respective cells are connected. Usually this approach is only appropriate in low dimensional C-spaces where "natural" cell boundaries exist (e.g. walls in 3D space) and when the robot is very simple.

potential fields

The idea behind this approach is simple. When an electron (having negative charge) is put into an electric field it will be attracted by a positive charge (the goal) and repelled by other negative charges (obstacles). Starting at a certain point it will move towards the goal, driven by the force exerted by the electric field. A robot's configuration is just a point in the configuration space C, just like the electron is just a point in our natural 3D space.

So if a mathematical potential field function can be constructed that adequately models qgoal and the obstacles just as the electric field models the distribution of charges, then the virtual forces exerted on a virtual electron positioned in the point qstart can be computed. This leads to a path from qstart to qgoal that avoids the obstacles.

This method has been successfully applied to many path planning problems. However, with increasing number of dof and complexity of the obstacles, finding an appropriate potential field function becomes increasingly difficult.


Roadmap-based planners are somewhat similar to those using cell decomposition. However, instead of using a graph with nodes that describe subsets of C-space, roadmap graphs use nodes that represent individual configurations. This makes them even easier to use than cell decomposition graphs. There are many different ways to construct roadmaps manually and automatically. The main drawback of roadmap planners is that because every node in the graph contains only little information they often require much more space than other methods to capture the whole Cfree adequately.

A roadmap-based planner finds a path connecting 2 configurations by looking for a path within the roadmap. This path is a sequence of nodes from Cfree used as waypoints. These waypoints are usually not a complete path for the robot because they are too far apart and intermediate configurations are required. This situation is comparable to driving directions like "take the first street to the left, then the second one right, then the first one left". These are just waypoints. A car can not teleport from one to the other, it has to drive along the streets that connect them. This corresponds to the edges of the graph. These edges however are usually reduced to the information q is connected with q'. The actual connection, i.e. the intermediate configurations that a robot has to go through are usually not stored explicitly. They are dynamically regenerated as the robot goes from one waypoint to the next. This function is performed by a so-called local planner which is a sub-planner within the roadmap planner.