# 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.