

![0_image_0.png](0_image_0.png)

## 2.1 Global Approaches

Global approaches are classically divided into two main classes: (i) retraction methods, and
(ii) decomposition methods. In the retraction methods, one tries to reduce the dimension of the initial problem by recursively considering sub-manifolds of the configuration space. In the decomposition methods, one tries to characterize the regions of the configuration space that are free of obstacles.  Both methods end up with a classical graph search over a discrete space. In principle, these methods are complete because they will find a path if one exists and will still terminate in a finite time if a path does not exist. Unfortunately, computing the retraction or the decomposition graph is an NP -complete problem: the complexity of this task grows exponentially as the number of DOF increases (Canny, 1988). Consequently, these planners are used only for robots having a limited number (three or four) of DOF. In addition, they are slow and can only be used off-line: the planner is invoked with a model of the environment, it produces a plan that is passed to the robot controller which, in turn, executes it. In general, the time necessary to achieve this is not short enough to allow the robot to move in a dynamic environment.

## 2.2  Path Planning With Local Planners

One way to combat the complexity of the problem is to trade completeness against performance. To do this, the local planners are guided by the gradient of a cost function (usually the Euclidean distance to the goal) and take into account the constraints introduced by the obstacles to avoid them (Faverjon & Tournassoud, 1987). Since the path planning problem is NP-complete, knowing the cost function, it is always possible to design a deceptive environment where the method will get trapped in a local minimum. However, these methods are useful in many industrial applications because they can deal with complex robots and