Home
About Us
People
Visitors
Groups
Projects
Publications
Software
Courses
Laboratory
Seminars
Students
Matlab
Alumni
Links
 
[Advanced Control Systems Group] [Autonomous Mobile Robotics Group]





Path Planning and Motion Control


Dynamic Window for Obstacle Avoidance

Dynamic Window for Obstacle Avoidance


The dynamic window approach is a velocity space based local reactive avoidance technique where search for commands controlling the robot is carried out directly in the space of velocities. Trajectory of a robot can be described by a sequence of circular and straight line arcs.

The search space is reduced by the kinematic and dynamic constraints of the robot to a certain span of velocities around the current velocity vector (vc,$ \omega_{{c}}^{}$) that can be reached within the next time interval. The dynamic window Vd containing the possible reachable velocities is defined as:

Vd = $\displaystyle \left\lbrace\vphantom{ (v,\omega) \mid\begin{array}{r} v\in \left...
...omega}_b\Delta t, \omega_{c}+\dot{\omega}_a\Delta t\right] \end{array} }\right.$(v,$\displaystyle \omega$) | $\displaystyle \begin{array}{r} v\in \left[ v_{c}-\dot{v}_b\Delta t, v_{c}+\dot{...
...c}-\dot{\omega}_b\Delta t, \omega_{c}+\dot{\omega}_a\Delta t\right] \end{array}$$\displaystyle \left.\vphantom{ (v,\omega) \mid\begin{array}{r} v\in \left[ v_{c...
..._b\Delta t, \omega_{c}+\dot{\omega}_a\Delta t\right] \end{array} }\right\rbrace$,
(2)

where accelerations $ \dot{v}_{a}^{}$ and $ \dot{\omega}_{a}^{}$ are maximal translational and rotational accelerations exertable by the motors and $ \dot{{v}}_{{b}}^{}$ and $ \dot{{\omega}}_{{b}}^{}$ are maximal translational and rotational breakage decelerations.

A velocity touples (v,$ \omega$) is considered safe if the robot is able to stop along the trajectory defined by (v,$ \omega$) before hitting any object that may be encountered along that path. The set Va of admissible velocities can be determined according to:

Va = $\displaystyle \left\lbrace\vphantom{ v, \omega \le \sqrt{2 \rho_{min}(v,\omega)\dot{v}_{b}} \wedge \sqrt{2 \rho_{min}(v,\omega) \dot{\omega}_{b}} }\right.$v,$\displaystyle \omega$$\displaystyle \le$$\displaystyle \sqrt{{2 \rho_{min}(v,\omega)\dot{v}_{b}}}$ $\displaystyle \wedge$ $\displaystyle \sqrt{{2 \rho_{min}(v,\omega) \dot{\omega}_{b}}}$$\displaystyle \left.\vphantom{ v, \omega \le \sqrt{2 \rho_{min}(v,\omega)\dot{v}_{b}} \wedge \sqrt{2 \rho_{min}(v,\omega) \dot{\omega}_{b}} }\right\rbrace$, (3)

where the term $ \rho_{{min}}^{}$(v,$ \omega$) represents the distance to the closest obstacle on the corresponding curvature.

If we denote the initial search space of velocities that are limited by the maximum translational and rotational velocity value as Vs the resulting search space can be described as the intersection of the restricted areas:

Vr = Vs $\displaystyle \cap$ Va $\displaystyle \cap$ Vd. (4)

Search space Vr can be expressed as the Cartesian product of two search spaces:

Vr = Vrv x Vr$\scriptstyle \omega$, (5)

where Vrv is translational velocity search space and Vr$\scriptstyle \omega$ rotational velocity search space. In Fig. 4 an example of such resulting space over the discrete set of velocities is shown.
Figure 4: Discrete search space generated by dynamic window.
\begin{figure}\centering\psfrag{miv}{\small{$v_c-\dot{v}_b \Delta t$}}\psfr...
...bb=33 185 543 605, clip=, width=0.49\textwidth}%{DWsearchspace.eps}
\end{figure}
We have chosen dimension of Vrv to be 5 and dimension of Vr$\scriptstyle \omega$ to be 7, therefore, number of velocity touples is 35. In this work, dimensions are chosen such that computational cost is acceptable. Each velocity touple (v,$ \omega$) uniquely determines a circular trajectory whose radius is calculated as r = $ {\dfrac{{v}}{{\omega}}}$ and a sequence of such velocity vectors forms a curvature that is approximated by a sequence of circular arcs. Higher dimension of Vr$\scriptstyle \omega$ than of Vrv is chosen with the purpose of denser spatial coverage with the possible trajectories (see Fig. 5). Translation velocities influent on the lengths of trajectories in given time and since in navigation higher velocities are prefered, the dimension of Vrv is less significant. The dynamic window is centred around the current velocity (vc,$ \omega_{{c}}^{}$) and the extensions of it depend on the accelerations that can be exerted. All curvatures outside the dynamic window cannot be reached within the next time interval and thus are not considered for the obstacle avoidance.
Figure 5: A snapshot of possible robot trajectories
\begin{figure}\centering\psfrag{aa }{\small{$(v_c-\dot{v}_b \Delta t, \omega_c...
...bb=48 185 544 583, clip=, width=0.49\textwidth}%{DWsearchspace.eps}
\end{figure}

In order to generate a trajectory to a given goal point for the next n time intervals it has to be determined which velocities (vi,$ \omega_{{i}}^{}$) for each of the n intervals must be executed. Therefore, the search space for these vectors is exponential in the number of the considered intervals. To make the search for velocities feasible and appropriate for fast reactive response, the dynamic window approach considers exclusively the first time interval to choose the optimal velocity vector and assumes that the velocities in the remaining n - 1 time intervals are constant. The reduced search space is two-dimensional over the discrete set of velocity touple (v,$ \omega$) and thus feasible in polynomial time search sense. The search is repeated after each time interval and the velocities stay automatically constant if no new commands are given. A snapshot of possible robot trajectories at given time and local obstacle configuration determined by resulting velocity space Vr assuming for a next n time intervals to be constant is depicted in Fig. 5.

The local obstacle configuration can be taken into account by calculating the distance until collision along a certain circular trajectory. Alternatively, the time until collision may be used, which takes velocity v of the robot more directly into account. The clearance objective measure $ \vartheta_{{clear}}^{}$ describes how close is a chosen trajectory to potential obstacles and is considered only if the basic admissibility condition for the particular trajectory is fulfilled (i.e. the breakage distance is smaller than the closest object on the trajectory):

$\displaystyle \vartheta_{{clear}}^{}$(v,$\displaystyle \omega$) = $\displaystyle \left\lbrace\vphantom{ \begin{array}{r@{\quad:\quad}l} 0 & t_{col...
...x}-T_{b}} & T_{b}<t_{col}<T_{max},   1 & t_{col}>T_{max} \end{array} }\right.$$\displaystyle \begin{array}{r@{\quad:\quad}l} 0 & t_{col} \le T_{b}   \frac{t...
...b}}{T_{max}-T_{b}} & T_{b}<t_{col}<T_{max},   1 & t_{col}>T_{max} \end{array}$ (6)

where Tb(v,$ \omega$) = max($ {\frac{{v}}{{\dot{v}_{b}}}}$,$ {\frac{{\omega}}{{\dot{\omega}_{b}}}}$) is the breakage time along a certain trajectory determined by (v,$ \omega$) and tcol(v,$ \omega$) = $ {\frac{{\rho_{min}(v,\omega)}}{{v}}}$,   is the time until collision with the closest obstacle on the trajectory. It has to be noted that the collision calculation is not based on the contact between an object and the robot contour itself but rather between an object and an enlarged safety contour margin around the robot. It is called speed dependent side clearance SCv and is used for the translational velocity. This side clearance grows linearly with v and the effect of it is that at higher speeds the free-space areas (i.e. corridors, passages between objects) appear narrower to the robot. Tmax = $ {\frac{{s_l}}{{v_{max}}}}$ is the admissible collision time and it represents the temporal limit above which a trajectory is considered void of obstacles. Its value depends on the maximum translational velocity of the robot vmax and the look-ahead distance of the sensors sl used.

The velocity maximizing a certain objective function $ \Gamma$(v,$ \omega$) is chosen from the remaining set of velocities Vr. It is expressed as weighted sum of objective measures for clearance $ \vartheta_{{clear}}^{}$, target heading $ \vartheta_{{head}}^{}$ and linear velocity $ \vartheta_{{vel}}^{}$:

$\displaystyle \Gamma$(v,$\displaystyle \omega$) = $\displaystyle \lambda_{{clear}}^{}$$\displaystyle \vartheta_{{clear}}^{}$ + $\displaystyle \lambda_{{head}}^{}$$\displaystyle \vartheta_{{head}}^{}$ + $\displaystyle \lambda_{{vel}}^{}$$\displaystyle \vartheta_{{vel}}^{}$. (7)

Linear velocity measure $ \vartheta_{{vel}}^{}$ is chosen such that higher linear velocities are preferred, and target heading measure $ \vartheta_{{head}}^{}$ considers achieving heading towards global goal position. This approach is susceptible to local minima without further global path information. If connectivity of free-space toward goal position is considered, local minima can be avoided. Although, the problem of determing weighting factors $ \lambda_{{clear}}^{}$, $ \lambda_{{head}}^{}$ and $ \lambda_{{vel}}^{}$ that influence the net performance of the robot motion significantly remains unsolved.



Next: Integration of Path Planning and Dynamic Window Up: Path Planning and Motion Control Previous: Path Planning

 

Home
About Us
People
Visitors
Groups
Projects
Publications
Software
Courses
Laboratory
Seminars
Students
Matlab
Alumni
Links