
where accelerations and are maximal translational and rotational accelerations exertable by the motors and and are maximal translational and rotational breakage decelerations. A velocity touples (v,) is considered safe if the robot is able to stop along the trajectory defined by (v,) before hitting any object that may be encountered along that path. The set V_{a} of admissible velocities can be determined according to: where the term (v,) 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 V_{s} the resulting search space can be described as the intersection of the restricted areas:
Search space V_{r} can be expressed as the Cartesian product of two search spaces:
where V_{rv} is translational velocity search space and V_{r} rotational velocity search space. In Fig. 4 an example of such resulting space over the discrete set of velocities is shown. We have chosen dimension of V_{rv} to be 5 and dimension of V_{r} 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,) uniquely determines a circular trajectory whose radius is calculated as r = and a sequence of such velocity vectors forms a curvature that is approximated by a sequence of circular arcs. Higher dimension of V_{r} than of V_{rv} 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 V_{rv} is less significant. The dynamic window is centred around the current velocity (v_{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. In order to generate a trajectory to a given goal point for the next n time intervals it has to be determined which velocities (v_{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 twodimensional over the discrete set of velocity touple (v,) 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 V_{r} 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 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): where T_{b}(v,) = max(,) is the breakage time along a certain trajectory determined by (v,) and t_{col}(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 SC_{v} 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 freespace areas (i.e. corridors, passages between objects) appear narrower to the robot. T_{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 v_{max} and the lookahead distance of the sensors s_{l} used. The velocity maximizing a certain objective function (v,) is chosen from the remaining set of velocities V_{r}. It is expressed as weighted sum of objective measures for clearance , target heading and linear velocity : Linear velocity measure is chosen such that higher linear velocities are preferred, and target heading measure considers achieving heading towards global goal position. This approach is susceptible to local minima without further global path information. If connectivity of freespace toward goal position is considered, local minima can be avoided. Although, the problem of determing weighting factors , and 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

