

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

PSfrag replacements

## 3.1 Path Planning As An Optimization Problem: Search

Given a robot with k dof, a tra jectory of length l may be parameterized as a sequence of n = k l successive movements. A starting point q^ along with such a parameterized tra jectory implicitly dene a path and a nal conguration q^l in the conguration space.

For example, for a holonomic mobile robot the tra jectory (

1

; d1; 2; d2; :::l; dl) can be interpreted as making a 1 degree turn, moving straight d1
, making a 2 degree turn and so on. Given the starting conguration q^, this tra jectory leads to the nal conguration q^l

(see Figure 3).

Given a distance function d on the conguration space, if we nd a tra jectory such that it does not collide with any obstacles and such that the distance between q^l and the goal q^

is zero, then we have a solution to our path planning problem. Therefore, the path planning problem may be seen as a minimization problem where:

1. The search space is a space of suitably parameterized tra jectories, the tra jectory space.

2. The function to minimize is d(^ql ; q^) if the path is collision-free, and d(^qi ; q^) otherwise
(^qi being the rst collision point).2