Page 298 - Introduction to Autonomous Mobile Robots

Planning and Navigation

S 283
10 9 8 7 8

11 10 6 7

5 6
obstacle cell
1 2 4 5
G 12 cell with
0 1 2 3 4 distance value

Figure 6.15
An example of the distance transform and the resulting path as it is generated by the NF1 function. S,
start; G, goal.

maintenance of large distances to obstacles and alignment to the goal heading. The objec-
tive function O has the form

⋅
(
,
⋅
(
,
O = a heading v ω,(⋅ ) + b velocity v ω) + c dist v ω) (6.12)
heading = Measure of progress toward the goal location;
velocity = Forward velocity of the robot → encouraging fast movements;
dist = Distance to the closest obstacle in the trajectory.
The global dynamic window approach. The global dynamic window approach adds, as
the name suggests, global thinking to the algorithm presented above. This is done by adding
NF1, or grassfire, to the objective function O presented above (see section 6.2.1.2 and
figure 6.15). Recall that NF1 labels the cells in the occupancy grid with the total distance
L to the goal. To make this faster the global dynamic window approach calculates the NF1
only on a selected rectangular region which is directed from the robot toward the goal. The
width of the region is enlarged and recalculated if the goal cannot be reached within the
constraints of this chosen region.
This allows the global dynamic window approach to achieve some of the advantages of
global path planning without complete a priori knowledge. The occupancy grid is updated
from range measurements as the robot moves in the environment. The NF1 is calculated for
every new updated version. If the NF1 cannot be calculated due to the fact that the robot is
surrounded by obstacles, the method degrades to the dynamic window approach. This
keeps the robot moving so that a possible way out may be found and NF1 can resume.