Page 443 - Introduction to AI Robotics

426

Robot Current Position 11 Localization and Map Making
Open Space

Occupied Space

Unknown Space

Centroid
Frontier

Figure 11.22 Example of a robot exploring an area using frontier-based method.
(Figure courtesy of the Navy Center for Applied Research in Artificial Intelligence,
Naval Research Laboratory.)

sensor noise there is usually a threshold of the minimum of number of cells
in a line before it can be treated as a frontier.
Once the robot has chosen a frontier to investigate, it must decide precisely
where to head. A good goal that will get the robot to the frontier is the cen-
troid, (x c ; c ), of y the edges in the frontier line. x and y is the location of the
centroid, either in map coordinates or the i,j indices in the grid. The centroid
for a two dimensional object is the center, or the “average” (x;y ) location.
The computation for the centroid in pseudocode is:

x_c = y_c = count = 0
for every cell on the frontier line with a location of (x, y)
x_c = x_c + x
y_c = y_c + y
count++