Page 375 - Introduction to AI Robotics

358

Figure 10.6 Regular grid. 10 Metric Path Planning

fares. It should also be noted that the curved edges in a GVG do not matter
to graph theory or graph algorithms. It is only the length, not the physical
reality, of the edges that make any difference.

10.3.3 Regular grids

Another method of partitioning the world space is a regular grid. The regular
grid method superimposes a 2D Cartesian grid on the world space, as shown
in Fig. 10.6. If there is any object in the area contained by a grid element, that
element is marked occupied. Hence, regular grids are often referred to as
occupancy grids. Occupancy grids will be detailed in Ch. 11.
Regular grids are straightforward to apply. The center of each element
in the grid can become a node, leading to a highly connected graph. Grids
4-CONNECTED are either considered 4-connected or 8-connected, depending on whether they
NEIGHBORS permit an arc to be drawn diagonally between nodes or not.
8-CONNECTED
Unfortunately, regular grids are not without problems. First, they intro-
NEIGHBORS
duce digitization bias, which means that if an object falls into even the smallest
DIGITIZATION BIAS
portion of a grid element, the whole element is marked occupied. This leads
to wasted space and leads to very jagged objects. To reduce the wasted space,
regular grids for an indoor room are often finely grained, on the order of 4- to
6-inches square. This fine granularity means a high storage cost, and a high
number of nodes for a path planning algorithm to consider.