For defining new neighborhoods, it is important to keep them simple because during execution, the neighborhoods that contain the state must be determined quickly. Suppose that all neighborhoods are open balls:

in which is the metric on . There are efficient algorithms for determining whether for some , assuming all of the neighborhoods are balls [700]. In practice, methods based on Kd-trees yield good performance [47,52] (recall Section 5.5.2). A new ball, , can be constructed in Step 3 for , but what radius can be assigned? For a point robot that translates in or , the Hausdorff distance between the robot and obstacles in is precisely the distance to from . This implies that we can set , and is guaranteed to be collision-free.

In a general configuration space, it is possible to find a value of such that , but in general . This issue arose in Section 5.3.4 for checking path segments. The transformations of Sections 3.2 and 3.3 become important in the determination of . For illustrative purposes, suppose that , which corresponds to a rigid robot, , that can translate and rotate in . Each point is transformed using (3.35). Now imagine starting with some configuration and perturbing each coordinate by some , , and . What is the maximum distance that a point on could travel? Translation affects all points on the same way, but rotation affects points differently. Recall Figure 5.12 from Section 5.3.4. Let denote the point that is furthest from the origin . Let denote the distance from to the origin. If the rotation is perturbed by some small amount, , then the displacement of any is no more than . If all three configuration parameters are perturbed, then

(8.53) |

is the constraint that must be satisfied to ensure that the resulting ball is contained in . This is actually the equation of a solid ellipsoid, which becomes a ball if . This can be made into a ball by reparameterizing so that has the same affect as and . A transformation maps into a new domain . In this new space, the equation of the ball is

in which represents the change in . The reparameterized version of (3.35) is

For a 3D rigid body, similar reparameterizations can be made to Euler angles or quaternions to generate six-dimensional balls. Extensions can be made to chains of bodies [983]. One of the main difficulties, however, is that the balls are not the largest possible. In higher dimensions the problem becomes worse because numerous balls are needed, and the radii constructed as described above tend to be much smaller than what is possible. The number of balls can be reduced by also allowing axis-aligned cylinders, but it still remains difficult to construct a cover over a large fraction of in more than six dimensions.

Steven M LaValle 2012-04-20