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


Path Planning and Dynamic Window Integration

Integration of Path Planning and Dynamic Window


A criterion for DW and FD* integration is proposed, which makes comparison of the current possible robot trajectories and the geometric global path by applying the global objective function $ \Gamma$(v,$ \omega$) expressed as weighted sum of objective measures for clearance $ \vartheta_{{clear}}^{}$(v,$ \omega$) and path alignment $ \vartheta_{{path}}^{}$(v,$ \omega$) :

$\displaystyle \Gamma$(v,$\displaystyle \omega$) = $\displaystyle \lambda$$\displaystyle \vartheta_{{clear}}^{}$ + (1 - $\displaystyle \lambda$)$\displaystyle \vartheta_{{path}}^{}$, (8)

where $ \lambda$ is the weighting factor. Path alignment measure relates possible robot trajectories with the local geometric path configuration and thus improves the restrictions on the translational velocity and also determines the local target heading direction. This restriction of the linear velocity is the key element since the velocity is adaptive according to the local path configuration. The path alignment measure $ \vartheta_{{path}}^{}$ for a robot trajectory is defined according to the following expression:

$\displaystyle \vartheta_{{path}}^{}$(v,$\displaystyle \omega$) = 1 - $\displaystyle {\frac{{\sum_{i=1}^{N_{t}} \sum_{j=1}^{N_{p}} j d_{ij} - D_{min}}}{{D_{max} - D_{min}}}}$. (9)

A trajectory generated by DW, which is a circular arc, is represented by a discrete set of points Nt . Trajectory length Lt is set according to the velocity tuple (v,$ \omega$) which characterize current trajectory and the time look-ahead Tmax beyond which all trajectories are considered clear of obstacles Lt(v,$ \omega$) = vTmax . Np is a set of points on the so called effective path and dij is the Euclidean distance between the i -th point on the trajectory and j -th point on the effective path. The number of points on both curve is fixed. When choosing these numbers one must consider computation complexity in one hand and a quality of approximation of the curves in another hand. In our work, we have assumed number of Np = 10 points to be valid approximation of straight line segment and number of Nt = 30 points to be valid approximation of circular trajectories (see Fig. 6).
Figure 6: The effective path and robot trajectory comparison
\begin{figure}\centering
\epsfig{file=trislovac.eps, bb=47 228 543 541, clip=, width=0.49\textwidth}
\end{figure}
When the number of points is fixed, resolution of the curves depends only on the velocities: higher velocities mean more rarely distributed points. The limit values Dmin = $ \min_{{(v,\omega)}}^{}$$ \left\lbrace\vphantom{ \sum_{i=1}^{N_{t}} \sum_{j=1}^{N_{p}} j d_{ij} }\right.$$ \sum_{{i=1}}^{{N_{t}}}$$ \sum_{{j=1}}^{{N_{p}}}$jdij$ \left.\vphantom{ \sum_{i=1}^{N_{t}} \sum_{j=1}^{N_{p}} j d_{ij} }\right\rbrace$ and Dmax = $ \max_{{(v,\omega)}}^{}$$ \left\lbrace\vphantom{ \sum_{i=1}^{N_{t}} \sum_{j=1}^{N_{p}} j d_{ij} }\right.$$ \sum_{{i=1}}^{{N_{t}}}$$ \sum_{{j=1}}^{{N_{p}}}$jdij$ \left.\vphantom{ \sum_{i=1}^{N_{t}} \sum_{j=1}^{N_{p}} j d_{ij} }\right\rbrace$ are used for normalization along all possible robot trajectories. The index factor j that weights the distance contributions is introduced to penalize more points at the end of the trajectories which define the trajectory deviation from the global path more than the starting points on different trajectories, since they all start from the same robot position.

The so called effective path is the straight line segment connecting the current robot position and a reference point on the path. Its orientation determines the current reference orientation of the robot in relation to the local path configuration affecting the rotational velocity of the robot $ \omega_{{ref}}^{}$ and its length determines what the optimal translational velocity vref should be. Reference point on the path has assigned constant time Tmax (admissible collision time) as a fixed travelled time from the current robot position to the reference point.

The nominal reference point position is at the point immediately before the second path direction change (path direction changes are multiples of 45o ), as can be seen in Fig. 7.

Figure 7: Determing the nominal reference point position on the global geometric path
\begin{figure}\centering
\epsfig{file=refpointslovac2.eps, bb=49 211 543 561, clip=, width=0.49\textwidth}
\end{figure}
This assumption is based on the fact that detecting the first path direction change which altered the path direction for $ \pm$45o starting from the robot position is not enough to determine the tendency of the path change thereafter. The second path direction change then determines whether the path direction changed back to its original direction or continued changing which signifies a stronger curvature change and therefore gives a good local curve tendency information.

Due to dynamic constraints of the robot, a distance between the reference point position on global path and robot current position R(vc) is upperbounded by a maximum translational velocity vc + $ \dot{{v}}_{a}^{}$$ \Delta$t , that can be accessed in the next time interval $ \Delta$t for the current robot velocity vector ( vc,$ \omega_{{c}}^{}$) , and the time look-ahead Tmax (see Fig. 8):

Rmax(vc) = (vc + $\displaystyle \dot{{v}}_{a}^{}$$\displaystyle \Delta$t)Tmax. (10)

Therefore, its length is adaptively increased as the robot speeds up or vice-versa.
Figure 8: Determing the upperbounded reference point position on the global geometric path
\begin{figure}\centering\psfrag{jj}{\small{$R_{max}(v_{c})=(v_{c}+\dot{v}_a\De...
...sfig{file=jjjj.eps, bb=49 228 543 541, clip=, width=0.49\textwidth}
\end{figure}

If the path direction change is detected in the immediate vicinity of the robot (for instance, the grid-cell next to the robot position), its direction change impact on the robot is not significant. Therefore, a distance between the reference point position on global path and robot current position is lowerbounded with Rmin that filters out the insignificant path direction changes that would slow down the robot but would not change its global position much (see Fig. 9).

Figure 9: Determing the lowerbounded reference point position on the global geometric path
\begin{figure}\centering\psfrag{ii}{\small{$R_{min}=\frac{1}{2}\dot{v}_{b}T^{2...
...sfig{file=iiii.eps, bb=49 223 543 547, clip=, width=0.49\textwidth}
\end{figure}
It is effectively set according to the maximal breakage time Tbmax = $ {\frac{{v_{max}}}{{\dot{v}_{b}}}}$ so the robot could stop along the minimal effective path length if it previously achieved maximal translation velocity:

Rmin = vmaxTbmax - $\displaystyle {\frac{{1}}{{2}}}$$\displaystyle \dot{{v}}_{{b}}^{}$T2bmax = $\displaystyle {\frac{{1}}{{2}}}$$\displaystyle \dot{{v}}_{{b}}^{}$T2bmax. (11)

Therefore, a minimal reference translation velocity would be vmin = $ {\frac{{R_{min}}}{{T_{max}}}}$ .



Next: Moving Obstacle Avoidance Up: Path Planning and Motion Control Previous: Dynamic Window for Obstacle Avoidance

 

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